Algorithme de prédiction de mots

Je suis sûr qu'il y est un post sur ce sujet, mais je ne pouvais pas en trouver un en posant cette question exacte. Considérez les points suivants:

1. Nous avons un dictionnaire de mots disponibles
2. Nous sommes nourris de nombreux paragraphes de mots, et je veux être en mesure de prédire le mot suivant dans une phrase donnée cette entrée.

Dire que nous avons quelques phrases telles que "Bonjour, mon nom est Tom", "Son nom est jerry", "Il va là où il n'y a pas d'eau". Nous vérifions une table de hash si un mot existe. Si cela ne fonctionne pas, nous lui affecter un id unique et le mettre dans la table de hachage. De cette façon, au lieu de stocker une chaîne de mots comme un bouquet de chaînes de caractères, nous pouvons juste avoir une liste d'id unique.

Ci-dessus, nous aurions par exemple (0, 1, 2, 3, 4), (5, 2, 3, 6), et (7, 8, 9, 10, 3, 11, 12). À noter que 3 est "est" et nous avons ajouté de nouvelles id unique que nous avons découvert de nouveaux mots. Donc, dire que nous sommes une phrase "son nom est", ce serait (13, 2, 3). Nous voulons savoir, compte tenu de ce contexte, que le mot suivant doit être. C'est l'algorithme que je pensais, mais je ne pense pas que son efficacité:

1. Nous avons une liste de N chaînes (observé phrases) où une chaîne peut être ex. 3,6,2,7,8.
2. Chaque chaîne est en moyenne de taille M, où M est la moyenne de la longueur des phrases
3. Nous sommes donné une nouvelle chaîne de taille S, ex. 13, 2, 3, et nous voulons savoir ce qui est le plus probable du mot suivant?

Algorithme:

1. Première analyse de l'ensemble de la liste des chaînes pour ceux qui contiennent l'intégralité des S entrée(13,2,3, dans cet exemple). Puisque nous avons à balayage N chaînes, chacune de longueur M, et de comparer les lettres à la fois, ses O(N*M*S).
2. Si il n'y a pas de chaînes de notre analyse qui ont le S complet, de l'analyse suivante en enlevant le moins de mot significatif (ie. la première, donc supprimer 13). Maintenant, scan (2,3) 1 dans le pire des cas O(N*M*S) qui est vraiment S-1.
3. Poursuivre la numérisation de cette façon jusqu'à ce que nous obtenons des résultats > 0 (si jamais).
4. Compter les mots suivants dans tous les autres chaînes que nous avons rassemblées. On peut utiliser une table de hachage qui compte à chaque fois que nous ajoutons, et de garder une trace de la plupart des mot ajouté. O(N) le pire des cas, construire, O(1) pour trouver le max de mots.
5. Le max de mot est le plus probable, si retour il.

Chaque scan prend O(M*N*S) le pire des cas. C'est parce qu'il y a N chaînes, chaque chaîne a M chiffres, et nous devons vérifier S numéros de superposition d'un match. Nous scannons S fois pire des cas (13,2,3,puis 2,3, puis 3 pour 3 scans = S). Ainsi, le total de la complexité est O(S^2 * M * N).

Donc, si nous avons de 100 000 chaînes et une durée moyenne des peines de 10 mots, nous sommes à la recherche 1 000 000 de*S^2 pour trouver la meilleure parole. Clairement, N >> M, puisque la durée de la peine, ne l'est pas avec le nombre de peines en général, de sorte que M peut être une constante. On peut alors réduire la complexité à O(S^2 * N). O(S^2 * M * N) peut être plus utile pour l'analyse, mais, depuis M peut être un important "constante".

Cela pourrait être la complète mauvais, de l'approche à prendre pour ce type de problème, mais je voulais partager mes pensées au lieu de simplement flagrante de demander de l'aide. La raison im de la numérisation de la façon dont je le fais c'est parce que je ne voulez analyser autant que je le dois. Si rien n'a le S complet, il suffit de garder l'élagage S jusqu'à ce que certaines chaînes de match. Si elles ne correspondent jamais, nous n'avons aucune idée de ce à prédire le mot suivant! Toutes les suggestions sur un moins de temps/espace solution complexe? Merci!

source d'informationauteur user2045279