Obtenir la chaîne la plus proche

J’ai besoin d’un moyen de comparer plusieurs chaînes à une chaîne de test et de renvoyer la chaîne qui lui ressemble:

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW CHOICE A : THE RED COW JUMPED OVER THE GREEN CHICKEN CHOICE B : THE RED COW JUMPED OVER THE RED COW CHOICE C : THE RED FOX JUMPED OVER THE BROWN COW 

(Si je l’ai fait correctement) La chaîne la plus proche du “TEST STRING” devrait être “CHOICE C”. Quelle est la manière la plus simple de faire ça?

Je prévois de l’implémenter dans plusieurs langues, y compris VB.net, Lua et JavaScript. À ce stade, le pseudo-code est acceptable. Si vous pouvez fournir un exemple pour une langue spécifique, cela est également apprécié!

On m’a présenté ce problème il y a environ un an quand il s’agissait de rechercher des informations entrées par l’utilisateur sur une plate-forme pétrolière dans une firebase database contenant diverses informations. Le but était de faire une sorte de recherche de chaîne floue qui pourrait identifier l’entrée de la firebase database avec les éléments les plus courants.

Une partie de la recherche a impliqué la mise en œuvre de l’algorithme de distance de Levenshtein , qui détermine combien de changements doivent être apportés à une chaîne ou à une phrase pour la transformer en une autre chaîne ou phrase.

L’implémentation que j’ai proposée était relativement simple et impliquait une comparaison pondérée de la longueur des deux phrases, du nombre de changements entre chaque phrase et de la possibilité de trouver chaque mot dans l’entrée cible.

L’article est sur un site privé, je ferai de mon mieux pour append les contenus pertinents ici:


Fuzzy Ssortingng Matching est le processus consistant à effectuer une estimation humaine de la similarité de deux mots ou expressions. Dans de nombreux cas, il s’agit d’identifier des mots ou des expressions qui se ressemblent le plus. Cet article décrit une solution interne au problème de correspondance des chaînes floues et son utilité dans la résolution de divers problèmes, ce qui peut nous permettre d’automatiser les tâches qui nécessitaient auparavant une implication fastidieuse des utilisateurs.

introduction

La nécessité de faire correspondre les chaînes de caractères floues est apparue à l’origine lors du développement de l’outil de validation du golfe du Mexique. Ce qui existait, c’était une firebase database de plates-formes pétrolières et de plates-formes pétrolières connues du Golfe du Mexique, et les acheteurs d’assurance nous fourniraient des informations mal typées sur leurs actifs. Quand il y avait très peu d’informations, le mieux que nous pouvions faire était de faire appel à un souscripteur pour “reconnaître” celui auquel il se référait et appeler les informations appropriées. C’est là que cette solution automatisée est utile.

J’ai passé une journée à rechercher des méthodes d’appariement de chaînes floues et je suis finalement tombé sur l’algorithme de distance très utile de Levenshtein sur Wikipedia.

la mise en oeuvre

Après avoir lu la théorie derrière cela, j’ai implémenté et trouvé des moyens de l’optimiser. Voici à quoi ressemble mon code en VBA:

 'Calculate the Levenshtein Distance between two ssortingngs (the number of insertions, 'deletions, and substitutions needed to transform the first ssortingng into the second) Public Function LevenshteinDistance(ByRef S1 As Ssortingng, ByVal S2 As Ssortingng) As Long Dim L1 As Long, L2 As Long, D() As Long 'Length of input ssortingngs and distance masortingx Dim i As Long, j As Long, cost As Long 'loop counters and cost of substitution for current letter Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution L1 = Len(S1): L2 = Len(S2) ReDim D(0 To L1, 0 To L2) For i = 0 To L1: D(i, 0) = i: Next i For j = 0 To L2: D(0, j) = j: Next j For j = 1 To L2 For i = 1 To L1 cost = Abs(StrComp(Mid$(S1, i, 1), Mid$(S2, j, 1), vbTextCompare)) cI = D(i - 1, j) + 1 cD = D(i, j - 1) + 1 cS = D(i - 1, j - 1) + cost If cI <= cD Then 'Insertion or Substitution If cI <= cS Then D(i, j) = cI Else D(i, j) = cS Else 'Deletion or Substitution If cD <= cS Then D(i, j) = cD Else D(i, j) = cS End If Next i Next j LevenshteinDistance = D(L1, L2) End Function 

