Javascript busca difusa que faz sentido

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

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

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

Eu quero usar isso no contexto da conclusão do texto, por isso, se eu tiver uma matriz ['international', 'splint', 'tinder'] , e minha consulta for int , acho que a sorting internacional deve ser mais altamente do que splint , mesmo embora o primeiro tenha uma pontuação (maior = pior) de 10 versus 3 do último.

Então, o que eu estou procurando (e irá criar se não existir), é uma biblioteca que faz o seguinte:

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

Alguém se deparou com algo assim? Eu percebo que StackOverflow não é o lugar para se estar pedindo recomendações de software, mas implícito (não mais!) No acima é: estou pensando sobre isso da maneira certa?


Editar

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

As funções de distância de edição afim atribuem um custo relativamente menor a uma sequência de inserções ou exclusões

a function de distância Monger-Elkan (Monge & Elkan 1996), que é uma variante afim da function de distância de Smith-Waterman (Durban et al. 1998) com parâmetros de custo particulares

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

Uma métrica amplamente similar, que não é baseada em um modelo edit-distance, é a métrica de Jaro (Jaro 1995; 1989; Winkler 1999). Na literatura de vinculação de registros, bons resultados foram obtidos usando variantes deste método, que é baseado 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 maior prefixo comum

(parecem ser destinados principalmente a strings curtas)

Para fins de conclusão de texto, as abordagens Monger-Elkan e Jaro-Winkler parecem fazer mais sentido. A adição de Winkler à métrica Jaro mede 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 a desfavorece muito.

Conclusão:

o ranking 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 afinada com lacuna afim proposta por Monge e Elkan apresentou 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ápida. Uma maneira simples de combinar o método TFIDF e o Jaro-Winkler é replace as correspondências de token exatas usadas no TFIDF com correspondências de token aproximadas baseadas no esquema Jaro-Winkler. Esta combinação tem um desempenho um pouco melhor do que o Jaro-Winkler ou o TFIDF, em média, e ocasionalmente funciona muito melhor. Também está próximo no desempenho de uma combinação de diversas 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 as correspondências exatas ou próximas ao “prefixo inicial” são algo que Levenshtein-Demerau não dá nenhum peso particular a elas – mas suas expectativas aparentes para o usuário seriam.

Eu procurei por “melhor que Levenshtein” e, entre outras coisas, achei isto:

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

Isso menciona várias medidas de “distância de seqüência”. Três que pareciam particularmente relevantes para sua necessidade, seriam:

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

  2. Distância q-gram: sum das diferenças absolutas entre vetores N-gram de ambas as seqüências.

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

Talvez você possa usar uma combinação ponderada (ou mínima) dessas métricas, com o Levenshtein – substring comum, N-gram comum ou Jaccard – todos irão preferir fortemente strings similares – ou talvez tentar apenas usar o Jaccard?

Dependendo do tamanho da sua lista / database, esses algoritmos podem ser moderadamente caros. Para uma pesquisa fuzzy implementada, usei um número configurável de N-grams como “chaves de recuperação” do database e, em seguida, executei a cara medida de distância de seqüência para classificá-las na ordem de preferência.

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

Aqui está uma técnica que usei algumas vezes … Isso dá bons resultados. Não faz tudo o que você pediu, no entanto. 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 string_similarity que retornará um número entre 0 e 1.0 dependendo de como elas são semelhantes. Este exemplo usa o 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

Verifique se o seu console está aberto ou você não vai ver nada 🙂

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

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

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

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

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

 > fuzzaldrin.filter(['international', 'splint', 'tinder'], 'int'); < ["international", "splint"] 
 (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/

    Intereting Posts