Simple vérification de l'orthographe algorithme

J'ai été chargé de la création d'un simple correcteur orthographique pour une mission, mais ont donné à peu près aucune directive, donc je me demandais si quelqu'un pouvait m'aider. Je ne suis pas après quelqu'un pour faire la mission pour moi, mais n'importe quelle direction ou de l'aide de l'algorithme serait génial! Si ce que je demande n'est pas dans le guildlines du site, puis je suis désolé et je vais chercher ailleurs. 🙂

Le projet se charge correctement orthographié minuscules mots et puis il faut faire des suggestions d'orthographe en fonction de deux critères:

Une lettre de différence (soit ajouté ou soustrait à obtenir la parole ainsi qu'un mot dans le dictionnaire). Par exemple une "pile" serait une suggestion pour "staick' et 'cool' serait une suggestion pour "coo".
Une lettre de substitution. Ainsi, par exemple, le "mauvais" serait une suggestion pour 'ca'.

Donc, juste pour m'assurer que j'ai bien expliquer.. je pourrais charger dans les mots [bonjour, au revoir, fantastique, bon, dieu] et puis les suggestions pour la (mal orthographiée) mot 'godd' [est bon, dieu].

Vitesse est mon compte principal, ici, alors que je pense que je sais un moyen d'obtenir ce travail, je ne suis vraiment pas trop sûr de savoir comment efficace elle sera. La façon dont je suis la pensée de le faire est de créer un map<string, vector<string>> puis pour chaque mot correctement orthographié qui est chargé, ajoutez l'correctement orthographié travail en tant que clé dans la carte et le remplir le vecteur à tous les "mauvais" permutations de ce mot.

Ensuite, quand je veux rechercher un mot, je vais regarder à travers tous les vecteurs dans la carte pour voir si ce mot est une déformation de l'un des mot correctement orthographié. Si elle l'est, je vais ajouter la clé, comme une suggestion orthographique.

Cela semble comme il l'aurait fait prendre des TAS de mémoire mais il y aurait sûrement des milliers de combinaisons possibles pour chaque mot? Il semble aussi que ce serait très très lent si mon premier dictionnaire de mots correctement écrits était grand?

Je pensais que je pourrais peut-être coupé du temps un peu en ne regardant dans les touches qui sont similaires à la parole, je suis à la recherche d'. Mais là encore, si elles sont similaires, d'une certaine façon, il est probable que la clé sera une suggestion en ce sens je n'ai pas besoin de toutes ces permutations!

Alors oui, je suis un peu perplexe sur la direction dans laquelle je devrais regarder dans. Je vous remercie de toute l'aide que je ne suis vraiment pas sûr de savoir comment estimer la vitesse des différentes façons de faire les choses (nous n'avons pas appris cela à tous dans la classe).

Il existe assez peu de traitement de la langue naturelle des outils open source et peut être utilisé comme une source d'inspiration sur les algorithmes sont en cours d'utilisation. Pour une C++ affectation à la recherche à un Java open Source, outil de e.g être un bon choix pour vous assurer que vous choisissez les algorithmes: voir languagetool.org pour un exemple.

InformationsquelleAutor Sam | 2011-10-18

algorithm c++language-agnostic nlp spell-checking

6

La manière la plus simple de résoudre le problème est en effet un précalculées carte [mauvais mot] -> [suggestions].

Le problème est que, bien que la suppression d'une lettre crée quelques "gros mots", pour l'addition ou la substitution vous avez de nombreux candidats.

Je vous suggère une autre solution 😉

Remarque: la distance d'édition que vous décrivez s'appelle le Levenshtein

La solution est décrite dans l'étape progressive, normalement, la vitesse de recherche doit améliorer en permanence à chaque idée et j'ai essayé de l'organiser avec le plus simple des idées (en terme de mise en œuvre) en premier. N'hésitez pas à arrêter chaque fois que vous êtes à l'aise avec les résultats.

0. Préliminaire
- Mettre en œuvre l'algorithme de Levenshtein
- Stocker le dictionnaire dans une séquence ordonnée (std::set par exemple, si une triés std::deque ou std::vector serait meilleure performance sage)
Points Clés:
- La Levenshtein compututation utilise un tableau, à chaque étape, la ligne suivante est calculée uniquement avec la ligne précédente
- La distance minimale dans une rangée est toujours supérieure (ou égale) à tout le moins, dans la rangée précédente
La propriété de ce dernier permettent à un court-circuit de mise en œuvre: si vous souhaitez vous limiter à 2 erreurs (seuil), alors à chaque fois que le minimum de la ligne en cours est supérieur à 2, vous pouvez abandonner le calcul. Une stratégie simple est de retourner le seuil de + 1 à la distance.

1. Première Tentative De

Commençons simple.

Nous allons mettre en œuvre une analyse linéaire: pour chaque mot, nous calculons la distance (en court circuit) et nous la liste de ces mots qui atteint la plus petite distance jusqu'à présent.

Il fonctionne très bien sur des petits dictionnaires.

2. L'amélioration de la structure de données

La distance de levenshtein est au moins égale à la différence de longueur.

En utilisant comme clé le couple (longueur, word) au lieu de word, vous pouvez restreindre votre recherche à la gamme de longueur [length - edit, length + edit] et de réduire considérablement l'espace de recherche.

3. Les préfixes et l'élagage

Améliorer cette situation, nous pouvons remarquer que lorsque nous construisons la matrice de distance, ligne par ligne, un monde est entièrement numérisé (le mot nous chercher), mais l'autre (le référent) ne l'est pas: nous n'utilisons une lettre pour chaque ligne.

Cette propriété très importante signifie que pour deux référents qui partagent la même séquence initiale (préfixe), puis les premières lignes de la matrice sont identiques.

