Chaque utilisateur a déjà eu des fautes de frappe lors de l'écriture de requêtes de recherche. L'absence de mécanismes qui corrigent les fautes de frappe conduit à la publication de résultats non pertinents, voire à leur absence. Par conséquent, pour rendre le moteur de recherche plus orienté utilisateur, des mécanismes de correction d'erreurs y sont intégrés.

La tâche de corriger les fautes de frappe, à première vue, semble plutôt simple. Mais si vous partez d'une variété d'erreurs, la mise en œuvre d'une solution peut être difficile. En général, la correction de faute de frappe est divisée en indépendant du contexte et sensible au contexte (où l'environnement du dictionnaire est pris en compte) . Dans le premier cas, les erreurs sont corrigées pour chaque mot séparément, dans le second - en tenant compte du contexte (par exemple, pour l'expression "elle est rentrée chez elle" dans le cas indépendant du contexte, la correction se produit pour chaque mot séparément, où nous pouvons obtenir "elle est rentrée chez elle", et dans le second cas, la correction correcte donnera "elle est rentrée chez elle").

Dans les requêtes de recherche de l'utilisateur russophone, quatre groupes principaux d'erreurs ne peuvent être distingués que pour une correction indépendante du contexte [ 1 ]:
1) les erreurs dans les mots eux-mêmes (disons mr → salut), cette catégorie comprend toutes sortes d'omissions, d'insertions et de permutations de lettres - 63,7%,
2) orthographe continue des mots - 16,9%,
3) disposition déformée (ghbdtn → hi) - 9,7%,
4) translittération (troène → salut) - 1,3%,
5) erreurs mixtes - 8,3%.

Les utilisateurs font des fautes de frappe dans environ 10 à 15% des cas. Dans le même temps, 83,6% des demandes ont une erreur, 11,7% - deux, 4,8% - plus de trois. Le contexte est important dans 26% des cas.

Ces statistiques ont été compilées sur la base d'un échantillon aléatoire du journal quotidien de Yandex en 2013 basé sur 10 000 requêtes. Dans le domaine public, il y a une présentation beaucoup plus ancienne de Yandex pour 2008, qui montre une distribution similaire des statistiques [ 2 ]. On peut en conclure que la distribution des variétés d'erreurs pour les requêtes de recherche, en moyenne, ne change pas avec le temps.

En général, le mécanisme de correction de faute est basé sur deux modèles: le modèle d'erreur et le modèle de langage. De plus, pour une correction indépendante du contexte, seul le modèle d'erreur est utilisé, et dans une correction dépendante du contexte, deux sont utilisés à la fois. Le modèle d'erreur est généralement soit la distance éditoriale ( distance Levenshtein, Damerau-Levenshtein, divers facteurs de pondération, des méthodes similaires à Soundex, etc. peuvent également être ajoutées ici - dans ce cas, la distance est appelée pondérée) , ou le modèle Bril-Moore, qui travaille sur les probabilités de transitions d'une ligne à l'autre. Bril et Moore positionnent leur modèle comme étant plus parfait, cependant, lors de l'une des dernières compétitions SpellRuEval, l'approche Damerau-Levenshtein a montré un meilleur résultat [ 3 ], malgré le fait que la distance Damerau-Levenshtein (la clarification n'est pas pondérée) n'utilise pas d'informations a priori sur les statistiques de non-garde . Cette observation est particulièrement indicative si les mêmes textes d'apprentissage ont été utilisés pour différentes implémentations d'auto-correcteurs dans la bibliothèque DeepPavlov.

De toute évidence, la possibilité d'une correction contextuelle complique la construction de l'autocorrecteur, car en plus du modèle d'erreur, le besoin d'un modèle de langage est ajouté. Mais si vous faites attention aux statistiques des fautes de frappe, alors ¾ toutes les requêtes de recherche mal écrites peuvent être corrigées sans contexte. Cela suggère que l'avantage d'au moins un auto-correcteur indépendant du contexte peut être très important.

