FR2799855A1 - Variable hierarchical data processing method includes two dimensional data tables leading to tree structure for analysis of merchandise items - Google Patents

Abstract

The system uses a series of keys in order to aid classification of products within a structured diagram. The method provides a variable hierarchical structure in an information processing system. The method includes creation of a two-dimensional data table with one action corresponding to each line. At least two columns of keys are provided containing data relating to categories of actions, with one column of actions which the process is intended to trigger. An order is defined for navigating the key columns, and using this order, a tree structure is created with a number of node levels equal to the number of key columns plus one. Each node contains at least one heading corresponding to a category or action data item from the data table and an identifier. It thus possible to display menus using the headings contained in the different nodes, or a graphical representation of the tree structure created.

Description

The present invention relates generally to the consultation of computer databases.

Consulting data such as that of a catalog of products intended for wide audience poses a number of problems related to the presentation of these data, their hierarchization, and the optimization of the computer resources implemented. At present, the presentation of data is usually done via a two-dimensional table, each row for a given data, and each column containing in the line considered an attribute or property of this data. major drawbacks as soon as the set of data presented exceeds some tens, and becomes humanly impractical with a few hundred data. In addition, some users will be interested in certain properties of data and others, this interest can also vary very quickly over time, even for the same user.

Hierarchization techniques make it possible, in a known way, to classify data into categories and subcategories, and to enable information to be retrieved, various groupings, via a query language, such as (Syntax Query Language), will enable the user to informed user to perform various classifications that suit him. This approach is unfortunately a specialist work, very little adapted to the general public who is generally not able to quickly build a SQL query or other. This is why the user generally has at his disposal only a limited number of predetermined types of requests, to which he has no access to modify them.

One of the problems with this approach is that it is often almost impossible to predict the exact needs of the user at the outset, and therefore to create any appropriate queries. It is then common to arrive at an aberrant situation, where the user must virtually already know the answer to his question, and where the information is stored.

From the foregoing, it can be seen that the optimization of computing resources is a major problem, often eluded, and which becomes fundamental in an architecture / server implemented for example on the Internet. Thus two types of problems exist and must be dealt with. The first is related to the amount of information sent from the server to the client. The second is related to 'database access present in the server, which is extremely expensive in processor time in RAM, which significantly slows response times in a client / server environment when the number of clients in the process of session is high.

The present invention aims to overcome these limitations of the state of the art and to provide a method for organizing a table of data in a hierarchical manner from the contents of the table columns. More precisely, the object of the invention is to reorganize the hierarchy of the presented data, by assigning any order to the columns of the table, this in an interactive and autonomous manner, for example by presenting these data hierarchized by drop-down menus. For this purpose, the present invention proposes a method for creating a variable hierarchical structure allowing a user to trigger by successive choices an action among a plurality of actions in a computer system, the method being characterized in that it comprises the steps of - creating a multi-row data table with several columns, with each line corresponding respective action, while at least two key columns contain category data of said actions and an action column contains data designating the different actions that the hierarchical structure must be able to trigger; define a browse order of at least a subset of the set of key columns; and - using said browse order, creating a tree structure of nodes having a number of nodes levels equal to the number of key columns of said subset increased by one, each n # ud containing less heading corresponding to a category datum or of data table action and identifier, a first level of the node structure containing a single node of which a plurality of items correspond to a plurality of category data present in the category column of the data table first in the table. a browse order, and each level following the first level containing, respectively attached to the node or each node of the level immediately below, a set of nodes equal to the number of items in said node to which they are attached, and each identifier of n # ud level higher than the first level being constructed a combination of the identifier of the node of the level immediately inferior to which it is attached and a heading contained in this same node.

Preferred, but not limiting, aspects of the method according to the invention are the following: the method further comprises the step of selectively displaying selection menus using the items contained in the different nodes. the method further comprises the step of displaying a representation of the tree structure with items.

* Each node contains one or more elements, each element containing a topic, data associated with a lower-level node, and data associated with a higher-level node.

* for the first-level node, the data elements contained in this node include data indicating that there is no lower-level node.

* for each last-level node, the data of the elements contained in this node include data indicating that there is no higher-level node * the method includes an intermediate step consisting of, for each n #ud, to develop a string consisting of the concatenation of the contents of the data table for a given row and in column order indicated by the defined order.

