FR2880715A1 - Element e.g. primitive concept, hierarchy representing lattice coding method for ontology consultation, involves establishing data structure as recursive hash table with entries equivalent to tree structure nodes in upper limit of lattice - Google Patents

Abstract

The method involves establishing a hierarchical generic data structure by associating a recursive N-ary tree structure to an element hierarchy representing lattice. Nodes of the tree structure are associated to the lattice elements and a hash table having keys formed by element representing objects. The data structure is formed as a recursive hash table with entries equivalent to successive line nodes in an upper limit of the lattice. Independent claims are also included for the following: (A) utilization of a data structure (B) a device for coding a lattice representing hierarchy of elements (C) computer program product recorded on a storage medium to execute the method for coding a lattice representing hierarchy of elements.

Description

PROCESS AND SYSTEM FOR CODING A REPRESENTATIVE MESH

The invention relates to a method and a system for coding a trellis representative of a hierarchy of elements, such as in particular primitive concepts and / or defined concepts belonging to an ontology.

An ontology is an entity formed by a set of knowledge, facts and rules relating to a given field, scientific, cultural, administrative, industrial or commercial know-how or other.

The aforementioned knowledge, facts and rules can include a hierarchy of concepts, which represent concepts between an empty concept, generated by a predicate which has no meaning in the considered ontology, and a universal concept, allowing to conceive all the concepts incorporating the considered ontology.

In addition to the aforementioned hierarchy of concepts, an ontology can commonly include predicates including entities such as concept, role or ordinary predicate.

To ensure the representation, from a coding, of a hierarchy of concepts of a given ontology, the most successful method currently known has been proposed by Mr. Alain Bidault, confer Thesis n 6932 presented to obtain the degree of doctor. es Sciences of the University of Paris XI Orsay specializing in Computer Science by this author, subject: Refinement of Requests to a Mediator within the PICSEL system, Paris July 2002.

According to the aforementioned method, the information contained in a given ontology is translated by predicates, link, semantic or logical association between signifying atoms which can be associated with different instances, specific significant values of a variable or of an atom.

A process of saturation of knowledge, rules, disjunctions, inclusions definitions of ontology makes it possible to calculate implicit information by means of a reasoner, defined for a precise language or description logic.

According to the aforementioned method, a concept is a unary predicate (accepting only one argument) with which it is possible to construct logical description formulas.

An ontology comprising a set of concepts and a hierarchy of concepts can be represented in the form of a lattice. A lattice is then defined as a partial order relation for which any pair of elements or concepts (el, e2) has an element eS greater than a common lower element eI according to the relations: el <eS and e2 <eS and> eIete2> el.

In these relations, the symbols> and <denote the above-mentioned order or hierarchy relation.

The order is partial, because it is not defined for all the elements. Some items are hierarchically inferior to others, but some items are not comparable to others. An element can have multiple hierarchically higher and lower elements.

The trellis structure is richer than a tree structure. Indeed, a tree does not allow an element to have several fathers. Now, if no element or concept can have several fathers, the only possibility of having a common lower element is to impose that a concept has no more than one son. Under these conditions, a vertical line hierarchy of little interest is obtained.

An example of a concept lattice described in description logic is given in relation to FIG. 1a, example in which the order relation of the lattice is the inclusion relation c: 1çAOBOCcDcT; 1cGÇT; IcFcEOC; AcE FOB.

In addition, as shown in Figure 1, an arrow going from C1 to C2 indicates that C1 is included in C2.

With reference to FIG. 1a and to the preceding relations, the relations of order or hierarchy are stated in relation to the concept A: (i) A is the son of B and E; (ii) B is the father of A and F; (iii) B, E, A and F are descendants of C; (iv) B, E, C and D are the generalizers of A; (v) T is the universal concept; (vi) 1 is the empty concept.

The order or hierarchy relation implicitly contains all the relations obtained by transitivity of the inclusion relation such as for the concept B: BçD; BÇT.

In the method described by the aforementioned dissertation, an encoding process is defined for unary predicate names (a single argument) appearing in simple rules of the form Predicatl (x) - 'Predicat2 (x).

The aforementioned predicates are then comparable to concepts appearing in description logic in a hierarchy of concepts in the form Predicatl cPredicat2.

However, the empty 1 and universal T concepts do not appear explicitly in the hierarchy, but are assumed to be present as specializing the most specialized concepts respectively as generalizing the most general concepts.

Due to the format of the rules at the origin of the coded hierarchy, the coding proposed in the aforementioned thesis document only takes into account the primitive concepts, still referred to as basic concepts, namely those which have no semantic definition. and which have for only semantics that associated with their position in the lattice of concepts, that is to say ultimately above and / or below other concepts.

The originality of the proposed coding lies in the existence of an identifier for each concept made up of one or more labels, labeling a series of alphanumeric characters between a and z and between 0 and 9.

Each label is unique on the concept lattice and corresponds to the existence of a path between the considered concept C and the universal concept T at the top of the lattice. The universal concept T and the empty concept 1, however, have no identifier.

As an example, a coding of the trellis of the ontology of concepts represented in figure 1 is stated with respect to the universal concept by the relations: D ("a") - G ("b") - C (" aa ") - B (" aaa ") - E (" aab ") - A (" aaaa "," aaba ") F (" aaab "," aabb "). In the above example, a label is encoded by alphanumeric characters belonging to all the letters of the alphabet {a, z}.

With reference to FIG. 1a, it can be seen that, relative to concept A, there are two paths making it possible to go from concept A to the universal concept T, ABCD and AECD. This justifies the presence of two labels in the identifier of concept A, that is to say one label per path.

The coding mode described in the aforementioned thesis dissertation thus makes it possible to locate the primitive concepts within a concept lattice, without however it being necessary to go through the constituted lattice. The position of a primitive concept in the aforementioned lattice is thus contained in the identifier of the latter, which makes it possible to reason at a lower cost on a set of concepts to carry out for example subsumption tests between two elements or a calculation of ppcg for. least common generalizing. It is also recalled here that a subsumption test consists in testing the inclusion of a concept in another concept. The results obtained are conditioned by the absence of redundancy in the concept lattice and by the respect of the constraint of uniqueness of the name of designation of the concept.

The coding mode described above was implemented in a joint development project, called project PICSEL, within the framework of a research contract between the LRI Computer Science Research Laboratory, Orsay 91400, France. and the plaintiff company. The aforementioned development was executed in JAVA language, the generalizing and specializing concepts being however stored in vectors.

Other developments intended to handle comparable data structures, ie ontologies defined in description logic, have been proposed.

Among these, a reasoner module designated Pellet intervenes on a precise description logic which includes specific notations and a syntax.

As part of the Mindswap research project conducted in the advanced computer science research laboratory at the University of Maryland (Baltimore USA), the aforementioned reasoning module makes it possible to manipulate an ontology described in a logic of broad description, written for example in OWL Full language, and to reason on ontologies described in a description logic restricted to certain operators, written for example in OWL DL or OWL Lite language. It is recalled here that a description logic is a logical language (included in the first order logic) which makes it possible to describe concepts by using logical operators between these concepts. The formalism of the OWL language allows these description logics to be expressed in a simple text file. However, the Pellet reasoner module requires the implementation, for the manipulation of an ontology, of three distinct entities for storing and processing information relating to an ontology, transmitted via an OWL document.

These entities are based on classic data structures offered in JAVA language and correspond to lists of objects contained in tables or hash sets or arrays.

The three aforementioned entities are designated Tbox, Rbox and Abox.

The named entity Tbox contains properties relating to the description logic such as inclusions between concepts or concept definitions. Each concept is identified by an integer class number, the universal concept T and the empty concept 1 included, and stored both in a table and in a hash set, the key of which is the name or literal designation of the concept. . The universal concept T is added as a generalizing of each concept. The list of generalizing concepts respectively of specializing concepts of a given concept is stored, for each concept, via a hash table whose key is also the name or literal designation of the concept.

The subsumption tests, which determine for each concept whether it generalizes another concept, are carried out during a first use, to initialize the lists, which requires significant processing and computation costs, but are then reduced to finding a concept as an entry to one of the hash tables.

In addition, a hierarchy of interfaces is also provided in order to manage the various objects encountered in the expression of concepts. Indeed, the grammar or syntactic rules associated with a concept expression being recursive, it is useful to define a hierarchy on the objects encountered in an expression according to their type or if they correspond to a list of objects or to symbols of functions.

The designated entity Rbox contains the ordinary rules which can be assimilated to a hierarchy of properties. The aforementioned hierarchy of properties makes it possible to associate a concept, via one or more properties, with one or more other concepts. The field of application of the properties then makes it possible to go from a general concept to a more precise concept, the sub-hierarchy of concepts inducing the hierarchy of properties. The aforementioned Rbox entity also makes it possible to express a property by inference by unifying object values constituting predicate arguments.

Finally, the entity named Abox contains the facts, namely predicates associated with instances.

The aforementioned developments of the prior art have the following drawbacks.

The PICSEL project is satisfactory, but if it allows coding of a hierarchy of primitive concepts belonging to an ontology, the identifiers attributed to each primitive concept formed by one or more sequences of alphanumeric characters made up of the letters of the alphabet and the numbers from 0 to 9, therefore limit the depth of the coded data structure finally obtained, while the memorization of generalizing and specializing concepts in the form of vectors implies sequential access by addressing to the variables constituting the latter, which implies a cost in terms of computation as a direct result of the size of the data structure thus obtained.

