WO2008031953A1 - Process for identifying a structure from among a collection of structures belonging to a list - Google Patents

Abstract

The invention relates to a process for identifying one or more structures from a collection of structures belonging to a list, employing a method for identifying a quantity N of potential groups of atoms (f) from among a collection of groups of atoms, said collection belonging to a dictionary and said dictionary comprising a defined quantity Q of groups of atoms (f), each group of atoms (f) consisting of a sequence of atoms (a) which are ordered one with respect to another and each belong to an alphabet, said alphabet comprising a defined quantity of atoms of different character. The process and the method according to the invention include an identification step which uses a method of probability calculation by the pairing of structures and/or groups of atoms.

Description

 METHOD FOR IDENTIFYING A STRUCTURE AMONG A COLLECTION OF STRUCTURES BELONGING TO A DIRECTORY

The invention relates to a method for identifying a structure from a collection of structures belonging to a repertoire, said structure comprising at least two groups of atoms, each group of atoms being associated with a dictionary.

Any structure may be hierarchically decomposed down to a basic level which is referred to in this patent as "atom".

These elementary components are grouped together to form groups of atoms that constitute an immediately superior hierarchical level. These groups of atoms themselves are arranged to form a structure, constituting the higher hierarchical level.

It is possible to build several other levels of intermediate structures, depending on the nature of the information to be processed. The atom is the smallest indivisible part of the group of atoms.

For information of a textual nature, the elementary level will for example be the alphanumeric character constituting in this case the "atom" level. These "atoms" are arranged to form groups of atoms. A group of atoms can be, in this example:

- a word ;

- or a syllable; or a phoneme. These groups of atoms are grouped together to form, in the upper level, respectively in this example: an address or a channel name or a chunk (sentence section); - a word ;

- a syllable.

Depending on the application and the degree of granularity, the processing will implement at least three levels, and often a number of level greater than three. When the number of level is three, the notion of "group of atoms" corresponds to the notion of "intermediate group".

The atom group is linked to a dictionary.

The intermediate group is linked, when it is different from the atom group, to a repertoire.

A structure composed of several intermediate groups refers to the combination of the respective directories.

When the number of levels is greater than three, the "intermediate group" may correspond to the "atom group" level. It can also correspond to a level between the level "group of atoms" and the level "atom", or at a level between the level "structure" and the level "group of atoms".

Of course, the invention is not limited to the processing of textual information, and the atoms are not necessarily alphanumeric characters.

Hereinafter "textual structure" will be called a set composed of several groups of atoms, each group of atoms forming a string of characters, the latter being letters, numbers or symbols belonging to a defined alphabet. Groups of atoms are also called fingerprints.

We will call "dictionary" a set of predetermined groups of atoms. We will call "directory" a set of predetermined structures.

The method according to the invention finds particular application in the identification of a geographical address among a plurality of possible geographical addresses that belong to a directory.

As part of this application, we can assimilate the geographic address to a structure.

The elements making up the geographical address, such as the name of the channel or the type of channel, for example, can be assimilated to said groups of atoms.

The directory can be likened to a set (or a collection) of predefined structures. For example, the list of addresses for a given city is a collection of structures that are known and saved.

As for the dictionaries associated with groups of atoms, they can correspond to a group of possible types of channels, or to all the names of lanes in a given city, or even to all numbers from 1 to 200 for example. To identify a geographical address, it is necessary to fill in fields with a string of characters constituting a group of atoms whose sequence is potentially erroneous, which will be called -φareafter "atomic group information", each of fields being associated with a dictionary, and said characters can be numbers, letters or symbols.

Since geographical addresses are generally associated with a natural or legal person, the invention may also help to identify said person from information concerning his address.

Also, the invention is intended in particular to be implemented by telephone information companies to search for postal or telephone coordinates of a person.

The terms of trade between the customers who call the information company and the operators to respond to the customer are the cause of loss of time and errors in the research.

Indeed, the customer may make mistakes in the spelling of the name of the person sought, or in the address thereof. At the same time, the operator may make typing errors or misunderstand the client's request.

The method according to the invention makes it possible to more quickly find the information sought by a client, despite the operator's accidental input errors, or incomplete or approximate information provided by the customer.

There are currently methods, implemented by search engines, that allow a search for structures among a plurality of structures.

Specifically, the structure corresponding to the geographical address comprises at least two groups of atoms, for example the name of the channel and the type of the channel.

This level of treatment corresponds to what is described in our invention as "group of atoms": a word is a group of atoms, the atoms corresponding to the characters forming the word.

Known methods include a step of preliminary information fields whose content is associated with a group of atoms and the dictionary associated with it. This step of field information consists in concretely entering into a box a series of letters, numbers or symbols.

The group of atoms filled in is then potentially erroneous, either because a typing error may have occurred, or because the person who filled in the fields misunderstood what was dictated to him, or because the person who dictation was incorrect or wrong. A known method of searching for a group of atoms among a plurality of groups of atoms is described in particular in US Pat. No. 6,879,983. According to this method, the groups of atoms that are indicated are compared with one another. one with the existing groups of potential atoms to suppress potential atomic groups that do not have exactly the same ordered atoms in the same way.

On the other hand, the groups of atoms similar to those which have been indicated are retained.

Thus, the search for structure is done according to a hierarchical approach which gives a result only in the case where the fields have been exactly informed.

The potential error of input by an operator filling fields is therefore not taken into account in this method.