Simple, rapide et une mésortingque très utile. En utilisant cela, j'ai créé deux mésortingques distinctes pour évaluer la similarité de deux chaînes. J'appelle "valuePhrase" et j'appelle "valueWords". valuePhrase n'est que la distance Levenshtein entre les deux expressions, et valueWords divise la chaîne en mots individuels, basés sur des délimiteurs tels que des espaces, des tirets et tout ce que vous souhaitez, et compare chaque mot entre eux, en additionnant le plus court Distance Levenshtein reliant deux mots. Essentiellement, il mesure si les informations d'une «phrase» sont réellement contenues dans une autre, tout comme une permutation par mots. J'ai passé quelques jours en tant que projet parallèle proposant le moyen le plus efficace de fractionner une chaîne basée sur des délimiteurs.

valueWords, valuePhrase et la fonction Split:

 Public Function valuePhrase#(ByRef S1$, ByRef S2$) valuePhrase = LevenshteinDistance(S1, S2) End Function Public Function valueWords#(ByRef S1$, ByRef S2$) Dim wordsS1$(), wordsS2$() wordsS1 = SplitMultiDelims(S1, " _-") wordsS2 = SplitMultiDelims(S2, " _-") Dim word1%, word2%, thisD#, wordbest# Dim wordsTotal# For word1 = LBound(wordsS1) To UBound(wordsS1) wordbest = Len(S2) For word2 = LBound(wordsS2) To UBound(wordsS2) thisD = LevenshteinDistance(wordsS1(word1), wordsS2(word2)) If thisD < wordbest Then wordbest = thisD If thisD = 0 Then GoTo foundbest Next word2 foundbest: wordsTotal = wordsTotal + wordbest Next word1 valueWords = wordsTotal End Function '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ' SplitMultiDelims ' This function splits Text into an array of substrings, each substring ' delimited by any character in DelimChars. Only a single character ' may be a delimiter between two substrings, but DelimChars may ' contain any number of delimiter characters. It returns a single element ' array containing all of text if DelimChars is empty, or a 1 or greater ' element array if the Text is successfully split into substrings. ' If IgnoreConsecutiveDelimiters is true, empty array elements will not occur. ' If Limit greater than 0, the function will only split Text into 'Limit' ' array elements or less. The last element will contain the rest of Text. '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' Function SplitMultiDelims(ByRef Text As String, ByRef DelimChars As String, _ Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _ Optional ByVal Limit As Long = -1) As String() Dim ElemStart As Long, N As Long, M As Long, Elements As Long Dim lDelims As Long, lText As Long Dim Arr() As String lText = Len(Text) lDelims = Len(DelimChars) If lDelims = 0 Or lText = 0 Or Limit = 1 Then ReDim Arr(0 To 0) Arr(0) = Text SplitMultiDelims = Arr Exit Function End If ReDim Arr(0 To IIf(Limit = -1, lText - 1, Limit)) Elements = 0: ElemStart = 1 For N = 1 To lText If InStr(DelimChars, Mid(Text, N, 1)) Then Arr(Elements) = Mid(Text, ElemStart, N - ElemStart) If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) > 0 Then Elements = Elements + 1 Else Elements = Elements + 1 End If ElemStart = N + 1 If Elements + 1 = Limit Then Exit For End If Next N 'Get the last token terminated by the end of the ssortingng into the array If ElemStart <= lText Then Arr(Elements) = Mid(Text, ElemStart) 'Since the end of string counts as the terminating delimiter, if the last character 'was also a delimiter, we treat the two as consecutive, and so ignore the last elemnent If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) = 0 Then Elements = Elements - 1 ReDim Preserve Arr(0 To Elements) 'Chop off unused array elements SplitMultiDelims = Arr End Function 

Mesures de similarité

En utilisant ces deux mésortingques et une troisième qui calcule simplement la distance entre deux chaînes, j'ai une série de variables que je peux exécuter avec un algorithme d'optimisation pour obtenir le plus grand nombre de correspondances. La comparaison de chaînes floues est elle-même une science floue, et en créant des mésortingques linéairement indépendantes pour mesurer la similarité des chaînes et en ayant un ensemble connu de chaînes, nous pouvons trouver les parameters qui, pour nos styles spécifiques de chaînes, donner les meilleurs résultats de correspondance floue.