Rappelez-vous que je vous demander de ranger le dictionnaire triés ? Cela signifie que les mots qui partagent le même préfixe sont adjacentes.

Supposons que vous consultiez votre parole contre cartoon et à car vous vous rendez compte qu'il ne fonctionne pas (la distance est déjà trop long), puis tous les mots commençant par car ne fonctionne pas, soit, vous pouvez sauter des mots tant qu'ils commencent par car.

L'ignorer elle-même peut être fait de façon linéaire ou avec une recherche (trouver le premier mot qui a une plus grande préfixe que car):
- linéaire qui fonctionne le mieux si le préfixe est long (quelques mots à ignorer)
- binaire de recherche qui fonctionne le mieux pour court préfixe (nombre de mots à ignorer)
Combien de temps est "long" dépend de votre dictionnaire et vous aurez à mesurer. J'irais avec le binaire de recherche pour commencer.

Remarque: la longueur de partitionnement œuvres contre le préfixe de partitionnement, mais il pruneaux beaucoup plus de l'espace de recherche

4. Les préfixes et les ré-utiliser

Maintenant, nous allons également essayer de ré-utiliser le calcul autant que possible (et pas seulement les "il ne fonctionne pas" résultat)

Supposons que vous ayez deux mots:
- cartoon
- station de lavage
Vous calculez d'abord la matrice ligne par ligne, pour cartoon. Puis lors de la lecture de carwash vous avez besoin pour déterminer la longueur du préfixe commun (ici car) et vous pouvez garder les 4 premières lignes de la matrice (correspondant à vide, c, a, r).

Donc, quand commencent à l'informatique carwash, vous en fait commencer l'itération à w.

Pour ce faire, il suffit d'utiliser un tableau alloué dès le début de votre recherche, et de le rendre assez grand pour accueillir le plus grand de référence (vous devez savoir quelle est la plus grande longueur dans votre dictionnaire).

5. À l'aide d'un "mieux" structure de données

D'avoir un temps plus facile de travailler avec des préfixes, vous pouvez utiliser un Trie ou une Patricia Arbre pour stocker le dictionnaire. Cependant, il n'est pas un STL structure de données et vous devez l'augmenter à stocker dans chaque sous-arbre de la gamme de longueur des mots qui sont stockés de sorte que vous aurez à faire votre propre mise en œuvre. Ce n'est pas aussi facile qu'il y paraît car il y a de la mémoire de l'explosion des questions qui peuvent tuer localité.

C'est une option de dernier recours. C'est coûteuse à mettre en œuvre.
- Hmm, Un Trie mis en œuvre en tant que vecteur de Node{unsigned short prevIndex, bool end; unsigned short nextIndex[26];} pourrait tenir 65536 mots en seulement 3,5 MO d'espace (pour en i7 de cache L3!), et rendrait le correcteur d'orthographe relativement simple récursive problème. Je vais jouer avec ça
- vous n'avez pas besoin prevIndex si vous maintenez un "gros" itérateur.
- Il est probablement plus facile de travailler prevIndex dans la récursion qu'un itérateur. Mais vous avez raison, il n'a pas besoin d'être là.
- Test Initial montre mon Trie est le double du temps de ma table de hachage. Table de hachage prend une chaîne de caractères, fuzzes, et voit si tout furets sont dans la table de hachage, classement par la façon dont il embrouillé et combien. Ne veut rien dire jusqu'à ce que j'en vérifier l'exactitude, soit si.
- Désolé pour ce si long à répondre mais tas merci pour cette, vraiment, vraiment utile. 🙂
- nice! Je dois avouer que je n'ai jamais étudié le "seul" beaucoup de changement, même Norvig jouet cas 2 erreurs qui augmente la taille de la carte. Comme pour la Tente: ils sont difficiles à obtenir pour jouer gentil. Il existe des stratégies pour compresser les extrémités (utilisation d'un seau de suffixes à la fin de chaque chemin, au lieu de totalement d'orthographe eux) et pour réduire la branche facteur (groupe "A-D" pour une seule branche, mais cela implique de stocker le mot complet à la fin que vous ne pouvez plus le reconstituer à partir de ce chemin seul). J'avoue qu'un simple triés conteneur est assez gentil pour commencer 🙂
InformationsquelleAutor Matthieu M.

Vous devriez jeter un oeil à cette explication de Peter Norvig sur comment écrire un correcteur orthographique .

Comment écrire un correcteur orthographique

Tout est bien expliquer dans cet article, à titre d'exemple le code python pour le vérificateur d'orthographe ressemble à ceci :

import re, collections

def words(text): return re.findall('[a-z]+', text.lower()) 

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(file('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(word):
   splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in splits if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   inserts    = [a + c + b     for a, b in splits for c in alphabet]
   return set(deletes + transposes + replaces + inserts)

def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words): return set(w for w in words if w in NWORDS)

def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)

Espérons que vous pouvez trouver ce dont vous avez besoin sur Peter Norvig site web.

InformationsquelleAutor Ricky Bobby

2

pour le vérificateur d'orthographe de nombreuses structures de données serait utile, par exemple, BK-Arbre. Vérifier Sacrément Cool Algorithmes, Partie 1: BK-Arbres j'ai fait de la mise en œuvre de la même ici

Mon code précédent lien peut être trompeuse, cette une est correct pour le correcteur orthographique.
- Les liens sont morts.
InformationsquelleAutor Avinash
0

sur le dessus de ma tête, vous pouvez diviser vos suggestions en fonction de la durée et de construire une structure arborescente où les enfants sont plus des variations de la durée plus courte de parent.

devrait être assez rapide, mais je ne suis pas certain que le code lui-même, je ne suis pas très bien versé dans le c++

InformationsquelleAutor Alex

Vous devez vous connecter pour publier un commentaire.