the method further comprises the steps of each new character string being constructed, associating therewith a node of a level immediately below, and storing the string / n # ud pair, - each time a string of characters is generated. characters, to check if a string / node pair containing this same string has already been memorized, if so, to associate with the elaborated string the next level node consisting of the second element of the pair already stored.

Other aspects, objects and advantages of the present invention will become more apparent on reading the following detailed description of a preferred embodiment thereof, given by way of nonlimiting example and with reference to the appended drawings, in which the figures 1a and 1b schematically illustrate two types of paths of a tree structure, FIG. 2 is a logic diagram illustrating a name generation algorithm for a row of a table in a given order, FIG. 3 is a logic diagram illustrating an algorithm for data organization using the generation algorithm of FIG. 2, FIGS. 4a to 4c illustrate the contents of the nodes obtained with the algorithm of FIG. 3 for the four products of a data table indicated below as FIG. example, and Figures 5a to 5d illustrate the menu flow for four possible rankings defining four modes of consultation.

By convention in the following description, we will indicate below with the first letter in uppercase the name of a variable, and with the first letter in lowercase the content or value of variable. <U> Definitions </ U> <I> a) Data table </ I> A data table, in the context of the present invention, is a two-dimensional array, each row corresponding to one datum, and each column of the considered line containing a characteristic or property of this datum. Note here the method of storage of this information is not to be considered here. Thus the data table can come from a text or binary file, result from the execution of a local or remote procedure, be directly constituted of a table belonging to a database, or result from a standard query SQL (Syntax Query Language) for example. <I> Table of Data </ I> homogeneous table of data, in the context used here, is said homogeneous if all the characteristics of a data exist for all the other data. For example, if a feature is named "Color", and all the data presented has a non-empty "Color" characteristic, then the table is homogeneous. In the case where a data table is not homogeneous, it is possible to make it homogeneous by extending the definition of one or more characteristics.

For example, for the "Color" feature, if all available colors are Red, Green, or Blue, the "No color" concept can be assigned to all data for which the color feature is meaningless. All available colors become Red, Green, Blue, No color. This process can usually be applied for any type of data.

According to another example, with a Boolean data (of type Yes / No), the value No can be assigned in the case where it does not make sense. Similarly, for a numeric datum, the value 0 can serve as a particular marker. <I> c) Hash table </ I> A hash table is used to associate data with value, thus creating pairs (key, value). A hash table is generally used in the context of databases, allowing quick or immediate access to one or more columns deemed important, and usually called keys. This organization promotes the speed of execution linked to a search, to the detriment of the space used to store data. It makes it possible to answer the questions is that the data X exists? or what is the value of the key Y? without having to make an explicit loop on all the existing data.

d) Dictionary A dictionary, in the context of the present invention, is a hash table associating a code with a string of characters. In most cases, the use of a dictionary can reduce the space required for the storage or transmission of a data table, in the case where it contains a large repetition of identical long character strings. A dictionary can also be used to extend the number of interface languages for a data table, without having to modify the data itself. e) <I> Drop-down menu </ I> A drop-down menu is a graphic object for displaying a hierarchical data space according to a fixed organization. It consists of one or more menus, each containing or several menu items. These menu items can be linked to other menus, which are then considered as submenus of the menu containing this menu item. This object is generally responsive to the keyboard or the mouse, allowing to display or hide the sub menus at the discretion of the user, by the passage of the mouse pointer on a given element, or the click of a mouse button . At each moment, there is at most one menu displayed for each level of hierarchy, which principle, allows to display on the screen the structure of an important data space in a very small space. A system and method for automatically organizing the contents of a data table will now be described in detail, the hierarchy being directly established by the contents of the columns. In addition, the order of the columns can be modified or specified as desired, without requiring access to the original external or local data source: These two points directly respond to the prioritization and optimization constraints mentioned above. .

In the following description, an example has been chosen to present the data in drop-down menu form. It is also possible to present them for example in the form of a tree, the difference between two structures being mainly related to the order of travel of the elements, the order being said depth-first (priority to the depth, see figure la) for a tree, and breadth-first (for width, see Figure lb) for a menu. The transition from one representation to another will not pose any particular problem in practice.

An essential aspect of the present invention relies on the use of hash tables, and proper naming of the menus being created. The use of hash tables optimizes the search for an object according to a key or category, the key used here being precisely the name used in the menus. The data Di can be represented as a result of strings of characters, corresponding to the value of each column c (i, j), placed in a given order, arbitrary.