En outre, une correction contextuelle pour corriger les fautes de frappe dans les demandes est très gourmande en ressources. Par exemple, dans l'un des discours de Yandex, la liste des paires pour corriger les fautes de frappe (bigrammes) de mots différait 10 fois par rapport au nombre de mots (unigrammes) , qu'en est-il alors des trigrammes? Évidemment, cela dépend fortement de la variabilité des requêtes. Cela semble un peu étrange lorsque l'autocorrecteur occupe la moitié de la mémoire du produit proposé par l'entreprise, dont le but n'est pas de résoudre le problème d'orthographe. Ainsi, la question de l'implémentation de corrections contextuelles dans les moteurs de recherche de produits logiciels peut être très controversée.

À première vue, on a l'impression qu'il existe de nombreuses solutions toutes faites pour tout langage de programmation qui peuvent être utilisées sans trop d'immersion dans les détails du fonctionnement des algorithmes, y compris dans les systèmes commerciaux. Mais en pratique, le développement de leurs solutions se poursuit. Par exemple, relativement récemment, Joom a pris sa propre décision de corriger les fautes de frappe en utilisant des modèles de langage pour les requêtes de recherche [ 4 ]. La situation est-elle vraiment difficile avec la disponibilité de solutions clé en main? À cette fin, dans la mesure du possible, un large aperçu des solutions existantes a été réalisé. Avant de commencer l'examen, nous déciderons de la façon dont la qualité de l'autocorrecteur est vérifiée.

Contrôle qualité

La question de la vérification de la qualité de l'autocorrecteur est très controversée. Une approche simple de la validation est la précision et le rappel. Conformément à la norme ISO, l'exactitude et l'exhaustivité sont complétées par l'exactitude (en anglais «corectness»).

L'exhaustivité (rappel) est calculée comme suit: une liste de mots corrects est fournie à l'autocorrecteur (Total_list_true) et le nombre de mots que l'autocorrecteur considère correct (Spellchecker_true), divisé par le nombre total de mots corrects (Total_list_true), sera considéré comme complet.

R e c a l l = S p e l l c h e c k e r_{t} r u e o v e r T o t a l_{l} i s t_{t} r u e

$Recall = {Spellchecker \ _true \ over Total \ _list \ _true}$

Pour déterminer la précision (Précision), une liste de mots incorrects (Total_list_false) est fournie à l'entrée de l'autocorrecteur et le nombre de mots que l'autocorrecteur considère incorrect (Spell_checker_false), divisé par le nombre total de mots incorrects (Total_list_false), est défini comme l'exactitude.

P r e c i s i o n = S p e l l c h e c k e r_{f} a l s e o v e r T o t a l_{l} i s t_{f} a l s e

$Precision = {Spellchecker \ _false \ over Total \ _list \ _false}$

Dans quelle mesure ces mesures sont généralement informatives et comment elles peuvent être utiles, chacune détermine indépendamment. Après tout, en fait, l'essence de ce test est que le mot est vérifié dans le dictionnaire de formation. L'exactitude peut être considérée comme une mesure plus visuelle, selon laquelle l'autocorrecteur pour chaque mot de l'ensemble de test de mots incorrects forme une liste de candidats de remplacement pour lesquels ce mot incorrect peut être corrigé (gardez à l'esprit qu'il peut y avoir des mots qui ne figurent pas dans le dictionnaire de formation) . Supposons que la taille d'une telle liste de candidats remplaçants soit de 5. Sur la base du fait que la taille de la liste est de 5, 6 groupes seront formés, dans l'un desquels nous mettrons chacun de nos mauvais mots originaux selon le principe suivant: dans le 1er groupe - si dans la liste des candidats de remplacement, le mot correct dans lequel nous sommes censés être est 1er, dans le 2e s'il est 2e, etc., et dans le dernier groupe, si le mot correct supposé ne figure pas dans la liste des candidats de remplacement. Bien sûr, plus le nombre de mots est tombé dans le 1er groupe et moins dans le 6ème, mieux fonctionne l'autocorrecteur.

Les auteurs ont considéré l'approche envisagée dans l'article [ 5 ], dans laquelle les auto-correcteurs indépendants du contexte avec un biais pour la norme ISO ont été comparés. Il fournit également des liens vers d'autres méthodes d'évaluation de la qualité.

