Obteniendo el juego de cuerdas más cercano

Necesito una forma de comparar cadenas múltiples con una cadena de prueba y devolver la cadena que se parece mucho a ella:

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 lo hice correctamente) La secuencia más cercana a “STRING STRING” debería ser “CHOICE C”. ¿Cuál es la forma más fácil de hacer esto?

Planeo implementar esto en varios idiomas, incluidos VB.net, Lua y JavaScript. En este punto, el pseudo código es aceptable. Si puede proporcionar un ejemplo para un idioma específico, ¡esto también se agradece!

Me presentaron este problema hace aproximadamente un año cuando se trataba de buscar información ingresada por el usuario sobre una plataforma petrolera en una base de datos de información miscelánea. El objective era hacer algún tipo de búsqueda de cadenas difusas que pudiera identificar la entrada de la base de datos con los elementos más comunes.

Parte de la investigación implicó la implementación del algoritmo de distancia Levenshtein , que determina cuántos cambios se deben realizar en una cadena o frase para convertirla en otra cadena o frase.

La implementación que se me ocurrió fue relativamente simple e implicó una comparación ponderada de la longitud de las dos frases, el número de cambios entre cada frase y si cada palabra se podía encontrar en la entrada de destino.

El artículo está en un sitio privado, así que haré todo lo posible para agregar los contenidos relevantes aquí:


Fuzzy String Matching es el proceso de realizar una estimación similar a la humana de la similitud de dos palabras o frases. En muchos casos, implica identificar palabras o frases que son más similares entre sí. Este artículo describe una solución interna para el problema de coincidencia de cadenas difusas y su utilidad para resolver una variedad de problemas que pueden permitirnos automatizar tareas que antes requerían una tediosa participación del usuario.

Introducción

La necesidad de hacer coincidencias de cadenas difusas surgió originalmente al desarrollar la herramienta Validator del Golfo de México. Lo que existía era una base de datos de plataformas petrolíferas conocidas del Golfo de México, y las personas que compraban seguro nos daban información mal escrita sobre sus activos y teníamos que asociarla a la base de datos de plataformas conocidas. Cuando se proporcionó muy poca información, lo mejor que podíamos hacer era confiar en un suscriptor para que “reconociera” al que se estaba refiriendo y llamara a la información adecuada. Aquí es donde esta solución automatizada es útil.

Pasé un día investigando métodos de combinación de cuerdas difusas, y finalmente tropecé con el muy útil algoritmo de distancia de Levenshtein en Wikipedia.

Implementación

Después de leer acerca de la teoría detrás de esto, implementé y encontré formas de optimizarlo. Así es como se ve mi código en 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 

Simple, rápida y una métrica muy útil. Al usar esto, creé dos métricas separadas para evaluar la similitud de dos cadenas. Uno que llamo "valuePhrase" y otro que llamo "valueWords". valuePhrase es solo la distancia de Levenshtein entre las dos frases, y valueWords divide la cadena en palabras individuales, basadas en delimitadores como espacios, guiones y cualquier otra cosa que desee, y compara cada palabra con cada otra palabra, resumiendo el más corto Levenshtein distancia conectando dos palabras. Esencialmente, mide si la información en una "frase" está realmente contenida en otra, al igual que una permutación de palabra en cuanto. Pasé unos días como un proyecto paralelo que surgió con la forma más eficiente posible de dividir una cadena basada en delimitadores.

valueWords, valuePhrase y 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 

Medidas de similitud

Usando estas dos métricas, y una tercera que simplemente calcula la distancia entre dos cadenas, tengo una serie de variables que puedo ejecutar un algoritmo de optimización para lograr la mayor cantidad de coincidencias. La coincidencia difusa de cadenas es, en sí misma, una ciencia difusa, por lo que al crear métricas linealmente independientes para medir la similitud de cadenas y tener un conjunto conocido de cadenas que deseamos unir entre sí, podemos encontrar los parámetros que, para nuestros estilos específicos de cadenas, da los mejores resultados de coincidencias difusas.