The operator having made an input error must verify that all the fields have been correctly filled in and must possibly make the effort to propose variants in the arrangement of atoms or variants of atoms in the groups of atoms so that the method delivers a result.

In the extreme, another method takes into account all possible typing errors for a field filled. This other method is for example described in US Pat. No. 7,047,493. This method determines all possible combinations of atoms for a group of atoms from the filled field.

For example, for the field filled "physical", the method consists in determining all the possible writings of the word "physical" taking into account the sounds generated by each of the atoms (or each of letters) or each association of atoms following the chain of distinguished atoms in the field. The results generated by such a method are extremely numerous: "fisikle", "fysicle" ... Also, the memory required in a computer to implement such a method is often insufficient, which causes operating anomalies. Identifying a structure from this method thus seems very difficult.

Another method is still implemented in mobile phones to help the user write messages from the keys on the phone's keypad, a key that can correspond to several letters of the alphabet.

This method is for example described in US patent application document US-2003/0234821. It consists of a method for predicting and proposing a word to a mobile phone user writing a mini message (SMS), from the sequence of letters typed by the user.

This method consists in particular of matching the sequence of typed letters, comparable to a group of ordered atoms, with words stored in a dictionary, said words being assimilable with groups of potential atoms. The method uses a likelihood calculation of possible words to which can match the series of letters typed by the user based on previously typed words and habits of this user.

This method does not take into account any possible typing errors of the user. Also, if the user types one key instead of another, the method will not find the word the user wanted to write. He will even have to erase the letters he has typed to write the word he is looking for correctly.

Also known in the state of the art US5659771 patent. This patent concerns an orthographic corrector, for the treatment of words in a text. The treatment consists of proposing, for each word of a text, a set of alternative words (the words of a set are the words usually confused). The problem is that each set only includes the known and previously observed confusions. In addition, it is necessary to record a very large dictionary including all possible sets of confusions, even for sequences of words for which the probability of confusion combination is zero.

In this set, words that have never been recorded as confusion, the treatment is inoperative; in other words, the method according to this prior art is extremely sensitive to the completeness of sets of confused words: the omission of a single word of confusion can make the treatment totally ineffective. This encourages us to build very large dictionaries, which leads to long processing and unnecessarily heavy data volumes.

The document 24th Australian Computer Science Conference, ISBN 0-7695-0963-0, is also known as "large scale experiments on correction of confused words". This proposes a treatment method similar to that described in patent US5659771. The dictionary is built in this document from phonetic confusions as well as typing confusions and includes an upstream training phase.

The article "Improving the performance of dictionary-based approaches in protein recognition CREST, author Yoshimasa Tsuroka, Jun'ichi Tsujii; Japan Science and Technology Agency, published October 8, 2004 at www.elsevier.com/locate/yjbin "offers heuristic processing based on the use of a distance function between two words. The distance is calculated based on a formula that takes into account the cost of bringing two words together based on the cumulative distance between sets of characters.

The invention relates to an automatic method for processing digital information.

It should be remembered that the invention does not simply concern the search for words in a dictionary, as is the case for documents of the prior art. The invention relates in fact to three level treatments:

Level 1: Set of "groups of atoms" (eg structure, or database record, complete mailing address, ...)

Level 2: Group of atoms (for example a word, a postal code, a numerical identifier, ...)

Level 3: Atoms (for example a character)

In the documents of the prior art, the processing is carried out only on two levels:

Level 1: Word (i.e. Group of Atoms) Level 2: Characters (i.e. Atoms)

The solutions proposed in the prior art therefore do not make it possible to carry out the treatments as claimed.

In the prior art, the treatments are performed exclusively on the level of the word relative to a dictionary, and do not take into account the structural context in which the word is used for the selection or the removal of doubt, after treatment the word.

To shed light on this difference, let's take a simple example of how to treat an address in a city. This address, to simplify includes = number in the street the name of the street The treatment according to the prior art consists in carrying out two consecutive treatments, using two "specialized" and distinct dictionaries: first of all, the recognition of the number in the street, from a search in a dictionary comprising all the possible street numbers to remember the most likely candidate first proceed to the recognition of the street name, from a search in a dictionary including all possible street names to retain the most likely candidate concatenate the two results to determine the corrected address.

The present invention aims to overcome the disadvantages of the state of the art.

The treatment according to the present invention consists in carrying out a global processing: proceed to the recognition of the address, from a search in a directory comprising all the existing addresses (complete addresses in the form of [Number in the street + street name]).

The directory is in a way a dictionary with several dimensions - two dimensions in the above-mentioned example), with a limitation of the instances to the only existing addresses actually. The size of this directory is therefore smaller than the size of the combinations of the dictionaries corresponding to each group of atoms. The resulting technical advantage, in addition to improving the relevance of recognition, is the reduction of processing times and the size of the memories required for the recording of information and their processing.

The invention firstly aims at a method that makes it possible to identify an amount N of potential groups of atoms from a collection of groups of atoms, said collection belonging to a dictionary F, said dictionary comprising a quantity Q of groups of atoms. atoms, each group of atoms consisting of a sequence of atoms which are ordered relative to each other and which each belong to an alphabet, said alphabet comprising a determined quantity P of atoms of different characters.

Specifically, in a first step and in the context of the application to address search in a directory, the method of the invention aims to identify, for example, a street name, from a street name seized and potentially erroneous, and that among all the street names of the collection belonging to the dictionary "street names" of a given city.

