Obtenir la correspondance de chaîne la plus proche

J'ai besoin d'un moyen de comparer plusieurs chaînes à une chaîne de test et de retourner la chaîne qui lui ressemble étroitement:

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 de la "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, notamment 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é!

Il y a environ un an, ce problème m'a été présenté lors de la recherche d'informations saisies par l'utilisateur sur une plate-forme pétrolière dans une base de données d'informations diverses. Le but était de faire une sorte de recherche de chaîne floue qui pourrait identifier l'entrée de base de données avec les éléments les plus courants.

Une partie de la recherche a consisté à implémenter l' algorithme de distance de Levenshtein , qui détermine le nombre de modifications à apporter à une chaîne ou une phrase pour la transformer en une autre chaîne ou phrase.

L'implémentation que j'ai trouvé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 si chaque mot pouvait être trouvé dans l'entrée cible.

L'article est sur un site privé, je ferai de mon mieux pour ajouter le contenu pertinent ici:

L'appariement de chaînes floues est le processus consistant à effectuer une estimation de type humain de la similitude de deux mots ou expressions. Dans de nombreux cas, il s'agit d'identifier des mots ou des phrases qui se ressemblent le plus. Cet article décrit une solution interne au problème de correspondance de chaînes floues et son utilité pour résoudre une variété de problèmes qui peuvent nous permettre d'automatiser des tâches qui nécessitaient auparavant une implication fastidieuse des utilisateurs.

introduction

La nécessité de faire une correspondance de chaîne floue est apparue à l'origine lors du développement de l'outil de validation du golfe du Mexique. Ce qui existait était une base de données des plates-formes et plates-formes pétrolières connues du golfe du Mexique, et les personnes achetant une assurance nous fourniraient des informations mal tapées sur leurs actifs et nous devions les faire correspondre à la base de données des plates-formes connues. Lorsqu'il y avait très peu d'informations fournies, le mieux que nous puissions faire était de compter sur un souscripteur pour «reconnaître» celle à laquelle il faisait référence 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 de Levenshtein très utile sur Wikipédia.

la mise en oeuvre

Après avoir lu la théorie sous-jacente, j'ai implémenté et trouvé des moyens de l'optimiser. Voici à quoi ressemble mon code dans VBA:

'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef S1 As String, ByVal S2 As String) As Long
    Dim L1 As Long, L2 As Long, D() As Long 'Length of input strings and distance matrix
    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

Métrique simple, rapide et très utile. À l'aide de cela, j'ai créé deux mesures distinctes pour évaluer la similitude de deux chaînes. Un que j'appelle "valuePhrase" et un que j'appelle "valueWords". valuePhrase est juste la distance de Levenshtein entre les deux phrases, et valueWords divise la chaîne en mots individuels, en fonction de délimiteurs tels que les espaces, les tirets et tout ce que vous souhaitez, et compare chaque mot à l'autre, résumant le plus court Distance Levenshtein reliant deux mots quelconques. Essentiellement, il mesure si l'information dans une «phrase» est vraiment contenue dans une autre, tout comme une permutation mot à mot. J'ai passé quelques jours en tant que projet parallèle à trouver le moyen le plus efficace possible de fractionner une chaîne en fonction des délimiteurs.

Fonction valueWords, valuePhrase et 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 string 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 similitude

En utilisant ces deux métriques, 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 un algorithme d'optimisation pour obtenir le plus grand nombre de correspondances. L'appariement de chaînes floues est, en soi, une science floue, et donc en créant des métriques linéairement indépendantes pour mesurer la similitude des chaînes, et en ayant un ensemble connu de chaînes que nous souhaitons faire correspondre, nous pouvons trouver les paramètres qui, pour nos styles spécifiques de chaînes, donnent les meilleurs résultats de correspondance floue.

Initialement, l'objectif de la métrique é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, cela était assez facile à définir en utilisant un ensemble de permutations bien définies et en concevant la formule finale de manière à ce que les résultats de recherche augmentent comme souhaité.

Dans la capture d'écran ci-dessus, j'ai modifié mon heuristique pour arriver à quelque chose qui me semblait bien adapté à ma différence perçue entre le terme de recherche et le résultat. L'heuristique que j'ai utilisée Value Phrasedans 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 des 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 à part cela partagent toujours la plupart des mêmes personnages subissent une pénalité réduite. J'ai utilisé la Value Wordsfonction telle quelle, puis mon SearchValheuristique finale a été définie comme=MIN(D2,E2)*0.8+MAX(D2,E2)*0.2- une moyenne pondérée. Le plus faible des deux scores a obtenu une pondération de 80% et 20% du score le plus élevé. 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 ensuite modifier pour obtenir le meilleur taux de correspondance avec leurs données de test.

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

