Búsqueda difusa de JavaScript que tiene sentido

Estoy buscando una biblioteca de JavaScript de búsqueda difusa para filtrar una matriz. Intenté usar fuzzyset.js y fuse.js , pero los resultados son terribles (hay demostraciones que puede 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 buscan los usuarios cuando escriben. Para aquellos que no lo saben, el sistema calcula cuántas inserciones , eliminaciones y sustituciones se necesitan 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 bulb es más similar a blub que boob , y el modelo que acabo de mencionar lo reconoce al permitir transposiciones .

Quiero usar esto en el contexto de la finalización de texto, por lo que si tengo una matriz ['international', 'splint', 'tinder']y mi consulta es int , creo que internacional debería tener una clasificación más alta que la tablilla , aunque la primera tiene una puntuación (más alta = peor) de 10 frente al 3 de este último.

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

• Pesa las diferentes manipulaciones de texto
• Pesa cada manipulación de manera diferente dependiendo de dónde aparecen en una palabra (las manipulaciones tempranas son más costosas que las manipulaciones tardías)
• Devuelve una lista de resultados ordenados por relevancia.

¿Alguien se ha encontrado con algo como esto? Me doy cuenta de que StackOverflow no es el lugar para pedir recomendaciones de software, pero 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 afines de distancia de edición asignan un costo relativamente menor a una secuencia de inserciones o eliminaciones

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

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

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 sobre vinculación de registros, se han obtenido buenos resultados utilizando variantes de este método, que se basa en el número y el 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

(parece estar destinado principalmente a cadenas cortas)

Para 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 pondera de manera efectiva los comienzos de las palabras más. 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 desaprovechará demasiado.

Conclusión:

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

¡Buena pregunta! Pero mi pensamiento es que, en lugar de intentar modificar Levenshtein-Demerau, sería 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 da un peso particular, pero sus expectativas aparentes de usuario sí 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 la cuerda". Tres que parecían particularmente relevantes para su requerimiento serían:

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

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

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

Tal vez podría usar una combinación ponderada (o un mínimo) de estas métricas, con Levenshtein: la subcadena común, el N-gram común o Jaccard preferirán encarecidamente similares cadenas , o tal vez intente usar simplemente Jaccard.

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

Escribí algunas notas sobre la búsqueda de cadenas difusas en SQL. Ver:

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

Intenté usar bibliotecas difusas existentes 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 números) , muy rápido y maneja su caso fácilmente:

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

Esta es una técnica que he usado varias veces ... Da muy buenos resultados. Sin embargo, no hace todo lo que pidió. Además, esto puede resultar caro si la lista es enorme.

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

Pasar dos cadenas a las string_similarityque devolverán un número entre 0y 1.0dependiendo 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

Además ... ten un violín

Asegúrese de que su consola esté abierta o no verá nada :)

esta es mi función corta y compacta para la coincidencia difusa:

function fuzzyMatch(pattern, str) {
  pattern = '.*' + pattern.split('').join('.*') + '.*';
  const re = new RegExp(pattern);
  return re.test(str);
}

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

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

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

Actualización de noviembre de 2019. Encontré que Fuse tiene algunas actualizaciones bastante decentes. Sin embargo, no pude hacer que usara los operadores bool (es decir, OR, AND, etc.) ni pude usar la interfaz de búsqueda API para filtrar los resultados.

Descubrí nextapps-de/flexsearch: https://github.com/nextapps-de/flexsearch y creo que supera con creces muchas de las otras bibliotecas de búsqueda de javascript que he probado, y tiene soporte bool, filtrado de búsquedas y paginación.

Puede ingresar una lista de objetos javascript para sus datos de búsqueda (es decir, almacenamiento), y la API está bastante bien documentada: https://github.com/nextapps-de/flexsearch#api-overview

Hasta ahora he indexado cerca de 10,000 registros y mis búsquedas son casi inmediatas; es decir, una cantidad de tiempo imperceptible para cada búsqueda.

aquí está la solución proporcionada por @InternalFX, pero en JS (la usé para compartir):

function get_bigrams(string){
  var s = string.toLowerCase()
  var v = s.split('');
  for(var i=0; i<v.length; i++){ v[i] = s.slice(i, i + 2); }
  return v;
}

function string_similarity(str1, str2){
  if(str1.length>0 && str2.length>0){
    var pairs1 = get_bigrams(str1);
    var pairs2 = get_bigrams(str2);
    var union = pairs1.length + pairs2.length;
    var hits = 0;
    for(var x=0; x<pairs1.length; x++){
      for(var y=0; y<pairs2.length; y++){
        if(pairs1[x]==pairs2[y]) hits++;
    }}
    if(hits>0) return ((2.0 * hits) / union);
  }
  return 0.0
}

Arreglé los problemas con la solución de bigram CoffeeScript de InternalFx y la convertí en una solución genérica de n-gramos (puede personalizar el tamaño de los gramos).

Esto es TypeScript, pero puede eliminar las anotaciones de tipo y también funciona como vainilla JavaScript.

/**
 * Compares the similarity between two strings using an n-gram comparison method. 
 * The grams default to length 2.
 * @param str1 The first string to compare.
 * @param str2 The second string to compare.
 * @param gramSize The size of the grams. Defaults to length 2.
 */
function stringSimilarity(str1: string, str2: string, gramSize: number = 2) {
  function getNGrams(s: string, len: number) {
    s = ' '.repeat(len - 1) + s.toLowerCase() + ' '.repeat(len - 1);
    let v = new Array(s.length - len + 1);
    for (let i = 0; i < v.length; i++) {
      v[i] = s.slice(i, i + len);
    }
    return v;
  }

  if (!str1?.length || !str2?.length) { return 0.0; }

  //Order the strings by length so the order they're passed in doesn't matter 
  //and so the smaller string's ngrams are always the ones in the set
  let s1 = str1.length < str2.length ? str1 : str2;
  let s2 = str1.length < str2.length ? str2 : str1;

  let pairs1 = getNGrams(s1, gramSize);
  let pairs2 = getNGrams(s2, gramSize);
  let set = new Set<string>(pairs1);

  let total = pairs2.length;
  let hits = 0;
  for (let item of pairs2) {
    if (set.delete(item)) {
      hits++;
    }
  }
  return hits / total;
}

Ejemplos:

console.log(stringSimilarity("Dog", "Dog"))
console.log(stringSimilarity("WolfmanJackIsDaBomb", "WolfmanJackIsDaBest"))
console.log(stringSimilarity("DateCreated", "CreatedDate"))
console.log(stringSimilarity("a", "b"))
console.log(stringSimilarity("CreateDt", "DateCreted"))
console.log(stringSimilarity("Phyllis", "PyllisX"))
console.log(stringSimilarity("Phyllis", "Pylhlis"))
console.log(stringSimilarity("cat", "cut"))
console.log(stringSimilarity("cat", "Cnut"))
console.log(stringSimilarity("cc", "Cccccccccccccccccccccccccccccccc"))
console.log(stringSimilarity("ab", "ababababababababababababababab"))
console.log(stringSimilarity("a whole long thing", "a"))
console.log(stringSimilarity("a", "a whole long thing"))
console.log(stringSimilarity("", "a non empty string"))
console.log(stringSimilarity(null, "a non empty string"))

Pruébelo en TypeScript Playground

(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/

Consulte mi complemento de Google Sheets llamado Flookup y use esta función:

Flookup (lookupValue, tableArray, lookupCol, indexNum, threshold, [rank])

Los detalles de los parámetros son:

1. lookupValue: el valor que estás buscando
2. tableArray: la tabla que desea buscar
3. lookupCol: la columna que desea buscar
4. indexNum: la columna de la que desea que se devuelvan los datos
5. threshold: el porcentaje de similitud por debajo del cual no se deben devolver los datos
6. rank: la enésima mejor coincidencia (es decir, si la primera coincidencia no es de su agrado)

Esto debería satisfacer sus requisitos ... aunque no estoy seguro del punto número 2.

Obtenga más información en el sitio web oficial .