The Pellet reasoner module involves the implementation of a complex software architecture requiring a first initialization of list structures costly in computation time, in order to allow, in use, simplified search processes operating on hash tables and no longer on the logical descriptive language of ontology.

The object of the present invention is to implement a method and a system for coding a trellis, representative of a hierarchy of elements and formed at least by a plurality of nodes, with each node of the trellis being associated with an element and its identifier, this coding method making it possible to overcome the limitations of previous solutions requiring initialization which is costly in terms of computation time.

Another object of the present invention is also the implementation of a method and a system for coding a trellis representative of a hierarchy of elements and formed at least by a plurality of nodes, at each node of the network. trellis being associated with an element and its identifier, with this trellis being associated, due to the coding of the latter, a recursive n-ary tree structure making it possible to establish a direct correspondence between an access path defined in the identifier associated with an element and this element.

Another object of the present invention is in particular the implementation of a lattice representative of a hierarchy of elements, these elements being primitive concepts and concepts defined in a hierarchy of concepts belonging to an ontology, said ontology being associated with a recursive n-ary tree structure via this trellis making it possible to establish a direct correspondence between an access path defined in the identifier associated with a primitive or defined concept of this hierarchy of concepts, this structure recursive n-ary tree allowing a direct correspondence to be established between an access path defined in the identifier associated with a primitive or defined concept and this primitive or defined concept.

Another object of the present invention is in particular the recursive n-ary tree data structure associated with a lattice of elements and / or a lattice of primitive concepts and concepts defined from a hierarchy of elements respectively of concepts belonging to to an ontology.

The method of encoding a trellis representative of a hierarchy of elements comprising at least a plurality of nodes, with each node of the trellis being associated an element considered and its identifier, this identifier being formed by at least one series of objects , each series of objects defining an access path between the upper bound of the trellis and the element considered via the successive parent elements, this identifier including all the series of objects each defining an access path of l 'one of the parent elements of the element considered at this upper bound, to which is added an object representative of this element considered, object of the invention, is remarkable in that it consists at least in establishing a hierarchical generic data structure by association with this trellis of a recursive n-ary tree structure, with each node of this tree structure being associated an element and a hash table to which a key is assigned formed by the representative object of the element considered. This tree-based data structure is established in the form of a recursive hash table comprising as many entries as there are successive child nodes under the upper bound and making it possible to establish a direct correspondence between an access path defined in the 'identifier associated with an element and this element.

This structure makes it possible in particular to advantageously test the membership of a node among a set of nodes without having to verify each of the nodes of this set.

The method for coding a trellis, which is the subject of the invention, is also remarkable in that the elements coming from a hierarchy of concepts belonging to an ontology, this hierarchy of concepts comprising primitive concepts and at least one concept. defined verifying a relation of order between a universal concept, upper bound of the lattice, and an empty concept, lower bound of the lattice, the sequences of objects forming the identifier of a primitive or defined concept are sequences of integers.

By fixing concepts as nodes of the preceding structure, the structure makes it possible to advantageously manipulate sets of concepts in order to carry out membership tests or searches for remarkable concepts for this set such as the most general or the most specific for example.

The method of encoding a trellis, which is the subject of the invention, is also remarkable in that it consists, when the elements of the trellis originate from a hierarchy of concepts belonging to an ontology, this hierarchy of concepts comprising primitive concepts and at least one defined concept, to establish a specific lexical data structure by association of the primitive or defined concepts with this trellis, via a hash table whose key is the name of the concept in this hierarchical generic data structure and in which are the only paths between this concept and the universal concept.

This redundancy of information obtained by the crossing of data makes it possible to test advantageously properties between two concepts or on a set of concepts such as subsumption for example.

The coded representation data structure of a trellis representative of a hierarchy of elements, object of the invention, this trellis comprising at least a plurality of nodes, with each node of the trellis being associated an element considered and an identifier, this identifier being formed by at least one series of objects, each series of objects defining an access path between the upper bound of the trellis and the element considered via the successive parent elements, this identifier including all the series objects each defining an access path from one of the parent elements of this element considered to this upper bound, to which is added an object representative of this element considered, object of the invention, is remarkable in that it comprises at least one hierarchical generic data structure associated with this trellis in the form of a recursive n-ary tree structure. Each node of the tree structure is associated with an element and a hash table to which is assigned a key formed by the object representative of this element. The tree-like data structure consists of a recursive hash table comprising as many entries as there are successive child nodes under this upper bound and making it possible to establish a direct correspondence between an access path defined in the associated identifier. to an element and this element.

The data structure, object of the aforementioned invention is also remarkable in that the elements being derived from a hierarchy of concepts belonging to an ontology, this hierarchy of concepts comprising primitive concepts and at least one defined concept verifying a order relation between a universal concept, upper bound of the lattice, and an empty concept, lower bound of the lattice, the series of objects forming the identifier of a primitive or defined concept are series of integers.

The data structure, object of the aforementioned invention, in which the elements resulting from a hierarchy of concepts belonging to an ontology, this hierarchy of concepts comprising primitive concepts and at least one defined concept verifying an order relation between a universal concept, upper bound of the lattice, and an empty concept, lower bound of the lattice, the series of objects forming the identifier of a primitive or defined concept are series of integers, is also remarkable in that it comprises a specific lexical data structure formed by association of the primitive concepts or defined with this trellis via a hash table whose key is the name of said concept in the aforementioned hierarchical generic data structure and in which only the access paths appear between this concept and the universal concept.

The method and the device for encoding a trellis representative of a hierarchy of elements and the data structure generated by the implementation of the method and / or of the encoding device, subjects of the present invention., Find application in the creation and management of ontology consultations comprising a hierarchy of elements, represented in the form of a lattice, the aforementioned ontologies possibly relating to any field of knowledge that can be used in industry and / or the economy.

They will be better understood on reading the description and observing the drawings below, in which, in addition to FIG. 1 a relating to a trellis coded according to a process of the prior art, FIG. illustrative, the essential steps of implementing the method for coding a trellis representative of a hierarchy of elements, object of the present invention, when this trellis comprises at least a plurality of nodes with each node of the trellis being associated with a element considered and its identifier, this identifier being formed by at least one series of objects; FIG. 2a represents, by way of illustration, a lattice representative of a hierarchy of elements in the particular case of FIG. 1 a where, each element is formed by a primitive concept or by a defined concept, with each node of the trellis being associated a primitive or defined concept and its identifier, this identifier being formed more particularly by at least one series of objects, c each series of objects being constituted by a series of integers; FIG. 2b represents, by way of illustration, a process for establishing a hierarchical generic data structure, in accordance with the coding method which is the subject of the invention shown in FIG. 1b, in the specific non-limiting case of FIG. 2a, this hierarchical generic data structure being represented, in FIG. 2b, according to a recursive n-ary tree structure not fully deployed; FIG. 2c represents, by way of illustration, a process of establishing a hierarchical generic data structure, corresponding to the process of FIG. 2b, in which, however, this hierarchical generic data structure is represented according to a tree structure n- fully expanded recursive area; FIG. 3 represents, by way of illustration, the additional essential steps for implementing the method for coding a trellis representative of a hierarchy of concepts, which is the subject of the present invention, these additional steps having for object to establish in in addition to a specific lexical data structure, allowing direct correspondence between the denomination of the primitive and / or defined concepts and the access paths between the primitive or defined concept and the universal concept; FIG. 4a represents, by way of illustration, the concrete structure of the hierarchical generic data structure represented in FIG. 2b, from successive, nested hash tables, this data structure itself constituting a recursive hash table comprising as many 'inputs that there are successive child nodes under the upper bound of the trellis; FIG. 4b represents, by way of illustration, the concrete structure of the specific lexical data structure associated with the hierarchical generic data structure represented in FIG. 4a, following the implementation of the additional steps illustrated in FIG. 3; FIG. 5a represents, by way of illustration, a first example of use of a hierarchical generic data structure, object of the present invention, in an application to the implementation of a thesaurus; FIG. 5b represents, by way of illustration, a second example of use of a hierarchical generic data structure, object of the present invention, in another application to the implementation of a genealogical tree; FIG. 5c represents, by way of illustration, an example of calculation of the current access path of a concept from the hierarchical generic data structure represented in FIG. 4a; FIG. 5d represents, by way of illustration, an example of calculation of a new access path and of the identifier, by merging one of two access paths relating to the same concept; FIG. 6a represents, by way of illustration, in the form of a functional diagram, a device for coding a trellis representative of elements, in accordance with the object of the present invention; FIG. 6b represents, by way of illustration, in the form of a functional diagram, a device for consulting and interpreting a trellis representative of a hierarchy of elements, in accordance with the subject of the present invention.

A more detailed description of the method of coding a trellis representative of a hierarchy of elements, in accordance with the object of the present invention will now be given in conjunction with FIG. 1b. In general, we consider any lattice representative of a hierarchy of elements, the aforementioned elements being able to be of any kind and, in particular, discrete or non-discrete sets of objects verifying a hierarchy relation of the form: { 1 <O; <T}.

- 13 - In general, it is indicated that, the hierarchy of elements corresponds to a hierarchy at least of dependence between elements, if not of inclusion, as described in the doctoral thesis thesis order number 6932 University Paris Sud XI, presented by Mr. Alain Bidault and entitled "Refinement of Requests to a Mediator".

It is understood, in particular, that when the hierarchy of aforementioned elements relates to primitive concepts as in the context of the previously mentioned thesis dissertation, then the hierarchical relation between elements is a relation of inclusion.

