búsqueda difusa rápida dinámica sobre 100k + cadenas 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 se inspiró en esta pregunta: ¿

Are there any Fuzzy Search or String Similarity Functions libraries written for C#?

El algoritmo de distancia Levenstein parece funcionar bien, pero se necesita tiempo para calcular. ¿Hay alguna optimización en torno al hecho de que la consulta deberá 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 que coincida con
• número de caracteres no coincidentes
• similares longitud
• errores tipográficos o fonéticas abreviaturas específicas
• negocios
• debe comenzar con la misma subcadena
• debe terminar con la misma subcadena

He trabajado mucho con los algoritmos de coincidencia de cadenas, y todavía no he encontrado ninguna biblioteca o código 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 Jaro-Winkler de Smith-Waterman &, 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 las coincidencias inesperadas y puntajes bajos en las coincidencias esperadas. La coincidencia de cadenas es muy de dominio específico. Si no defines correctamente tu dominio, entonces eres como un pescador sin idea, lanzando ganchos y esperando lo mejor.

Answer 2

This blog post 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 la coincidencia 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 vez 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".