Ottenere la corrispondenza di stringa più vicina

Ho bisogno di un modo per confrontare più stringhe con una stringa di test e restituire la stringa che le assomiglia da vicino:

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 

(Se l’ho fatto correttamente) La stringa più vicina a “TEST STRING” dovrebbe essere “CHOICE C”. Qual è il modo più semplice per farlo?

Ho intenzione di implementarlo in più lingue tra cui VB.net, Lua e JavaScript. A questo punto, lo pseudo codice è accettabile. Se puoi fornire un esempio per una lingua specifica, anche questo è apprezzato!

Mi è stato presentato questo problema circa un anno fa, quando si trattava di cercare informazioni inserite dall’utente su una piattaforma petrolifera in un database di informazioni varie. L’objective era di fare una sorta di ricerca di stringa fuzzy che potesse identificare la voce del database con gli elementi più comuni.

Parte della ricerca riguardava l’implementazione dell’algoritmo di distanza Levenshtein , che determina il numero di modifiche che devono essere apportate a una stringa oa una frase per trasformarla in un’altra stringa o frase.

L’implementazione che mi è stata presentata era relativamente semplice e comportava un confronto ponderato della lunghezza delle due frasi, il numero di modifiche tra ogni frase e se ogni parola potesse essere trovata nella voce di destinazione.

L’articolo è su un sito privato, quindi farò del mio meglio per aggiungere il contenuto pertinente qui:


Fuzzy String Matching è il processo di esecuzione di una stima simile a quella umana della somiglianza di due parole o frasi. In molti casi, comporta l’identificazione di parole o frasi che sono più simili tra loro. Questo articolo descrive una soluzione interna al problema della corrispondenza delle stringhe fuzzy e la sua utilità nel risolvere una serie di problemi che possono consentirci di automatizzare attività che in precedenza richiedevano un noioso coinvolgimento dell’utente.

introduzione

La necessità di eseguire la convergenza delle stringhe fu originariamente sviluppata durante lo sviluppo dello strumento di convalida del Golfo del Messico. Ciò che esisteva era un database di piattaforms petrolifere e piattaforms petrolifere conosciute e le persone che acquistavano un’assicurazione ci davano alcune informazioni mal tipate sulle loro risorse e dovevamo abbinarle al database delle piattaforms conosciute. Quando ci sono state poche informazioni fornite, il meglio che possiamo fare è affidarsi a un sottoscrittore per “riconoscere” quello a cui si riferivano e richiamare le informazioni corrette. Questo è dove questa soluzione automatizzata è utile.

Ho trascorso una giornata alla ricerca di metodi di abbinamento di stringhe fuzzy e alla fine sono incappato nell’utilissimo algoritmo di distanza Levenshtein su Wikipedia.

Implementazione

Dopo aver letto la teoria alla base, ho implementato e trovato modi per ottimizzarlo. Ecco come appare il mio codice in 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 

Metrica semplice, rapida e molto utile. Usando questo, ho creato due metriche separate per valutare la similarità di due stringhe. Uno chiamo "valuePhrase" e uno che chiamo "valueWords". valuePhrase è solo la distanza di Levenshtein tra le due frasi e valueWords divide la stringa in singole parole, in base a delimitatori come spazi, trattini e qualsiasi altra cosa desideri e confronta ogni parola tra loro, sumndo il più breve La distanza di Levenshtein collega due parole qualsiasi. Essenzialmente, misura se l'informazione in una "frase" è realmente contenuta in un'altra, proprio come una permutazione word-wise. Ho trascorso alcuni giorni come un progetto parallelo in cui è venuto fuori il modo più efficiente di dividere una stringa in base ai delimitatori.

valueWords, valuePhrase e Split function:

 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 

Misure di similarità

Usando queste due metriche e una terza che calcola semplicemente la distanza tra due stringhe, ho una serie di variabili che posso eseguire un algoritmo di ottimizzazione per ottenere il maggior numero di corrispondenze. La combinazione di stringhe fuzzy è, a sua volta, una scienza confusa, e quindi creando metriche linearmente indipendenti per misurare la somiglianza delle stringhe e avendo un insieme noto di stringhe che desideriamo corrispondere tra loro, possiamo trovare i parametri che, per i nostri specifici stili di stringhe, danno i migliori risultati di una partita fuzzy.