Inicialmente, el objective de la métrica era tener un valor de búsqueda bajo para una coincidencia exacta y boost los valores de búsqueda para medidas cada vez más permutadas. En un caso poco práctico, esto fue bastante fácil de definir utilizando un conjunto de permutaciones bien definidas, e ingeniería de la fórmula final de modo que tuvieran resultados de valores de búsqueda crecientes como se deseaba.

Fuzzy String Matching Permutations

En la captura de pantalla anterior, modifiqué mi heurística para llegar a algo que me pareció mejor para mi diferencia percibida entre el término de búsqueda y el resultado. La heurística que utilicé para la Value Phrase en la hoja de cálculo anterior fue =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)) . Estaba efectivamente reduciendo la penalización de la distancia de Levenstein en un 80% de la diferencia en la longitud de las dos "frases". De esta forma, las "frases" que tienen la misma duración sufren la penalización completa, pero las "frases" que contienen "información adicional" (más larga) pero aparte de las que aún comparten en su mayoría los mismos personajes sufren una penalización reducida. Utilicé la función Value Words los Value Words como está, y luego mi heurística SearchVal final se definió como =MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 - un promedio ponderado. Cualquiera de los dos puntajes fue menor, se ponderaron 80% y 20% del puntaje más alto. Esto fue solo una heurística que se ajustaba a mi caso de uso para obtener una buena tasa de coincidencia. Estos pesos son algo que uno podría ajustar para obtener la mejor tasa de coincidencia con sus datos de prueba.

Fuzzy String Matching Value Phrase

Fuzzy String Matching Value Words

Como puede ver, las dos últimas métricas, que son métricas de coincidencia de cadenas difusas, ya tienen una tendencia natural a dar puntajes bajos a las cadenas que están destinadas a coincidir (en la diagonal). Esto es muy bueno.

Aplicación Para permitir la optimización de la coincidencia difusa, peso cada métrica. Como tal, cada aplicación de coincidencia de cuerdas difusas puede ponderar los parámetros de manera diferente. La fórmula que define el puntaje final es una combinación simple de las métricas y sus ponderaciones:

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

Usando un algoritmo de optimización (la neural network es la mejor aquí porque es un problema discreto y multidimensional), el objective ahora es maximizar el número de coincidencias. Creé una función que detecta el número de coincidencias correctas de cada conjunto, como se puede ver en esta captura de pantalla final. Una columna o fila recibe un punto si se asigna la puntuación más baja a la cadena que debía corresponderse, y se otorgan puntos parciales si hay un empate para la puntuación más baja, y la coincidencia correcta se encuentra entre las cadenas emparejadas vinculadas. Luego lo optimicé. Puede ver que una celda verde es la columna que mejor coincide con la fila actual, y un cuadrado azul alrededor de la celda es la fila que mejor coincide con la columna actual. El puntaje en la esquina inferior es aproximadamente el número de coincidencias exitosas y esto es lo que le decimos a nuestro problema de optimización para maximizar.

Fuzzy String Matching Optimized Metric

El algoritmo fue un éxito maravilloso, y los parámetros de la solución dicen mucho sobre este tipo de problema. Notarás que el puntaje optimizado fue 44 y el mejor puntaje posible es 48. Las 5 columnas al final son señuelos y no tienen ninguna coincidencia con los valores de las filas. Cuantos más señuelos haya, más difícil será encontrar la mejor combinación.

En este caso de coincidencia particular, la longitud de las cadenas es irrelevante, porque estamos esperando abreviaturas que representan palabras más largas, por lo que el peso óptimo para la longitud es -0.3, lo que significa que no penalizamos las cadenas que varían en longitud. Reducimos el puntaje anticipándose a estas abreviaturas, dando más espacio para las coincidencias parciales de palabras para reemplazar las coincidencias que no son palabras que simplemente requieren menos sustituciones porque la secuencia es más corta.

