Statistiques sur les fautes de frappe dans le monde réel ?

Question

Où puis-je trouver des statistiques sur les fautes de frappe dans le monde réel ?

J'essaie de faire correspondre le texte saisi par les gens à des objets internes, et les gens ont tendance à faire des fautes d'orthographe.
Il y a 2 types d'erreurs :

1. typos - "Helllo" au lieu de "Hello" / "Satudray" au lieu de "Saturday", etc.
2. Spelling - "Shikago" au lieu de "Chicago".

J'utilise Distance Damerau-Levenshtein pour les fautes de frappe et Double Métaphone pour l'orthographe (implémentations Python aquí y aquí ).

Je veux me concentrer sur la méthode Damerau-Levenshtein (ou simplement edit-distance ). Les implémentations des manuels utilisent toujours '1' pour le poids des suppressions, insertions, substitutions et transpositions. Bien que cela soit simple et permette de créer de beaux algorithmes, cela ne correspond pas à la "réalité" / aux "probabilités du monde réel".

Exemples :

• Je suis sûr que la probabilité de "Helllo" ("Bonjour") est plus grande que celle de "Helzlo", pourtant ils sont tous deux à une distance d'une édition.
• "Gello" est plus proche que "Qello" de "Hello" sur un clavier QWERTY.
• Translittérations Unicode : Quelle est la distance "réelle" entre "München" et "Munchen" ?

Quelles devraient être les pondérations du "monde réel" pour les suppressions, insertions, substitutions et transpositions ?

Même Le très cool correcteur d'orthographe de Norvig utilise la distance d'édition non pondérée.

BTW- Je suis sûr que les poids doivent être des fonctions et non pas de simples flottants (selon les exemples ci-dessus)...

Je peux ajuster l'algorithme, mais où puis-je "apprendre" ces poids ? Je n'ai pas accès à Données à l'échelle de Google ...

Je dois les deviner ?

EDIT - j'essaie de répondre aux questions des utilisateurs :