Initialement, l'objective de la mésortingque était d'avoir une faible valeur de recherche pour une correspondance exacte et d'augmenter les valeurs de recherche pour des mesures de plus en plus permutées. Dans un cas peu pratique, il était relativement facile à définir en utilisant un ensemble de permutations bien définies et en élaborant la formule finale de manière à obtenir des résultats de recherche toujours meilleurs.

Permutation de cordes floues

Dans la capture d'écran ci-dessus, j'ai modifié mon heuristique pour trouver quelque chose qui me semblait bien adapté à ma différence perçue entre le terme de recherche et le résultat. L'heuristique utilisée pour Value Phrase dans la feuille de calcul ci-dessus était =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)) . Je réduisais effectivement la pénalité de la distance de Levenstein de 80% de la différence de longueur entre les deux "phrases". De cette façon, les "phrases" qui ont la même longueur subissent la pénalité complète, mais les "phrases" qui contiennent des "informations supplémentaires" (plus longues) mais en dehors de cela partagent toujours les mêmes personnages subissent une pénalité réduite. J'ai utilisé la fonction de Value Words telle SearchVal , puis mon heuristique finale de SearchVal été définie comme suit =MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 - une moyenne pondérée. Quel que soit le score le plus bas, 80% et 20% du score le plus élevé ont été pondérés. C'était juste une heuristique qui convenait à mon cas d'utilisation pour obtenir un bon taux de correspondance. Ces poids sont quelque chose que l'on pourrait alors modifier pour obtenir le meilleur taux de correspondance avec leurs données de test.

Phrase de correspondance de chaîne floue

Mots de valeurs correspondant à des chaînes floues

Comme vous pouvez le voir, les deux dernières mesures, qui sont des mesures de correspondance de chaînes floues, ont déjà tendance à donner des notes faibles aux chaînes destinées à correspondre (en bas de la diagonale). C'est très bien.

Application Pour permettre l'optimisation de l'appariement flou, je pondère chaque mésortingque. En tant que tel, chaque application de correspondance de chaîne floue peut pondérer les parameters différemment. La formule qui définit le score final est une simple combinaison des mésortingques et de leurs pondérations:

 value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight + Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight + lengthWeight*lengthValue 

En utilisant un algorithme d'optimisation (le réseau neuronal est le meilleur ici car il s'agit d'un problème discret et multidimensionnel), l'objective est maintenant de maximiser le nombre de correspondances. J'ai créé une fonction qui détecte le nombre de correspondances correctes de chaque ensemble, comme on peut le voir sur cette capture d'écran finale. Une colonne ou une ligne obtient un point si le score le plus bas est atsortingbué à la chaîne qui doit être comparée, et des points partiels sont atsortingbués s'il y a égalité pour le score le plus bas, et la correspondance correcte fait partie des chaînes correspondantes. Je l'ai ensuite optimisé. Vous pouvez voir qu'une cellule verte correspond à la colonne qui correspond le mieux à la ligne actuelle et qu'un carré bleu autour de la cellule correspond à la ligne qui correspond le mieux à la colonne en cours. Le score dans le coin inférieur correspond approximativement au nombre de correspondances réussies et c'est ce que nous disons à notre problème d'optimisation de maximiser.

Chaîne floue correspondant à la métrique optimisée

L’algorithme a été un grand succès et les parameters de la solution en disent long sur ce type de problème. Vous remarquerez que le score optimisé était de 44, et le meilleur score possible est de 48. Les 5 colonnes à la fin sont des leurres et n'ont aucune correspondance avec les valeurs des lignes. Plus il y a de leurres, plus il sera difficile de trouver le meilleur match.

Dans ce cas particulier, la longueur des chaînes est sans importance, car nous attendons des abréviations qui représentent des mots plus longs. Le poids optimal pour la longueur est donc de -0,3, ce qui signifie que nous ne pénalisons pas les chaînes de longueur variable. Nous réduisons le score en prévision de ces abréviations, en laissant plus de place aux correspondances de mots partielles pour remplacer les correspondances de mots qui nécessitent simplement moins de substitutions, car la chaîne est plus courte.

Le poids du mot est de 1,0, tandis que le poids de la phrase est seulement de 0,5, ce qui signifie que nous pénalisons les mots entiers manquants dans une chaîne et que la valeur entière est intacte. Ceci est utile car beaucoup de ces chaînes ont un mot en commun (le péril) où ce qui compte vraiment est de savoir si la combinaison (région et péril) est maintenue ou non.