The method according to the invention comprises, in a manner known per se, a step of informing a field by a group of potentially erroneous atoms constituting a group of atoms indicated, and a step of identifying said quantity N of groups. potential atoms which may correspond to said group of atoms indicated among those of said collection of said dictionary. According to the invention, the identification step consists of the following steps:

pairing said group of atoms filled with each of the Q groups of atoms of said collection of said dictionary F, for each pairing, calculating a probability of similarity between the group of atoms indicated and the group of atoms of the paired dictionary ,

and identification of the N groups of potential atoms whose probability of similarity is highest.

The identification step thus carried out makes it possible to associate several groups of atoms with a probability of correspondence, which enables the invention to provide one or more results (ie an amount N) as a function of previously established parameters.

For example, by means of the method according to the invention, it is possible to retain all the groups of atoms of the dictionary whose probability of matching with the group of atoms indicated would be greater than a given percentage, or else the 10 or 20 groups of atoms of the dictionary whose probabilities of matching with the group of atoms indicated would be the best.

The method according to the invention thus makes it possible to retain several possible results, while remaining limiting on the quantity of results so as not to encumber the memory of a device that would implement the method. In the context of a first embodiment of the invention which will be described and illustrated subsequently, the similarity probability calculation is a product of probability calculations for each atom of the group of atoms which is indicated. The probability calculations take into account, preferably, the position and the character of each atom in the sequence of atoms of the group of atoms which is indicated.

It is advantageously provided that the probability calculations take into account a phonetic confusion factor between, on the one hand, an atom of defined position and character which is identified in the group of atoms indicated, and, on the other hand, another atom.

For example, and concretely, this embodiment makes it possible to calculate the probability of similarity between a word and another which takes into account a possible error of input of the operator, the latter may have mistakenly entered a letter whose sound is close to that of the letter he should have seized.

In the context of a parallel embodiment, it is expected that the probability calculations take into account a neighborhood confusion factor between two successive atoms in the sequence of atoms of said atomic group of atoms, and on the other hand two other atoms.

This embodiment takes into account any operator input error that would have reversed two letters in the word. Advantageously, it can also be provided that the calculations of probabilities take into account a factor of visual confusion between on the one hand an atom whose position and the associated character are defined and which is identified in the group of atoms indicated, and on the other hand another atom.

This embodiment takes into account any operator input error that would have confused two letters that are similar.

It can still be advantageously provided that the probability calculations take into account a geographical confounding factor on an atom input keyboard, between

on the one hand, an atom observed in the sequence of atoms of the group of atoms, the observed atom having a position and a character which are defined, the atom being associated with a key of said input keyboard whose geographical position; on said keyboard is identified,

and on the other hand another atom which is associated with a key close to the key identified on said keyboard which is associated with the observed atom.

This embodiment takes into account a possible typing error of the operator who would have pressed the key next to the one on which he wanted to press.

Thus defined, the method according to the invention makes it possible, at first, to find several possible results from a sequence of characters entered by an operator, said sequence of characters entered defining a group of atoms indicated, and each result corresponding also to a group of atoms, these last groups of atoms belonging to a collection of groups of atoms in a dictionary.

As indicated above, the objective of the invention is above all to identify a structure from a collection of structures, each structure being composed of several groups of atoms.

To this end, the invention also relates, and in a second step, to a method for identifying a structure from a collection of structures belonging to a repertoire, said structure comprising at least two groups of atoms, each group of atoms being associated with a dictionary.

In the first place, the method according to the invention consists in identifying, for each group of atoms, an amount N of groups of atoms by applying the method defined above.

Secondly, the structure identification method according to the invention implements the following steps:

identification of all the potential combinations of structures from the N groups of potential atoms identified,

- identification of the most relevant structure from the repertoire structure collection by performing the following steps: matching each of the potential structures identified with each of the structures from the directory structure collection,

- for each pairing, calculation of a likelihood of similarity,

and identification of the most relevant structure among those in the collection of repertoire structures, the likelihood of which is similar to a directory structure is greatest.

Thus realized, the method according to the invention finds the most probable structure in a repertoire from groups of indicated atoms which are potentially erroneous, taking into account the best possibilities of similarity between the sequences of atoms indicated by the operator and those of associated dictionaries, without following a hierarchical model that removes the possibility of input errors.

In the context of an advantageous embodiment, it is expected that the calculation of the probability of similarity between a structure of the repertoire and the structure composed of atomic groups of information takes into account the probability of identifying a given group of atoms. in a structure knowing the group of atoms that is close to it.

In parallel, the invention relates to a system for identifying structures implementing the identification method described above, as well as a system for identifying groups of atoms implementing the identification method described above. An example embodiment of the method and method according to the invention will now be described with reference to the appended drawings, among which: FIG. 1 represents a Bayesian network implemented by the method according to the invention, FIG. schematically represents a keyboard "AZERTY" used by an operator to enter groups of atoms, Figure 3 represents a Bayesian network implemented by the method according to the invention, Figure 4 is a diagram showing the data exchanges generated by the identification method according to the invention, FIG. 5 is a diagram showing the data exchanges generated by the identification method according to the invention,

and FIG. 6 schematically illustrates a structure and dictionaries associated with each of the groups of atoms composing said structure.

To better understand the invention, the description that follows will refer to only one example of application: a search address or person from fields filled by an operator.

