arunkumar9t2 / trie

implementacja java struktury danych Trie.

wprowadzenie

próby są mapami jak uporządkowane struktury danych oparte na drzewie, które zapewniają szybkie wyszukiwanie kolejności O(k) gdzie k jest długością klucza. Przeczytaj więcej o trie tutaj.

motywacja

początkowo został zbudowany do użycia w mojej aplikacji na Androida, T9 App Launcher, aby szybko przeszukiwać listę zainstalowanych aplikacji i uruchamiać je.

publiczne API

obecnie istnieją 3 publiczne implementacje, które można wybrać spośród.

• MapTrie: HashMap wspierana implementacja trie.
• SortedTrie: TreeMap wspierana implementacja trie, która zwraca sugestie i wartość jest rosnącą kolejnością sortowania.
• T9Trie: implementacja pomocnicza do przechowywania i pobierania sugestii dla sekwencji T9.

przykładowe użycie

Tworzenie prostego trie i uzyskiwanie sugestii.

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

powyższe wywołanie print() wyświetli strukturę drzewa w ten sposób.

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

teraz spróbujmy znaleźć wszystkie słowa zaczynające się od ha. Pamiętaj, że domyślnie klawisze nie uwzględniają wielkości liter.

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

to wyświetli na konsoli. Wartość pozostaje nietknięta.

Contribution

jeśli jesteś programistą i chcesz wnieść swój wkład, rozważ złożenie pull request. Byłbym wdzięczny za wszelkie uwagi krytyczne w odniesieniu do kodu lub implementacji w ogóle.

Licencja

ten projekt jest licencjonowany na licencji Apache 2.0.