Enfin, le poids minimum est optimisé à 10 et le poids maximal à 1. Cela signifie que si le meilleur des deux scores (phrase de valeur et mots de valeur) n'est pas très bon, le match est fortement pénalisé, mais nous ne pénalisent pas beaucoup le pire des deux scores. Essentiellement, cela met l'accent sur le fait que le valueWord ou le valuePhrase doivent avoir un bon score, mais pas les deux. Une sorte de "prendre ce que l'on peut avoir" la mentalité.

C'est vraiment fascinant ce que la valeur optimisée de ces 5 pondérations indique sur le type de correspondance de chaîne floue. Pour des cas pratiques de correspondance de chaîne floue complètement différents, ces parameters sont très différents. Je l'ai utilisé pour 3 applications distinctes jusqu'à présent.

Bien qu'inutilisée dans l'optimisation finale, une feuille de référence a été établie, qui associe les colonnes à tous les résultats parfaits en diagonale, et permet à l'utilisateur de modifier les parameters en fonction de la différence entre les expressions ( qui pourrait en théorie être utilisé pour compenser les faux positifs dans les résultats)

Fuzzy String Matching Benchmark

Autres applications

Cette solution peut être utilisée partout où l'utilisateur souhaite qu'un système informatique identifie une chaîne dans un ensemble de chaînes sans correspondance parfaite. (Comme une correspondance approximative pour les chaînes).


Donc, ce que vous devriez en déduire, c'est que vous souhaiterez probablement utiliser une combinaison d'heuristiques de haut niveau (trouver des mots à partir d'une phrase dans l'autre phrase, longueur des deux phrases, etc.) avec l'implémentation de l'algorithme de distance Levenshtein. Parce que décider quelle est la "meilleure" correspondance est une détermination heuristique (floue) - vous devrez trouver un ensemble de poids pour toutes les mesures que vous proposez pour déterminer la similarité.

Avec l'ensemble approprié d'heuristiques et de pondérations, votre programme de comparaison prendra rapidement les décisions que vous auriez sockets.

Ce problème se pose tout le temps en bioinformatique. La réponse acceptée ci-dessus (qui était excellente en passant) est connue en bioinformatique comme les algorithmes de Needleman-Wunsch (comparer deux chaînes) et de Smith-Waterman (trouver une sous-chaîne approximative dans une chaîne plus longue). Ils travaillent très bien et sont des bourreaux de travail depuis des décennies.

Mais que faire si vous avez un million de chaînes à comparer? C’est une comparaison de mille milliards, chacune étant O (n * m)! Les séquenceurs d’ADN modernes génèrent facilement un milliard de courtes séquences d’ADN, chacune contenant environ 200 “lettres” d’ADN. En règle générale, nous voulons trouver, pour chacune de ces chaînes, la meilleure correspondance avec le génome humain (3 milliards de lettres). Clairement, l’algorithme Needleman-Wunsch et ses proches ne le feront pas.

Ce soi-disant “problème d’alignement” est un domaine de recherche actif. Les algorithmes les plus courants sont actuellement capables de trouver des correspondances inexactes entre 1 milliard de chaînes courtes et le génome humain en quelques heures sur du matériel raisonnable (par exemple, huit cœurs et 32 ​​Go de RAM).

La plupart de ces algorithmes fonctionnent en trouvant rapidement des correspondances exactes courtes (semences), puis en les étendant à la chaîne complète en utilisant un algorithme plus lent (par exemple, le Smith-Waterman). La raison pour laquelle cela fonctionne est que nous ne sums vraiment intéressés que par quelques matchs rapprochés, il est donc avantageux de se débarrasser des 99,9 …% de paires qui n’ont rien en commun.

Comment trouver des correspondances exactes aide-t-il à trouver des correspondances inexactes ? Eh bien, disons que nous n’autorisons qu’une seule différence entre la requête et la cible. Il est facile de voir que cette différence doit apparaître dans la moitié droite ou gauche de la requête et que l’autre moitié doit correspondre exactement. Cette idée peut être étendue à de multiples incompatibilités et constitue la base de l’algorithme ELAND couramment utilisé avec les séquenceurs d’ADN Illumina.