D'une part, cette approche n'est pas basée sur des statistiques brutes, qui peuvent être basées sur le modèle d'erreur de Brill-Moore [ 6 ] ou le modèle d'erreur de distance pondérée Damerau-Levenshtein.

Pour vérifier la qualité du travail d'un correcteur automatique indépendant du contexte, nous avons créé notre propre générateur de faute de frappe, qui a généré des fautes de frappe de la mauvaise mise en page et des fautes d'orthographe sur la base des statistiques sur les fautes de frappe soumises par Yandex. Pour les fautes d'orthographe, des insertions, remplacements, suppressions, réarrangements aléatoires ont été générés, et le nombre d'erreurs a également varié en fonction de ces statistiques. Pour les erreurs dans la disposition déformée, le mot correct a été changé caractère par caractère entièrement conformément au tableau de traduction des caractères.

Ensuite, une série d'expériences a été menée pour la liste complète des mots du dictionnaire d'apprentissage (les mots du dictionnaire d'apprentissage ont été corrigés pour les mots incorrects en fonction de la probabilité d'une faute de frappe particulière) . En moyenne, l'autocorrecteur corrige correctement les mots dans 75% des cas. Sans aucun doute, ce nombre sera réduit lorsque le dictionnaire d'apprentissage sera reconstitué avec des mots proches dans une distance éditoriale, une grande variété de formes de mots. Ce problème peut être résolu en complétant avec des modèles de langage, mais il convient de garder à l'esprit que la quantité de ressources requises augmentera considérablement.

Solutions prêtes à l'emploi

La réflexion sur des solutions toutes faites a été menée en mettant l'accent sur leur propre usage, et la priorité a été donnée aux auto-correcteurs qui répondent à trois critères:
1) langage d'implémentation,
2) type de licence,
3) possibilité de mise à jour.

Dans le développement de produits, Java est considéré comme l'un des plus populaires, donc la priorité lui a été accordée lors de la recherche de bibliothèques. Parmi les licences pertinentes: MIT, Public, Apache, BSD. Mise à jour - pas plus de 2 ans après la dernière mise à jour. Au cours de la recherche, des informations supplémentaires ont été enregistrées, par exemple sur la plate-forme prise en charge, les programmes supplémentaires requis, les fonctionnalités de l'application, les difficultés possibles pour la première utilisation, etc. Des liens avec des ressources de base et utiles vers les sources sont donnés à la fin de l'article. En général, s'il n'est pas limité aux critères ci-dessus, le nombre de solutions existantes est important. Jetons un bref coup d'œil aux principaux et accordons plus d'attention à quelques-uns seulement.

Historiquement, l'un des plus anciens correcteurs automatiques est Ispell (International Spell), écrit en assembleur en 1971, transféré plus tard à C et utilisant la distance éditoriale Damerau-Levenshtein comme modèle d'erreurs. Pour lui, il existe même un dictionnaire en russe. Par la suite, il a été remplacé par deux correcteurs automatiques HunSpell (anciennement MySpell ) et Aspell . Les deux sont implémentés en C ++ et sont distribués sous licences GPL. HunSpell est également couvert par la GPL / MPL et est utilisé pour corriger les fautes de frappe dans OpenOffice, LibreOffice, Google Chrome et d'autres outils.

Il existe de nombreuses solutions JS pour Internet et les navigateurs (cela inclut: phrases nodehun , nspell , node-markdown-spellcheck , Proofreader , Spellcheck-API - un groupe de solutions basées sur l'auto- correcteur Hunspell ; grunt-spell - pour NodeJS; yaspeller- ci - wrapper pour Yandex.Speller auto- corrector , distribué sous MIT; rousseau - Relecteur léger en JS - utilisé pour l'orthographe).

La catégorie des solutions payantes comprend: Spellex ; Vérificateur d'orthographe du code source - en tant qu'application de bureau; pour JS: nanospell ; pour Java: Keyoti RapidSpell Spellchecker , JSpell SDK , WinterTree (WinterTree peut même acheter du code source pour 5000 $).