Application Pour permettre l'optimisation de la correspondance floue, je pondère chaque métrique. Ainsi, chaque application de correspondance de chaîne floue peut pondérer les paramètres différemment. La formule qui définit le score final est une simple combinaison des métriques et de leurs poids:

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

En utilisant un algorithme d'optimisation (le réseau de neurones est préférable ici car il s'agit d'un problème discret et multidimensionnel), l'objectif 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 dans cette capture d'écran finale. Une colonne ou une ligne obtient un point si le score le plus bas est affecté à la chaîne qui devait être mise en correspondance, et des points partiels sont donnés s'il y a une égalité pour le score le plus bas, et la correspondance correcte est parmi les chaînes correspondantes liées. Je l'ai ensuite optimisé. Vous pouvez voir qu'une cellule verte est la colonne qui correspond le mieux à la ligne actuelle, et un carré bleu autour de la cellule est la ligne qui correspond le mieux à la colonne actuelle. Le score dans le coin inférieur est à peu près le nombre de matchs réussis et c'est ce que nous disons à notre problème d'optimisation de maximiser.

L'algorithme a été un formidable succès et les paramètres de la solution en disent long sur ce type de problème. Vous remarquerez que le score optimisé était de 44 et que 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 naturellement difficile de trouver le meilleur match.

Dans ce cas de correspondance particulier, la longueur des chaînes n'est pas pertinente, car nous attendons des abréviations qui représentent des mots plus longs, donc le poids optimal pour la longueur est de -0,3, ce qui signifie que nous ne pénalisons pas les chaînes dont la longueur varie. Nous réduisons le score en prévision de ces abréviations, ce qui donne plus de place aux correspondances partielles de mots pour remplacer les correspondances non verbales 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 n'est que de 0,5, ce qui signifie que nous pénalisons les mots entiers manquants dans une chaîne et valorisons davantage la phrase entière étant intacte. Ceci est utile car beaucoup de ces chaînes ont un mot en commun (le péril) où ce qui importe 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 maximum à 1. Ce que cela signifie, c'est que si le meilleur des deux scores (expression de valeur et mots de valeur) n'est pas très bon, le match est fortement pénalisé, mais nous ne 't pénaliser considérablement le pire des deux scores. Essentiellement, cela met l'accent sur l'exigence soit le valueWord ou valuePhrase pour avoir un bon score, mais pas les deux. Une sorte de mentalité de «prendre ce que nous pouvons obtenir».

C'est vraiment fascinant ce que la valeur optimisée de ces 5 poids dit sur le type de correspondance de chaîne floue qui a lieu. Pour des cas pratiques complètement différents de correspondance de chaînes floues, ces paramètres sont très différents. Je l'ai utilisé jusqu'à présent pour 3 applications distinctes.

Bien qu'elle ne soit pas utilisée dans l'optimisation finale, une feuille d'analyse comparative a été établie qui associe les colonnes à elles-mêmes pour tous les résultats parfaits dans la diagonale, et permet à l'utilisateur de modifier les paramètres pour contrôler la vitesse à laquelle les scores divergent de 0 et noter les similitudes innées entre les expressions de recherche ( qui pourrait en théorie être utilisé pour compenser les faux positifs dans les résultats)

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 où il n'y a pas de correspondance parfaite. (Comme une correspondance approximative avec vlookup pour les chaînes).

Donc, ce que vous devriez en déduire, c'est que vous voulez probablement utiliser une combinaison d'heuristiques de haut niveau (trouver des mots d'une phrase dans l'autre phrase, la longueur des deux phrases, etc.) avec la mise en œuvre 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 pondérations pour toutes les mesures que vous proposez pour déterminer la similitude.

Avec l'ensemble d'heuristique et de pondération approprié, votre programme de comparaison prendra rapidement les décisions que vous auriez prises.

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

Mais que faire si vous avez un million de chaînes à comparer? C'est un billion de comparaisons par paire, dont chacune est O (n * m)! Les séquenceurs d'ADN modernes génèrent facilement un milliard courtes séquences d'ADN, chacune d'environ 200 "lettres" d'ADN. Typiquement, nous voulons trouver, pour chacune de ces chaînes, la meilleure correspondance avec le génome humain (3 milliards de lettres). De toute évidence, l'algorithme Needleman-Wunsch et ses proches ne le feront pas.

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