Il existe de nombreux très bons algorithmes pour effectuer une correspondance de chaîne exacte. Étant donné une chaîne de requête de longueur 200 et une chaîne cible de longueur 3 milliards (le génome humain), nous voulons trouver un endroit dans la cible où il existe une sous-chaîne de longueur k qui correspond exactement à une sous-chaîne de la requête. Une approche simple consiste à commencer par indexer la cible: prenez toutes les sous-chaînes longues, placez-les dans un tableau et sortingez-les. Ensuite, prenez chaque sous-chaîne k-long de la requête et recherchez l’index sortingé. Le sorting et la recherche peuvent être effectués en heure O (log n).

Mais le stockage peut être un problème. Un indice de la cible de 3 milliards de lettres devrait contenir 3 milliards de pointeurs et 3 milliards de mots de long. Il semblerait difficile de l’adapter à moins de plusieurs dizaines de gigaoctets de RAM. Mais étonnamment, nous pouvons fortement compresser l’index, en utilisant la transformation Burrows-Wheeler , et il sera toujours interrogeable efficacement. Un index du génome humain peut contenir moins de 4 Go de RAM. Cette idée est à la base des aligneurs de séquences populaires tels que Bowtie et BWA .

Alternativement, nous pouvons utiliser un tableau de suffixes , qui stocke uniquement les pointeurs, mais représente un index simultané de tous les suffixes de la chaîne cible (essentiellement, un index simultané pour toutes les valeurs possibles de k; il en est de même pour la transformation Burrows-Wheeler) ). Un index de tableau de suffixe du génome humain prendra 12 Go de RAM si nous utilisons des pointeurs de 32 bits.

Les liens ci-dessus contiennent une mine d’informations et des liens vers des documents de recherche primaires. Le lien ELAND va dans un PDF avec des figures utiles illustrant les concepts impliqués et montre comment gérer les insertions et les suppressions.

Enfin, alors que ces algorithmes ont fondamentalement résolu le problème du (re) séquençage de génomes humains uniques (un milliard de chaînes courtes), la technologie de séquençage de l’ADN s’améliore encore plus rapidement que la loi de Moore et nous approchons rapidement des ensembles de données. Par exemple, il y a actuellement des projets en cours pour séquencer les génomes de 10 000 espèces de vertébrés , chacune d’environ un milliard de lettres. Naturellement, nous allons vouloir faire une correspondance de chaîne inexacte par paires sur les données …

Je conteste ce choix B est plus proche de la chaîne de test, car il ne s’agit que de 4 caractères (et 2 suppressions) de la chaîne d’origine. Alors que vous voyez C plus proche car il comprend à la fois le marron et le rouge. Il aurait cependant une plus grande distance de assembly.

Il existe un algorithme appelé Levenshtein Distance qui mesure la distance de assembly entre deux entrées.

Voici un outil pour cet algorithme.

  1. Choix de tarifs A à une distance de 15.
  2. Choix du tarif B sur une distance de 6.
  3. Choix de tarif C sur une distance de 9.

EDIT: Désolé, je continue à mélanger des chaînes dans l’outil levenshtein. Mis à jour pour corriger les réponses.

Mise en œuvre de Lua, pour la postérité:

 function levenshtein_distance(str1, str2) local len1, len2 = #str1, #str2 local char1, char2, distance = {}, {}, {} str1:gsub('.', function (c) table.insert(char1, c) end) str2:gsub('.', function (c) table.insert(char2, c) end) for i = 0, len1 do distance[i] = {} end for i = 0, len1 do distance[i][0] = i end for i = 0, len2 do distance[0][i] = i end for i = 1, len1 do for j = 1, len2 do distance[i][j] = math.min( distance[i-1][j ] + 1, distance[i ][j-1] + 1, distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1) ) end end return distance[len1][len2] end 

Vous pourriez être intéressé par cet article de blog.

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-ssortingng-matching-in-python

Fuzzywuzzy est une bibliothèque Python qui fournit des mesures de distance faciles telles que la distance Levenshtein pour la correspondance de chaînes. Il est construit au-dessus de difflib dans la bibliothèque standard et utilisera l’implémentation C Python-levenshtein si disponible.

http://pypi.python.org/pypi/python-Levenshtein/

Vous pourriez trouver cette bibliothèque utile! http://code.google.com/p/google-diff-match-patch/