It will be recalled with reference to FIG. 1 a that the trellis comprises a plurality of nodes and that with each node of the trellis is associated an element considered represented from A to G in the aforementioned FIG. 1 a and its identifier, the identifier being formed by at least one series of objects.

In a non-limiting manner in conjunction with FIG. 1a, it is recalled that each object forming a series of objects included in an identifier can be an alphanumeric character such as a letter of the alphabet or an integer for example.

Finally, each series of objects defines an access path between the upper bound of the trellis, i.e. the universal concept T in the nonlimiting case of a trellis of primitive concepts as described in the thesis of the aforementioned thesis and the element considered such as one of the elements A to G of FIG. 1a via the successive parent elements.

It is recalled that under these conditions the notion of parent element corresponds to the notion of an element with respect to which any other element satisfies the dependency relation as described previously.

With reference to the same figure 1a, it is recalled that the identifier associated with each of the nodes of the trellis includes all the series of objects each defining an access path of one of the parent elements of the element considered, namely l 'element E for example, that is to say the element C father of the element E in figure la, at the upper limit, the universal concept T in the above-mentioned non-limiting case, to which is added a representative object of the element considered, that is to say the object b in the specific case of the element E child of the element C according to the adopted convention.

With reference to FIG. 1a, it is indicated that each identifier associated with one of the considered elements of the trellis, this element being denoted Oi for example, is denoted IDi to designate the considered identifier.

Thus, for element A, the identifier IDi is equal to [aaaa aaba].

With reference to FIG. 1b, the coding method, object of the invention, consists for any element Oi of the trellis associated with a corresponding node Ni, i being arbitrary, in establishing, in a step A, a hierarchical generic data structure by association with the trellis of a recursive n-ary tree structure, with each node Ni of the tree structure being associated an element Oi of the trellis and a hash table denoted hi (C,) to which is assigned a key Ci formed by l object representative of the element Oi considered.

Thus, in step A of FIG. 1b, each node Ni of the trellis 15 is associated with the object corresponding to this node Oi and a hash table hi (Ci) and of course the identifier IDi.

Such an association can be carried out for any successive level and for any node in this level of value n, between a starting value such as for example n = 0 for the upper bound of the trellis and n = nf for the lower bound of the trellis , each element and finally each node of the trellis of the same level n being subjected to an association corresponding to step A. Step A is of course repeated successively for each level n and of course for each element Oi associated with a recursively corresponding node Ni.

Thus, for this purpose, step A carried out for each level n can be followed advantageously by a test step B consisting in verifying the absence of identification of the element Oi considered at the lower limit of the trellis.

This operation is represented by the relation: Oi = 1? in step B of figure lb. - 15 - On a negative response to the test in step B, a step C is called which consists of moving to the next level by incrementing n = n + 1 and returning to step A for execution of successive establishment of tree structure.

On the contrary, on a positive response to test B, when the lower limit of the trellis is reached, we have the hierarchical data structure executed in the form of a recursive hash table comprising as many entries as there are successive child nodes. on the upper bound T of the trellis.

