en java-implementering af præfikset Trie-datastruktur.
introduktion
forsøg er kort som ordnede træbaserede datastrukturer, der giver hurtig søgning af ordren O(k)
hvor k
er længden af nøglen. Læs mere om trie her.
Motivation
dette blev oprindeligt bygget til brug i min Android-app, T9 App Launcher til hurtigt at søge gennem listen over installerede applikationer og starte dem.
offentlige API ‘ er
i øjeblikket er der 3 offentlige implementeringer, der kan vælges fra.
-
MapTrie
:HashMap
bakket trie implementering. -
SortedTrie
:TreeMap
bakket trie implementering, som returnerer forslag og værdi er stigende sorteringsrækkefølge. -
T9Trie
: hjælper implementering til at gemme og hente forslag til T9 sekvens.
eksempel brug
oprettelse af en simpel trie og få forslag.
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();
ovenstående print()
opkald ville udskrive træstrukturen som denne.
└── h ├── e │ └── l │ ├── l │ │ └── o'Hello │ └── p'Help └── a ├── s'Has ├── v │ └── e'Have └── d'Had └── n └── ' └── t'Hadn't
lad os nu prøve at finde alle ordene, der starter med ha
. Husk, at tasterne som standard er store og små bogstaver.
List<String> suggestions = trie.getValueSuggestions("ha");System.out.print(suggestions.toString());
dette udskrives til konsollen. Værdien forbliver uberørt.
Bidrag
hvis du er udvikler og gerne vil bidrage, kan du overveje at lave en pull-anmodning. Jeg vil sætte pris på enhver kritik med hensyn til kode eller implementering generelt.
Licens
dette projekt er licenseret under Apache 2.0 licens.