Recherche floue Javascript qui a du sens

Je recherche une bibliothèque JavaScript de recherche floue pour filtrer un tableau. J'ai essayé d'utiliser fuzzyset.js et fuse.js , mais les résultats sont terribles (il existe des démos que vous pouvez essayer sur les pages liées).

Après avoir lu quelques lectures sur la distance de Levenshtein, cela me semble être une mauvaise approximation de ce que les utilisateurs recherchent lorsqu'ils tapent. Pour ceux qui ne le savent pas, le système calcule le nombre d' insertions , de suppressions et de substitutions nécessaires pour faire correspondre deux chaînes.

Un défaut évident, qui est fixé dans le modèle Levenshtein-Demerau, est que les deux blub et seins sont considérés également semblable à l' ampoule (chacun nécessitant deux substitutions). Il est clair, cependant, que l' ampoule ressemble plus à blub qu'à boob , et le modèle que je viens de mentionner le reconnaît en permettant des transpositions .

Je veux utiliser cela dans le contexte de la complétion de texte, donc si j'ai un tableau ['international', 'splint', 'tinder']et que ma requête est int , je pense que l' international devrait se classer plus haut que splint , même si le premier a un score (plus élevé = pire) de 10 contre ce dernier 3.

Donc, ce que je recherche (et je créerai s'il n'existe pas), c'est une bibliothèque qui fait ce qui suit:

• Pondère les différentes manipulations de texte
• Pondère chaque manipulation différemment en fonction de l'endroit où elles apparaissent dans un mot (les premières manipulations étant plus coûteuses que les manipulations tardives)
• Renvoie une liste de résultats triés par pertinence

Quelqu'un at-il rencontré quelque chose comme ça? Je me rends compte que StackOverflow n'est pas l'endroit où demander des recommandations logicielles, mais implicite (plus maintenant!) Dans ce qui précède est: est-ce que je pense à cela de la bonne façon?

Éditer

J'ai trouvé un bon article (pdf) sur le sujet. Quelques notes et extraits:

Les fonctions de distance d'édition affine attribuent un coût relativement inférieur à une séquence d'insertions ou de suppressions

la fonction de distance de Monger-Elkan (Monge & Elkan 1996), qui est une variante affine de la fonction de distance de Smith-Waterman (Durban et al.1998) avec des paramètres de coût particuliers

Pour la distance Smith-Waterman (wikipedia) , "Au lieu de regarder la séquence totale, l'algorithme Smith-Waterman compare des segments de toutes les longueurs possibles et optimise la mesure de similarité." C'est l'approche n-gramme.

Une métrique largement similaire, qui n'est pas basée sur un modèle de distance d'édition, est la métrique Jaro (Jaro 1995; 1989; Winkler 1999). Dans la littérature sur le couplage d'enregistrements, de bons résultats ont été obtenus en utilisant des variantes de cette méthode, qui est basée sur le nombre et l'ordre des caractères communs entre deux chaînes.

Une variante de ceci due à Winkler (1999) utilise également la longueur P du préfixe commun le plus long

(semble être principalement destiné aux chaînes courtes)

