Algorithme de recherche floue (algorithme approximatif d'appariement des chaînes de caractères))
je souhaite créer un algorithme de recherche flou. Cependant, sur des heures de recherche je suis vraiment en difficulté.
je veux créer un algorithme qui effectue une recherche floue sur une liste de noms d'écoles.
c'est Ce que j'ai regardé jusqu'à présent:
la plupart de mes recherches pointent vers "chaîne de caractères métriques" sur Google et Stackoverflow tels que:
- Levenshtein distance
- distance de damerau-Levenshtein
- algorithme de Needleman-Wunsch
Cependant cela donne juste un score de comment similaires 2 chaînes le sont. La seule façon que je peux penser à la mettre en œuvre comme un algorithme de recherche est d'effectuer une recherche linéaire et d'exécuter l'algorithme métrique de la chaîne de caractères pour chaque chaîne de caractères et de retourner les chaînes de caractères avec des scores au-dessus d'un certain seuil. (À l'origine j'avais mes cordes emmagasinées dans un arbre, mais ça ne m'aidera pas ici!)
bien que ce ne soit pas une si mauvaise idée pour les petites listes, ce serait problématique pour les listes avec disons 100.000 noms, et l'Utilisateur a effectué de nombreuses requêtes.
un autre algorithme que j'ai regardé est le méthode de vérification de L'orthographe, où vous faites juste une recherche de toutes les fautes d'orthographe possibles. Toutefois, cela est aussi très inefficace car il nécessite plus de 75 000 mots pour un mot de longueur 7 et le nombre d'erreurs de 2.
ce dont j'ai besoin?
quelqu'un Peut-il svp me suggérer un bon algorithme de recherche fuzzy efficace. avec:
- Nom de l'algorithme
- Comment ça marche ou un lien à la façon dont il fonctionne
- Pro et le contre, et quand il est utilisé au mieux (en option)
je comprends que tous les algorithmes ont leurs avantages et inconvénients et il n'y a pas de algorithme.
4 réponses
considérant que vous essayez de faire une recherche floue sur une liste de noms d'école, Je ne pense pas que vous voulez aller pour la similarité de chaîne traditionnelle comme la distance Levenshtein. Mon hypothèse est que vous prenez l'entrée d'un utilisateur (soit entrée clavier ou parlé au téléphone), et vous voulez trouver rapidement l'école correspondante.
les mesures de Distance vous indiquent comment deux chaînes similaires sont basées sur des substitutions, des suppressions et des insertions. Mais ces algorithmes ne vous disent pas n'importe quoi sur la façon dont les chaînes sont similaires comme des mots dans un langage humain.
prenons, par exemple, les mots "smith," "smythe," et "frappa". Je peux passer de "smythe" à "smith" en deux étapes:
smythe -> smithe -> smith
smote -> smite -> smith
Si les deux ont la même distance que chaînes de caractères, mais aussi mots, ils sont très différents. Si quelqu'un vous a dit (langue parlée) qu'il cherchait pour "Symthe College", tu dirais presque certainement, " Oh, je pense que tu veux dire Smith."Mais si quelqu'un disait "Smote College", tu n'aurais aucune idée de ce dont il parlait.
ce dont vous avez besoin est un phonétique algorithmeSoundex ou Metaphone. Fondamentalement, ces algorithmes décomposent un mot en phonèmes et créer une représentation de la façon dont le mot est prononcé dans la langue parlée. Vous pouvez ensuite comparer le résultat avec une liste connue des mots pour trouver une correspondance.
un Tel système serait beaucoup plus rapide qu'une métrique de distance. Considérer qu'avec une distance métrique, vous devez comparer l'entrée de l'utilisateur avec chaque mot dans la liste pour obtenir la distance. Cela coûte cher sur le plan informatique et les résultats, comme je l'ai démontré avec "smith" et "smote" peuvent être ridiculement mauvais.
en utilisant un algorithme phonétique, vous créez la représentation phonématique de chacun de vos mots connus et la placez dans un Dictionnaire (une carte de hachage ou peut-être un trie). C'est un coût de démarrage. Ensuite, chaque fois que l'utilisateur entre un terme de recherche, vous créez la représentation phonématique de son entrée et cherchez dans votre dictionnaire. C'est beaucoup plus rapide et produit de bien meilleurs résultats.
considérez aussi que lorsque les gens orthographient mal les noms propres, ils reçoivent presque toujours la bonne lettre, et le plus souvent qu'ils ne prononcent pas la mauvaise orthographe sons comme le mot qu'ils ont essayé de orthographe. Si c'est le cas, alors les algorithmes phonétiques sont définitivement la voie à suivre.
vous confondez les algorithmes de recherche floue avec l'implémentation: une recherche floue d'un mot peut donner 400 résultats de tous les mots qui ont une distance Levenshtein de, disons, 2. Mais, pour l'utilisateur, vous devez afficher seulement le top 5-10.
mise en Œuvre-sage, vous aurez pré-traitement de tous les mots dans le dictionnaire et enregistrer les résultats dans une DB. Les mots populaires (et leurs goûts flous) seront sauvegardés dans cache-layer - de sorte que vous n'aurez pas à frapper la base de données pour chaque demande.
vous pouvez ajouter une couche AI qui ajoutera les fautes d'orthographe les plus courantes et les ajoutera au DB. Et etc.
j'ai écrit un article sur comment j'ai implémenté une recherche floue:
https://medium.com/@Srekel/implementing-a-fuzzy-search-algorithm-for-the-debuginator-cacc349e6c55
la mise en œuvre est en Github et est dans le domaine public, alors n'hésitez pas à jeter un oeil.
https://github.com/Srekel/the-debuginator/blob/master/the_debuginator.h#L1856
les bases de cela est: Split toutes les chaînes que vous serez à la recherche pour dans les pièces. Donc si vous avez des chemins, alors "C:\documents\lol.txt" est peut-être "C", "documents", "lol", "txt".
vous Assurer de minuscules ces chaînes pour vous assurer qu'il est insensible à la casse. (Peut-être seulement le faire si la chaîne de recherche est en minuscule).
puis associez votre chaîne de recherche à celle-ci. Dans mon cas, je veux l'apparier quel que soit l'ordre, donc "loldoc" correspondrait toujours au chemin ci-dessus même si "lol" vient après "doc".
l'appariement doit avoir un certain marquer pour être bon. La partie la plus importante, je pense, est consécutifs correspondant à, donc plus il y a de personnages qui se suivent les uns les autres, mieux c'est. Donc " doc "est mieux que"dcm".
alors vous voudrez probablement donner un score supplémentaire pour un match qui est à la démarrer d'une partie. Donc vous obtenez plus de points pour "doc" que pour "ocu".
Dans mon cas, j'ai aussi donner plus de points correspondant à l' d'une partie.
Et enfin, vous pouvez envisager de donner des points supplémentaires pour correspondre à la dernière partie(s). Cela fait en sorte que l'appariement du nom de fichier/fin des scores plus élevé que les dossiers menant à elle.
Un algorithme simple pour "une sorte de recherche floue"
pour être honnête, dans certains cas, la recherche floue est surtout inutile et je pense qu'un algorithme plus simple peut améliorer le résultat de la recherche Tout en fournissant le sentiment que nous effectuons toujours une recherche floue.
Voici mon cas d'utilisation: Filtrage d'une liste de pays à l'aide de "recherche Floue".
la liste avec laquelle je travaillais comprenait deux pays, à commencer par Z: La Zambie et Zimbabwe.
j'ai été en utilisant Fusejs.
dans ce cas, lors de la saisie de l'aiguille "zam", le résultat était d'avoir 19 correspondances et la plus pertinente pour tout humain (Zambie) En bas de la liste. Et la plupart des autres pays dans le résultat, n'ont même pas la lettre " z " dans leur nom.
C'était pour une application mobile où vous pouvez vous procurer un pays à partir d'une liste. C'était supposé être un peu comme quand vous devez choisir un contact à partir du téléphone contacter. Vous pouvez filtrer la liste de contacts en saisissant un terme dans la boîte de recherche.
IMHO, ce genre de contenu limité à rechercher ne doit pas être traité d'une manière qui fera que les gens se demanderont "qu'est-ce que ça fout?!?".
on pourrait suggérer de trier par correspondance la plus pertinente. Mais c'est hors de question dans ce cas parce que l'Utilisateur devra alors toujours trouver visuellement le "point D'intérêt" dans la liste réduite. Gardez à l'esprit que ceci est supposé être un filtrage outil, pas un moteur de recherche "à la Google". Le résultat doit donc être trié de manière prévisible. Et avant de filtrer le classement alphabétique. Si la liste filtrée doit être triée par ordre alphabétique sous-ensemble de la liste originale.
alors j'ai trouvé l'algorithme suivant ...
- saisissez l'aiguille ... dans ce cas: zam
- insérer le .* le modèle au début et à la fin de l'aiguille
- insérer le .* modèle entre chaque lettre de l'aiguille
- effectuer une recherche Regex dans la botte de foin en utilisant la nouvelle aiguille qui est maintenant .*z.*un.m.
Dans ce cas, l'utilisateur aura une conséquence attendue par trouver tout ce qui a en quelque sorte les lettres z, a et m apparaissant dans cet ordre. Toutes les lettres dans les aiguilles seront présents dans les matches dans le même ordre.
cela correspondra aussi aux noms de pays comme Mo zam bique ... qui est parfait.
je pense juste que parfois, nous ne devrions pas essayer de tuer une mouche avec un bazooka.