However, it should be understood that this application is not limiting, and that the invention can be applied to the identification of data or elements in other fields. The method and method according to the invention are applied by computer system which is used by an information telephone operator 1.

The telephone operator 1 must find an address or a person from data provided to him by a customer.

The data provided by the client constitute groups of atoms filled in, and these groups of atoms are memorized by the operator in fields, each field being associated with a dictionary.

Specifically, the operator 1 enters in boxes (corresponding to said fields), using a keyboard 2, sequences of characters that can be a sequence of letters and / or numbers and / or symbols. The groups of atoms that are indicated thus consist of a sequence of characters.

Figure 6 shows schematically the composition of a structure s of an address.

The structure s comprises groups of atoms f1, f2, f3, f4 and f5.

Each group of atoms is associated with a dictionary having a collection of F atoms predefined groups f _±. Thus, and in the context of the address search application, the group of atoms f1 is associated with the dictionary Fl which concerns the numbers, and which includes all numbers from 1 to 999, for example.

Also, the dictionary F1 has a quantity Q of groups of atoms which is predetermined and which, in this case, is equal to 999.

The group of atoms f2 is associated with the dictionary F2 which concerns the types of tracks, and which comprises a defined quantity of writing types of ways such as "av", "avenue", "avenue d", "avenue de »,« Street »,« street »,« boulevard »...

The group of atoms f3 is associated with the dictionary F3 of the names of way which includes all the names of ways of a city, for example.

The group of atoms f4 is associated with the dictionary F4 of the postal codes which includes all the postal codes listed on the French territory, for example.

The group of atoms f5 is associated with the dictionary F5 of cities which includes all the names of cities listed in France, for example.

The dictionary F2 to F5 respectively contain quantities of groups of atoms determined. In the search for a person based on information concerning his address, four steps are identified, which are shown schematically in Figure 4.

The four steps are:

Identification 3 of the track name, Identification 4 of the track type Identification 5 of the track Identification 6 of the wanted person.

The completion of each of these steps uses a Bayesian program.

Operator 1 enters the fields corresponding to the name of the channel and the type of channel. These two intelligence steps are symbolized by arrows R1 and R2 in Figure 4.

The description which follows will now refer to the identification step 3 of the name of the channel.

It should be noted here that this identification step 3 is performed in the same way as the identification step 4 of the type of channel.

The identification step 3 consists, in accordance with the invention, of matching the group of atoms f3 indicated by the operator and associated with the dictionary F3 "channel name", with each of the groups of atoms f3 belonging to the F3 dictionary collection. For each pairing, we then calculate the probability that the path name is f3 knowing that we have f3. This probability calculation is noted P (f3 / f3) in FIG.

The same goes for the probability calculation of the type of channel f2 knowing the type of channel filled f2: P (f2 / f2).

Reference will now be made to FIG. 1 to describe the method according to the invention which is implemented to identify several types of possible f3 channels from a sequence of characters entered by the operator 1 in the field associated with the F3 dictionary "name of lanes".

In general, the method consists in finding the distribution of probability of pairing between the group of atoms observed f and each of the groups of atoms f of the dictionary F.

To define P (f / f), the Applicant represents a group of atoms observed f by a sequence of pairs: f = <1, a1> <2, a2> <3,! 3> ... <k, ak >

where aj is the "j-th" atom of the group of atoms observed f.

Take the example of the street name "Saint Fergus". The operator was wrong in entering the street name and typed "knows jergus". In the context of this example, we have:

f = <l, s> <2, a> <3, i> <4, t> <5, ''> <6, j> <7, e> <8, r> <9, g>

<10 _f u><ll,s>

We want to calculate P (f / f) = P (f / <1, a1> <2, a2> <3, a3> ... <k, ak>), where k = length (f).

To calculate this value for any element f belonging to the dictionary F, it must be considered that each pair (j, aj) is an observation pair of a group of atoms f of the dictionary.

The first value j is the index is the observed index of an index j of f. The indices of f range from 1 to length (f). The lengths of the atomic groups and the groups of atoms of the dictionary may be different. The second value aj is the observed atom given the atom aj of f.

The probability calculation for each pairing between the group of atoms observed and a group of atoms among those of the associated dictionary is as follows:

P (f j j aj ij) = P (f) P (J / f) P (J / j) P (aj / jf) P (aj / aj)

The Bayesian network corresponding to this probability calculation is shown in FIG.

P (f) is the probability distribution of all groups of atoms in the Fet dictionary and is known. P (j / f) is the distribution of the index j knowing the group of atoms f and is defined as follows:

P (j / f) = 1 / length (f) if j <= length (f) otherwise, P (j / f) = 0

^p (d / J) ^{is a} distribution of observed 3 index as the index j. This distribution is a so-called "normal" (that is to say Gaussian) distribution of average j and spacing type σ.

P (j / j) = Normal (j, j, σ)

P (aj / jf) is the probability distribution representing the obtaining of the atom aj from the index j and the group of atoms f.

P (aj / jf) = 1 if aj is the "j-th" atom of f, else P (aj / jf) = 0

P (aj / aj) is the probability distribution of observing the aj atom from the aj atom. This distribution is normally obtained from statistics describing the frequencies of confusion and / or knowledge of an expert in the field of application.

In applications where the atoms are the symbols of a computer keyboard 2, the confusions are established by the neighborhood of keyboard keys 2, phonetic proximity, resemblance and spelling among others.