Thus a table of m columns on n lines will adopt, with the definition given above, the following configuration

Data <SEP> Column <SEP> 0 <SEP> Column <SEP> 1 <SEP> Column <SEP> j <SEP> Column <SEP> m
<tb> c (0,0) <SEP> c (0,1) <SEP> c (O, j) <SEP> c <SEP> m)
<tb> c (1,0) <SEP> c (1,1) <SEP> c (l, j) <SEP> c <SEP> m)
<tb> c (i, 0) <SEP> c (i, l) <SEP> c (i, j) <SEP> c <SEP>'<SEP> m)
<tb> c (n, 0) <SEP> c (n, l) <SEP> c (n, j) <SEP> c <SEP> m) Moreover, for each row of the table corresponding to a datum Di, we establish a variable names (Di) as follows:.

 names (Di) = {c (1,0), c (1,0) -c (i, l), ..., c (i, 0) -c (i, l) -...- c (ij), ..., c (i, 0) -c (i, l) - .., c (i, m)} We understand that this is a multidimensional variable containing, in one position j data, the concatenation of the character strings corresponding to the values of the cells of the columns 0 to j for the considered line, separated two by two by dashes.

To take a concrete example, here we consider an extract from a data table that could correspond to the products in the catalog of an electronic sporting goods store.