El peso de la palabra es 1.0, mientras que el peso de la frase es de solo 0.5, lo que significa que penalizamos las palabras enteras que faltan en una cadena y valoramos más la integridad de la frase completa. Esto es útil porque muchas de estas cadenas tienen una palabra en común (el peligro) donde lo que realmente importa es si la combinación (región y peligro) se mantiene o no.

Finalmente, el peso mínimo se optimiza a 10 y el peso máximo a 1. Lo que esto significa es que si el mejor de los dos puntajes (frase de valor y palabras de valor) no es muy bueno, el partido es muy penalizado, pero no lo hacemos `` penalizará grandemente el peor de los dos puntajes. Esencialmente, esto pone énfasis en requerir que la palabra valor o la frase valor tenga una buena calificación, pero no ambas. Una especie de mentalidad de "toma lo que podemos conseguir".

Es realmente fascinante lo que dice el valor optimizado de estos 5 pesos sobre el tipo de coincidencia de cuerdas difusas que tiene lugar. Para casos prácticos completamente diferentes de emparejamiento difuso de cuerdas, estos parámetros son muy diferentes. Lo he usado para 3 aplicaciones separadas hasta el momento.

Mientras no se utilizaba en la optimización final, se estableció una hoja de referencia que combina las columnas con todos los resultados perfectos en la diagonal, y permite al usuario cambiar los parámetros para controlar la velocidad con la que los puntajes divergen de 0 y observar similitudes innatas entre las frases de búsqueda ( que en teoría podría usarse para compensar falsos positivos en los resultados)

Fuzzy String Matching Benchmark

Aplicaciones adicionales

Esta solución tiene potencial para ser utilizada en cualquier lugar donde el usuario desee que un sistema informático identifique una cadena en un conjunto de cadenas en las que no existe una correspondencia perfecta. (Como un match match aproximado para cadenas).


Entonces, lo que debes tomar de esto es que probablemente quieras usar una combinación de heurística de alto nivel (encontrar palabras de una frase en la otra frase, duración de ambas frases, etc.) junto con la implementación del algoritmo de distancia de Levenshtein. Debido a que decidir cuál es la "mejor" coincidencia es una determinación heurística (borrosa): tendrás que encontrar un conjunto de ponderaciones para las métricas que se te ocurran para determinar la similitud.

Con el conjunto adecuado de pesos y heurísticas, tendrá su progtwig de comparación tomando rápidamente las decisiones que habría tomado.

Este problema aparece todo el tiempo en bioinformática. La respuesta aceptada anteriormente (que fue genial por cierto) es conocida en bioinformática como los algoritmos Needleman-Wunsch (comparar dos cadenas) y Smith-Waterman (encontrar una subcadena aproximada en una cadena más larga). Funcionan muy bien y han sido caballos de batalla durante décadas.

Pero, ¿y si tienes un millón de cadenas para comparar? ¡Eso es un trillón de comparaciones por parejas, cada una de las cuales es O (n * m)! Los secuenciadores de ADN modernos generan fácilmente mil millones de secuencias cortas de ADN, cada una de aproximadamente 200 “letras” de ADN de largo. Por lo general, queremos encontrar, para cada cadena, el mejor partido contra el genoma humano (3 mil millones de letras). Claramente, el algoritmo de Needleman-Wunsch y sus familiares no funcionarán.

Este llamado “problema de alineación” es un campo de investigación activa. Los algoritmos más populares actualmente pueden encontrar coincidencias inexactas entre mil millones de cadenas cortas y el genoma humano en cuestión de horas con un hardware razonable (por ejemplo, ocho núcleos y 32 GB de RAM).

La mayoría de estos algoritmos funcionan al encontrar rápidamente coincidencias exactas cortas (semillas) y luego extenderlas a la cadena completa utilizando un algoritmo más lento (por ejemplo, Smith-Waterman). La razón por la que esto funciona es porque realmente solo estamos interesados ​​en unos pocos partidos cercanos, así que vale la pena deshacerse del 99.9 …% de pares que no tienen nada en común.