Neighborhood confusion is the exchange of one atom by another. For example, on the keyboard 2 AZERTY shown in Figure 2, it is more likely to confuse the key "G" with the neighboring keys "F", "R", "T", "Y", "H", " N "," B ", and" V ", than to confuse the" G "key with the" L "key.

In the case of neighborhood confusion, we take into account the normal probability distribution with a standard deviation σ and an average equal to the distance between aj and aj, that is to say:

P (aj / aj) = Normal (aj, distance (aj, aj), σ), where distance (aj, aj) is the distance between the two atoms aj and aj.

Phonetic proximity is to confuse atoms because of their close pronunciation. For example, some interlocutors might confuse the "e" with the "o".

The confusion by resemblance consists in confusing two atoms because of their resemblance in their writing, or topology. For example the letter "1" can be easily confused with the number "1".

Orthographic proximity is also a source of confusion. From all the distribution calculations, that is to say of probability, which have been defined above, it is possible to calculate the probability that a group of atoms indicated f corresponds to a particular group of atoms f among those of a list group of atoms, or dictionary F.

P (f / f) = P (f / <1, a1> 2, a2><3,a3> ... <k, ak>) = P (f / <1, a1><2,a2><3,a3> ... <kl, k-1> 2 _a . P (J / f) P (3 = k / d) P (aj / jf) P (aj = ak / aj)

with P (f / <1, II>) = P (f) Σ _{jf aj} P (j / f) P (3 = 1 / j) P (aj / jf) P (aj = a1 / aj)

Now that the calculation of probability has been explained in detail, it is necessary to return to the main problem at the root of the invention, which consists in finding an address or a person from incomplete data provided by a client to a telephone operator. . It is recalled here that this problem is illustrated in particular in FIG.

By applying the method described above, the identification steps 3 and 4 of the name of the channels and the type of channels respectively revealed a quantity N of possible results with which probability coefficients are associated.

For example, the method according to the invention has revealed the 3 channel names with the probabilities of similarity are the best, and the 3 types of channels whose probabilities of similarity are the best. In this example, N is equal to 3. N can be a previously defined quantity of results. N is however not limited to this definition. N can also be defined as the quantity of results whose probability is greater than a given percentage.

The identification step 7 of the desired address implements the structure identification method according to the invention.

It is appropriate here to recall the definition of the matching problem: either s a given structure (or instance observed) and ES = - {si, s2, s3 ... sn) a collection of structures belonging to a directory. The problem of matching structures is to find the instance or instances in ES most similar to s.

It should also be remembered that the structure is potentially wrong.

The pattern matching model takes up part of the pattern of pairing of groups of atoms. Three additional variables s, i and fi are however introduced.

The variable s represents a structure among all those in the ES collection belonging to the associated directory.

The variable i represents the index of a group of atoms of s and fi is the "i-th" group of atoms of s. The Bayesian network of structure matching is shown schematically in Figure 3.

The likelihood calculation of structural matching is as follows:

P (if fi jj aj aj) = P (s) P (i / s) P (f / s) P (f / f) P (J / f) P (J / j) P (aj / j) ) P (aj / aj)

P (s) is the probability, or distribution, of I / O instances.

P (i / s) is the probability of the index of a group of atoms of s. This probability is defined as follows:

If i> = length (s), then P (i / s) = 1 / length (s), otherwise P (i / s) = 0

P (fi / s i) is a probability distribution of the i-th group of atoms given s and i:

P (fi / s i) = 1 if fi is the i-th group of atoms of s, otherwise P (fi / s i) = 0

P (/ / fi) is the distribution obtained from the previously described atom group matching submodel. The distribution P (fi / fi) represents the probability of pairing the element fi of the dictionary F given the i-th group of atoms of a structure in the repertoire ES. This distribution must be built at from the Bayesian model of structural matching by calculating the probability P (f / f) for each structure belonging to the collection of the repertoire.

The other distributions P (j / f), P (j / j), P (aj / jf) and P (aj / aj) are similar to those presented in the method of identifying groups of atoms defined above.

The detailed probability calculation that is used is as follows:

Let s = [l, fl], [2, f2], ... [n, fn]

The probability distribution of a structure P (s / s) is then calculated as follows:

P (s / s) = P (s / [l, fl], [2, f2], ... [m, fm])

By substituting fm for the pair sequence <j, aj> for j≈l, ..., k, we have:

P (s / [l, fl], [2, f 2], ... [m, fm])

= P (s / [l, fl], [2, f2], ... [m-1, fm-1] [m, <1, a1m> <2, a2m> ... <m, akm>])

= P (s / [l, fl], [2, f2], ... [ml, fm-1] [m, <1, to1m> <2, 2m> ... <m, I (k- 1) m>])

P (i = m / s) P _f i _f i _aj P P (/ / S i = m) P (/ /)) P (J /)) P (j = k / d)

P (aj / jf) P (aj = ikm / aj) with

P (s / <1, ill>) = P (s) P (i = 1 / s)

Σ _f i _{fj aj} P (fi / si = 1) P (/ /)) P (J /)) P (J = I)

/ j) P (aj / jf) P (Ij = 111 / aj)

Now that the probability calculation has been detailed, it is necessary to return to the main problem at the origin of the invention, which consists in finding an address or a person from incomplete data provided by a client to a telephone operator.

It is recalled here that this problem is illustrated in particular in FIG.

From the results provided by steps 4 and 3, respectively, of identification of type of channel 4 and of channel name 3, and of the method according to the invention, step 5 of identification of the channel has delivered the address most likely given the customer's indications.

By consulting the ES directory, the computer system provided to the operator, the name of the person associated with the address found. This is the identification step 6 shown in FIG. It should be noted that the invention could apply only to the search for a person from his own name.

This application is illustrated by the diagram of FIG. 5 showing the data exchanges generated by the identification method according to the invention.

The operator 1 fills a field by entering a sequence of atoms f dictated by a client.

The system would apply the method according to the invention to identify a given quantity N of names to which the name could be related, and deliver as a result only the group of atoms f which will be associated with the greatest likelihood of matching.

A particular application of the invention concerns the search for duplicates in a database.

For this application, a step of identifying potential duplicates is performed consisting in calculating, for each structure recorded in the database, a signature formed by a collection of identifiers of similar substructures, and then constituting a sub-structure. together the structures whose signatures are correlated, the correlation function being determined by the existence for each intermediate group of the compared structures of at least one common identifier, then to calculate for the structures matched by the correlation function, the result of applying to each of said paired structures the treatment according to the method of the invention, and assigning a proximity indicator according to the proximity of said results. The following description relates to a particular example of the application of the invention to search for duplicates in a database by a Bayesian method.

Let D be a database1, S the structure of an entry in the base D, and if, sj two instances of S, then sj is a duplicate of si if sj is supposed to represent the same information as if and vice versa .

The elements si and sj have a well-defined structure. We recall that a "structure" is a set composed of several groups of atoms also called "fingerprints".

For example, a database of educational institutions could have the lines below.

No of institution: Center for Computing Research

Address: Av. Juan de dios Buildings s / n casi esq. Miguel Othon from Mendizabal

City: Mexico State or Region: D. F. Postal Code: 07738 Pay: Mexico

No of institution: Center for Computing Research (CIC);

Address: Av. Juan de Dios Buildings s / n casi esquina Miguel Othon de Mendizabal City: Mexico

State or Region: Mexico D. F

Postal Code: 07738

Pay: Mexico

No from institution: Center for Computing Research of the National Polytechnic Institute

Address: Av. Juan de Dios Buildings s / n, Esq. Miguel Othόn from Mendizâbal Unidad Profesional City: Mexico City

State or Region: Mexico. D. F .; Postal Code: 7738 Paying: Mexico

The three previous entries correspond to three instances of the structure S of the database. Call these instances if, s2 and s3 respectively. These instances are meant to represent the same information, despite the differences in their content. We call a set of duplicates to any set of instances that are supposed to represent the same information. Thus, the set ES = {sl, s2, s3} is a set of duplicates. For simplicity, we consider that a set of cardinality 1 is also a set of duplicates.

A data base D is composed of a set of instances of a structure S:

D- {J ,, J ,, ..., J _B } The duplication of D consists of:

Find an I • ' ² '^"'' ^{k '} ' D partition where each A- subset of the partition is a set of duplicates.

dans la partition, créer une instance ^sι dit « propre » et représentant le sous- ensemble ^υ> . L'instance⁵' est obtenue à partir d'une fonction de nettoyage f\', c'est-à-dire ^sι ^{= J}\^υi) . La fonction ^J\' pourrait simplement rendre un élément de Q _ou bien, une instance résultant d'une procédure complexe combinant les groupes d'atomes ( fingerprints ) des éléments de A.For each subset ''

in the partition, create an instance ^s ι says "clean" and representing the subset ^υ>. The body ⁵ is obtained from a cleaning function f \ ", that is to say, ^{s = J} ι \ ^υ i). The function ^J \ 'could simply render an element of Q _or an instance resulting from a complex procedure combining the groups of atoms (fingerprints) of the elements of A.

est le dédoublonnage de D.The database

is the duplication of D.

The main problematic of the procedure described in the preceding paragraph is the obtaining of a partition P of duplication. In this paragraph, we describe the principle to obtain this partition.

We note v ⁵ "P ⁾ the subset of D defined as follows:

D {s _i , p)

