regex - Pesquisa difusa em JavaScript que faz sentido

Estou procurando uma biblioteca JavaScript de busca difusa para filtrar um array. Já tentei usar fuzzyset.js e fuse.js, mas os resultados são terríveis (existem demos que você pode testar nas páginas vinculadas).

Depois de ler um pouco sobre a distância de Levenshtein, parece-me uma aproximação ruim do que os usuários estão procurando quando digitam. Para aqueles que não sabem, o sistema calcula quantas inserções, deleções e substituições são necessárias para fazer duas strings coincidirem.

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

Quero usar isso no contexto de conclusão de texto, então, se eu tiver um array ['international', 'splint', 'tinder'], e minha consulta for int, acho que international deveria ter uma classificação mais alta do que splint, mesmo que o primeiro tenha uma pontuação (maior=pior) de 10 em comparação com 3 do segundo.

Então, o que eu estou procurando (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 maneira diferente dependendo de onde elas aparecem em uma palavra (manipulações no início custando mais do que no final)
• Retorna uma lista de resultados ordenados por relevância

Alguém já se deparou com algo assim? Eu sei que o Stack Overflow 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 de distância de edição afim atribuem um custo relativamente menor 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 particulares

Para a distância de 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 similar, que não se baseia em um modelo de distância de edição, é 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 se baseia no número e na ordem dos caracteres comuns entre duas cadeias de caracteres.

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

(parecem ser destinados principalmente para strings curtas)

Para fins de conclusão de texto, os métodos Monger-Elkan e Jaro-Winkler parecem fazer mais sentido. A adição de Winkler à métrica Jaro efetivamente dá mais peso ao início das palavras. E o aspecto afim do Monger-Elkan significa que a necessidade de completar uma palavra (que é simplesmente uma sequência de adições) não a desfavorecerá de forma muito pesada.

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 affine-gap ajustada, proposta por Monge e Elkan, teve o melhor desempenho entre várias métricas de distância de edição de strings. 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 com o Jaro-Winkler é substituir as correspondências exatas de tokens usadas no TFIDF por correspondências aproximadas de tokens baseadas no esquema Jaro-Winkler. Essa combinação apresenta desempenho ligeiramente melhor do que o Jaro-Winkler ou TFIDF isoladamente, em média, e ocasionalmente apresenta desempenho muito melhor. Também é próximo em desempenho de uma combinação aprendida de várias das melhores métricas consideradas neste artigo.

Resposta #1

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 busca do Sublime. https://github.com/farzher/fuzzysort

O único erro de digitação que ele permite é uma inversão. É bem 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}]

Resposta #2

Boa pergunta! Mas meu pensamento é que, em vez de tentar modificar o Levenshtein-Demerau, você talvez esteja melhor tentando um algoritmo diferente ou combinando/pesando os resultados de dois algoritmos.

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

Eu pesquisei por "melhor que Levenshtein" e, entre outras coisas, encontrei isto:

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

Isto menciona várias medidas de "distância de string". Três que pareceram particularmente relevantes para o seu requisito seriam:

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

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

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

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

Dependendo do tamanho da sua lista/ banco de dados, esses algoritmos podem ser moderadamente caros. Para uma busca aproximada que implementei, usei um número configurável de N-grams como "chaves de recuperação" do banco de dados e, em seguida, executei a medida de distância de strings mais cara para ordená-las em ordem de preferência.

Eu escrevi algumas notas sobre Pesquisa de Strings Ambíguas no SQL. Veja:

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

Resposta #3

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

function escapeRegExp(str: string) {
  return str.replace(/[.*+?^${}()|[\]\\]/g, '\\$&');
}

function fuzzyMatch(pattern, str) {
  pattern = '.*' + pattern.split('').map(l => `${escapeRegExp(l)}.*`).join('');
  const re = new RegExp(pattern);
  return re.test(str);
}

graças ao jt3k, atualizei a função para escapar regex

escapeRegExp conforme sugerido na documentação do MDN

Resposta #4

Aqui está uma técnica que usei algumas vezes... Ela dá resultados bem 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 string_similarity, que retornará um número entre 0 e 1.0 dependendo de quão semelhantes elas 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... dê uma brincada

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

Resposta #5

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

Isto é TypeScript, mas você pode remover as anotações de tipo e ainda funcionará bem como JavaScript puro.

/**
 * 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 do TypeScript