tablas - recorrer tabla javascript

Javascript búsqueda difusa que tiene sentido

Question

Estoy buscando una biblioteca de búsqueda difusa de JavaScript para filtrar una matriz. He intentado usar fuzzyset.js y fuse.js , pero los resultados son terribles (hay demostraciones que puedes probar en las páginas vinculadas).

Después de leer un poco sobre la distancia de Levenshtein, me parece una mala aproximación de lo que los usuarios buscan cuando escriben. Para aquellos que no lo saben, el sistema calcula cuántas inserciones , eliminaciones y sustituciones son necesarias para hacer coincidir dos cadenas.

Un defecto obvio, que se corrige en el modelo de Levenshtein-Demerau, es que tanto el blub como el boob se consideran igualmente similares al bulbo (cada uno requiere dos sustituciones). Sin embargo, está claro que la bombilla es más similar a blub que boob , y el modelo que acabo de mencionar lo reconoce al permitir las transposiciones .

Quiero usar esto en el contexto de la finalización del texto, así que si tengo una matriz [''international'', ''splint'', ''tinder''] , y mi consulta es int , creo que internacional debería tener un rango más alto que la férula , incluso aunque el primero tiene una puntuación (mayor = peor) de 10 frente al 3 de este último.

Entonces, lo que estoy buscando (y creará si no existe), es una biblioteca que hace lo siguiente:

• Sopesa las diferentes manipulaciones del texto.
• Pesa cada manipulación de manera diferente según el lugar en el que aparece en una palabra (las manipulaciones tempranas son más costosas que las manipulaciones tardías)
• Devuelve una lista de resultados ordenados por relevancia.

¿Alguien ha encontrado algo como esto? Me doy cuenta de que StackOverflow no es el lugar para pedir recomendaciones de software, pero lo implícito (¡ya no!) En lo anterior es: ¿estoy pensando en esto de la manera correcta?

Editar

Encontré un buen artículo (pdf) sobre el tema. Algunas notas y extractos:

Las funciones de edición de distancia afines asignan un costo relativamente menor a una secuencia de inserciones o eliminaciones

la función de distancia Monger-Elkan (Monge y Elkan 1996), que es una variante afín de la función de distancia Smith-Waterman (Durban et al. 1998) con parámetros de costo particulares

Para la distancia Smith-Waterman (wikipedia) , "En lugar de observar la secuencia total, el algoritmo Smith-Waterman compara segmentos de todas las longitudes posibles y optimiza la medida de similitud". Es el enfoque n-gramo.

Una métrica muy similar, que no se basa en un modelo de distancia de edición, es la métrica de Jaro (Jaro 1995; 1989; Winkler 1999). En la literatura de vinculación de registros, se han obtenido buenos resultados utilizando variantes de este método, que se basan en el número y orden de los caracteres comunes entre dos cadenas.

Una variante de esto debido a Winkler (1999) también usa la longitud P del prefijo común más largo

(parecen estar destinados principalmente para cuerdas cortas)

Para propósitos de completar el texto, los enfoques de Monger-Elkan y Jaro-Winkler parecen tener más sentido. La adición de Winkler a la métrica de Jaro pesa de manera efectiva los comienzos de las palabras más intensamente. Y el aspecto afín de Monger-Elkan significa que la necesidad de completar una palabra (que es simplemente una secuencia de adiciones) no la desfavorecerá demasiado.

Conclusión:

El ranking TFIDF se desempeñó mejor entre varias métricas de distancia basadas en token, y una métrica afín afinada de la brecha de edición propuesta por Monge y Elkan se desempeñó mejor entre varias métricas de distancia de edición de cadena. Una métrica de distancia sorprendentemente buena es un esquema heurístico rápido, propuesto por Jaro y más tarde extendido por Winkler. Esto funciona casi tan bien como el esquema de Monge-Elkan, pero es un orden de magnitud más rápido. Una forma sencilla de combinar el método TFIDF y el Jaro-Winkler es reemplazar las coincidencias exactas de token utilizadas en TFIDF por coincidencias aproximadas de token basadas en el esquema Jaro-Winkler. Esta combinación tiene un rendimiento ligeramente mejor que el de Jaro-Winkler o TFIDF en promedio, y ocasionalmente funciona mucho mejor. También tiene un rendimiento cercano a una combinación aprendida de varias de las mejores métricas consideradas en este documento.

Answer 1

