algorithme pour le modèle correspondant

Question

Contexte

Je suis la conception d'une application qui convertit le texte d'une langue à l'autre. Par exemple, le texte de saisie hello sera converti en texte de langue spécifié. Ceci est fait en ayant une table de recherche pour chaque langue. L'algorithme de conversion comporte les étapes suivantes.

1. Recherche la correspondance exacte. Le mot entier hello sera le modèle. Si des correspondances trouvées, arrêtez le traitement et renvoyez la correspondance.
2. Sinon, démarrez de gauche à droite et recherchez chaque caractère jusqu'à ce que toutes les combinaisons soient terminées. Ex: Itération1: modèle = h, 2ème - he, 3ème - hel et ainsi de suite. Le jeton correspondant sera conservé dans un tampon temporaire et retourné lorsqu'il n'y aura plus de correspondance. Cela fonctionne comme la règle maximale de munch.
3. Si la correspondance est trouvée, le texte correspondant sera supprimé du texte d'origine et poursuivra le traitement avec le texte restant.

Cet algorithme devra parcourir plusieurs fois le texte d'entrée et conduire à une complexité quadratique. J'essaye d'optimiser ceci en arrangeant la table de recherche dans une structure en arbre (très semblable à l'arbre de suffixe). S'il y a du texte recherche pour h, hel, lo, il sera organisé comme

root 
--h 
----hel 
--lo 

Cela me permettra d'éviter les recherches inutiles. Après la correspondance h, je dois aller au caractère suivant seulement si le noeud h a des enfants. Cela réduit considérablement le nombre d'itérations.

Questions

1. Quel est le nom de ce type de structure de données? Existe-t-il une implémentation prête à l'emploi pour C ou C++?
2. Voyez-vous des améliorations possibles sur l'algorithme ou la structure de données ci-dessus?

Des pensées ...?

Answer 1

Regardez la structure de données 'Trie'.

Pourquoi ne pas utiliser Lucene que le texte des index de façon très rapide, et plus encore - l'indexation comprend des algorithmes pour

• steming
fusible
• correspondant

et ainsi de suite.

Answer 2

Un arbre de recherche ternaire pourrait être ce dont vous parlez. C'est comme un trie, mais plus efficace d'après ce que je comprends.