est appelé l'ensemble d' appariement de ⁵< dans D. Si nous obtenons l'ensemble d' appariement pour toutes les instances de D alors nous obtenons l'ensemble D contenant les ensembles d' appariement de D :WHERE (ΨΛ is the distribution of probability of matching of s ^'/. To ^s ι and PJ' J is a threshold probability of matching. All

is called the matching set of ⁵ <in D. If we get the matching set for all instances of D then we get the set D containing the matching sets of D:

D = [D (S ₁ , p), D (s ₂ , p), ..., D (s _n , p)}

Clearly, D is not necessarily a partition of D because an intersection can exist between two sets

^D { ^s nP) and I ¹ V /. However, from the set D ₁ it is possible to obtain a partition P of D. The elements appearing in more than one set of matching could be kept only in the set where their probability of matching is the same. more

big. Thus, we have that V / or ^ w is the transforming function D in a partition of D. In the following, we call D the base set of P.

The construction of the base D can be very heavy. Indeed, D is obtained from the comparison of (nxn-n) _pairs (s ,, Sj) ≡DxD _{QÙ i ≠ j} ^ _{vQ ± r Eχpression (1) # An} important cardinality could make this task prohibitive. On the other hand we have to define the function

^ W. In the following paragraphs, we explain how it is possible to relax the calculation of the base set.

We recall that an instance of structure s is composed of a group of atoms (fingerprints):

W.Λ-Λ For example, for the following instance:

No of institution: Center for Computing Research Address: Av. Juan de dios Buildings s / n casi esq. Miguel Othon from Mendizabal

City: Mexico State or Region: D.F. ZIP Code: 07738 Pay: Mexico

We have six groups of atoms:

/ i = Center for Computing Research

/ 2 = Av. Juan de dios Buildings s / n casi esq. Miguel Othon from Mendizabal

/ 3 = Mexico

J ₆ = Mexico

une valeur de probabilité, nous définissons la caractérisation de /1 comme suit :Let 'V ¹ ' ^ ²¹ '' ^Jn i be any dictionary of n elements associated with -A and

a probability value, we define the characterization of / 1 as follows:

C, = {ye {l, 2, ..., n} | P (/; | /,)> _Λ }

where v / J /, ⁾ _is the probability of matching f> to * J. The set ^ 'is the set of identifiers of the dictionary ^ for which the probability of pairing with Ji is greater than or equal to Pc. For example, if the dictionary ^ s is defined as follows:

₅ F = {/, ⁵ = 07778, / ₂ = ⁵ 098 535, / ₃ = ⁵ 077 654, / ₄ = ⁵ 07638}

then, for our instance example above we could have that: C ₅ = {1.4}

If ⁵ = 07778 ^ In other words, the probability of V- ⁷ '' pairing and

(/ ₄ ⁵ = 07638) with U = ^{07 738)} is greater than or equal to Pc.

de S comme l'ensemble des caractérisations de ses groupes d'atomes :Similarly, given a set of dictionaries F ₁ F ₂ ... F _L associated with a structure S, we define the characterization of an instance

of S as the set of characterizations of its groups of atoms:

C ()) = (C ₁₅ C ₂ -Q)

Thus, the characterization of s could be, for example:

C (5, p _c ) = ({l, 5,7}, {l, 2,8} - {7,8}) Obtaining the basic set resides in the computation of the characterizations of the instances of the database.

Let there be any two instances -V- ^ ^ D then ^s i is a potential doublet of ⁵ i if ^VC < ^GC ( ⁵ "O ' ^C - ^{2 E 6} VvZ ⁷ J _{We have that} C ₁ HC ₁ ^≠ 0 _# WE denote this together by ^D Λ ^s ι).

= {l,3,5},c; =

= {5,7},) , C(S₂, p_L) ≈ (C₁ ² = {2,3},C₂ ² = {3,5,8},C₃ ² = {2},C² = {l,5,}) ,For example, let C {s _vPc ) = (c \ =

= {l, 3,5}, c; =

= {5,7},), C (S ₂ , p _L ) ≈ (C ₁ ² = {2,3}, C ₂ ² = {3,5,8}, C ₃ ² = {2}, C ² = {l, 5,}),

— ^υ _cornme suit :

