Meilleure structure de données pour l’implémentation d’un dictionnaire?

Quelle serait la meilleure structure de données pour stocker tous les mots d’un dictionnaire? La meilleure chose à laquelle je pouvais penser était d’utiliser un HashMap , qui correspondrait à un HashTable . Fondamentalement, en fonction du premier caractère, nous obtiendrons la HashTable associée et en utilisant ceci, nous pourrons append les mots commençant par ce caractère. Nous choisirons ensuite une bonne fonction de hachage en fonction de la chaîne.

Est-ce qu’il y a une meilleure approche?

    Selon ce que vous voulez faire, il existe de nombreuses structures de données.

    Si vous voulez juste stocker les mots et demander “est-ce que ce mot est ici ou non?”, Une table de hachage standard sans autre machine sophistiquée est une approche raisonnable. Si ce mot est une liste fixée à l’avance, envisagez d’utiliser une table de hachage parfaite pour obtenir d’excellentes performances et une meilleure utilisation de l’espace.

    Si vous voulez être capable de vérifier si un préfixe donné existe tout en prenant en charge les recherches rapides, un sortinge est une bonne option, bien que cela puisse être un peu inefficace. Il prend également en charge les insertions ou suppressions rapides. Il permet également une itération dans l’ordre alphabétique, ce que le hachage n’offre pas. C’est essentiellement la structure que vous avez décrite dans votre réponse, mais selon le cas d’utilisation, d’autres représentations d’essais pourraient être meilleures.

    Si, en plus de ce qui précède, vous savez que la liste de mots est corrigée, envisagez d’utiliser un DAWG (graphe de mots acycliques dirigés), qui est essentiellement un DFA à l’état minimum pour le langage. Il est sensiblement plus compact que le sortinge, mais supporte plusieurs des mêmes opérations.

    Si vous voulez un comportement de type sortinge mais que vous ne voulez pas payer une énorme pénalité d’espace, l’ arbre de recherche ternaire est une autre option viable, tout comme l’ arbre radix . Ce sont des structures très différentes, mais elles peuvent être bien meilleures que dans des circonstances différentes.

    Si l’espace est un problème mais que vous voulez un sortingé, examinez la représentation succincte de sortinge , qui a des recherches plus lentes mais à peu près théoriquement une utilisation optimale de l’espace. Le lien explique comment il est utilisé en JavaScript comme moyen simple de transmettre une grande quantité de données. Une représentation compacte alternative est le sortingèdre double , bien que je sache très peu à ce sujet.

    Si vous souhaitez utiliser le dictionnaire pour des opérations telles que la vérification orthographique où vous devez trouver des mots similaires à d’autres mots, l’ arborescence BK est une excellente structure de données à prendre en compte.

    J’espère que cela t’aides!