<U> Table <SEP> I <SEP> (n <SEP> = <SEP> 4, <SEP> m <SEP> = <SEP> 3 <SEP>) </ U>
<tb><U> Number <SEP> Article <SEP> Type <SEP> Product <SEP> Brand <SEP> Name </ U>
<tb> 1 <SEP> Shoes <SEP> Reebok <SEP><SEP> The <SEP> Answer <SEP>
<tb> 2 <SEP> Shoes <SEP> Reebok <SEP><SEP> After <SEP> Shock <SEP> Mid <SEP>
<tb> 3 <SEP> Shoes <SEP> Adidas <SEP><SEP> Real <SEP> Deal <SEP>
<tb> 4 <SEP> Accessories <SEP> Shimano <SEP><SEP> ATV <SEP> Rider <SEP> (Note: All trademarks mentioned here are registered trademarks.

We understand that for item number 1, we have Names (l) = <B> {"</ B> Shoes <B>", </ B> "Shoes-Reebok", "Shoes-Reebok-ne Answer "} This denomination highlights that the product No. 1 should be in the menu" Shoes ", which allows itself to access the menu" Shoes-Reebok ", and finally the name of the product. The result obtained is an automatic grouping according to the characteristics of the products, highlighted directly by the denomination function. Thus it can clearly be seen that Item No. 2, whose names are: Names (2) = {<B> "</ B> Shoes <B>", "</ B> Shoes-Reebok", " Shoes-Reebok-After Shock Mid "belongs to the same group as unit number 1.

According to the present invention, the <U> Names </ U> variables are formed by using either the increasing order of columns 0 to 1, as performed above, or by using a column order fixed by an Order variable, which will further detail it, so as to be able to browse categories defined in these columns according to any desired priority.

More particularly, considering two columns, four rankings are possible, namely two rankings by taking each column one by one, without taking into account the other column, and two rankings considering each column, then with a lower priority the other column. .

nombre augmente très rapidement avec le nombre de colonnes; en effet, N(2) = 4, N(3) = 15, N(4) = 64... In the general case, the number N (m) of possible orders is the sum of all the arrangements of m objects taken p to p, for p varying from 1 to m, ie

number increases very rapidly with the number of columns; indeed, N (2) = 4, N (3) = 15, N (4) = 64 ...

The algorithms used according to the present invention will be more comprehensible by introducing the notion object, present in object-oriented languages, such as the Java language (registered trademark) of Sun Microsystems, or the C ++ language for example.

Two objects are used here, namely an object of type Node, and an object of type Element. These ets adopt a tree structure: a given N # ud has a unique N # parent (unless it is the highest level node) and one or more child nodes (unless it is a node of the highest level). An element of type Element has - a Message, which constitutes what must be displayed in a menu, - A Parent N #, - A Child N #.

It is represented in the form {Message, Parent, Child} It will be noted here that, in the case where an Element has no child, then the variable Name (see below of the N # ud Child takes the value pull .

An N # ud type object has a Name, - a Positive Depth Level, starting at 0, a Link, consisting of an Element type object, - a List, consisting of an array of Elements. The Link is actually the Element in the N # Parent that allows you to get to that Node.

We represent here an object N # ud in the form {Name, Level, Link, {List}} Referring now to Figure 2, will describe an algorithm for generating the multidimensional variable Names as described above for a line i of a given table.

uses the following conventions here is the number of columns in the table; (i, j) is the value of column j at line i, as indicated above; string {x} is a function that creates a string consisting of x; concatenation (x, y) is a function that creates a string consisting of string {x} followed by string; Order indicates a given order of the course of all or part of the different columns 0 to m-1 of a table, and Order is the number of the column at the kth place of Order, where k varies between 0 and m-1 (or between 0 and integer less than m-1 if the order concerns only a subset of the category columns).

Step 210 of FIG. 2 is a step of creating a first list element [0] of a list for line i, the list element [0] being constituted by string {c (i, order [0 ]}, that is the character string constituted by the element contained in the line i and in the column fixed by the value order [0]. At the step 220 is carried out a progressive incrementation of a variable Col, starting with from 1 to m-1.

Step 230 consists in updating the list, building the list element [col] by concatenation of the previously established value list [col-1] and performing the operation of completing the list string [col-1] by a dash and then by the string string {c (i, order [col], that is to say by the contents of the table in the i-line and in the column fixed by the value order [col].

 Step 240 is a test to determine whether all columns for row i have been traversed (in order set by the Order value). If not, the program returns to step 220 to complete the list item. If yes, the list (equal to list [m-1]) is returned (step 250).

To take a concrete example, we will consider the third line of the table given above, with an order value equal to (2, l, 3).

list value [3] delivered by the algorithm of Figure 2 is then equal to Adidas-Shoes-Real Deal.

It is therefore understood that the algorithm of FIG. 2 is capable of successively generating all the elements of the multidimensional variable Names for the line i considered.

Figure 3 illustrates the main data organization algorithm according to the present invention. In box 310, the following information algorithm is applied - a data table of n rows xm columns, - a desired Order variable, namely a given order of successive integers between 1 and m- 1 Step 320 is an initialization step consisting of - creating a root node called root, whose is 0, whose level is 0, whose Link has pull value, and finally whose List of Elements is empty, and - to create a hash table h (name, n # ud), - to add in the hash table a pair (0, root) (by an add function called h.add) Step 330 allows you to browse successively all the lines i of the table, from the first to the last.

For each line, step 340 uses the name generation algorithm of FIG. 2 to create a set of Name Names (i, Order) consisting of list [0], ..., list [m-1] . Each of these names is named name (j), with j varying from 0 to m-1. This step also indicates that the Parent Node for the Elements that will be created at each step 380 (see below) is the root node defined above.

Step 350 makes it possible to successively process the m values of Name (j).

For each name value (j), step 360 determines that there exists in the hash table a pair containing (j) as the first element of the pair, that is, if a node object has already been associated with name (j) in the hash table.

If so, the program proceeds to step 370, where it is determined that the Parent Node of the element in question is the one in the association hash with name (j).

If not, the program proceeds to the step in which - we create an Element e = elementIc (i, Order <B> (j) </ B> parent, null}, that is, an element whose the Message is the string of characters c (i, Order (j)), whose N # parent Parent, and whose Child Node is pull (absence Child Node) - we set a Level value (value level) equal to the Level value of the Parent N # incremented by 1 (level - parent.level + l) - create a N node equal to {name (j), level, e, {blank}}, that is, say a Node that has the Name name (j, as Level the level value indicated above, as Link the element e created above, and as List empty content; - add the Element in the List of N #ud Parent - we assign to e a Child Node constituted by (child function = n) - finally we perform the function h.add of adding node n associated with name (j) in the hash table by the h.add function (name (j), n).

The program then proceeds to step 370 described above.

After step 370, the program tests in 390 the entire list of Names <U> name </ U> (j) has been traversed. In negative, the program returns to step 350 to process the next name. If so, the program proceeds to a step 400 in which - we create the element e = element (c ', m), parent, null, that is, the Element that has the string name c (i, m) of the table, like Ncode Parent parent, and as Node Child null (no child node); - Element e is added to the Parent N # List.

The next step 410 tests whether all rows of the table have been traversed. If not, we go back to step 330 to process the next line and if so, the program proceeds to step 420 in which we can now create the different menus from the elements created in step 4 these menus. responding for example to the action of a mouse.

Referring now to FIGS. 4a to 4c, there is illustrated the progressive construction of the nodes corresponding to the four-line table indicated above with the algorithm described with reference to FIG.

Each rectangle corresponds to a N # ud, the upper part of the rectangle containing the Node Name and its lower part containing the message or messages of the element or elements associated with this node, that is to say listed in List for this N #ud, messages that will be displayed as individually selectable items in the menus.

The complete node structure is shown at the bottom of Figure 4c.

Figure 5a illustrates the menu structure obtained by applying the algorithms described above using as order (1, 2, 3) that is to say the order of the original table.

Figure 5b illustrates the menu structure obtained by using as Order (2,1,3). Figure 5c illustrates the structure obtained using as Order <B> (1,3). </ B>

Finally Figure 5d illustrates the structure obtained using as Order <B> (2,3). </ B>

It will thus be noted that the variable Order may have a dimension equal to m-1 (in the case of FIGS. 5a and 5b), but that it may also have a dimension of less than m-1 (the case of FIGS. 5c and in which case the number of levels in the hierarchy menus is decreased by as much.

Advantageously, in a practical implementation, it is proposed to the user, for example in an independent menu or by dialogue and selection in a specific window, the order to be used, the latter being indicated in clear to the user. In the example shown above, if the user wishes to use the order (2,1,3), it can be designated the corresponding choice by choice by brand, then by product, then by product name? .

Of course, the present invention is not limited to the embodiment described, but the skilled person will be able to make any modification variant consistent with his mind.

In particular, although the foregoing description has referred to products classified according to different keys or categories (here product type and brand), the invention applies to any kind of information triggering actions in a local computer system or in a network) and organized according to at least two groups of categories.

Claims (8)

A method for creating a variable hierarchical structure allowing a user to successively trigger one of a plurality of actions in a computer system comprising a processor and a memory, the method being characterized by comprising the steps of to create in the computer system and store therein a data table (c (i, j)) with several lines (i) and with several columns (j), with each line corresponding a respective action, while at least two columns keys contain category data of said actions and an action column contains data designating the different actions that the hierarchical structure must allow to trigger; define by interaction between the computer system and the user a browse order (Order) of at least one subset of the set of key columns; and - using said browse command, using the processor to create and store in the memory a tree structure of nodes (Nodes) having a number of levels of nodes equal to the number of key columns of said sub-node. set increased by one, each node containing at least one item (Message) corresponding to a category or action datum of the data table and an identifier (Name), a first level the node structure containing a single node whose plurality of items correspond to a plurality of category data present in the category column of the data table first in the browse order, and each level following the first containing level, respectively attached to the node or node of the level immediately lower, a set of nodes equal to the number of items in said node to which they are attached, and each level node identifier superior to the first level being constructed by a combination of the node identifier of the next lower level to which it is attached and a topic contained in that same node. 2. Method according to claim 1, characterized in that it further comprises the step of selectively displaying in the computer system selection menus using the items contained in the different nodes. 3. Method according to the claim characterized in that it further comprises the step of displaying in the computer system a representation of the tree structure with its items. 4. Method according to one of claims 1 to 3, characterized in that each node contains one or more elements (Element), each element containing a section (Message), data (Parent associated with a lower level node, and data (Child) associated with a higher level node. 5. Method according to claim 4, characterized in that, for the first-level node, the data of the elements contained in this node comprise a datum (0) indicating that there is no lower-level node. 6. Method according to one of claims 4 and 5, characterized in that, for each last-level node, data elements contained in this node include a data (null) indicating that it does not exist. Node of higher level. 7. Method according to one of claims 1 to 6, characterized in that it comprises an intermediate step consisting, for each n # ud to develop using the processor and to store a string of characters (Name) constituted by the concatenating the contents (i, j)) of the data table for a given row in a column order indicated by the defined order. 8. Method according to claim 7, characterized in that it further comprises the steps performed by the processor and consisting - for each new string of characters elaborated, to associate with this string a node of immediately lower level (N # ud Parent), and to memorize in the memory, the pair string / n # ud (h (name, n # ud)), - at each elaboration of a string, to check if a pair string / n # ud containing the same string has already been memorized, if so, to associate with the elaborated string the next level node consisting of the second element of the already memorized pair.