¿De qué manera encontrar coincidencias exactas ayuda a encontrar coincidencias inexactas ? Bueno, digamos que permitimos solo una diferencia única entre la consulta y el objective. Es fácil ver que esta diferencia debe ocurrir en la mitad derecha o izquierda de la consulta, por lo que la otra mitad debe coincidir exactamente. Esta idea puede extenderse a múltiples desajustes y es la base del algoritmo ELAND comúnmente utilizado con los secuenciadores de ADN Illumina.

Hay muchos algoritmos muy buenos para hacer una coincidencia exacta de cadenas. Dada una cadena de consulta de longitud 200 y una cadena de destino de 3 mil millones de longitud (el genoma humano), queremos encontrar cualquier lugar en el objective donde exista una subcadena de longitud k que coincida exactamente con una subcadena de la consulta. Un enfoque simple es comenzar indexando el objective: tomar todas las subcadenas k-long, ponerlas en una matriz y ordenarlas. Luego tome cada subcadena k-long de la consulta y busque el índice ordenado. Ordenar y buscar se puede hacer en el tiempo O (log n).

Pero el almacenamiento puede ser un problema. Un índice del objective de 3 mil millones de letras necesitaría contener 3 mil millones de punteros y 3 mil millones de palabras largas. Parecería difícil encajar esto en menos de varias decenas de gigabytes de RAM. Pero, sorprendentemente, podemos comprimir enormemente el índice, utilizando la transformación Burrows-Wheeler , y aún así se podrá consultar de manera eficiente. Un índice del genoma humano puede caber en menos de 4 GB de RAM. Esta idea es la base de alineadores de secuencias populares como Bowtie y BWA .

Alternativamente, podemos usar una matriz de sufijos , que almacena solo los punteros, pero representa un índice simultáneo de todos los sufijos en la cadena objective (esencialmente, un índice simultáneo para todos los valores posibles de k; lo mismo es cierto para la transformación Burrows-Wheeler ) Un índice de matriz de sufijo del genoma humano tomará 12 GB de RAM si usamos punteros de 32 bits.

Los enlaces anteriores contienen una gran cantidad de información y enlaces a documentos de investigación principales. El enlace ELAND va a un PDF con figuras útiles que ilustran los conceptos involucrados, y muestra cómo lidiar con inserciones y eliminaciones.

Finalmente, aunque estos algoritmos básicamente han resuelto el problema de (re) secuenciar genomas humanos únicos (mil millones de cuerdas cortas), la tecnología de secuenciación de ADN mejora incluso más rápido que la ley de Moore, y nos acercamos rápidamente a los conjuntos de datos de billones de letras. Por ejemplo, actualmente hay proyectos en curso para secuenciar los genomas de 10.000 especies de vertebrados , cada uno de un billón de letras de largo más o menos. Naturalmente, querremos hacer una coincidencia de cadenas inexacta por parejas en los datos …

Yo impugno que la opción B está más cerca de la cadena de prueba, ya que son solo 4 caracteres (y 2 eliminaciones) de ser la cadena original. Mientras que usted ve C más cerca porque incluye tanto marrón como rojo. Sin embargo, tendría una mayor distancia de edición.

Hay un algoritmo llamado Levenshtein Distance que mide la distancia de edición entre dos entradas.

Aquí hay una herramienta para ese algoritmo.

  1. Las tasas de elección A como una distancia de 15.
  2. Califica la opción B como una distancia de 6.
  3. Las tasas de elección C como una distancia de 9.

EDITAR: Lo siento, sigo mezclando cadenas en la herramienta levenshtein. Actualizado para corregir respuestas.

Implementación de Lua, para la posteridad:

 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 

Puede que le interese esta publicación de blog.

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

Fuzzywuzzy es una biblioteca de Python que proporciona medidas de distancia fáciles, como la distancia de Levenshtein para hacer coincidir cuerdas. Está construido sobre difflib en la biblioteca estándar y hará uso de la implementación C Python-levenshtein si está disponible.

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

¡Puede encontrar útil esta biblioteca! http://code.google.com/p/google-diff-match-patch/

Actualmente está disponible en Java, JavaScript, Dart, C ++, C #, Objective C, Lua y Python

Funciona bastante bien también. Lo uso en un par de mis proyectos de Lua.

¡Y no creo que sea demasiado difícil portarlo a otros idiomas!

Si está haciendo esto en el contexto de un motor de búsqueda o interfaz frente a una base de datos, puede considerar el uso de una herramienta como Apache Solr , con el complemento ComplexPhraseQueryParser . Esta combinación le permite buscar en un índice de cadenas con los resultados ordenados por relevancia, según lo determinado por la distancia de Levenshtein.

Lo hemos estado usando contra una gran colección de artistas y títulos de canciones cuando la consulta entrante puede tener uno o más errores tipográficos, y ha funcionado bastante bien (y notablemente rápido teniendo en cuenta que las colecciones están en los millones de cadenas).

Además, con Solr, puede buscar en el índice bajo demanda a través de JSON, por lo que no tendrá que reinventar la solución entre los diferentes idiomas que está viendo.

Un recurso muy, muy bueno para este tipo de algoritmos es Simmetrics: http://sourceforge.net/projects/simmetrics/

Desafortunadamente, el increíble sitio web que contiene una gran cantidad de la documentación se ha ido 🙁 En caso de que vuelva a aparecer, su dirección anterior era la siguiente: http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Voila (cortesía de “Wayback Machine”): http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Puede estudiar la fuente del código, hay docenas de algoritmos para este tipo de comparaciones, cada una con una compensación diferente. Las implementaciones están en Java.

Para consultar un conjunto grande de texto de manera eficiente, puede utilizar el concepto Editar distancia de distancia de edición de prefijo.

Editar distancia ED (x, y): número mínimo de transfroms para llegar del término x al término y

Pero calcular ED entre cada término y el texto de consulta requiere mucho tiempo y recursos. Por lo tanto, en lugar de calcular ED para cada término primero, podemos extraer posibles términos coincidentes utilizando una técnica denominada Índice Qgram. y luego aplica el cálculo ED en esos términos seleccionados.

Una ventaja de la técnica de índice de Qgram es que es compatible con la búsqueda difusa.

Un posible enfoque para adaptar el índice QGram es construir un índice invertido usando Qgrams. Aquí almacenamos todas las palabras que consisten en Qgram particular, debajo de ese Qgram. (En vez de almacenar una cadena completa puede usar una ID única para cada cadena). Puede usar la estructura de datos Tree Map en Java para esto. Lo que sigue es un pequeño ejemplo de almacenamiento de términos

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

Luego, cuando consultamos, calculamos el número de Qgrams comunes entre el texto de la consulta y los términos 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 

número de q-gramos en común = 4.

Para los términos con un alto número de Qgramos comunes, calculamos el ED / PED contra el término de la consulta y luego sugerimos el término al usuario final.

puedes encontrar una implementación de esta teoría en el siguiente proyecto (Ver “QGramIndex.java”). No dude en hacer cualquier pregunta. https://github.com/Bhashitha-Gamage/City_Search

Para estudiar más sobre Editar distancia, Prefijo Editar índice de Qgram de distancia, mira el siguiente video del Prof. Dr. Hannah Bast https://www.youtube.com/embed/6pUg2wmGJRo (La lección comienza a partir de las 20:06)

El problema es difícil de implementar si los datos de entrada son demasiado grandes (digamos millones de cadenas). Utilicé la búsqueda elástica para resolver esto. Simplemente inserte todos los datos de entrada en DB y podrá buscar cualquier cadena en función de cualquier distancia de edición rápidamente. Aquí hay un fragmento de C # que le dará una lista de resultados ordenados por distancia de edición (menor a mayor)

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