The tree data structure obtained in the form of a recursive hash table is denoted H {Ni, Oi, hi (Ci),. The aforementioned recursive hash table comprises as many entries as there are successive child nodes under the upper bound T of the trellis and makes it possible to establish a direct correspondence between an access path defined in the identifier associated with an element and the element considered, as will be described later in the description.

In particular, it can be seen that taking into account the choice of the key C; assigned to each hash table, this key allows direct access to the element O; with which the hash table is associated via the node Ni of the trellis and of course with the identifier ID, corresponding.

In general, it is indicated that a hash table is a coded computer entity which makes it possible to extend the conventional structure of tables or lists with faster processing and which therefore makes it possible to obtain much more significant results.

Such a coded computer entity makes it possible to manipulate objects of variable size and finally any object O; associated with each table h, (C,) by directly accessing the object via the key C ,, which can itself be constituted by an object and in particular by a character, a character string or other as will be described below.

The method, which is the subject of the present invention, finds application to lattices of very general shape and relating to any elements, provided that the aforementioned elements satisfy a dependency relationship as mentioned previously in the description.

The notion of dependency relation can be for example that relating to the lexical relation of words in a dictionary, according to the succession of letters which compose these words, to the organization of a human family according to the succession of parents which resulted in a family member or the like, as will be described later in the description.

However, the aforementioned dependency relation allows a particularly advantageous implementation of the coding method which is the subject of the present invention when this dependency relation is a partial order relation for example, or, where appropriate, a total order relation. and, in particular, when a concept trellis including primitive concepts and at least one defined concept has been the subject of coding by numbering similar to that described previously in the description and the identifiers, that is to say say the series of objects associated with each of the nodes of the trellis and of course the concept associated with the latter, primitive or defined concept, are formed by series of integers exclusively.

Such a coding process has, in particular, been described in French patent application n FR 05 07326 entitled "Coding method and system in the form of a trellis of a hierarchy of concepts belonging to an ontology", filed in the name by the plaintiff on July 8, 2005.

In connection with the aforementioned patent application, it is recalled that the coding process of the described trellis allows coding by numbering of the primitive and / or defined concepts appearing in description logic in a concept trellis.

The relations of this lattice are of the form: concept 1 ç concept 2 where ç is the relation of subsumption, that is to say of generalization between two concepts.

Under these conditions, the upper bound of the trellis is the universal concept T and the lower bound of the trellis is the empty concept 1, which do not appear explicitly in the hierarchy of concepts. The universal concept T and the empty concept 1 are however supposed to be present as specializing and generalizing the most specialized and general concepts.

For a more detailed description of the coding method implemented in the aforementioned patent application, it is useful to refer to the patent application as such or to the owner of the latter, if applicable.

The aforementioned method of coding by numbering from series of integers appears advantageous insofar as this coding method makes it possible to find all the generalizers of a concept C and its descendants by going through the identifier of the concept C and the list of concepts. It is also possible to know the maximum and minimum number of arcs which separate each concept from the universal concept T and, consequently, its depth in the lattice.

The aforementioned numbering coding also makes it possible to carry out a subsumption test between two concepts. It is recalled here that a subsumption test is a complex computation in an ontology described in description logic and which makes it possible to determine whether the instances of a concept are included or not in that of another concept, based on the definition concepts.

Finally, it will be recalled that the aforementioned numbering coding method described in the aforementioned patent application also makes it possible to determine the smallest generalizing common also known as ppcg of two concepts C1 and C2. This set of common generalizers contains all the concepts that subsume both C1 and C2. The least common generalizing ppcg is the largest subset such that no concept of the least common generalizing subsumes another concept of the least common generalizing and such that no concept of the least common generalizing subsumes a concept of l 'together "remain". In particular, the least common generalizing ppcg of two concepts can be directly accessible in a saturated ontology thanks to the coding by numbering described in the aforementioned patent application. It is also easy to extend the computation of least common generalizing ppcg from 2 to n concepts by computation of common prefixes between two concepts.

The method, object of the invention, when the latter is applied to a lattice of primitive and / or defined concepts will now be described in conjunction with FIG. 2a.

In FIG. 2a, the trellis of FIG. 1a has been shown, in which further defined concepts H and I and their respective identifiers have been added.

Thus, with reference to FIG. 2a: H [113 23] I [1131 231] represent the defined concepts H and I and their identifiers formed by the series of integer numbers 113 23 and 1131 231 respectively.

It is noted that in a specific manner the arcs connecting the defined concepts of the lattice to the other primitive concepts C and G, for example of this same lattice, are represented in dotted lines in a nonlimiting manner.

The coding method, object of the present invention, as implemented in accordance with the embodiment previously described with FIG. 1b will now be described and explained in conjunction with FIG. 2b, when this method is implemented on the trellis represented. in figure 2a.

During the implementation of steps A, B, C, D of FIG. 1b, the association is thus carried out with each node N, and for the successive levels n as described above, of each element O; corresponding to the primitive concepts A to G and to the defined concepts H and 1, to each node of the trellis Ni, i being an arbitrary index, being associated with a hash table h, (C;) the identifier being of course maintained.

Thus, by implementing the method that is the subject of the invention, we obtain, as shown in FIG. 2b, a recursive n-ary tree structure, in which, with each node, an element and a hash table is associated with which key C is assigned; formed by the object representative of the element, that is to say in this case the integer representative of the corresponding primitive or defined concept, this integer corresponding to the added integer representative of the primitive concept or defined in the path d access from one of the parent elements of the primitive or defined concept considered up to the universal concept T. Consequently and with reference to FIG. 2b, the entities associated with each node Ni are written in conjunction with FIG. 2a: N { D, hi (1), [1]} N2 {G, h2 (2), [2]} N3 {C, h3 (1), [11]} N4 {B, h4 (1), [111]} N5 {E, hs (2), [112]} N6 {H, h6 (3), [113 23]} N7 {A, h7 (1), [1111 1121]} N8 {F, h8 (2), [1112 1122]} N9 {I, h9 (1), [1131 231]}.

It can be seen, from the observation of FIG. 2a, that due to the coding thus executed, a hierarchical generic data structure has been established formed by an n-ary tree structure not fully deployed, insofar as at each node Ni can correspond several access paths, the access paths 1112 and 1122 for the node N8, that is to say for the concept F for example.

A fully deployed n-ary structure is shown in figure 2c, which corresponds to the n-ary structure of figure 2b in which, however, at each access path for a considered node is represented a specific node the nodes N6, N7 , N8 and N9 relating to the concepts H, A, F and I thus being deployed to represent a single node per access path.

It is thus understood that two nodes such as N7 and N'7 for example, which of course have different access paths, however comprise a similar hash table h7, which, of course, includes the same key value, the integer 1, as shown in Figure 2c. The same is true for nodes N8 and N'8, N9 and N'9 and N6 and N'6.

The n-ary tree structure represented in FIG. 2c is then fully deployed, that is to say that each access path corresponds to a node and only one even if two nodes or several nodes may have hash tables - 20 - similar because they relate to the same concept and consequently have the same key value.

Finally, as regards the implementation of the aforementioned generic hierarchical structure, it is indicated that in order to constitute the latter, the coding method, object of the invention, in fact consists in forming the branches of this data structure by the input variables of each hash table, each of the branches being defined by the key of the hash table associated with its parent node and of the hash table making it possible to associate each of the branches with its child nodes. Each hash table thus comprises a pointer to the hash table associated with the corresponding child node, successively, as will be described later in the description.

In addition, the coding method that is the subject of the invention finally consists in listing the nodes of the tree-like data structure and the primitive or defined concepts associated with the latter at the same depth level with respect to the root node.

This makes it possible to obtain, after full deployment, the structure of dormers as shown in FIG. 2c.

Finally, it is indicated that in a non-limiting preferred embodiment, the input variables forming the key of each hash table are advantageously constituted by integers generated in increasing order in steps of 1.

Thus, each identifier comprises at least one access path to a node of the tree structure and to the corresponding primitive and / or defined concept formed by a series of integer numbers.

The data structure thus obtained, as represented in FIG. 2c, makes it easy to generate a path, that is to say an element constituting the identifier associated with a concept corresponding effectively to the location of a primitive concept or defined within the trellis, to complete or cut off paths to complete identifiers and finally to access each path of an identifier, to find a concept from one of the paths of its identifier and to compare the prefixes of different paths.

All of the aforementioned properties are then particularly advantageous because they make it possible to efficiently and quickly find fathers, sons, brothers and other concepts close to another concept and, finally, make it possible to determine whether one concept subsumes another or not. The aforementioned properties also make it possible in a particularly advantageous manner to determine the least common generalizing ppcg of several concepts.

In addition, and by virtue of the coding method that is the subject of the present invention, the introduction of hash tables in the generic hierarchy data structure makes it possible to obtain a significant saving in processing time thanks to the accesses via the data cards. aforementioned hash. More specifically, it is indicated that the hash tables hi (C,) can be constituted by HashMap class hash tables in JAVA language which are potentially more efficient than a search for prefixes on several strings of characters. In addition and according to a more specific and particularly advantageous aspect of the coding method which is the subject of the invention, it is indicated that the fact of performing a duplication of part of the information within the data structure itself, this duplication which may correspond initially to the association for each primitive or defined concept not only of the identifier ID, but also of the hash key value, the value of which is necessarily the last integer of the series of integers making up the paths representing the identifier allows access to determined information such as the identifier of a concept, the concept itself the number of paths that it contains its generalizers or other depending on the processing to be performed, as well as will be described later in the description.

In addition, the coding method that is the subject of the present invention appears particularly advantageous insofar as it makes it possible to introduce a gain in genericity of the domain, namely a relaxation of the implementation constraints whatever the language used and, in particular, on the following points: - 22 - although the number of fixed nodes of a concept remains limited because this number is imposed by the number of different values that the characters to write can take, the fact of using sequences of d 'whole to constitute the identifiers makes it possible to push back the limit of the techniques of the prior art. Indeed, the limit imposed by the constraints of coding of identifiers is now that relating to the number of different integers coded by the chosen type, for example 256 values on one byte, that is to say 256 possible children for a concept. using only one byte per character; in the prior art, the size of a path whose depth of the hierarchy could be increased by the maximum length of the character string type. Indeed, for example in certain Pascal compilers, a limit can be imposed corresponding to the maximum size of the sets of objects, limit which is generally small. Thanks to the method which is the subject of the invention, the number of characters of a path is no longer increased except by the free memory.

With reference to the notion of duplication of part of the information within the same data structure, in order to allow access to specific information, as mentioned previously in the description, a preferred embodiment without limitation of the coding method which is the subject of the invention, will now be described in conjunction with FIG. 3.

The coding process described in connection with FIG. 3 is additional to the coding process described in connection with FIG. 1b and supplements the latter.

Indeed, with reference to the aforementioned FIG. 3, when the elements of the trellis come from a hierarchy of concepts belonging to an ontology and when the coded trellis is one of the trellises in which the series of objects forming the identifier of a primitive or defined concept are sequences of integers, then the method, object of the invention, can also consist, advantageously, in establishing a specific lexical data structure, by association of the primitive concepts or defined in the trellis via a table of hash whose key is the name of the concept in the hierarchical generic data structure, the information encoded in the new hash table then being the only access paths between the primitive or defined concept and the universal concept.

Thus, with reference to FIG. 3, we consider, for example, the hierarchical generic data structure as represented in FIG. 2c, that is to say the structure: H {PCi, DCk, h; (C;), ID;}.

In the aforementioned generic hierarchical structure, PC; denotes primitive concepts and DCk denotes defined concepts. Each has a hash table denoted generically h; (Ci) and an identifier IDi. Of course, the above-mentioned primitive and defined concepts verify the order relation: {1cPC;, DCkOT}.

It will be understood, in particular, that the establishment of the specific lexical data structure can then be carried out advantageously from the generic hierarchical structure, as represented for example in FIG. 2c, by traversing successive nodes and, in particular, levels n as shown for example in FIG. 2c.

The method, object of the invention, for establishing the specific lexical data structure, then consists, as represented in FIG. 3, in a step E starting from the nodes and the primitive concepts PC; and defined DCk and their identifiers ID; in establishing the hash table denoted T [("PC;", CH;) / ("DCk", CHk)].

Step E is executed for all the nodes of the same level n and can then be followed by a step F consisting in checking that none of the concepts of the following level is constituted by the empty concept.

This operation in step F is denoted: n PC ;, Dk = 1? On a negative response to the test F, a step G is called which consists in going to the next level n = n + 1 in order to reiterate the step E on the nodes of the level n + 1. The operation is continued as long as the empty concept is not reached.

- 24 - On reaching the empty concept, that is to say in positive response to step F of figure 3, the operation of establishing the specific lexical data structure is then terminated and we have of the aforementioned structure noted: T [(“PCi”, CHi) / (“DCk”, CHk)].

With reference to figure 3 it is indicated that in the specific lexical data structure: “PCi” designates the name of the concept PCi, “DCk” designates the name of the defined concept DCk, CHi designates the set of access paths to the concept primitive PCi starting from the universal concept T, CHk designates the set of access paths to the defined concept DCk starting from the universal concept T. It is understood that the coding process represented in FIG. 3 thus consists in establishing a lexical data structure specific by association of the primitive or defined concepts with the lattice on the one hand, and, on the other hand, with an array of tables of integers which represent the access paths between 1, th concept considered and the universal concept.

In Figure 3, the table of tables of integers and denoted: T [("PCi", CHi) / ("DCk", CHk)].

A more detailed description of a hierarchical generic data structure of coded representation of a trellis representative of a hierarchy of elements, this trellis comprising at least a plurality of nodes and with each node of the trellis being associated a considered element and a identifier, will now be given in conjunction with FIG. 4a.

In the context of the description of FIG. 4a, it is indicated that the data structure, object of the invention, comprises at least the hierarchical generic data structure associated with the trellis in the form of a recursive n-ary tree structure, with each node of the tree structure being associated with an element and a hash table to which is assigned a key formed by the object representative of the element considered. The tree-like data structure is itself constituted by a recursive hash table comprising as many entries as there are successive child nodes under the upper bound making it possible to establish a direct correspondence between an access path defined in the identifier associated with an element and the element considered.

It will thus be understood that the aforementioned hierarchical generic data structure corresponds of course to the tree structure shown in FIG. 2c.

In addition, this structure groups the properties of a hash table or map and an n-ary tree and is therefore called HashMaptree.

Indeed, the classic recursive structure of n-ary trees has been completed, in accordance with the object of the invention, by optimizations obtained by means of the keys of the hash maps.

By analogy, the root of the recursive n-ary tree structure corresponds to the global hash map for example and a node, consisting of an object carrying information, is represented in Figure 4a by the star character (*) and by a hash card represented in FIG. 4a by a square (0). The branches are made up of the different entries in the hash tables. Leaves are the nodes whose hash map is empty. An empty hash card is symbolized by a cross in the corresponding square (). It is thus understood that the symbol * represents any object whose type can be set by the classes heir to HashMaptree. The object represented by the aforementioned star corresponds to the objects carrying information in the data structure, that is to say to objects such as the words of a dictionary as described previously in connection with Figures la and lb, otherwise to a primitive or defined concept as described previously in connection with Figures 2a, 2b, 2c.

Further, the hash table key values represented by an integer in Figure 4a can have any type, character, string or other, but also the value of an integer in the representation mode of FIG. 4a above. This type is fixed in the heir classes for example.

- 26 - With reference to FIG. 4a and, of course, to FIGS. 2b and in particular 2c, it will be understood that the keys placed end to end and the values in the form of integers make it possible to obtain the access paths to the objects carriers of information.

With reference to FIG. 4a, the surrounded node is connected to the root node represented virtually by NR by three inputs. The first is that of key 1 of the first hash table also represented in FIG. 2c and designated h1 (1) at node N1. the second that of the key 1 of the hash table h3 (1) of the node N3 and the third corresponds to the entry of the key 3, that is to say of the hash table h6 (3) of the node N6 in figure 2c. The node circled in Figure 4a corresponds to entry 3 of the third hash map designated h6 (3) in Figure 2c.

The access path associated with the information contained in the hash table, the access path of which is 113, is none other than the concept H as represented at node N6 in FIG. 2c. The corresponding access path is indeed the path 113 which is of size or depth 3. It is indicated that the size designates the degree of filiation with respect to the root node.

With reference to FIG. 4a, and, of course, to FIG. 2c which represents the corresponding n-ary tree structure, this structure represents a division into successive strata, that is to say into successive depth levels, and constitutes therefore a tree structure very close to the intrinsic organization of the concepts of an ontology. The access keys to the constituent hash table of the. aforementioned generic hierarchical tree structure are directly comparable with the identifiers obtained by coding by numbering of the primitive and defined concepts described in the patent application mentioned above in the description.

It can thus be seen that the hierarchical generic n-ary type tree data structure makes it possible to return a concept from a path of its identifier.

Indeed, with reference to FIGS. 2c and 4a for example, to obtain a concept from the aforementioned generic hierarchical tree structure, it suffices to access the node to which the requested concept is associated, in particular, by the access path or respectively by the successive keys of the hash tables which represent the aforementioned access path. Finally, it is recalled that, with reference to FIG. 4a, the nodes whose hash card is empty constitute the leaves of the tree structure and are represented in the aforementioned figure by a cross in the corresponding hash table. On the contrary, any information symbolized by a star present in the hash table constitutes the information relating to the stored concepts, that is to say the concepts A to I represented in FIG. 2a.

The hierarchical generic data structure represented in FIG. 4a, due to the implementation of the latter in the form of hash tables, allows optimal use of the coding by numbering of the primitive and / or defined concepts of an ontology. The hierarchical generic hash map is thus a generic map centered on sequences of integers of an access path, in order to obtain the corresponding concepts.

However, thanks to the implementation of the method which is the subject of the invention as represented in FIG. 3 and in particular of the process of encoding a specific lexical hash table, it is indicated, with reference to FIG. 4b, that this card is a complementary card making it possible to optimize the use of any ontology coded by numbering as mentioned previously with reference to the patent application in the name of the applicant cited in the description.

With reference to FIG. 4b, it can be seen that the specific lexical hash table is formed by an array of integer tables with which are associated the denomination of the concepts belonging to the ontology, and, in particular, to the corresponding trellis, such as that shown in FIG. 2c for example.

Thus, one notes that with each name of concept such as: "PCi" = A, B, C, D, E, F, G, H, I for example is associated one or more tables of integers representing the paths d 'access to the concept whose corresponding denomination is designated from the root NR node, that is to say finally from the universal concept.

Thus, and in accordance with a remarkable aspect of the coding method which is the subject of the present invention, the first hierarchical generic data structure, represented in FIG. 4a, is a generic hash table centered on the series - 28 - of integers on the paths. to obtain the concepts and the second specific lexical data structure is, on the contrary, centered on the denominations of concepts formed by character strings for example to obtain all the information concerning them, via an object of the concept type.

With reference to FIG. 4b, it is indicated that the keys of the specific lexical data structure are formed by a character string corresponding to the name of a concept and which therefore allows access to information relating to the concept, such as its full identifier for example.

Thus, it appears that access by a key and of course by a succession of keys to the first hierarchical generic data structure, to obtain the corresponding concept, respectively access to the specific lexical data structure from a key formed by the designation of a concept, to obtain the access path to the aforementioned concept, are substantially symmetrical accesses.

It is recalled that the ontologies manipulated by virtue of the implementation of the coding method which is the subject of the present invention and of the coding method by numbering described above with reference to the patent application in the name of the applicant respects the uniqueness constraint of the denomination of each concept, namely that two different names represent different predicates and the same name represents one and the same predicate.

Each access key to the specific lexical data structure allows, among other things, to access the identifier of the corresponding stored concept, on the one hand, through an array of integer arrays, and, on the other hand, by a generic hierarchical map.

According to a remarkable aspect of the method and of the data structures described in connection with FIGS. 4a and 4b, object of the present invention, these entities are complementary for the processing and redundant as regards the information they contain.

For this reason, the aforementioned entities provide gains in genericity and in processing time, as mentioned previously in the description.

- 29 - In particular, the fact that the integers used to generate the different entries on the hash tables constituting the hierarchical generic data structure represented in FIGS. 2c and 4a are generated in ascending order and in steps of one starting from 1 , allows for example, in the absence of a given integer, to deduce that this integer does not exist, but especially that there is no superior identifier resulting from the same father and therefore with the same prefix , that is to say the prefix corresponding to the path of the father.

For example, the absence of entry 3, that is to say of a key whose numerical value is an integer 3, in a hierarchical generic data structure comparable to that represented in FIG. 4a, of course makes it possible to deduce that the last child of the root node or universal concept T is the node G of the trellis of the prior art shown in FIG. la, for which the access key is the value 2, and that there is no concept of which one of the paths in this hierarchy begin with 3, 4, or any higher value integer.

In addition, the specific lexical data structure makes it possible to quickly know the number of paths that an identifier has, as well as the size of each of the aforementioned paths.

The advantages of the specific lexical data structure are as follows: ^ Advantages inherent in the array of integer arrays: This array allows you to quickly find out the number of paths that an identifier has, as well as the size of each of these paths. This makes it possible to optimize: the subsumption tests: if A subsumes B then A cannot have more path in its identifier, since A transmits all its paths to its descendants; the calculations of least common generalizing ppcg: the maximum number of paths belonging to the ppcg of several concepts is equal to the number of paths of the identifier of the smallest. Browsing the array of the identifier with the fewest paths is therefore sufficient to calculate a ppcg.

^ Advantages inherent in the hash map constituting the specific lexical data structure: The information contained by the latter must not be restricted to the keys of the maps of the hash tables. In fact, storing a concept in addition makes it possible to use more widely the properties of the hierarchical generic data structure to easily obtain the primitive or defined concepts fathers and the generalizing concepts of a determined concept.

The gains obtained with this new hash table are comparable to those obtained with the hierarchical generic data structure. In particular, it is no longer necessary to iterate through string vectors or even strings before finding the relevant prefix or realizing that it does not exist.

In addition, many recursive algorithms can be applied, which then often boil down to a test for the existence of keys in several nested hash maps.

^ Advantages inherent in the use of the hash table: Subsumption test: if a concept A subsumes a concept B then the hash table of A is included in the hash table of B. Computation of least common generalizing ppcg: the set of sheets of a map obtained by intersection of the maps of the identifiers of several concepts C forms the smallest generalizing commons of the concept C. To obtain the hash table and the specific lexical data structure, after having carried out the first scan of all the concepts such as represented in FIG. 1b, a second scan of the latter is carried out to initialize the data structure H {PC ,, DCk, h, (C,), ID;} of each of the concepts, as represented in FIG. 3, then traversing the hierarchical generic data structure.

Different examples of use of the hierarchical generic data structure represented in FIGS. 2c and 4a and / or of the specific lexical data structure represented in FIG. 4b will now be given, in conjunction with FIGS. 5a to 5d.

As regards the use of the hierarchical generic data structure, it will be recalled that the latter is able to represent a hierarchy of any objects.

With reference to FIG. 5a, the lattice represents the organization of] all the words of a dictionary for example, as a function of the succession of letters which make up this word.