Inizialmente, l'objective della metrica era avere un valore di ricerca basso per una corrispondenza esatta e aumentare i valori di ricerca per misure sempre più permutate. In un caso impraticabile, questo era abbastanza facile da definire usando un insieme di permutazioni ben definite, e ingegnerizzando la formula finale in modo tale da avere risultati di valori di ricerca crescenti come desiderato.

Permutazioni di stringa fuzzy

Nello screenshot qui sopra, ho ottimizzato la mia euristica per trovare qualcosa che mi sentivo adattato bene alla mia differenza percepita tra il termine di ricerca e il risultato. L'euristico che ho usato per la Value Phrase nel foglio di calcolo sopra era =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)) . Stavo effettivamente riducendo la penalità della distanza di Levenstein dell'80% della differenza nella lunghezza delle due "frasi". In questo modo, "frasi" che hanno la stessa lunghezza subiscono la penalità totale, ma "frasi" che contengono "informazioni aggiuntive" (più lunghe) ma a parte quelle che ancora condividono maggiormente gli stessi personaggi subiscono una penalità ridotta. Ho usato la funzione Value Words com'è, e quindi il mio euristico SearchVal finale è stato definito come =MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 - una media ponderata. Qualunque dei due punteggi era inferiore, l'80% era pesato e il 20% del punteggio più alto. Questo era solo un euristico adatto al mio caso d'uso per ottenere un buon tasso di corrispondenza. Questi pesi sono qualcosa che è ansible modificare per ottenere il miglior tasso di corrispondenza con i loro dati di test.

Frase di valore di corrispondenza stringa sfocata

Parole di valore di corrispondenza di stringa fuzzy

Come puoi vedere, le ultime due metriche, che sono metriche di corrispondenza delle stringhe sfocate, hanno già una naturale tendenza a dare punteggi bassi alle stringhe che devono corrispondere (lungo la diagonale). Questo va molto bene.

Applicazione Per consentire l'ottimizzazione della corrispondenza fuzzy, peso ciascuna metrica. In quanto tale, ogni applicazione della stringa di stringa fuzzy può pesare i parametri in modo diverso. La formula che definisce il punteggio finale è una semplice combinazione delle metriche e dei loro pesi:

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

Utilizzando un algoritmo di ottimizzazione (la rete neurale è la migliore qui perché è un problema discreto e multi-dimensionale), l'objective è ora di massimizzare il numero di corrispondenze. Ho creato una funzione che rileva il numero di corrispondenze corrette di ciascun set tra loro, come si può vedere in questo screenshot finale. Una colonna o una riga ottiene un punto se al punteggio più basso viene assegnata la stringa che doveva essere abbinata, e vengono assegnati punti parziali se c'è un pareggio per il punteggio più basso e la corrispondenza corretta è tra le stringhe abbinate legate. L'ho poi ottimizzato. Puoi vedere che una cella verde è la colonna che corrisponde meglio alla riga corrente e un quadrato blu attorno alla cella è la riga che meglio corrisponde alla colonna corrente. Il punteggio nell'angolo in basso corrisponde approssimativamente al numero di corrispondenze riuscite e questo è quello che diciamo al nostro problema di ottimizzazione per massimizzare.

Metrica ottimizzata per la corrispondenza a stringa fuzzy

L'algoritmo è stato un grande successo e i parametri della soluzione dicono molto su questo tipo di problema. Noterai che il punteggio ottimizzato era 44 e il miglior punteggio ansible è 48. Le 5 colonne alla fine sono di tipo decoy e non hanno alcuna corrispondenza con i valori delle righe. Più richiami ci sono, più difficile sarà naturalmente trovare la migliore corrispondenza.

In questo particolare caso di matching, la lunghezza delle stringhe è irrilevante, perché ci aspettiamo che le abbreviazioni rappresentino parole più lunghe, quindi il peso ottimale per la lunghezza è -0.3, il che significa che non penalizziamo le stringhe che variano in lunghezza. Riduciamo il punteggio in previsione di queste abbreviazioni, dando più spazio alle corrispondenze parziali delle parole per sostituire le corrispondenze senza parole che richiedono semplicemente meno sostituzioni perché la stringa è più corta.

Il peso della parola è 1.0 mentre il peso della frase è solo 0,5, il che significa che penalizziamo le parole intere mancanti da una stringa e valutiamo l'interezza dell'intera frase. Questo è utile perché molte di queste stringhe hanno una parola in comune (il pericolo) dove ciò che conta è se la combinazione (regione e pericolo) viene mantenuta o meno.

Infine, il peso minimo è ottimizzato a 10 e il peso massimo a 1. Ciò significa che se il migliore dei due punteggi (valore frase e parole valore) non è molto buono, la partita è fortemente penalizzata, ma noi don penalizzare molto il peggiore dei due punteggi. In sostanza, ciò pone l'enfasi sulla necessità che il valore Word o valuePhrase abbiano un buon punteggio, ma non entrambi. Una sorta di "prendere ciò che possiamo ottenere" mentalità.

È davvero affascinante il valore ottimizzato di questi 5 pesi a proposito del tipo di corrispondenza di stringa fuzzy in atto. Per casi pratici completamente diversi di combinazioni di stringa fuzzy, questi parametri sono molto diversi. L'ho usato per 3 applicazioni separate finora.

Quando non è stato utilizzato nell'ottimizzazione finale, è stato creato un foglio di benchmarking che confronta le colonne con se stessi per tutti i risultati perfetti lungo la diagonale e consente all'utente di modificare i parametri per controllare la frequenza con cui i punteggi divergono da 0 e notare le innate somiglianze tra le frasi di ricerca ( che in teoria potrebbe essere usato per compensare i falsi positivi nei risultati)

Benchmark Fuzzy String Matching

Ulteriori applicazioni

Questa soluzione ha il potenziale per essere utilizzata ovunque l'utente desideri che un sistema informatico identifichi una stringa in un insieme di stringhe in cui non esiste una corrispondenza perfetta. (Come una partita approssimativa vlookup per le stringhe).


