arunkumar9t2 / trie

een java implementatie van de Prefix Trie data structure.

Inleiding

pogingen zijn kaartachtige geordende boomgebaseerde datastructuren die snel zoeken in de volgorde O(k) mogelijk maken waarbij k de lengte van de sleutel is. Lees hier meer over trie.

motivatie

dit werd in eerste instantie gebouwd om te gebruiken in mijn Android app, T9 App Launcher om snel door de lijst met geïnstalleerde applicaties te zoeken en ze te starten.

publieke API ‘ s

Momenteel zijn er 3 publieke implementaties waaruit kan worden gekozen.

• MapTrie: HashMap ondersteunde trie implementatie.
• SortedTrie: TreeMap ondersteunde trie-implementatie die suggesties retourneert en waarde oplopende sorteervolgorde is.
• T9Trie: Helper-implementatie om suggesties voor T9-sequentie op te slaan en op te halen.

voorbeeld gebruik

een eenvoudige trie maken en suggesties krijgen.

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();

de bovenstaande print() aanroep zou de boomstructuur als volgt afdrukken.

└── h ├── e │ └── l │ ├── l │ │ └── o'Hello │ └── p'Help └── a ├── s'Has ├── v │ └── e'Have └── d'Had └── n └── ' └── t'Hadn't

laten we nu proberen alle woorden te vinden die beginnen met ha. Onthoud dat de toetsen standaard hoofdletterongevoelig zijn.

List<String> suggestions = trie.getValueSuggestions("ha");System.out.print(suggestions.toString());

dit zal naar de console afdrukken. De waarde blijft onaangeroerd.

bijdrage

als u een ontwikkelaar bent en een bijdrage wilt leveren, overweeg dan een pull request te doen. Ik zou alle kritiek op de code of de uitvoering in het algemeen op prijs stellen.

Licentie

dit project is gelicenseerd onder Apache 2.0 licentie.