The elements of the trellis are then concepts for which there can be several synonyms, the empty element being noted.

The upper element of the lattice, in this situation, is the universal concept which is expressed without any letters and the lower element of the lattice is the empty concept representing all the concepts of the lattice. A synonym is located in the lattice thanks to the series of letters which defines a path between the upper element and the synonym. There are thus as many paths as the concept has synonyms. The depth of the occurrences of a concept in the lattice is fixed by the number of letters of each of its synonyms. The identifier of a concept corresponds to the set of successions of letters which form the synonyms of this concept.

With reference to FIG. 5a, it is indicated that the sub-paths which do not correspond to concepts are associated with an empty element noted.

Thus, with reference to the aforementioned figure, there are four different concepts: the words "friend", "friends" and "friend" corresponding to the same concept B, the words "soul" and "souls" corresponding to concept C. Another Application of the hierarchical numerical structure shown in figure 4a is given in relation to figure 5b.

In this situation, the trellis represents the organization of a family according to the succession of parents that has engendered a family member.

The members of the trellis are individuals for whom there can be several parents. The upper element of the lattice representing the universal designer is none other than the first being at the origin of all mankind, which has no date of birth, and the lower element represents a hypothetical descendant or virtual resulting from the union of all the humans of the lattice.

A member of the family is thus represented in the trellis thanks to the series of dates of birth which define a path between the upper element and the individual of the trellis.

In order to keep the date uniqueness constraint, for the same parent, all you have to do is specify the hours and minutes in the date for example.

Thus, there are as many paths as the concept has ascendants in the family tree. The depth of the occurrences of an individual in the lattice is fixed by the number of known ascendants of each of these occurrences. The identifier of an individual corresponds to the set of successions of dates of birth which form the ascendants of this individual.

With reference to FIG. 5b, it is indicated that Marc, who appears twice as an individual son of Frédéric respectively of Sophie, is the son of individuals Frédéric and Sophie.