• Mon algorithme non pondéré actuel échoue souvent lorsqu'il est confronté à des coquilles pour les raisons susmentionnées. "Return on Tursday" : toute "vraie personne" peut facilement dire que le jeudi est plus probable que le mardi, et pourtant ils sont tous les deux à une distance d'une édition ! (Oui, j'enregistre et mesure mes performances).
• Je développe un moteur de recherche de voyage NLP, mon dictionnaire contient donc ~25K destinations (qui devraient passer à 100K), des expressions temporelles ~200 (1K prévu), des expressions de personnes ~100 (300 prévu), des expressions d'argent ~100 (500 prévu), des "mots logiques de colle" ("de", "beau", "appartement") ~2K (10K prévu) et ainsi de suite...
• L'utilisation de la distance d'édition est différente pour chacun des groupes de mots ci-dessus. J'essaie d'"auto-corriger quand c'est évident", c'est-à-dire à 1 distance d'édition d'un seul autre mot du dictionnaire. J'ai beaucoup de d'autres règles adaptées à la main, par exemple le double métaphone qui ne se trouve pas à plus de 2 distances d'édition d'un mot du dictionnaire d'une longueur > 4... La liste des règles continue de s'allonger au fur et à mesure que j'apprends à partir de données réelles.
• "Combien de paires d'entrées de dictionnaire se situent dans votre seuil ?": eh bien, cela dépend du "système de pondération fantaisiste" et des données réelles (futures), n'est-ce pas ? Quoi qu'il en soit, j'ai mis en place des tests unitaires approfondis afin que chaque modification apportée au système ne fasse que l'améliorer (en fonction des entrées passées, bien sûr). La plupart des mots de moins de 6 lettres sont à une distance d'édition d'un mot qui est à une distance d'édition d'une autre entrée du dictionnaire.
• Aujourd'hui, lorsqu'il y a deux entrées de dictionnaire à la même distance de l'entrée, j'essaie d'appliquer diverses statistiques pour mieux deviner ce que l'utilisateur voulait dire (par exemple, Paris, France a plus de chances d'apparaître dans ma recherche que Pārīz, Iran).
• Le coût du choix d'un mot erroné est de renvoyer des résultats semi-aléatoires (souvent ridicules) à l'utilisateur final et de perdre potentiellement un client. Le coût de l'incompréhension est légèrement moins élevé : l'utilisateur sera invité à reformuler sa réponse.
• Le coût de la complexité en vaut-il la peine ? Oui, je suis sûr que oui. Vous n'imaginez pas la quantité de fautes de frappe que les gens envoient au système et attendent de lui qu'il les comprenne. Précision et rappel .

Answer 1

Une source possible de statistiques sur les fautes de frappe dans le monde réel serait dans le L'historique complet des modifications de Wikipédia .

http://download.wikimedia.org/

Vous pourriez également être intéressé par le RegExTypoFix de l'AWB.

http://en.wikipedia.org/wiki/Wikipedia:AWB/T

Answer 2

Je vous conseille de vérifier le trigramme alogrithme . À mon avis, il est plus efficace pour trouver les fautes de frappe que l'algorithme de distance d'édition. Il devrait également être plus rapide et si vous conservez le dictionnaire dans une base de données Postgres, vous pouvez utiliser l'index.

Vous pouvez trouver utile stackoverflow sujet à propos de google "Did you mean"

Answer 3

Notation de probabilité pour la correction orthographique de Church et Gale pourrait vous aider. Dans cet article, les auteurs modélisent les coquilles comme un canal bruyant entre l'auteur et l'ordinateur. L'annexe contient des tableaux pour les coquilles observées dans un corpus de publications d'Associated Press. Il existe un tableau pour chacun des types de coquilles suivants :

• suppression
• insertion
• substitution
• transposition

Par exemple, en examinant le tableau d'insertion, on peut voir que l a été incorrectement inséré après l 128 fois (le chiffre le plus élevé de cette colonne). En utilisant ces tableaux, vous pouvez générer les probabilités que vous recherchez.

Answer 4

Si la recherche est votre intérêt, je pense que continuer avec cet algorithme, en essayant de trouver des poids décents serait fructueux.

Je ne peux pas vous aider avec les statistiques de typo, mais je pense que vous devriez aussi jouer avec la difflib de python. Plus précisément, la méthode ratio() de SequenceMatcher. Elle utilise un algorithme que la docs http://docs.python.org/library/difflib.html claim convient bien aux correspondances qui ont l'air correctes, et peut être utile pour compléter ou tester ce que vous faites.

Pour les programmeurs python qui recherchent simplement les fautes de frappe, c'est un bon point de départ. Un de mes collègues a utilisé à la fois la distance d'édition de Levenshtein et le ratio() de SequenceMatcher et a obtenu de bien meilleurs résultats avec le ratio().

Answer 5

Quelques questions pour vous, afin de vous aider à déterminer si vous devez poser votre question "où puis-je trouver des poids réels" :

Avez-vous réellement mesuré l'efficacité de la mise en œuvre de la pondération uniforme ? Comment ?

Combien d'"objets internes" différents avez-vous, c'est-à-dire quelle est la taille de votre dictionnaire ?

Comment utilisez-vous réellement la distance d'édition, par exemple John/Joan, Marmaduke/Marmeduke, Featherstonehaugh/Featherstonhaugh : s'agit-il de "1 seule erreur" ou d'une différence de 25% / 11,1% / 5,9% ? Quel seuil utilisez-vous ?

Combien de paires d'entrées de dictionnaire se situent dans votre seuil (par exemple, John vs Joan, Joan vs Juan, etc.) ? Si vous introduisiez un système de pondération fantaisiste, combien de paires d'entrées de dictionnaire passeraient (a) de l'intérieur du seuil à l'extérieur (b) vice versa ?

Que faites-vous si John et Juan figurent tous deux dans votre dictionnaire et que l'utilisateur tape Joan ?

Quels sont les pénalités/coûts de (1) choisir le mauvais mot du dictionnaire (pas celui que l'utilisateur voulait dire) (2) ne pas reconnaître l'entrée de l'utilisateur ?

L'introduction d'un système de pondération compliqué réduira-t-elle réellement les probabilités des deux types d'erreur susmentionnés dans une mesure suffisante pour que la complication et la vitesse plus lente en valent la peine ?

BTW, comment savez-vous quel clavier l'utilisateur utilisait ?

Mise à jour :

"""Mon algorithme non pondéré actuel échoue souvent lorsqu'il est confronté à des coquilles pour les raisons ci-dessus. "Return on Tursday" : toute "vraie personne" peut facilement dire que le jeudi est plus probable que le mardi, alors qu'ils sont tous deux à une distance d'édition ! (Oui, je consigne et mesure mes performances).""""

Oui, jeudi -> jeudi en omettant un "h", mais mardi -> jeudi en substituant un "r" au lieu d'un "e". E et R sont l'un à côté de l'autre sur les claviers qwERty et azERty. Chaque "vraie personne" peut facilement devinez que le jeudi est plus probable que le mardi. Même si les statistiques et les suppositions indiquent que le jeudi est plus probable que le mardi (peut-être que l'omission de h coûtera 0,5 et que e->r coûtera 0,75), la différence (peut-être 0,25) sera-t-elle suffisamment significative pour toujours choisir le jeudi ? Votre système peut-il demander ou demandera-t-il : "Vouliez-vous dire mardi ?" ou choisira-t-il simplement le jeudi ?