La plupart de ces algorithmes fonctionnent en trouvant rapidement des correspondances exactes courtes (graines) puis en les étendant à la chaîne complète à l'aide d'un algorithme plus lent (par exemple, Smith-Waterman). La raison pour laquelle cela fonctionne est que nous ne sommes vraiment intéressés que par quelques matchs serrés, donc cela vaut la peine de se débarrasser des 99,9 ...% de paires qui n'ont rien en commun.

Comment la recherche de correspondances exactes aide-t-elle à trouver des correspondances inexactes ? 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 se produire dans la moitié droite ou gauche de la requête et que l'autre moitié doit donc correspondre exactement. Cette idée peut être étendue à plusieurs asymétries 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 exacte des chaînes. É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 tout endroit dans la cible où il y a 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: prendre toutes les sous-chaînes de longueur k, les placer dans un tableau et les trier. Prenez ensuite chaque sous-chaîne k de la requête et recherchez l'index trié. Le tri et la recherche peuvent être effectués en temps O (log n).

Mais le stockage peut être un problème. Un indice de l'objectif de 3 milliards de lettres devrait contenir 3 milliards de pointeurs et 3 milliards de mots de long. Il semblerait difficile d'intégrer cela dans moins de plusieurs dizaines de gigaoctets de RAM. Mais étonnamment, nous pouvons compresser considérablement l'index, en utilisant la transformation Burrows-Wheeler , et il sera toujours efficacement interrogable. Un index du génome humain peut tenir dans 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 dans la chaîne cible (essentiellement, un index simultané pour toutes les valeurs possibles de k; il en va de même pour la transformation Burrows-Wheeler ). Un index de suffixe du génome humain prendra 12 Go de RAM si nous utilisons des pointeurs 32 bits.

Les liens ci-dessus contiennent une mine d'informations et des liens vers des articles de recherche principaux. Le lien ELAND permet d'accéder à un PDF contenant des figures utiles illustrant les concepts impliqués et montre comment gérer les insertions et les suppressions.

Enfin, alors que ces algorithmes ont 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 d'ensembles de données de plusieurs milliards de lettres. Par exemple, des projets sont actuellement en cours pour séquencer les génomes de 10 000 espèces de vertébrés , chacune d'un milliard de lettres environ. Naturellement, nous voudrons faire une correspondance de chaîne inexacte par paire sur les données ...

Je conteste que le choix B soit 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 près, car il comprend à la fois le brun et le rouge. Il aurait cependant une plus grande distance d'édition.

Il existe un algorithme appelé Levenshtein Distance qui mesure la distance d'édition entre deux entrées.

Voici un outil pour cet algorithme.

1. Choix des tarifs A à une distance de 15.
2. Tarifs choix B à une distance de 6.
3. Tarifs choix C à une distance de 9.

EDIT: Désolé, je continue à mélanger les cordes dans l'outil levenshtein. Mis à jour pour corriger les réponses.

Implémentation 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-string-matching-in-python

Fuzzywuzzy est une bibliothèque Python qui fournit des mesures de distance faciles telles que la distance de Levenshtein pour l'appariement 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 assez bien aussi. Je l'utilise dans quelques-uns de mes projets 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 base de données, vous pourriez envisager d'utiliser un outil comme Apache Solr , avec le plugin ComplexPhraseQueryParser . Cette combinaison vous permet de rechercher un index de chaînes avec les résultats triés par pertinence, comme déterminé par la distance de Levenshtein.

Nous l'avons utilisé contre une grande collection d'artistes et de titres de chansons lorsque la requête entrante peut avoir une ou plusieurs fautes de frappe, et cela fonctionne assez bien (et remarquablement rapide étant donné que les collections sont dans les millions de chaînes).

De plus, avec Solr, vous pouvez effectuer une recherche par rapport à l'index à la demande via JSON, vous n'aurez donc pas à réinventer la solution entre les différentes langues que vous regardez.

Une très, très bonne ressource pour ces types d'algorithmes est Simmetrics: http://sourceforge.net/projects/simmetrics/

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/simmetrics.html

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

Vous pouvez étudier la source du code, 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 texte, vous pouvez utiliser le concept Modifier la distance / Préfixe Modifier la distance.

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