In the case where the coded trellis, in accordance with the method which is the subject of the invention, is a trellis of primitive and / or defined concepts and that, consequently, the identifiers are formed by series of integers, as described previously in the description, an example of the use of the hierarchical generic data structure in different situations will now be given in connection with FIGS. 5c and 5d.

FIG. 5c represents a current path calculation process for the addition of a concept A, child of a parent concept E, as represented for example in FIG. 2a, 2b or 2c.

We consider a priori the concept E, before addition, as a leaf of the considered lattice, the access path from the universal concept T to the leaf E whose hash table is symbolized by a cross is given by the series of keys successive hash tables, that is to say the path 112 in FIG. 5c.

The addition of the child concept A of the parent concept E simply consists in adding a hash table for the child concept A, this hash table becoming - 33 - a sheet for the hierarchical generic data structure represented in FIG. 5c or, more particularly , for the branch of the latter. The key assigned to the hash table of the child concept A is the numerical value 1 and the access path is then the concatenation of the previous access path of the parent node E and of the key of value 1, the access path becoming 1121, as shown in Figure 5c.

Another example of the use of a hierarchical generic data structure, or of a branch of the latter, as represented in FIG. 2b, 2c or 4a is illustrated in FIG. 5d for the addition of a new path with merging of two paths relating to an added concept A.

With reference to FIG. 5d, the concept A associated with the corresponding node and which corresponds for example to node N7 {A, h7 (1), [1111]} and N'7 {A, h7 (1), [1121]} successive hash tables are available before merging as shown in FIG. 5d, each comprising the keys formed by the integers 1111 respectively 1121, as shown in the aforementioned figure. The merger operation as shown in the same figure then consists in substituting for the two aforementioned paths the common path formed by the prefix 11 of the two paths to which, of course, each of the distinct paths is added, that is to say paths 11 and 21 as shown in FIG. 5d.

It is thus understood that the merger of the successive hash tables, relating to the first path 1111 respectively to the second path 1121, makes it possible to reconstitute the hierarchical generic data structure as represented in FIG. 2c and, in particular, the branches thereof and , of course, the implementation of this generic structure in the form of hash tables or cards, as represented in FIGS. 4a and 5d for the branch considered.

With regard to the joint use of the hierarchical generic data structure represented in FIG. 4a and of the specific lexical data structure represented in FIG. 4b, it is indicated that, due to the duplication of the information previously mentioned in the description, the manipulation of the entities and in particular of the concepts associated with the node of the lattice and the corresponding n-ary structure is then greatly facilitated.

- 34 - It is understood, in particular, that the aforementioned use can then consist, in the particularly advantageous manner, of either directly obtaining the concept by the hierarchical generic data structure associated with the trellis, from one of the access paths of the identifier associated with the concept and of course with the corresponding node, this generic structure being shown in Figures 2c and 4a, or to introduce the name of a concept to obtain directly from the specific lexical data structure, shown in Figure 4b , links corresponding concept.

The aforementioned use can also consist in obtaining the name of a concept and / or its identifier from the considered concept or in obtaining one of the access paths to the concept from its identifier from the lexical data structure. specific as shown in Figure 4b.

As regards the implementation of the aforementioned specific hierarchical and lexical generic data structures, it is indicated that these structures can advantageously be implemented for example in JAVA language by an extension of the “Hashmap” class of the aforementioned language. This extension makes it possible to define a corresponding extended class for example.

The aforementioned extended class allows the definition of specific functions below: The nodes of the hash table thus constituted are composed of an object carrying information, that is to say of a concept for example and of a pointer to another hash table of the same extended class.

Two primitive access functions then make it possible to return from a key value either the object carrying stored information, or the following hash table table via the aforementioned pointer associated with the key value considered. .

The two access functions make it possible to define the access functions successively from a path as described previously in the description.

Other primitive functions can be dedicated to modification functions starting from an integer or from a path, as described previously in connection with FIGS. 5b and 5c for example.

Finally, within the framework of the aforementioned JAVA language, the hierarchical generic data structure and the specific lexical data structure can be defined in an "Ontology" class in which: the hierarchical generic data structure is the previously mentioned extended class in which the keys are integers that can represent up to the value 231 and where the objects are objects of the "HashMaptreenode" class allowing recursion, each node containing a concept; the specific lexical data structure is a hash table in which the keys are the denominations of the concepts, i.e. character strings, the objects are concepts comprising at least one identifier in the form of an array of paths and a path is an array of integers.

The implementation of the hierarchical generic data structure represented in FIG. 4a and of the lexical data structure which is the subject of the invention, as represented in FIG. 4b then makes it possible to perform specific calculations which are particularly simplified under the conditions below. : Execution of a test of absence of subsumption verifying that a first concept A does not subsume a second concept B: In this hypothesis, the use of the aforementioned data structures consists in verifying, from the lexical data structure specific, that the number of access paths of the identifier of the first concept A, equal to the number of integer arrays present in the integer array array associated with the first concept A, is in fact greater than the number of paths access of the identifier of the second concept B, itself equal to the number of integer tables present in the integer table table associated with the second concept B By way of example, for the specific lexical data structure as represented in figure 4b, the computation of the answer to the question asked: Does F (1112 1122) subsume G (2)? then consists in consulting the table of identifiers as shown in FIG. 4b. The answer is given by the fact that F does not subsume G, because the number of paths of F is greater than that of G. Likewise, to the question: Does G (2) subsume F (11121122)? consulting the tables of identifiers, as shown in FIG. 4b, does not make it possible to quickly answer no.

It is then sufficient to consult the hierarchical generic data structure represented in FIG. 4a to verify that the unique key of the first level for the concept G, that is to say the integer key value 2, does not appear in the map of the identifier of F. Consequently, G does not subsume F. In addition, the hierarchical generic data structure can advantageously be used to perform a subsumption test verifying that a first concept A subsumes a second concept B. In this situation, this use consists in verifying, from the hierarchical generic data structure represented in FIG. 4a, that a series of keys of the hash table, obtained by one of the access paths to the first concept A, constitutes a prefix of one of the series of keys of the hash table obtained by one of the access paths to the second concept B. By way of example, with reference to FIGS. 2a, 2c and 4a for example, to the question: Is- what A (1111 1121) subsumes F (1112 1122) ? simply consulting the tables of identifiers shown in FIG. 4b does not make it possible to provide a quick answer. No.

The corresponding use then consists of consulting the hash tables represented in FIG. 4a or in FIG. 2c.

We then check the unique key of the first level, i.e. the value 1 which appears in the hash card of the identifier of F. - 37 We then check the unique key of the 2nd level, c ' i.e. the value 1 which appears in the card of the identifier of F. We look at the first of the two keys of the 3rd level 1 appears in the card of the identifier of F, while the only key of the last level 1 does not appear in the identifier map of F, therefore, concept A does not subsume concept F. Similarly to the question: Does E (112) subsume A (1111, 1121)? the consultation of the specific lexical data structure represented in FIG. 4b does not make it possible to answer No.

One then proceeds to the consultation of the data structure represented in figure 4a or in figure 2c and one operates as follows: one checks the single key of the 1st level, the value 1 appears in the hash table of the identifier A; - the unique key of the 2nd level is checked, the value 1 appears in the hash table of the identifier A; we check the unique key of the last level, the value 2, which appears in the hash table of the identifier A. Consequently the concept E subsumes the concept A, because one of the access paths to the first concept E constitutes a prefix of one of the key sequences of the hash table obtained by one of the access paths to the second concept A. By way of comparison, we indicate that, previously, that is to say in the manipulation of ontologies of the prior art, the subsumption test was executed by a search for a concept name, that is to say a character string in a list of concepts constituting a generalizer, this list of generalizer concepts which can be very large.

Thanks to the implementation of the method which is the subject of the present invention, from a coding method by numbering as indicated above, and from the hierarchical generic data structure represented in FIGS. 2c and 4a and from the data structure specific lexical represented in figure 4b, the corresponding operation is done by a simple traversal of a path belonging to the potential generalizing which has for maximum length the depth of the hierarchy of concepts.

It is understood, of course, that the preceding operations can be performed by traversing the tree structure shown in particular in FIG. 2c and, consequently, by reading the keys of the hash tables represented in FIG. 4a for the corresponding branch via pointers associated with them.

Calculation of the least common generalizing of a set of concepts The hierarchical generic data structure represented in FIGS. 2c and 4a and the specific lexical data structure represented in FIG. 4b, in accordance with the object of the invention, particularly allow advantageous to perform the computation of the set of smaller common generalizing concepts of a subset of concepts under particularly advantageous conditions.

Thus, to perform such a calculation, the corresponding use consists at least, from the generic hierarchical tree structure associated with each successive concept of the subset of concepts, accessible via the specific lexical data structure, to be calculated. the intersection of the sequences of keys of the hash tables corresponding to the access path of the successive pairs of concepts of the subset of concepts, to keep the resulting intersection access paths via the hierarchical tree structure, then, to be retained as a set of the smallest generalizing commons, the concept or concepts obtained from the hierarchical generic data structure associated with the trellis, comprising at least one of these access paths equal to at least one of the calculated intersection access paths.

The aforementioned operating mode will be illustrated from two successive examples corresponding to the questions: - 39 - What is the least common generalizing ppcg of A (1111 1121) and F (1112 1122)? The common part of the two hash tables containing the corresponding identifiers is then discriminated, this common part being given by 111 and 112.

The smallest common set generalizing ppcg of A and F is therefore formed by the concepts associated with the leaves of the corresponding hash table and we obtain, in particular, the denomination of the concepts B and E on the lexical data structure specific shown in Figure 4b.