Quindi, ciò che dovresti prendere da questo, è che probabilmente vorresti usare una combinazione di euristiche di alto livello (trovare parole da una frase nell'altra frase, lunghezza di entrambe le frasi, ecc.) Insieme all'implementazione dell'algoritmo di distanza di Levenshtein. Perché decidere quale sia la "migliore" corrispondenza è una determinazione euristica (fuzzy) - dovrai determinare una serie di pesi per qualsiasi metrica che emergerai per determinare la similarità.

Con l'insieme appropriato di euristica e pesi, avrai il tuo programma di confronto che prende rapidamente le decisioni che avresti preso.

Questo problema si presenta continuamente in bioinformatica. La risposta accettata sopra (che peraltro è stata fantastica) è conosciuta in bioinformatica come gli algoritmi Needleman-Wunsch (confrontare due stringhe) e Smith-Waterman (trovare una sottostringa approssimativa in una stringa più lunga). Funzionano alla grande e sono stati cavalli da lavoro per decenni.

Ma cosa succede se hai un milione di stringhe da confrontare? Questo è un trilione di confronti a coppie, ognuno dei quali è O (n * m)! I moderni sequenziatori di DNA generano facilmente un miliardo di sequenze di DNA corte, ciascuna di circa 200 “lettere” di DNA. In genere, vogliamo trovare, per ciascuna di queste corde, la migliore corrispondenza con il genoma umano (3 miliardi di lettere). Chiaramente, l’algoritmo di Needleman-Wunsch e i suoi parenti non lo faranno.

Questo cosiddetto “problema di allineamento” è un campo di ricerca triggers. Gli algoritmi più popolari sono attualmente in grado di trovare corrispondenze inesatte tra 1 miliardo di stringhe corte e il genoma umano in poche ore su hardware ragionevole (ad esempio, otto core e 32 GB di RAM).

La maggior parte di questi algoritmi funziona individuando rapidamente corrispondenze esatte (semi) e quindi estendendoli all’intera stringa utilizzando un algoritmo più lento (ad esempio, Smith-Waterman). Il motivo per cui questo funziona è che ci interessano solo poche partite ravvicinate, quindi vale la pena di sbarazzarsi del 99,9% delle coppie che non hanno nulla in comune.

In che modo trovare corrispondenze esatte aiuta a trovare corrispondenze inesatte ? Bene, diciamo che permettiamo solo una singola differenza tra la query e il target. È facile vedere che questa differenza deve verificarsi nella metà destra o nella parte sinistra della query, quindi l’altra metà deve corrispondere esattamente. Questa idea può essere estesa a più disallineamenti ed è la base per l’algoritmo ELAND comunemente usato con i sequenziatori di DNA Illumina.

Esistono molti algoritmi molto validi per eseguire la corrispondenza esatta delle stringhe. Data una stringa di query di lunghezza 200 e una stringa di destinazione di lunghezza 3 miliardi (il genoma umano), vogliamo trovare qualsiasi posizione nella destinazione in cui esiste una sottostringa di lunghezza k che corrisponde esattamente a una sottostringa della query. Un semplice approccio consiste nell’indicizzare il target: prendi tutte le sottostringhe k-long, inseriscile in un array e ordinale. Quindi prendi ogni sottostringa k-long della query e cerca l’indice ordinato. L’ordinamento e la ricerca possono essere eseguiti in tempo O (log n).

Ma lo storage può essere un problema. Un indice del target da 3 miliardi di lettere dovrebbe contenere 3 miliardi di puntatori e 3 miliardi di parole k-long. Sembrerebbe difficile adattarsi a questo in meno di diverse decine di gigabyte di RAM. Ma sorprendentemente possiamo notevolmente comprimere l’indice, usando la trasformazione di Burrows-Wheeler , e sarà ancora interrogabile in modo efficiente. Un indice del genoma umano può adattarsi a meno di 4 GB di RAM. Questa idea è alla base di allineatori di sequenze popolari come Bowtie e BWA .

In alternativa, possiamo usare un suffisso array , che memorizza solo i puntatori, ma rappresenta un indice simultaneo di tutti i suffissi nella stringa di destinazione (in sostanza, un indice simultaneo per tutti i possibili valori di k, lo stesso vale per la trasformazione di Burrows-Wheeler ). Un indice di array suffisso del genoma umano richiederà 12 GB di RAM se utilizziamo puntatori a 32 bit.

I link qui sopra contengono una grande quantità di informazioni e collegamenti a documenti di ricerca primari. Il collegamento ELAND passa a un PDF con figure utili che illustrano i concetti coinvolti e mostra come gestire inserimenti e cancellazioni.

Infine, mentre questi algoritmi hanno sostanzialmente risolto il problema del (ri) sequenziamento di singoli genomi umani (un miliardo di stringhe corte), la tecnologia di sequenziamento del DNA migliora ancora più velocemente della legge di Moore e stiamo rapidamente avvicinandoci a dataset da trilioni di lettere. Per esempio, ci sono attualmente progetti in corso per sequenziare i genomi di 10.000 specie di vertebrati , ciascuna lunga un miliardo di lettere o giù di lì. Ovviamente, vorremmo eseguire una corrispondenza delle stringhe inesatta a coppie sui dati …

Concordo sul fatto che la scelta B sia più vicina alla stringa di test, dato che sono solo 4 caratteri (e 2 eliminazioni) dall’essere la stringa originale. Mentre vedi C più vicino perché include sia il marrone che il rosso. Tuttavia, avrebbe una maggiore distanza di modifica.

Esiste un algoritmo chiamato Levenshtein Distance che misura la distanza di modifica tra due input.

Ecco uno strumento per tale algoritmo.

  1. Scelta delle tariffe A a una distanza di 15.
  2. La scelta delle tariffe B è una distanza di 6.
  3. La scelta delle tariffe C è una distanza di 9.

EDIT: Scusa, continuo a mescolare le stringhe nello strumento levenshtein. Aggiornato per correggere le risposte.

Implementazione Lua, per i posteri:

 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 

Potresti essere interessato a questo post sul blog.

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

Fuzzywuzzy è una libreria Python che fornisce misure a distanza facile come la distanza di Levenshtein per la corrispondenza delle stringhe. È costruito su difflib nella libreria standard e utilizzerà l’implementazione C Python-levenshtein se disponibile.

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

Potresti trovare utile questa libreria! http://code.google.com/p/google-diff-match-patch/

È attualmente disponibile in Java, JavaScript, Dart, C ++, C #, Objective C, Lua e Python

Funziona abbastanza bene anche. Lo uso in un paio dei miei progetti Lua.

E non penso sarebbe troppo difficile portarlo in altre lingue!

Se stai facendo questo nel contesto di un motore di ricerca o di un frontend contro un database, potresti prendere in considerazione l’utilizzo di uno strumento come Apache Solr , con il plugin ComplexPhraseQueryParser . Questa combinazione ti permette di cercare un indice di stringhe con i risultati ordinati per rilevanza, come determinato dalla distanza di Levenshtein.

Lo abbiamo usato contro una vasta collezione di artisti e titoli di canzoni quando la query in entrata può avere uno o più refusi e ha funzionato abbastanza bene (e incredibilmente veloce considerando che le raccolte sono in milioni di stringhe).

Inoltre, con Solr, puoi cercare l’indice su richiesta tramite JSON, quindi non dovrai reinventare la soluzione tra le diverse lingue che stai guardando.

Una risorsa molto, molto buona per questi tipi di algoritmi è Simmetrics: http://sourceforge.net/projects/simmetrics/

Sfortunatamente il fantastico sito web che contiene molta della documentazione è andato 🙁 Nel caso in cui ritorni di nuovo, il suo indirizzo precedente era questo: http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Voila (per gentile concessione di “Wayback Machine”): http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Puoi studiare la sorgente del codice, ci sono dozzine di algoritmi per questi tipi di confronti, ognuno con un diverso compromesso. Le implementazioni sono in Java.

Per interrogare un ampio set di testo in modo efficiente è ansible utilizzare il concetto di Modifica distanza / prefisso Modifica distanza.

Modifica distanza ED (x, y): numero minimo di transfrom per passare dal termine x al termine y

Ma calcolare l’ED tra ogni termine e il testo di una query richiede risorse e tempo. Pertanto, invece di calcolare prima l’ED per ciascun termine, possiamo estrarre possibili termini di corrispondenza usando una tecnica chiamata Qgram Index. e quindi applicare il calcolo ED su quei termini selezionati.

Un vantaggio della tecnica dell’indice Qgram è il supporto per Fuzzy Search.

Un ansible approccio per adattare l’indice QGram è build un indice invertito usando Qgrams. Qui memorizziamo tutte le parole che sono costituite da un particolare Qgram, sotto quel Qgram (invece di memorizzare una stringa completa, puoi usare un ID univoco per ogni stringa). È ansible utilizzare la struttura dei dati della struttura ad albero in Java per questo. Di seguito è riportato un piccolo esempio sulla memorizzazione dei termini

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

Quindi, quando si esegue una query, viene calcolato il numero di Qgram comuni tra il testo della query e i termini disponibili.

 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 

numero di q-gram in comune = 4.

Per i termini con alto numero di Qgram comuni, calcoliamo l’ED / PED rispetto al termine di ricerca e quindi suggeriamo il termine all’utente finale.

puoi trovare un’implementazione di questa teoria nel seguente progetto (vedi “QGramIndex.java”). Sentiti libero di fare qualsiasi domanda. https://github.com/Bhashitha-Gamage/City_Search

Per ulteriori informazioni su Modifica distanza, indice Preg. Modifica distanza Qgram, guarda il seguente video del Prof. Dr Hannah Bast https://www.youtube.com/embed/6pUg2wmGJRo (Lezione inizia dalle 20:06)

Il problema è difficile da implementare se i dati di input sono troppo grandi (ad esempio milioni di stringhe). Ho usato la ricerca elastica per risolvere questo. Basta inserire tutti i dati di input in DB ed è ansible cercare rapidamente qualsiasi stringa basata su qualsiasi distanza di modifica. Ecco uno snippet C # che ti fornirà un elenco di risultati ordinati per distanza di modifica (da minore a maggiore)

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