Meilleure structure de données pour la mise en œuvre d'un dictionnaire?
Quelle serait la meilleure structure de données pour stocker tous les mots d'un dictionnaire? Le mieux que je pouvais penser était d'utiliser un HashMap
, qui correspondra à un HashTable
. En gros, selon le premier caractère, nous allons obtenir la HashTable
et puis, à l'aide de cela, nous pouvons ajouter les mots commençant par ce caractère. Nous allons ensuite chercher une bonne fonction de hachage basée sur la chaîne.
Est-il une meilleure approche?
Vous devez vous connecter pour publier un commentaire.
En fonction de ce que vous voulez faire, il ya beaucoup de bonnes structures de données.
Si vous voulez juste pour stocker les mots et de demander "est-ce ici le mot ou pas?" un standard de la table de hachage avec aucune autre fantaisie machines est une approche raisonnable. Si ce mot est de la liste fixée à l'avance, pensez à utiliser un parfait de la table de hachage pour obtenir d'excellentes performances et de l'utilisation de l'espace.
Si vous voulez être en mesure de vérifier si un préfixe existe, tout en soutenant rapide des recherches, un trie est une bonne option, même si elle peut être un peu d'espace inefficace. Il prend également en charge rapide des insertions ou des suppressions. Il permet également à l'itération dans l'ordre alphabétique, de hachage n'offre pas. C'est essentiellement la structure que vous avez décrit dans votre réponse, mais selon le cas d'utilisation d'autres représentations de la tente peut-être mieux.
Si, en plus de ce qui précède, vous savez pour un fait que la liste de mots est fixe, pensez à utiliser un DAWG (dirigé acyclique mot graphique), qui est essentiellement un minimum-etat du DFAE pour la langue. Il est nettement plus compact que le trie, mais prend en charge un grand nombre des mêmes opérations.
Si vous voulez trie-comme le comportement, mais ne voulez pas payer un énorme espace de pénalité, la ternaire, un arbre de recherche est une autre option viable, comme c'est le radix arbre. Ce sont des structures très différentes, mais peut être beaucoup mieux que les trie dans des circonstances différentes.
Si l'espace est un sujet de préoccupation, mais vous voulez un trie, regarder dans la succincte trie représentation, qui est plus lent recherches mais théoriquement optimale l'utilisation de l'espace. Le lien explique comment il est utilisé en JavaScript comme un moyen facile de transmettre une énorme quantité de données. Une alternative représentation compacte est la double-tableau trie, certes je sais très peu de choses sur elle.
Si vous souhaitez utiliser le dictionnaire pour des opérations comme la vérification orthographique dans lequel vous devez trouver des mots semblables à d'autres mots, la BK-arbre est une excellente structure de données à prendre en compte.
Espérons que cette aide!