Mais le calcul de l'ED entre chaque terme et le texte de la requête demande beaucoup de ressources et de temps. Par conséquent, au lieu de calculer ED pour chaque terme, nous pouvons d'abord extraire les termes correspondants possibles en utilisant une technique appelée Qgram Index. puis appliquer le calcul ED sur ces 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'index QGram consiste à créer un index inversé à l'aide de Qgrams. Là, nous stockons tous les mots qui se composent d'un Qgram particulier, sous ce Qgram (au lieu de stocker la chaîne complète, vous pouvez utiliser un ID unique pour chaque chaîne). Pour cela, vous pouvez utiliser la structure de données Tree Map en Java. Voici un petit exemple sur le stockage des termes

col: col mbia, col ombo, gan col a, ta col ama

Ensuite, lors de la requête, nous calculons le nombre de Qgrammes 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 Qgrammes communs, nous calculons l'ED / PED par rapport au terme de requête, puis suggérons 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 la distance, l'index Qgram de la modification de la distance, veuillez regarder la vidéo suivante du professeur Hannah Bast https://www.youtube.com/embed/6pUg2wmGJRo (la leçon commence à partir de 20:06)

Le problème est difficile à mettre en œuvre si les données d'entrée sont trop volumineuses (disons des millions de chaînes). J'ai utilisé la recherche élastique pour résoudre ce problème.

Démarrage rapide: https://www.elastic.co/guide/en/elasticsearch/client/net-api/6.x/elasticsearch-net.html

Insérez simplement toutes les données d'entrée dans la base de données et vous pouvez rechercher rapidement n'importe quelle chaîne basée sur n'importe quelle distance d'édition. Voici un extrait C # qui vous donnera une liste de résultats triés par distance de modification (du plus petit au plus élevé)

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

Ici, vous pouvez avoir un golang POC pour calculer les distances entre les mots donnés. Vous pouvez régler le minDistanceet differencepour d'autres étendues.

Aire de jeux: https://play.golang.org/p/NtrBzLdC3rE

package main

import (
    "errors"
    "fmt"
    "log"
    "math"
    "strings"
)

var data string = `THE RED COW JUMPED OVER THE GREEN CHICKEN-THE RED COW JUMPED OVER THE RED COW-THE RED FOX JUMPED OVER THE BROWN COW`

const minDistance float64 = 2
const difference float64 = 1

type word struct {
    data    string
    letters map[rune]int
}

type words struct {
    words []word
}

// Print prettify the data present in word
func (w word) Print() {
    var (
        lenght int
        c      int
        i      int
        key    rune
    )
    fmt.Printf("Data: %s\n", w.data)
    lenght = len(w.letters) - 1
    c = 0
    for key, i = range w.letters {
        fmt.Printf("%s:%d", string(key), i)
        if c != lenght {
            fmt.Printf(" | ")
        }
        c++
    }
    fmt.Printf("\n")
}

func (ws words) fuzzySearch(data string) ([]word, error) {
    var (
        w      word
        err    error
        founds []word
    )
    w, err = initWord(data)
    if err != nil {
        log.Printf("Errors: %s\n", err.Error())
        return nil, err
    }
    // Iterating all the words
    for i := range ws.words {
        letters := ws.words[i].letters
        //
        var similar float64 = 0
        // Iterating the letters of the input data
        for key := range w.letters {
            if val, ok := letters[key]; ok {
                if math.Abs(float64(val-w.letters[key])) <= minDistance {
                    similar += float64(val)
                }
            }
        }

        lenSimilarity := math.Abs(similar - float64(len(data)-strings.Count(data, " ")))
        log.Printf("Comparing %s with %s i've found %f similar letter, with weight %f", data, ws.words[i].data, similar, lenSimilarity)
        if lenSimilarity <= difference {
            founds = append(founds, ws.words[i])
        }
    }

    if len(founds) == 0 {
        return nil, errors.New("no similar found for data: " + data)
    }

    return founds, nil
}

func initWords(data []string) []word {
    var (
        err   error
        words []word
        word  word
    )
    for i := range data {
        word, err = initWord(data[i])
        if err != nil {
            log.Printf("Error in index [%d] for data: %s", i, data[i])
        } else {
            words = append(words, word)
        }
    }
    return words

}

func initWord(data string) (word, error) {
    var word word

    word.data = data
    word.letters = make(map[rune]int)
    for _, r := range data {
        if r != 32 { // avoid to save the whitespace
            word.letters[r]++
        }

    }
    return word, nil
}
func main() {
    var ws words
    words := initWords(strings.Split(data, "-"))
    for i := range words {
        words[i].Print()
    }
    ws.words = words

    solution, _ := ws.fuzzySearch("THE BROWN FOX JUMPED OVER THE RED COW")
    fmt.Println("Possible solutions: ", solution)

}