À des fins de complétion de texte, les approches Monger-Elkan et Jaro-Winkler semblent avoir le plus de sens. L'ajout de Winkler à la métrique Jaro pondère plus fortement les débuts des mots. Et l'aspect affine de Monger-Elkan signifie que la nécessité de compléter un mot (qui est simplement une séquence d'ajouts) ne le défavorisera pas trop.

Conclusion:

le classement TFIDF a obtenu les meilleurs résultats parmi plusieurs mesures de distance basées sur des jetons, et une mesure de distance d'édition affine-gap réglée proposée par Monge et Elkan a obtenu les meilleurs résultats parmi plusieurs mesures de distance d'édition de chaîne. Une métrique de distance étonnamment bonne est un schéma heuristique rapide, proposé par Jaro et étendu plus tard par Winkler. Cela fonctionne presque aussi bien que le schéma Monge-Elkan, mais c'est un ordre de grandeur plus rapide. Un moyen simple de combiner la méthode TFIDF et le Jaro-Winkler est de remplacer les correspondances de jetons exactes utilisées dans TFIDF par des correspondances de jetons approximatives basées sur le schéma Jaro-Winkler. Cette combinaison fonctionne légèrement mieux que Jaro-Winkler ou TFIDF en moyenne, et parfois beaucoup mieux. Il est également proche en termes de performances d'une combinaison savante de plusieurs des meilleures mesures prises en compte dans cet article.

Bonne question! Mais ma pensée est que, plutôt que d'essayer de modifier Levenshtein-Demerau, vous feriez peut-être mieux d'essayer un algorithme différent ou de combiner / pondérer les résultats de deux algorithmes.

Il me semble que les correspondances exactes ou proches du "préfixe de départ" sont quelque chose à quoi Levenshtein-Demerau n'accorde aucun poids particulier - mais vos attentes apparentes de l'utilisateur le feraient.

J'ai recherché "mieux que Levenshtein" et, entre autres, j'ai trouvé ceci:

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

Cela mentionne un certain nombre de mesures de «distance de chaîne». Trois qui semblaient particulièrement pertinents pour vos besoins seraient:

1. Distance de sous-chaîne commune la plus longue: nombre minimum de symboles à supprimer dans les deux chaînes jusqu'à ce que les sous-chaînes résultantes soient identiques.

2. Distance q-gramme: somme des différences absolues entre les vecteurs N-gramme des deux chaînes.

3. Distance de Jaccard: 1 minute le quotient des N-grammes partagés et de tous les N-grammes observés.

Peut-être pourriez-vous utiliser une combinaison pondérée (ou un minimum) de ces métriques, avec Levenshtein - sous-chaîne commune, N-gramme commun ou Jaccard préféreront tous fortement des chaînes similaires - ou peut-être essayer simplement d'utiliser Jaccard?

Selon la taille de votre liste / base de données, ces algorithmes peuvent être modérément coûteux. Pour une recherche floue que j'ai implémentée, j'ai utilisé un nombre configurable de N-grammes comme "clés de récupération" à partir de la base de données, puis j'ai exécuté la mesure de distance de chaîne coûteuse pour les trier par ordre de préférence.

J'ai écrit quelques notes sur Fuzzy String Search dans SQL. Voir:

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

J'ai essayé d'utiliser des bibliothèques floues existantes comme fuse.js et je les ai également trouvées terribles, alors j'en ai écrit une qui se comporte essentiellement comme la recherche de sublime. https://github.com/farzher/fuzzysort

La seule faute de frappe autorisée est une transposition. C'est assez solide (1k étoiles, 0 problème) , très rapide et gère votre cas facilement:

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

Voici une technique que j'ai utilisée quelques fois ... Elle donne de très bons résultats. Mais ne fait pas tout ce que vous avez demandé. En outre, cela peut être coûteux si la liste est massive.

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

Passez deux chaînes string_similarityauxquelles renverra un nombre entre 0et en 1.0fonction de leur similitude. Cet exemple utilise Lo-Dash

Exemple d'utilisation ...

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

Aussi .... avoir un violon

Assurez-vous que votre console est ouverte ou vous ne verrez rien :)

c'est ma fonction courte et compacte pour la correspondance floue:

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

vous pouvez jeter un oeil à https://github.com/atom/fuzzaldrin/ lib d' Atom .

il est disponible sur npm, a une API simple et a bien fonctionné pour moi.

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

Mise à jour de novembre 2019. J'ai trouvé le fusible pour avoir des mises à niveau assez décentes. Cependant, je ne pouvais pas le faire utiliser des booléens (c'est-à-dire les opérateurs OR, AND, etc.) ni utiliser l'interface de recherche API pour filtrer les résultats.

J'ai découvert nextapps-de/flexsearch: https://github.com/nextapps-de/flexsearch et je crois qu'il surpasse de loin beaucoup des autres bibliothèques de recherche javascript que j'ai essayées, et il prend en charge boolle filtrage des recherches et la pagination.

Vous pouvez saisir une liste d'objets javascript pour vos données de recherche (c'est-à-dire le stockage), et l'API est assez bien documentée: https://github.com/nextapps-de/flexsearch#api-overview

Jusqu'à présent, j'ai indexé près de 10 000 enregistrements et mes recherches sont presque immédiates; c'est-à-dire une durée imperceptible pour chaque recherche.

voici la solution fournie par @InternalFX, mais en JS (je l'ai utilisée pour partager):

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
}

J'ai résolu les problèmes avec la solution bigram CoffeeScript d'InternalFx et en ai fait une solution générique de n-gramme (vous pouvez personnaliser la taille des grammes).

Il s'agit de TypeScript, mais vous pouvez supprimer les annotations de type et cela fonctionne également bien en tant que JavaScript vanilla.

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

Exemples:

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

Essayez-le dans le 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/

Découvrez mon add-on Google Sheets appelé Flookup et utilisez cette fonction:

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

Les détails des paramètres sont:

1. lookupValue: la valeur que vous recherchez
2. tableArray: la table que vous souhaitez rechercher
3. lookupCol: la colonne que vous souhaitez rechercher
4. indexNum: la colonne à partir de laquelle vous voulez que les données soient renvoyées
5. threshold: le pourcentage de similarité en dessous duquel les données ne doivent pas être renvoyées
6. rank: la nième meilleure correspondance (c'est-à-dire si la première correspondance ne vous convient pas)

Cela devrait satisfaire vos exigences ... même si je ne suis pas sûr du point numéro 2.

En savoir plus sur le site officiel .