Recherche prefix dans un arbre radix / patricia Trie

Question

Je réalise actuellement un arbre radix / patricia Trie (tout ce que vous voulez l'appeler). Je veux l'utiliser pour les recherches préfixe dans un dictionnaire sur un morceau de matériel sévèrement underpowered. Il est censé fonctionner plus ou moins comme l'auto-complétion, i. e. montrant une liste de mots qui correspond au préfixe tapé.

Ma mise en œuvre est basée sur cet article , mais le code qui y doesn « t inclure des recherches de préfixe, bien que l'auteur dit:

  

[...] Disons que vous voulez énumérer tous les noeuds qui ont des clés avec un préfixe commun « AB ». Vous pouvez effectuer une recherche en profondeur d'abord à partir de cette racine, s'arrêtant chaque fois que vous rencontrez en arrière bords.

Mais je ne vois pas comment cela est censé fonctionner. Par exemple, si je construis un arbre de radix ces mots:

  

maladie
  imaginaire
  imagination
  imaginez
  imitation
  
immédiate   immédiatement
  immense
  en

Je vais obtenir exactement le même « meilleur match » pour les préfixes « i » et « dans » afin qu'il me semble difficile de rassembler tous les mots correspondant juste en traversant l'arbre de ce meilleur match.

En outre, il y a une mise en œuvre de l'arbre radix en Java qui a une recherche de préfixe mis en œuvre RadixTreeImpl.java . Ce code vérifie explicitement tous les nœuds (à partir d'un certain noeud) pour un match de préfixe -. Il se compare en fait octets

Quelqu'un peut-il me pointer vers une description détaillée sur la mise en œuvre d'une recherche de préfixe sur les arbres radix? L'algorithme est utilisé dans la mise en œuvre de Java la seule façon de le faire?

Answer 1

Pensez à ce que votre code Trie. A chaque nœud, vous avez le chemin qui vous conduit à ce noeud, donc dans votre exemple, vous commencez à Λ (c'est capital Lambda, cette police grecque sorte de suce) le nœud racine correspondant à une chaîne vide. Λ a des enfants pour chaque lettre utilisée, donc dans votre ensemble de données, vous avez une branche, pour « i ».

• Λ
• Λ → "i"

Au noeud « i », il y a deux enfants, l'un pour « m » et un pour « n ». La lettre suivante est « n », de sorte que vous prenez cela,

• Λ → "i" → "n"

et que le seul mot qui commence « i », « n » dans votre ensemble de données « dans », il n'y a pas d'enfants de « n ». C'est un match.

Maintenant, disons que l'ensemble de données, au lieu d'avoir « dans », avait « infindibulum ». (Qu'est-ce que je SF référencement est laissé en exercice.) Vous souhaitez toujours accéder à la « n » noeud de la même manière, mais si la lettre suivante vous obtenez est « q », vous savez que le mot ne semble pas dans votre ensemble de données du tout, parce qu'il n'y a pas de branche « q ». À ce moment-là, vous dites « OK, pas de match. » (Peut-être que vous commencez alors ajouter le mot, peut-être pas, en fonction de l'application.)

Mais si la lettre suivante est « f », vous pouvez continuer. Vous pouvez court-circuit avec un peu de métier, cependant: une fois que vous atteignez un nœud qui représente un chemin unique, vous pouvez accrocher toute la chaîne ce nœud. Lorsque vous arrivez à ce nœud, vous savez que le reste de la chaîne doit être « findibulum », de sorte que vous avez utilisé le préfixe pour correspondre à la chaîne entière, et le retourner.

Comment votre utilisation vous? dans un grand nombre de non-commande UNIX interprètes, comme le vieux VAX DCL, vous pouvez utiliser un préfixe unique d'une commande. Ainsi, l'équivalent de ls (1) était DIRECTORY, mais aucune autre commande a commencé avec DIR, de sorte que vous pouvez taper DIR et qui a été aussi bon que faire le mot entier. Si vous ne vous souveniez pas la bonne commande, vous pouvez taper simplement « D », et appuyez sur (je pense) ESC; la DCL CLI voulez-vous revenir tous les commandes qui ont commencé avec D, qu'il pourrait faire une recherche extrêmement rapide.

Answer 2

Il se trouve les extensions GNU pour la norme C ++ lib inclut une implémentation de Patricia Trie. Elle se trouve sous les structures de données basée sur des stratégies d'extension. Voir http://gcc.gnu.org/onlinedocs/libstdc++/ext /pb_ds/trie_based_containers.html

Answer 3

Un autre algorithme: Keep It Simple Stupid

Il suffit de faire une liste triée de vos mots-clés. Lorsque vous avez un préfixe, recherche binaire pour trouver où ce préfixe serait situé dans la liste. Toutes vos commandes possibles se trouve à partir de cet index, prêt à être consulté en place.

Cet algorithme ne nécessitera que 5% du code de Patricia et Trie est facile à entretenir, comprendre et mettre à jour. Il est presque certain que cette recherche simple liste sera plus efficace aussi bien.

Le seul inconvénient est que si vous avez un très grand nombre de mots-clés longue avec des préfixes similaires, une structure arborescente permet d'économiser un espace de stockage car il n'a pas besoin de garder le préfixe complet pour chaque entrée. En pratique, si vous avez moins de quelques millions de mots, ce n'est pas une économie, car le pointeur au-dessus de l'arbre dominera. Cette épargne est plus pour des applications telles que la recherche des bases de données de chaînes d'ADN avec des millions de caractères, pas des mots-clés du texte.

Answer 4

Une autre alternative est un algo arbre de recherche ternaire (plus efficace de la mémoire) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree