arunkumar9t2 / trie

Eine Java-Implementierung der Präfix-Trie-Datenstruktur.

Einführung

Versuche sind kartenartige geordnete baumbasierte Datenstrukturen, die eine schnelle Suche in der Reihenfolge O(k) ermöglichen, wobei k die Länge des Schlüssels ist. Lesen Sie hier mehr über trie.

Dies wurde ursprünglich für die Verwendung in meiner Android-App T9 App Launcher entwickelt, um die Liste der installierten Anwendungen schnell zu durchsuchen und zu starten.

Öffentliche APIs

Derzeit stehen 3 öffentliche Implementierungen zur Auswahl.

• MapTrie: HashMap unterstützte Trie-Implementierung.
• SortedTrie: TreeMap die Trie-Implementierung, die Vorschläge und Werte zurückgibt, ist in aufsteigender Sortierreihenfolge.
• T9Trie: Hilfsimplementierung zum Speichern und Abrufen von Vorschlägen für die T9-Sequenz.

Anwendungsbeispiel

Erstellen eines einfachen Versuchs und Abrufen von Vorschlägen.

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

Der obige print() Aufruf würde die Baumstruktur wie folgt drucken.

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

Versuchen wir nun, alle Wörter zu finden, die mit ha beginnen. Denken Sie daran, dass bei den Schlüsseln standardmäßig die Groß- und Kleinschreibung nicht berücksichtigt wird.

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

Dadurch wird auf die Konsole gedruckt. Der Wert bleibt unberührt.

Beitrag

Wenn Sie ein Entwickler sind und einen Beitrag leisten möchten, ziehen Sie bitte eine Pull-Anfrage in Betracht. Ich würde mich über Kritik in Bezug auf Code oder Implementierung im Allgemeinen freuen.

Lizenz

Dieses Projekt ist unter der Apache 2.0 Lizenz lizenziert.