¡Buena pregunta! Pero mi pensamiento es que, en lugar de tratar de modificar Levenshtein-Demerau, puede ser mejor probar un algoritmo diferente o combinar / ponderar los resultados de dos algoritmos.

Me parece que las coincidencias exactas o cercanas al "prefijo inicial" son algo a lo que Levenshtein-Demerau no le otorga ningún peso en particular, pero sus expectativas aparentes de usuario lo harían.

Busqué "mejor que Levenshtein" y, entre otras cosas, encontré esto:

http://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/

Esto menciona una serie de medidas de "distancia de cadena". Tres que parecían particularmente relevantes para su requerimiento, serían:

1. Distancia más larga de subcadena común: Número mínimo de símbolos que deben eliminarse en ambas cadenas hasta que las subcadenas resultantes sean idénticas.

2. Distancia q-gramo: suma de las diferencias absolutas entre los vectores N-gramo de ambas cadenas.

3. Distancia Jaccard: 1 minuto el cociente de N-gramos compartidos y todos los N-gramos observados.

Tal vez podría usar una combinación ponderada (o mínima) de estas métricas, con Levenshtein (subcadena común, N-gramo común o Jaccard), ¿todas preferirán cadenas similares , o quizás intente simplemente usar Jaccard?

Dependiendo del tamaño de su lista / base de datos, estos algoritmos pueden ser moderadamente costosos. Para una búsqueda difusa que implementé, usé un número configurable de N-gramas como "claves de recuperación" de la base de datos y luego ejecuté la costosa medida de distancia de la cadena para clasificarlas en orden de preferencia.

Escribí algunas notas en Fuzzy String Search en SQL. Ver:

• http://literatejava.com/sql/fuzzy-string-search-sql/

Answer 2

Aquí hay una técnica que he usado varias veces ... Da buenos resultados. Aunque no hace todo lo que pediste. Además, esto puede ser costoso si la lista es masiva.

get_bigrams = (string) ->
    s = string.toLowerCase()
    v = new Array(s.length - 1)
    for i in [0..v.length] by 1
        v[i] = s.slice(i, i + 2)
    return v

string_similarity = (str1, str2) ->
    if str1.length > 0 and str2.length > 0
        pairs1 = get_bigrams(str1)
        pairs2 = get_bigrams(str2)
        union = pairs1.length + pairs2.length
        hit_count = 0
        for x in pairs1
            for y in pairs2
                if x is y
                    hit_count++
        if hit_count > 0
            return ((2.0 * hit_count) / union)
    return 0.0

Pase dos cadenas a string_similarity que devolverá un número entre 0 y 1.0 dependiendo de qué tan similares sean. Este ejemplo usa Lo-Dash

Ejemplo de uso ....

query = ''jenny Jackson''
names = [''John Jackson'', ''Jack Johnson'', ''Jerry Smith'', ''Jenny Smith'']

results = []
for name in names
    relevance = string_similarity(query, name)
    obj = {name: name, relevance: relevance}
    results.push(obj)

results = _.first(_.sortBy(results, ''relevance'').reverse(), 10)

console.log results

También .... tener un fiddle

Asegúrate de que tu consola esté abierta o no verás nada :)

Answer 3

Intenté usar bibliotecas difusas como fuse.js y también las encontré terribles, así que escribí una que se comporta básicamente como una búsqueda sublime. https://github.com/farzher/fuzzysort

El único error tipográfico que permite es una transposición. Es bastante sólido (1k estrellas, 0 problemas) , muy rápido , y maneja tu estuche fácilmente:

fuzzysort.go(''int'', [''international'', ''splint'', ''tinder''])
// [{highlighted: ''*int*ernational'', score: 10}, {highlighted: ''spl*int*'', socre: 3003}]

Answer 4

puede echar un vistazo a https://github.com/atom/fuzzaldrin/ lib de Atom.

está disponible en npm, tiene API simple y funcionó bien para mí.

> fuzzaldrin.filter([''international'', ''splint'', ''tinder''], ''int'');
< ["international", "splint"]

Answer 5

(function (int) {
    $("input[id=input]")
        .on("input", {
        sort: int
    }, function (e) {
        $.each(e.data.sort, function (index, value) {
          if ( value.indexOf($(e.target).val()) != -1 
              && value.charAt(0) === $(e.target).val().charAt(0) 
              && $(e.target).val().length === 3 ) {
                $("output[for=input]").val(value);
          };
          return false
        });
        return false
    });
}(["international", "splint", "tinder"]))

jsfiddle http://jsfiddle.net/guest271314/QP7z5/