java implementace datové struktury prefixu Trie.
Úvod
pokusy jsou mapovány jako uspořádané stromové datové struktury, které poskytují rychlé vyhledávání pořadí O(k)
, kde k
je délka klíče. Přečtěte si více o trie zde.
motivace
toto bylo původně vytvořeno pro použití v mé aplikaci pro Android, T9 App Launcher pro rychlé vyhledávání v seznamu nainstalovaných aplikací a jejich spuštění.
veřejné API
v současné době existují 3 veřejné implementace, ze kterých lze vybrat.
-
MapTrie
:HashMap
couval implementace trie. -
SortedTrie
:TreeMap
couval trie implementace, která vrací návrhy a hodnota je vzestupně řazení. -
T9Trie
: implementace pomocníka pro ukládání a načítání návrhů pro sekvenci T9.
příklad použití
vytvoření jednoduchého trie a získání návrhů.
final MapTrie<String> trie = new MapTrie<>();trie.insert("Hello", "Hello");trie.insert("Help", "Help");trie.insert("Has", "Has");trie.insert("Have", "Have");trie.insert("Had", "Had");trie.insert("Hadn't", "Hadn't"); // Print to stdouttrie.print();
výše uvedené volání print()
vytiskne stromovou strukturu takto.
└── h ├── e │ └── l │ ├── l │ │ └── o'Hello │ └── p'Help └── a ├── s'Has ├── v │ └── e'Have └── d'Had └── n └── ' └── t'Hadn't
nyní se pokusíme najít všechna slova začínající ha
. Nezapomeňte, že ve výchozím nastavení jsou klíče necitlivé na velká a malá písmena.
List<String> suggestions = trie.getValueSuggestions("ha");System.out.print(suggestions.toString());
tím se vytiskne na konzoli. Hodnota zůstává nedotčena.
příspěvek
pokud jste vývojář a chcete přispět, zvažte prosím žádost o stažení. Ocenil bych jakoukoli kritiku, pokud jde o kodex nebo implementaci obecně.
Licence
tento projekt je licencován pod licencí Apache 2.0.