Quelle serait la meilleure façon (pratique) de stocker des données sur les occurrences et les positions de mots dans un texte afin qu'il soit rapidement accessible?

Question

Je suis sur le point de commencer à écrire un programme qui va analyser un texte et stocker tous les mots uniques dans le texte sous une forme qui peut être appelée plus tard. Lorsqu'il est appelé, il donnera la position de toutes les occurrences de ce mot dans le texte original et retournera les mots environnants.

Je pense que la meilleure façon de le faire serait d'utiliser un hashmap parce qu'il fonctionne avec les mots uniques comme une clé, puis un int [] comme valeurs mappées. Mais je ne sais pas si cela est considéré comme une bonne pratique ou non. Ma solution aurait un tableau pour stocker le texte original, qui pourrait être assez grand, et un hashmap avec une paire clé-valeur pour chaque mot unique qui pourrait être presque aussi grand que le tableau contenant le texte. Comment le résoudriez-vous?

Answer 1

Une autre possibilité est un arbre 26-aire (compte tenu de votre alphabet a 26 caractères).
Construisez votre arbre en stockant les mots que vous rencontrez, chaque nœud représentera un mot; Dans chaque nœud, vous pouvez ensuite stocker un tableau de pointeurs pointant vers les occurrences des mots dans les chaînes (ou un tableau d'indices int représentant). En termes de mémoire et de complexité, il est équivalent à l'implémentation de la carte de hachage (même vitesse, légèrement plus compact), mais il me semble un peu plus intuitif que la carte de hachage.
Donc, je dirais que c'est principalement à vous et à vos structures préférées.

Answer 2

Un hachage-cartes sont faites pour ce genre de tâche. Vous devez probablement mapper les chaînes à une structure (plutôt qu'à un tableau int). Cette structure pourrait enregistrer la position et le mot précédent et suivant - ce que vous entendez par «entourant» n'est pas très clair.

Vous devrez peut-être décider si votre processus respecte la casse. Est-ce que "Vous" et "vous" avez le même mot? En fonction de la langue, vous pouvez fournir un comparateur et une fonction de hachage insensibles à la casse ou avoir besoin de «minuscules» toutes les entrées.