en java-implementering av Prefikset Trie datastruktur.
Innledning
Prøver er kart som bestilte trebaserte datastrukturer som gir rask søking av ordren O(k)
der k
er lengden på nøkkelen. Les mer om trie her.
Motivasjon
Dette ble opprinnelig bygget for å bruke I Min Android app, T9 App Launcher for raskt å søke gjennom listen over installerte applikasjoner og starte dem.
Offentlige Apier
For tiden er det 3 offentlige implementeringer som kan velges fra.
-
MapTrie
:HashMap
stottet trie implementering. -
SortedTrie
:TreeMap
støttet trie implementering som returnerer forslag og verdi er stigende sorteringsrekkefølge. -
T9Trie
: Helper implementering for å lagre og hente forslag Til T9 sekvens.
Eksempelbruk
Opprette en enkel 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();
ovennevnte print()
kall ville skrive ut trestrukturen som dette.
└── h ├── e │ └── l │ ├── l │ │ └── o'Hello │ └── p'Help └── a ├── s'Has ├── v │ └── e'Have └── d'Had └── n └── ' └── t'Hadn't
la Oss nå prøve å finne alle ordene som begynner med ha
. Husk at tastene som standard er små bokstaver.
List<String> suggestions = trie.getValueSuggestions("ha");System.out.print(suggestions.toString());
dette vil skrive ut til konsollen. Verdien er uberørt.
Bidrag
hvis du er en utvikler og ønsker å bidra kan du vurdere å gjøre en pull forespørsel. Jeg vil sette pris på kritikk med hensyn til kode eller implementering generelt.
Lisens
dette prosjektet er lisensiert Under Apache 2.0 lisens.