Il est actuellement disponible en Java, JavaScript, Dart, C ++, C #, Objective C, Lua et Python

Cela fonctionne très bien aussi. Je l’utilise dans quelques projets de Lua.

Et je ne pense pas qu’il serait trop difficile de le porter dans d’autres langues!

Si vous faites cela dans le contexte d’un moteur de recherche ou d’une interface avec une firebase database, vous pouvez envisager d’utiliser un outil tel qu’Apache Solr , avec le plug- in ComplexPhraseQueryParser . Cette combinaison vous permet de rechercher un index de chaînes avec les résultats sortingés par pertinence, comme déterminé par la distance Levenshtein.

Nous l’utilisons contre une grande collection d’artistes et de titres de chansons lorsque la requête entrante peut contenir une ou plusieurs fautes de frappe, et elle fonctionne plutôt bien (et remarquablement rapidement compte tenu des millions de chaînes).

De plus, avec Solr, vous pouvez effectuer une recherche sur l’index à la demande via JSON, afin de ne pas avoir à réinventer la solution entre les différentes langues que vous consultez.

Simmesortingcs est une très bonne ressource pour ce type d’algorithmes: http://sourceforge.net/projects/simmesortingcs/

Malheureusement, le site Web génial contenant une grande partie de la documentation a disparu 🙁 Au cas où il reviendrait, son adresse précédente était la suivante: http://www.dcs.shef.ac.uk/~sam/simmesortingcs.html

Voila (avec la permission de “Wayback Machine”): http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmesortingcs.html

Vous pouvez étudier le code source, il existe des dizaines d’algorithmes pour ces types de comparaisons, chacun avec un compromis différent. Les implémentations sont en Java.

Pour interroger efficacement un grand ensemble de textes, vous pouvez utiliser le concept de modifier la distance d’édition / de préfixe.

Editer la distance ED (x, y): nombre minimal de transfroms pour passer du terme x au terme y

Mais calculer ED entre chaque terme et le texte de la requête demande beaucoup de temps et de ressources. Par conséquent, au lieu de calculer ED pour chaque terme, nous pouvons d’abord extraire des termes de correspondance possibles en utilisant une technique appelée Qgram Index. puis appliquer le calcul ED sur les termes sélectionnés.

Un avantage de la technique d’indexation Qgram est qu’elle prend en charge la recherche floue.

Une approche possible pour adapter l’indice QGram consiste à créer un index inversé à l’aide de Qgram. Ici, nous stockons tous les mots qui contiennent un Qgram particulier, sous ce Qgram (au lieu de stocker une chaîne complète, vous pouvez utiliser un identifiant unique pour chaque chaîne). Vous pouvez utiliser la structure de données Tree Map en Java pour cela. Voici un petit exemple de stockage de termes

col: colbia, colombo, gan cola, ta cola

Ensuite, lors de l’interrogation, nous calculons le nombre de QGrams communs entre le texte de la requête et les termes disponibles.

 Example: x = HILLARY, y = HILARI(query term) Qgrams $$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$ $$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$ number of q-grams in common = 4 

nombre de q-grammes en commun = 4.

Pour les termes avec un nombre élevé de Qgram communs, nous calculons l’ED / PED par rapport au terme de la requête et suggérons ensuite le terme à l’utilisateur final.

Vous pouvez trouver une implémentation de cette théorie dans le projet suivant (voir “QGramIndex.java”). N’hésitez pas à poser des questions. https://github.com/Bhashitha-Gamage/City_Search

Pour en savoir plus sur la modification de l’index Qgram de modification de distance, préfixe, veuillez regarder la vidéo suivante du professeur Hannah Bast https://www.youtube.com/embed/6pUg2wmGJRo (la leçon commence à 20h06)

Le problème est difficile à implémenter si les données d’entrée sont trop grandes (par exemple, des millions de chaînes). J’ai utilisé la recherche élastique pour résoudre ce problème. Il suffit d’insérer toutes les données d’entrée dans la firebase database et vous pouvez rechercher n’importe quelle chaîne en fonction de toute distance de modification rapidement. Voici un extrait C # qui vous donnera une liste de résultats sortingés par distance d’édition (plus petit à plus haut)

 var res = client.Search(s => s .Query(q => q .Match(m => m .Field(f => f.VariableName) .Query("SAMPLE QUERY") .Fuzziness(Fuzziness.EditDistance(5)) ) ));