Structure de données pour les suggestions de mots à partir d'un fichier texte

Question

Problème: Nous recevons un fichier texte contenant plusieurs lignes de texte. Maintenant, l'utilisateur saisira quelques lettres et nous devons donner une suggestion de saisie semi-automatique basée sur le texte du fichier qui nous est donné. Supposons que le fichier contienne computer science is fun. computer engineering is awesome. Maintenant, si l'utilisateur tape com, nous devons donner comme suggestion computer science et computer engineering. Si l'utilisateur tape is, la suggestion doit être fun et awesome. L'utilisateur peut entrer n'importe quel mot qui pourrait ou ne pourrait pas être dans le fichier texte. Si le mot n'est pas dans le fichier, il ne devrait y avoir aucune suggestion.

Quelle serait la meilleure structure de données pour ce problème.
Je sais que nous pouvons construire un trie mais avec cela nous pourrions seulement être en mesure de suggérer computer lorsque l'utilisateur tape com.

Appréciez toute aide.

Answer 1

Préparation:

1. Lire toutes les lignes du fichier texte comme un tableau de chaîne
2. Trier lexicographique ce tableau

Requête:

1. Obtenez l'indice lower bound étant donné la chaîne d'entrée: first
2. Augmentez la valeur du dernier caractère de votre chaîne d'entrée de 1 (sinon à sa valeur maximale) et obtenez l'index lower bound, last, pour cette nouvelle chaîne d'entrée. Si votre dernier caractère ne peut pas être incrémenté, utilisez l'index après la fin de votre arrar.

Toutes les suggestions sont dans le tableau trié entre ces deux bornes non compris le dernier indice: [first, last).

S'il y a trop de suggestions, vous pouvez filtrer en suggérant seulement les 3 suggestions les plus courtes, ou les trier par fréquences statistiques.

Vous pouvez également imprimer le nombre de suggestions au lieu de les suggérer. Similaire à la façon dont google vous indique combien de pages correspondent à votre requête. Et puis, ne suggérez que des chaînes lorsque le nombre de correspondances est gérable par votre interface utilisateur.