C (s ₃ , pJ = (c'≈ {3}, C ₂ ³ ≈ {\, 5}, C ₃ ⁱ = {3}, Cl≈ {l, l},) then ^s i is a potential duplicate of ⁵ i. in contrast, ^five 3 is not a potential duplicate for ⁵ i C _{3 3} DC = O _^ The set D ≈ {D {s _v p), D {s ₁ , p), ..., D {s _n , p)} _is redefined _by redefining

- ^υ _cornme follows:

The invention further relates to applications such as database merging and forming clusters of structures homologous to a reference structure.

For an application to database merging, a step of identifying potential duplicates is performed consisting of calculating, for each structure recorded in each of the databases, a signature formed by a collection of identifiers of similar intermediate groups , then to constitute a subset of the structures whose signatures are correlated, the correlation function being determined by the existence for each intermediate group of the compared structures of at least one common identifier, then to calculate for the structures matched by the correlation function, the result of the application on each of said paired structures of the processing according to claim 8 and to assign a proximity indicator according to the proximity of said results and to record a database merged with the unique structures.

For the application of constituting clusters of structures homologous to a reference structure, the method according to claim 1 is applied to said reference structure on the one hand, and to all the available structures of a directory, for determine for each of said available structures a probability of similarity and to record in a subset the available structures whose probability of similarity is greater than a predetermined value.

Other applications are planned: Cleaning of marketing and commercial database

It is an application that brings together all the functions to clean a database with database deduplication, database merge, standardization, clustering and input help. The product would primarily target companies managing prospect or customer bases.

features

Features will align with the data lifecycle in the marketing and sales businesses:

- Database Deduplication, which applies to an existing table with approximate duplicates.

- The merging of databases. As an example, a tool shop that buys a competitor, but whose product bases include different field names and CDMs.

- The characterization of customers from web browsing, the chain of clicks ...

- Reconciliations: application in credit card fraud. {Historical transaction databases, fraud files (Banque de France), Reconciliation concept, Different system hours, Amounts not equivalent (commissions, rounding, exchange rates, ...).

Apart from the deterministic card number, the rest is unclear. Complex object: string of characters. Management close dates with notion of distance between two dates. - Profiling and clustering: Which structures correspond to a typical profile? Classes are defined with examples.

Classification: Multi-criteria market segmentation tool that works by learning and inference.

Standardization. From several imperfect information, find the index in the corresponding database.

- Input help: Type addresses anyhow, and they are formatted according to baseline. We clean and we choose the good occurrences. Proposal of existing structures if a new entry looks like it, prevention of duplicates (is closer to standardization). - Dynamic corrections: Probabilistic model of computer keys. According to the semantic field.

- Cleaning and indexing a database by querying a remote information system.

Claims

1 - Method for determining the similarity between an amount of several groups of potential atoms from a collection of groups of reference atoms, said collection belonging to a dictionary (F), said dictionary comprising a determined quantity Q of groups of atoms (f), each group of atoms (f) consisting of a sequence of atoms (a) which are ordered relative to each other and which each belong to an alphabet, said alphabet comprising a determined quantity of atoms of different characters, said method comprising: a step of informing a field by a group of potentially erroneous atoms constituting a group of atoms indicated (f), and a step of identifying said quantity N of potential groups of atoms that may correspond to said group of atoms indicated (f) from those of said collection of said dictionary (F) characterized, in that said identification step consists of the following steps: pairing said group of atoms indicated (f) with each of the Q groups of atoms (f) of said collection of said dictionary (F), for each pairing, calculating a probability P (f / f) of similarity between the group of atoms indicated (f) and the group of atoms of the paired dictionary (f), and identifying the N potential atomic groups whose probability of similarity is highest or whose probability is greater than a threshold value. 2 - Method according to claim 1, characterized in that the calculation of said probability of similarity P (f / f) is a product of calculations of probabilities for each atom of the group of atoms which is indicated (f). 3 - Method according to claim 2, characterized in that said calculations of probabilities take into account the position (j, j) and the character (aj, aj) of each atom (a) in the sequence of atoms of the group d atoms which is informed (f). 4 - Method according to any one of claims 2 or 3, characterized in that the probability calculations take into account a phonetic confusion factor between on the one hand an atom of position (j, j) and character (aj, aj) defined which is identified in the group of atoms filled, and on the other hand another atom. 5 - Method according to any one of claims 2 to 4, characterized in that the probability calculations take into account a distal neighborhood confusion factor (aj, aj) between on the one hand two successive atoms in the sequence of atoms of said atomic group of atoms, and on the other hand two other atoms. 6 - Method according to any one of claims 2 to 5, characterized in that the calculations of probabilities take into account a factor of visual confusion between on the one hand a position (j, j) and character (aj, ij) defined which is identified in the group of atoms indicated, and on the other hand another atom. 7 - Method according to any one of claims 2 to 6, characterized in that the probability calculations take into account a geographical confusion factor on an atom input keyboard, between on the one hand, an atom observed in the sequence of atoms of the group of atoms indicated, the observed atom having a position (j, j) and a character (aj, aj) which are defined, the atom being associated; a key of said input keyboard whose geographical position on said keyboard is identified, and on the other hand another atom which is associated with a key close to the key identified on said keyboard which is associated with the observed atom. 8 - Method for determining the similarity between a candidate structure (s) and a referenced structure belonging to a repertoire (ES), said structure (s) comprising at least two intermediate groups (f 1, f 2), each of the intermediate groups (f 1) f2) being associated with a repertoire (F1, F2), said method comprising identifying, for each intermediate group (f1, f2), an amount N of intermediate groups (f) by applying the method according to any one of the preceding claims , said structure identification method being characterized in that it comprises the following steps: identification of all the potential combinations of structures from the N identified potential intermediate groups, identifying the most relevant structure from the collection of repertoire structures by performing the following steps: matching each of the potential structures identified with each structure (s) of the Directory Structure (ES) collection, for each pairing, calculating a probability of similarities P (S / s), - and identification of the most relevant structure (s) among those in the collection of structures (s) of the repertoire (ES), whose probability of similarity P (s / s) with structure (s) of the repertoire is the strongest. 9 - Process according to claim 8, characterized in that the calculation of said probability of similarity P (S / s) takes into account the probability P (fi / fi) to identify a given group of atoms in a structure knowing the group of atoms that is nearby. 10 - Application of the method according to claim 1 for the duplication of a database, characterized in that a step is taken to identify potential duplicates consisting of calculating, for each structure recorded in the database , a signature formed by a collection of identifiers of similar intermediate groups, then to constitute a subset of the structures whose signatures are correlated, the correlation function being determined by the existence for each intermediate group of the compared structures of minus a common identifier, and then to compute for the structures matched by the correlation function, the result of applying to each of said paired structures the processing of claim 8 and assigning a proximity indicator according to the proximity of said results. 11 - Application of the method according to claim 1 for the merging of databases, characterized in that a step is taken to identify potential duplicates consisting of calculating, for each structure recorded in each of the databases, a signature (characterization) formed by a collection of identifiers of similar intermediate groups, then to constitute a subset of the structures whose signatures are correlated, the correlation function being determined by the existence for each intermediate group of the compared structures of at least one common identifier, and then calculate for the matched structures. by the correlation function, the result of the application on each of said paired structures of the processing according to claim 8 and assigning a proximity indicator according to the proximity of said results and recording a database merged with the unique structures. 12 - Application of the method according to claim 1 for constituting clusters of structures homologous to a reference structure, characterized in that the method according to claim 1 is applied to said reference structure on the one hand, and to the set of available structures of a repertoire, for determining for each of said available structures a probability of similarity and to record in a subset the available structures whose probability of similarity is greater than a predetermined value. 13 - System for determining the similarity between a candidate structure and a referenced structure implementing the method according to any one of claims 8 or 9.