What is the least common generalizing ppcg of the concepts A and F previously cited and of the concept H (21 113)? In this situation, in which the concept H has been added to the previous situation, a similar procedure is carried out for the intersections of hash tables taken two by two.

Thus, for concepts A and F, we obtain, as previously, for the discrimination of the common part of the identifiers (111 112).

By again intersecting the resulting paths with the path of node H, path 21 is necessarily removed from the latter. Accordingly, the resulting intersection is given by the resulting path 11.

Consulting the specific lexical data structure represented in FIG. 4b then makes it possible to determine that the generalizing concept constituting the ppcg of A, F and H is unique and constituted by the concept C. As a comparative example, it is indicated that, in the prior art, a least common computation generalizing ppcg was performed through a path-by-path maximum prefix computation, the paths being stored in arrays. Then it was necessary to remove any redundant paths to keep only the smallest generalizing commons. Thanks to the implementation of the method and the data structures obtained

by the method, objects of the invention, as described in the present application, the calculation 20 - 40 - of the least common generalizing of a set of concepts is carried out by a simple intersection of the hash tables, level by level, as described above in connection with FIGS. 2c and 4a, 4b.

Finally, other uses of the hierarchical generic and specific lexical data structures, in accordance with the object of the present invention, can of course be envisaged.

Indeed, the aforementioned data structures allow a potential user of an ontology to perform numerous calculations quickly in order to offer explanations in real time on the field of the ontology and, if necessary, to suggest modifications to his. request.

The generic and lexical hierarchical data structures in accordance with the subject of the invention thus make it possible to carry out cooperative processing using formulations of queries.

For example, a request requesting a train journey from Dar Es Salaam to the city of Zanzibar appears legitimate but cannot be satisfied.

The explanation to be presented to the user will be able to be obtained more quickly than during the manipulation of ontologies of the prior art, thanks to the implementation of the hierarchical generic data structures and specific lexical described previously in the description.

Indeed, the user may be informed that Dar Es Salaam is in Tanzania, that is to say on the African continent and that Zanzibar is on an island off the coast of Africa and therefore does not exist. of railway line between the island and the African continent.

The latter's request can then be changed by a boat trip from Dar Es Salaam to Zanzibar City or train trips from Dar Es Salaam and other mainland cities.

A more detailed description of a device for coding a trellis representative of a hierarchy of elements, in accordance with the subject of the present invention, will now be given in conjunction with FIG. 6a.

In general, it is indicated that the device for coding a trellis object of the invention, as represented in the aforementioned figure, allows the coding of a -41 - trellis comprising at least a plurality of nodes, to each node of the trellis being associated with an element considered and its identifier. The identifier is formed by at least one series of objects, each series of objects defining an access path between the correct upper bound of the trellis and the element considered via the successive parent elements.

The identifier ID thus includes all the sequences of objects each defining an access path to one of the parent elements of the element considered at the upper bound to which is added an object representative of this element considered, as described. in conjunction with Figures 1a and lb. For this purpose, in addition to a central processing unit, denoted CPU, a working memory, RAM, and an input device, FO output, the coding device of a trellis, object of the invention, thus comprises a module acquisition of the trellis subjected to the coding process, as described previously in the description.

The acquisition module of the trellis can be constituted by a module Mo, which, through the intermediary of the central processing unit and of the input / output member 1/0, allows access to the considered trellis supplied by an ontology provider for example, the corresponding trellis, such as represented for example in FIG. 1a or 2a, then being stored in the random access memory RAM of the device or, where appropriate, in a specific storage memory not represented in the drawing.

The device which is the subject of the invention further comprises a module MI for calculating a hierarchical generic data structure by association with the acquired trellis of a recursive n-ary tree structure, as described previously in the description, in conjunction with the FIG. 2c or with FIG. 4a. This structure is such that each node of the tree structure is associated with an element and a hash table to which is assigned a key formed by the object representative of this element.

It is also recalled that this tree-based data structure is established in the form of a recursive hash table comprising as many entries as there are successive child nodes under the upper limit. It makes it possible to establish a direct correspondence between an access path defined in the identifier associated with an element and this element. Finally, the coding device which is the subject of the invention comprises a module PM for storing the aforementioned hierarchical generic data structure.

In a preferred non-limiting mode of implementation, the storage module PM of the hierarchical generic data structure is a non-volatile programmable memory for example making it possible not only to perform the actual coding and the storage of the data structure. aforementioned hierarchical generic but also the updating and / or modification of the latter.

In addition, as has also been shown in FIG. 6a, the coding device which is the subject of the invention makes it possible to code any trellis in which the elements come from a hierarchy of concepts belonging to an ontology.

In this hypothesis, the hierarchy of concepts comprises primitive concepts and at least one defined concept verifying an order relation between a universal concept, upper bound of the lattice, and an empty concept, lower bound of the lattice. The series of objects forming the identifier of a primitive or defined concept are series of integers as described previously in the description.

For this purpose, the device which is the subject of the invention further comprises a module M2 for calculating a specific lexical data structure formed by association of the primitive concepts or defined in the trellis via a hash table whose key is the name of the concept. primitive or defined in the hierarchical generic data structure and in which only the access paths between the concept and the universal concept appear, this hash table being represented in FIG. 4b previously in the description.

It is understood, of course, that the aforementioned calculation modules M1 and M2 thus allow the implementation of the coding method as illustrated previously in the description in conjunction with FIGS. 1b and 3, and are advantageously constituted by modules of computer program called up in RAM working memory and executed by the central processing unit CPU of the coding device shown in FIG. 6a.

- 43 - A more detailed description of a device for consulting and interpreting a trellis representative of a hierarchy of coded elements in the form of at least one data structure of coded representation of this trellis, formed by a hierarchical generic data structure as described in connection with FIGS. 4a and / or by a specific lexical data structure as represented in FIG. 4b will now be given in connection with FIG. 6b.

The aforementioned consultation and interpretation device conventionally comprises a central processing unit CPU, a RAM working memory and an input output I / O unit.

The device shown in FIG. 6b further comprises a module Mo for acquiring a data structure such as represented in FIG. 4a and a module M3 for interrogating the aforementioned data structure of coded representation of the trellis making it possible to obtain directly a concept from the hierarchical generic data structure associated with the trellis, from one of the access paths of its identifier.

It is understood, in particular, that the acquisition module Mo can be constituted by a software module making it possible to acquire from the ontology supplier a hierarchical generic data structure such as represented in FIG. 4a, this data structure having been calculated thanks to the implementation of the coding device represented in FIG. 6a.

The device for consulting and interpreting a trellis representative of a hierarchy of elements in accordance with the object of the present invention further includes a module for acquiring a specific lexical data structure as described in connection with figure 4b. This module can be formed by the previously mentioned Mo module. The aforementioned acquisition module can be constituted by a program module executed by the central unit CPU of the device shown in FIG. 6b.

The device that is the subject of the invention shown in the aforementioned figure further comprises a module for interrogating the specific lexical data structure stored for example in RAM working memory or in a storage memory, not shown in the drawing, making it possible to introduce the name of a concept to obtain directly from this specific lexical data structure the corresponding concept, as described previously in the description.

The interrogation module bears the reference M4 in FIG. 6b.

It is understood, in particular, that the aforementioned module M3 allowing the interrogation of the data structure of coded representation of the trellis making it possible to obtain the concept directly from the hierarchical generic data structure, respectively the module M4 making it possible to introduce the denomination of a concept to obtain directly from the specific lexical data structure the corresponding concept, can be constituted by computer program modules executed by the aforementioned central CPU unit, after calling them in the memory RAM working.

Finally, the consultation and interpretation device, object of the invention, as represented in FIG. 6b further comprises a module M5 for cross-interrogating the data structure, from the hierarchical generic data structure respectively the specific lexical data structure. This cross interrogation module can advantageously be formed by a program module making it possible to use either the hierarchical generic data structure represented in FIG. 4a, or the specific lexical data structure represented in FIG. 4b, this program module advantageously being able to be used. either independent or directly integrated into a reasoning module which is an integral part of the device for consulting and interpreting a trellis in accordance with the subject of the present invention.

In particular, the reasoner module M5 may comprise at least one submodule in the form of a computer program for executing a test for the absence of subsumption as described previously in the description, a subsumption test submodule as described above, and a sub-module for calculating a set of common smaller concepts generalizing a subset of concepts as described previously in the description in conjunction with] FIGS. 4a and 4b. In addition, it is indicated that the device which is the subject of the invention, the coding device of FIG. 6a, and the device for consulting and interpreting an ontology, as represented in FIG. 6b, can be integrated into one. single device to form an ontology management device for example.

It is understood, in particular, that the device which is the subject of the invention as represented in FIG. 6a or 6b or the device for managing ontologies comprising the functionalities of the two preceding devices are implemented from computer programs as well as previously mentioned.

In particular, the invention also covers a computer program product recorded on a storage medium, for execution by the central processing unit of a computer or a dedicated device, remarkable in that during the execution, this program product executes the method of encoding a trellis representative of a hierarchy of elements, as described previously in the description in conjunction with FIGS. 1b and 2b, 2c or 3. During this execution, the corresponding program product makes it possible to establish a data structure representing this trellis as represented in FIGS. 2c and 4a respectively in FIG. 4b.

Finally, the invention also covers a computer program product recorded on a storage medium, for execution by the central processing unit of a computer or a dedicated device, remarkable in that during execution this program product executes the functions of consultation, respectively execution, interpretation, interrogation and test of a device as described in connection with FIG. 6b.

