truncar - Búsqueda Fast Dynamic Fuzzy en 100k+cadenas en C#

string en c++

Question

Digamos que son símbolos de stock precargados, escritos en un cuadro de texto. Estoy buscando un código que pueda copiar, no una biblioteca para instalar.

Esto fue inspirado por esta pregunta:

¿Hay alguna biblioteca de Fuzzy Search o String Similarity Functions escritas para C #?

El algoritmo de distancia de Levenstein parece funcionar bien, pero lleva tiempo calcularlo. ¿Hay alguna optimización en torno al hecho de que la consulta tendrá que volver a ejecutarse a medida que el usuario escribe una letra extra? Estoy interesado en mostrar como máximo las 10 mejores coincidencias para cada entrada.

Answer 1

Debe determinar las reglas de coincidencia alrededor de sus cadenas. Lo que determina una ''cadena similar''

• número de caracteres coincidentes
• número de caracteres que no coinciden
• longitud similar
• errores tipográficos o fonéticos
• abreviaciones específicas de negocios
• debe comenzar con la misma subcadena
• debe terminar con la misma subcadena

He trabajado mucho con los algoritmos de coincidencia de cadenas, y aún no he encontrado ninguna biblioteca o código existente que cumpla con mis requisitos específicos. Revíselos, pídales prestados ideas, pero invariablemente tendrá que personalizar y escribir su propio código.

El algoritmo de Levenstein es bueno pero un poco lento. Tuve cierto éxito con los algoritmos de Smith-Waterman y Jaro-Winkler, pero lo mejor que encontré para mi propósito fue Monge (de memoria). Sin embargo, vale la pena leer la investigación original y determinar por qué han escrito sus algoritmos y su conjunto de datos objetivo.

Si no define correctamente lo que quiere hacer coincidir y medir, encontrará puntajes altos en partidos inesperados y puntajes bajos en partidos esperados. La coincidencia de cadenas es muy específica del dominio. Si no defines correctamente tu dominio, entonces eres como un pescador sin idea, lanzando ganchos y esperando lo mejor.

Answer 2

Esta publicación de blog describe algunos trabajos que se realizaron en Lucene en esta área. Pudieron implementar el emparejamiento borroso de distancia de Levenshtein usando un transductor de estado finito (autómata) de manera bastante eficiente para una distancia de edición de hasta 2. Sin embargo, el código es todo en Java y un poco complejo, aunque es de código abierto.

Pero la idea básica es bastante simple: piense en su diccionario como un árbol gigante de estados de letras. En state0, no tienes letras. En state1, admite cualquier letra que podría ser la primera letra de una palabra. State2 está condicionado por state1; si la primera letra era ''x'', el siguiente estado admite solo letras que podrían seguir a x (en la posición 2). etc.

Ahora para el emparejamiento de Levenshtein, recorre el árbol de letras mientras permite algunos errores: eliminaciones, inserciones (comodín de una letra) y posiblemente transposición (una buena extensión de Levenshtein es considerar una transposición como una sola edición en lugar de 2). Debe mantener el estado para realizar un seguimiento de cuántas ediciones se han permitido. Esto se puede hacer de manera muy eficiente, lo suficientemente rápido para un sugerente de ortografía interactivo "mientras escribes".