L'auto-correcteur de Peter Norwig est largement utilisé, dont le code Python est accessible au public dans l'article « Comment écrire un correcteur orthographique » [ 7 ]. Basé sur cette solution simple, les auto- correcteurs ont été construits dans d'autres langues, par exemple: Norvig-spell-check , scala-norvig-spell-check (sur Scala), toy-orthographe-correcteur - Golang Spellcheck (sur GO), pyspellchecker (sur Python) . Bien sûr, nous ne parlons pas ici de modèles de langage et de correction contextuelle.

Pour les éditeurs de texte, en particulier pour VIM made vim-dialect , vim-ditto - distribué sous licence publique; pour Notepad ++ développé par DspellCheck en C ++, licence GPL; Emacs dispose d'un outil de détection automatique des langues lors de l'impression, appelé langage de devinettes , distribué sous licence publique.

Il existe des services distincts des géants de la recherche: Yandex.Speller - de Yandex, à propos de l'emballage car il a été mentionné ci-dessus, google-api-spelling-java (respectivement, de Google).

Bibliothèques gratuites pour Java: languagetool (sous licence LGPL), s'intègre à la bibliothèque de recherche de texte Lucene et permet l'utilisation de modèles de langage, Java version 8 est requis; Jazzy (un analogue d' Aspell ) est sous licence LGPLv2 et n'a pas été mis à jour depuis 2005, et en 2013 a été porté sur GitHub. À l'image de cet auto-correcteur, une solution distincte a été faite [ 8 ]; Jortho (Java Orthography) est distribué sous la GPL et permet une utilisation gratuite exclusivement à des fins non commerciales, à des fins commerciales - moyennant des frais supplémentaires; Jaspell (sous licence BSD et n'a pas été mis à jour depuis 2005); Open Source Java Suggester - n'a pas été mis à jour depuis 2013, distribué par SoftCorporation LLC et permet une utilisation commerciale; LuceneSpellChecker est un autocorrecteur Lucene écrit en Java et distribué sous la licence Apache.

Pendant longtemps, Wolf Garbe a traité les fautes de frappe, il a proposé les algorithmes SymSpell (sous la licence MIT) et LinSpell (sous la LGPL) avec des implémentations C # [ 9 ] qui utilisent la distance Damerau-Levenshtein pour le modèle d'erreur. La particularité de leur implémentation est qu'au stade de générer des erreurs possibles pour le mot d'entrée, seules les suppressions sont utilisées, au lieu de toutes sortes de suppressions, insertions, remplacements et permutations. En comparaison avec la mise en œuvre de l'auto-correcteur de Peter Norwig, les deux algorithmes fonctionnent plus rapidement pour cette raison, tandis que l'augmentation de la vitesse augmente considérablement si la distance Damerau-Levenshtein devient supérieure à deux. De plus, du fait que seules des suppressions sont utilisées, le temps de formation du dictionnaire est réduit. La différence entre les deux algorithmes est que LinSpell est plus économique en mémoire et plus lent en vitesse de recherche, SymSpell - vice versa. Dans une version ultérieure, SymSpell corrige les erreurs d'orthographe fractionnée. Les modèles de langage ne sont pas utilisés.

Yandex.Speller , JamSpell [ 10 ], DeepPavlov [ 11 ] sont parmi les plus récents et prometteurs pour l'utilisation d'auto-correcteurs travaillant avec des modèles de langage et corrigeant les fautes de frappe contextuelles . Les 2 derniers sont distribués gratuitement: JamSpell (MIT), DeepPavlov (sous Apache).

