Pesquisa fuzzy de Javascript que faz sentido

Estou procurando uma biblioteca JavaScript de pesquisa difusa para filtrar uma matriz. Tentei usar o fuzzyset.js e o fuse.js , mas os resultados são terríveis (há demonstrações que você pode experimentar nas páginas vinculadas).

Depois de fazer algumas leituras sobre a distância de Levenshtein, me parece uma aproximação pobre do que os usuários procuram quando digitam. Para quem não sabe, o sistema calcula quantas inserções , exclusões e substituições são necessárias para fazer a correspondência de duas strings.

Uma falha óbvia, corrigida no modelo Levenshtein-Demerau, é que tanto o blub quanto o boob são considerados igualmente semelhantes ao bulbo (cada um exigindo duas substituições). É claro, no entanto, que bulb é mais semelhante a blub do que boob , e o modelo que acabei de mencionar reconhece isso ao permitir transposições .

Quero usar isso no contexto de preenchimento de texto, portanto, se eu tiver uma matriz ['international', 'splint', 'tinder']e minha consulta for int , acho que internacional deve ter uma classificação mais alta do que splint , embora o primeiro tenha uma pontuação (maior = pior) de 10 versus o último 3.

Portanto, o que procuro (e criarei se não existir) é uma biblioteca que faça o seguinte:

• Pesa as diferentes manipulações de texto
• Pesa cada manipulação de forma diferente, dependendo de onde elas aparecem em uma palavra (as manipulações iniciais são mais caras do que as manipulações posteriores)
• Retorna uma lista de resultados classificados por relevância

Alguém encontrou algo assim? Sei que StackOverflow não é o lugar para pedir recomendações de software, mas implícito (não mais!) No acima está: estou pensando sobre isso da maneira certa?

Editar

Encontrei um bom artigo (pdf) sobre o assunto. Algumas notas e trechos:

Funções afins de edição de distância atribuem um custo relativamente mais baixo a uma sequência de inserções ou exclusões

a função de distância Monger-Elkan (Monge & Elkan 1996), que é uma variante afim da função de distância Smith-Waterman (Durban et al. 1998) com parâmetros de custo específicos

Para a distância Smith-Waterman (wikipedia) , "Em vez de olhar para a sequência total, o algoritmo Smith-Waterman compara segmentos de todos os comprimentos possíveis e otimiza a medida de similaridade." É a abordagem de n-gram.

Uma métrica amplamente semelhante, que não é baseada em um modelo de edição de distância, é a métrica Jaro (Jaro 1995; 1989; Winkler 1999). Na literatura record-linkage, bons resultados têm sido obtidos usando variantes desse método, que se baseia no número e na ordem dos caracteres comuns entre duas strings.

Uma variante disso devido a Winkler (1999) também usa o comprimento P do prefixo comum mais longo

(parece ser destinado principalmente para strings curtas)

Para fins de preenchimento de texto, as abordagens Monger-Elkan e Jaro-Winkler parecem fazer mais sentido. O acréscimo de Winkler à métrica Jaro pondera efetivamente o início das palavras com mais intensidade. E o aspecto afim de Monger-Elkan significa que a necessidade de completar uma palavra (que é simplesmente uma sequência de acréscimos) não vai desfavorecê-la muito.

Conclusão:

a classificação TFIDF teve o melhor desempenho entre várias métricas de distância baseadas em tokens, e uma métrica de distância de edição de gap afinado proposta por Monge e Elkan teve o melhor desempenho entre várias métricas de distância de edição de string. Uma métrica de distância surpreendentemente boa é um esquema heurístico rápido, proposto por Jaro e posteriormente estendido por Winkler. Isso funciona quase tão bem quanto o esquema Monge-Elkan, mas é uma ordem de magnitude mais rápido. Uma maneira simples de combinar o método TFIDF e o Jaro-Winkler é substituir as correspondências de token exatas usadas no TFIDF por correspondências de token aproximadas baseadas no esquema de Jaro-Winkler. Esta combinação tem um desempenho ligeiramente melhor do que Jaro-Winkler ou TFIDF em média, e ocasionalmente tem um desempenho muito melhor. Também se aproxima em desempenho de uma combinação aprendida de várias das melhores métricas consideradas neste artigo.

Boa pergunta! Mas meu pensamento é que, em vez de tentar modificar Levenshtein-Demerau, talvez seja melhor tentar um algoritmo diferente ou combinar / ponderar os resultados de dois algoritmos.

Parece-me que correspondências exatas ou próximas ao "prefixo inicial" são algo a que Levenshtein-Demerau não dá importância especial - mas suas expectativas aparentes do usuário sim.

Eu pesquisei "melhor do que Levenshtein" e, entre outras coisas, encontrei este:

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

Isso menciona uma série de medidas de "distância da string". Três que pareciam particularmente relevantes para o seu requisito, seriam:

1. Distância de substring comum mais longa: Número mínimo de símbolos que devem ser removidos em ambas as strings até que as substrings resultantes sejam idênticas.

2. distância de q-gram: Soma das diferenças absolutas entre vetores de N-gram de ambas as cadeias.

3. Distância de Jaccard: 1 minuto o quociente de N-gramas compartilhados e todos os N-gramas observados.

Talvez você possa usar uma combinação ponderada (ou mínimo) dessas métricas, com Levenshtein - substring comum, N-grama comum ou Jaccard terão todos uma preferência forte strings semelhantes - ou talvez tentar apenas usar Jaccard?

Dependendo do tamanho de sua lista / banco de dados, esses algoritmos podem ser moderadamente caros. Para uma pesquisa difusa que implementei, usei um número configurável de N-gramas como "chaves de recuperação" do banco de dados e, em seguida, executei a medida de distância de string cara para classificá-los em ordem de preferência.

Eu escrevi algumas notas sobre Fuzzy String Search em SQL. Vejo:

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

Eu tentei usar bibliotecas fuzzy existentes como fuse.js e também as achei terríveis, então escrevi uma que se comporta basicamente como a pesquisa do sublime. https://github.com/farzher/fuzzysort

O único erro de digitação que permite é uma transposição. É bastante sólido (1k estrelas, 0 problemas) , muito rápido e lida com seu caso facilmente:

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

Aqui está uma técnica que usei algumas vezes ... Ela dá resultados muito bons. Porém, não faz tudo o que você pediu. Além disso, isso pode ser caro se a lista for 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

Passe duas strings para as string_similarityquais retornará um número entre 0e1.0 dependendo de quão semelhantes são. Este exemplo usa Lo-Dash

Exemplo 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

Também .... tem um violino

Certifique-se de que seu console esteja aberto ou você não verá nada :)

esta é minha função curta e compacta para correspondência difusa:

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

você pode dar uma olhada em https://github.com/atom/fuzzaldrin/ do Atom lib .

está disponível no npm, tem API simples e funcionou bem para mim.

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

Atualização de novembro de 2019. Eu descobri que o fusível tem algumas atualizações bastante decentes. No entanto, não consegui fazer com que ele usasse bool's (ou seja, operadores OR, AND, etc.) nem poderia usar a interface de pesquisa da API para filtrar os resultados.

Eu descobri nextapps-de/flexsearch: https://github.com/nextapps-de/flexsearch e acredito que ultrapassa de longe muitas das outras bibliotecas de pesquisa javascript que experimentei e tem suportebool para filtrar pesquisas e paginação.

Você pode inserir uma lista de objetos javascript para seus dados de pesquisa (ou seja, armazenamento), e a API é bem documentada: https://github.com/nextapps-de/flexsearch#api-overview

Até agora, indexei perto de 10.000 registros e minhas pesquisas são quase imediatas; ou seja, quantidade de tempo imperceptível para cada pesquisa.

aqui está a solução fornecida por @InternalFX, mas em JS (usei para compartilhar):

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
}

Corrigi os problemas com a solução de bigrama CoffeeScript da InternalFx e a tornei uma solução genérica de n gramas (você pode personalizar o tamanho dos gramas).

Este é o TypeScript, mas você pode remover as anotações de tipo e funciona bem como o JavaScript vanilla também.

/**
 * 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;
}

Exemplos:

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"))

Experimente no Playground TypeScript

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

Verifique meu complemento do Planilhas Google chamado Flookup e use esta função:

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

Os detalhes dos parâmetros são:

1. lookupValue: o valor que você está procurando
2. tableArray: a mesa que você deseja pesquisar
3. lookupCol: a coluna que você deseja pesquisar
4. indexNum: a coluna da qual você deseja que os dados sejam retornados
5. threshold: a porcentagem de similaridade abaixo da qual os dados não devem ser retornados
6. rank: a enésima melhor correspondência (ou seja, se a primeira correspondência não for do seu agrado)

Isso deve satisfazer seus requisitos ... embora eu não tenha certeza sobre o ponto número 2.

Saiba mais no site oficial .