In particular, the method, the generic hierarchical and specific lexical data structures obtained by implementing the method and the ontology consultation device are fully applicable to their installation on computer terminals, computers or mobile telephone terminals directly connected to the device. the INTERNET, because of the ease of use of the latter by any user not familiar with handling the description of ontologies, by means of classical languages such as OWL.

- 46 -

Claims (20)

1. Method for coding a trellis representative of a hierarchy of elements, said trellis comprising at least a plurality of nodes, with each node of the trellis being associated an element considered and its identifier, the identifier being formed by at least a series of objects, each series of objects defining an access path between the upper bound of the trellis and the element considered via the successive parent elements, the identifier including all the series of objects each defining a access path of one of said parent elements of said element considered to said upper bound, to which is added an object representative of said element considered, characterized in that said method consists at least in: establishing a hierarchical generic data structure by association with said lattice of a recursive n-ary tree structure, with each node of said tree structure being associated an element and a hash table to which is assigned a key formed by the object representative of said element, said tree data structure being established in the form of a recursive hash table comprising as many entries as there are successive child nodes under said upper limit and making it possible to establish a direct correspondence between an access path defined in the identifier associated with an element and said element. 2. Coding method according to claim 1, characterized in that said elements coming from a hierarchy of concepts belonging to an ontology, said hierarchy of concepts comprising primitive concepts and at least one defined concept verifying an order relation between a universal concept, upper bound of the lattice, and an empty concept, lower bound of the lattice, said series of objects forming the identifier of a primitive or defined concept are series of integers. 3. Coding method according to claim 2, characterized in that said method further consists in establishing a specific lexical data structure by association of the concepts primitive or defined with said trellis, via a hash table whose key is the name of said concept. in said hierarchical generic data structure where only the access paths between said concept and the universal concept appear. 4. Method according to claim 1, characterized in that the latter further consists in: forming the branches of said tree structure by the input variables of each hash table, each of said branches being defined by the key of the table. of hashing associated with its parent node and of the hash table making it possible to associate each of said branches with its child nodes; listing said nodes of said tree data structure and said primitive or defined concepts associated with the latter in levels of the same depth with respect to the root node. 5. Method according to one of claims 2, 3 and 4, characterized in that the input variables forming the key of each hash table consist of integers generated in ascending order in steps of 1, each identifier comprising at least at least one access path to a node of said tree structure and to the corresponding primitive and / or defined concept, formed by a series of integers. 6. Coding method according to claim 3, characterized in that said method consists at least in establishing a specific lexical data structure by association of the primitive or defined concepts on the one hand, said trellis, on the other hand, with a table. tables of integers which represent the paths between said concept and the universal concept. 7. Data structure of coded representation of a trellis representative of a hierarchy of elements, said trellis comprising at least a plurality of nodes, with each node of the trellis being associated an element considered and an identifier, the identifier being formed. by at least one series of objects, each series of objects defining an access path between the upper bound of the trellis and the element considered via the successive parent elements, the identifier including all the series of objects each defining an access path from one of said parent elements of said element under consideration to said upper bound, to which is added an object representative of said element under consideration, characterized in that said data structure comprises at least: a structure of generic hierarchical data associated with said trellis in the form of a recursive n-ary tree structure, with each node of said tree structure being associated an element and a hash table to which is assigned a key formed by the object representative of said element, said tree data structure being constituted by a recursive hash table comprising as many entries as there are successive child nodes under said upper limit and allowing to establish a direct correspondence between an access path defined in the identifier associated with an element and said element. 8. Data structure according to claim 7, characterized in that said elements being derived from a hierarchy of concepts belonging to an ontology, said hierarchy of concepts comprising primitive concepts and at least one defined concept verifying an order relation between a universal concept, upper bound of the trellis, and an empty concept, lower bound of the trellis, said series of objects forming the identifier of a primitive or defined concept are series of integers, said specific lexical data structure formed by association of the concepts primitive or defined with said trellis via a hash table whose key is the denomination of said concept in said hierarchical generic data structure and in which only the access paths between said concept and the universal concept appear. 9. Use of a data structure according to claim 8, characterized in that it consists at least in: directly obtaining the concept by said generic hierarchical data structure associated with said trellis from one of the access paths its identifier; and / or introduce the name of a concept to obtain directly, from said specific lexical data structure, the corresponding concept; and / or 2880715 - 49 - - obtain the name of a concept and / or its identifier from the concept; - obtain one of the access paths to the concept from its identifier. 10. Use according to claim 9, characterized in that, to perform a test for the absence of subsumption verifying that a first concept (A) does not subsume a second concept (B), said use consists in verifying, from said specific lexical data structure, that the number of access paths of the identifier of the first concept (A), equal to the number of integer arrays present in the integer array array associated with the first concept (A) , is greater than the number of access paths of the identifier of the second concept (B), equal to the number of integer arrays present in the integer array array associated with the second concept (B). 11. Use according to one of claims 9 or 10, characterized in that, to perform a subsumption test verifying that a first concept (A) subsumes a second concept (B), said use consists in verifying from said tree hierarchical generic data structure that a series of keys of the hash table obtained by one of the access paths to the first concept (A) constitutes a prefix of one of the series of keys of the hash table obtained by one of the access paths to the second concept (B). 12. Use according to claim 9, characterized in that, in order to perform the calculation of the set of smaller common generalizing concepts of a subset of concepts, it consists at least, from said associated hierarchical tree structure to each successive concept of said subset of concepts, accessible via the specific lexical data structure, to: calculate the intersection of the series of keys of the hash tables corresponding to the paths of the successive pairs of concepts of said subset of concepts for preserve the resulting intersection paths via a hierarchical tree structure; - 50 - retain as a set of the smallest commons generalizing the concept or concepts, obtained from the hierarchical data structure associated with said trellis, comprising at least one of its access paths equal to at least one of said intersection access paths calculated. 13. Device for coding a trellis representative of a hierarchy of elements, said trellis comprising at least a plurality of nodes, with each node of the trellis being associated a considered element and its identifier, the identifier being formed by at least a series of objects, each series of objects defining an access path between the upper bound of the trellis and the element considered via the successive parent elements, the identifier including all the series of objects each defining a access path from one of the parent elements of said element considered to said upper limit, to which is added an object representative of this element considered, characterized in that, in addition to a central processing unit for input / output devices and a working memory, said device includes at least: means for acquiring said trellis; means for calculating a hierarchical generic data structure by association with this trellis of a recursive n-ary tree structure, with each node of the tree structure being associated an element and a hash table to which a key is assigned formed by the object representative of this element, said tree data structure being established in the form of a recursive hash table comprising as many entries as there are successive child nodes under said upper bound and making it possible to establish a direct correspondence between an access path defined in the identifier associated with an element and said element; and - means for storing said hierarchical generic data structure. 14. Device according to claim 13, characterized in that said elements coming from a hierarchy of concepts belonging to an ontology, said hierarchy of concepts comprising primitive concepts and at least one defined concept verifying an order relation between a concept. universal, upper bound of the trellis, and an empty concept, lower bound of the trellis, said series of objects forming the identifier of a primitive or defined concept are series of integers, said device further comprises: calculation means a specific lexical data structure formed by association of the primitive concepts or defined with said trellis via a hash table whose key is the name of said primitive concept or defined in said hierarchical generic data structure and in which only the paths of access between said concept and the universal concept. 15. Device for consulting and interpreting a trellis representative of a hierarchy of elements, characterized in that said device includes at least: a recursive n-ary tree structure, with each node of the tree structure being associated with a element and a hash table to which is assigned a key formed by the object representative of this element, said tree data structure being established in the form of a recursive hash table comprising as many entries as there are child nodes successive under said upper limit and making it possible to establish a direct correspondence between an access path defined in the identifier associated with an element and said element; and means for acquiring a data structure of coded representation of this trellis according to claim 7; means for interrogating said data structure of coded representation of this trellis making it possible to obtain the concept directly from said generic hierarchical data structure associated with said trellis from one of said access paths of its identifier. 16. Device according to claim 15, characterized in that the latter further includes: means for acquiring a specific lexical data structure, according to claim 8; means for interrogating said specific lexical data structure making it possible to introduce the denomination of a concept in order to obtain directly, from this specific lexical data structure, the corresponding concept. - 52 - 17. Device according to claim 16, characterized in that it further comprises means for cross-interrogating said data structure from said hierarchical generic data structure respectively from said specific lexical data structure, making it possible to obtain the name of a concept and / or its identifier from the concept, respectively one of the access paths to the concept from its identifier. 18. Device according to one of claims 16 to 17, characterized in that it further comprises a reasoner module, said reasoner module comprising at least: a sub-module for executing the absence of subsumption test according to claim 10; a subsumption test execution submodule according to claim 11; a sub-module for calculating a set of common smaller concepts generalizing a subset of concepts according to claim 12. 19. Computer program product recorded on a storage medium, for execution by the central processing unit of a computer or a dedicated device, characterized in that during execution, by said central unit, said program product executes the method of encoding a trellis representative of a hierarchy of elements, according to one of claims 1 to 6, and establishes a data structure representing this trellis according to one of claims 7 or 8. 20. Computer program product recorded on a storage medium, for execution by the central processing unit of a computer or of a dedicated device, characterized in that during execution by said central unit, said program product executes the functions of consultation, interpretation, interrogation respectively execution of one of the tests of a device according to claims 15 to 18.