Yandex.Speller utilise l'algorithme CatBoost, fonctionne avec plusieurs langues et corrige toutes sortes d'erreurs, même en tenant compte du contexte. La seule solution trouvée qui corrige les erreurs de mise en page et la translittération incorrectes. La solution est polyvalente, ce qui la rend populaire. Son inconvénient est qu'il s'agit d'un service à distance, et les restrictions et conditions d'utilisation peuvent être trouvées ici [ 12 ]. Le service fonctionne avec un nombre limité de langues; vous ne pouvez pas ajouter de mots vous-même et gérer le processus de correction. Conformément à la ressource [ 3 ] selon les résultats du concours RuSpellEval, cet auto-correcteur a montré la plus haute qualité de corrections. JamSpell est le correcteur automatique le plus rapide connu (implémentation C ++), il existe des classeurs prêts à l'emploi pour d'autres langages. Corrige les erreurs uniquement dans les mots eux-mêmes et fonctionne avec une langue spécifique. Vous ne pouvez pas utiliser la solution au niveau des unigrammes et des bigrammes. Pour obtenir une qualité acceptable, un grand texte de formation est requis.
DeepPavlov a quelques bonnes pratiques, cependant, l'intégration de ces solutions et le support ultérieur dans leur propre produit peuvent poser des problèmes, car travailler avec eux nécessite de se connecter à un environnement virtuel et d'utiliser une version antérieure de Python 3.6. DeepPavlov propose un choix de trois implémentations d'auto- correcteurs prêtes à l'emploi, dans deux desquelles les modèles d'erreur de Bril-Moore sont utilisés et dans deux modèles de langage. Il ne corrige que les fautes d'orthographe et l'option avec un modèle d'erreurs basé sur la distance Damerau-Levenshtein peut corriger les erreurs d'écriture continue.

Je mentionnerai une autre des approches modernes de correction des fautes de frappe, qui est basée sur l'utilisation de représentations vectorielles des mots (Word Embeddings). Son avantage est qu'il peut être utilisé pour construire un correcteur automatique pour corriger les mots en fonction du contexte. Plus de détails sur cette approche peuvent être trouvés ici [ 13 ]. Mais afin de l'utiliser pour corriger les fautes de frappe des requêtes de recherche, vous devrez accumuler un grand journal de requêtes. De plus, le modèle lui-même peut être assez volumineux en termes de consommation de mémoire, ce qui affectera la complexité de l'intégration dans le produit.

Choix de Naumen

Parmi les solutions prêtes à l'emploi pour Java, un auto-correcteur de Lucene a été sélectionné (distribué sous licence Apache). Vous permet de corriger les fautes de frappe dans les mots. Le processus d'apprentissage est rapide: par exemple, la formation d'une structure de données de dictionnaire spéciale - un index pour 3 millions de lignes était de 30 secondes sur un processeur Intel Core i5-8500 3,00 GHz, 32 Go de RAM, Lucene 8.0.0. Dans les versions antérieures, le délai peut être 2 fois plus long. La taille du dictionnaire d'apprentissage est de 3 millions de lignes (~ 73 Mb fichier txt), la structure de l'index est ~ 235 Mb. Pour le modèle d'erreur, vous pouvez choisir la distance de Jaro-Winkler, Levenshtein, Damerau-Levenshtein, N-Gram, si nécessaire, vous pouvez ajouter la vôtre. Si nécessaire, il est possible de connecter un modèle de langage [ 14 ]. Des modèles sont connus depuis 2001, mais leur comparaison avec des solutions modernes bien connues dans le domaine public n'a pas été trouvée. L'étape suivante consiste à vérifier leur travail.

La solution basée sur Lucene qui en résulte ne corrige que les erreurs dans les mots eux-mêmes. Il n'est pas difficile d'ajouter une correction d'une disposition de clavier déformée à une telle solution au moyen d'une table de traduction appropriée, réduisant ainsi la possibilité de sortie non pertinente à 10% (conformément aux statistiques de typo). De plus, il est facile d'ajouter une écriture séparée de 2 mots fusionnés et une translittération.

Les principaux inconvénients de la solution sont le besoin de connaissance de Java, le manque de cas d'utilisation détaillés et de documentation détaillée, ce qui se traduit par une diminution de la vitesse de développement des solutions pour les spécialistes de la Data Science. De plus, les fautes de frappe avec une distance Damerau-Levenshtein supérieure à 2 ne sont pas corrigées. Encore une fois, si nous partons des statistiques de fausses déclarations, plus de 2 erreurs dans un mot se produisent moins fréquemment que dans 5% des cas. La nécessité de compliquer l'algorithme, notamment une augmentation de la consommation mémoire, est-elle justifiée? Cela dépend déjà du cas du client. S'il existe des ressources supplémentaires, pourquoi ne pas les utiliser?

Ressources clés pour des correcteurs automatiques abordables :

Les références

Présentation des solutions Open Typo Correction

Contrôle qualité

Solutions prêtes à l'emploi

Choix de Naumen

More articles: