T9 Wörterbuch

belbono

Hallo,
ich habe die Aufgabe ein (primitives) T9 Wörterbuch zu implementieren.
Ich habe bisher noch keine besonders gute Vorstellung welche Datenstruktur ich dafür am besten verwenden sollte.
Anfangs hab ich darüber nachgedacht wie das ganze mit Hash Tabellen aussehen könnte aber ich weiß nicht ob das so besonders clever ist.

Mir wurde zu Packed-Trie geraten, allerdings als ich mich dafür etwas einlesen wollte im Netz fand ich keine besonders guten Quellen.

Also erstmal: ist ein Packed-Trie eine gute Wahl ?

und: wie funktioniert das ganze. Ein dokumentiertes Interface oder ähnliches anschauliches Material in welcher Form würde ich sehr begrüßen.

MfG

belbono

burny

Ich kann mit dem Begriff 'Packed Tree' ad hoc nicht viel anfangen, aber erinnert mich an B-Bäume, die man z.B. in Datenbanken verwendet (ein Blattknoten hat einen Eintrag nach dem er sortiert wird, und eine große Datenmenge die damit verbunden ist, die aber nur in den Speicher geladen wird wenn sie benötigt wird).
Wikipedia hat ein bisschen Basiswissen anzubieten. Unter dem Begriff Abstract Data Structure (ADS) kannst du vielleicht was ergoogeln.

So wie ich das sehe brauchst du eine Datenstruktur, die von einem Knoten ausgehend bis zu 10 Verbindungen zu anderen Knoten haben kann, wobei der Knoten selbst * Einträge (vielleicht mit Priorisierung) speichern kann. Muss man wohl selbst programmieren (falls du nicht eine T9-Bibliothek findest).

Burny

Wolfibolfi

Isn Packed Tree nicht sowas wie ein Baum wo jeder Knoten für jeden Buchstaben einen Unterknoten hat?

Also wenn ich das Wort "Pups" suche, geh ich mal in den P Knoten, dann schau ich obs nen U-Unterknoten gibt, wenn ja, dann such ich darunter einen P-Unterknoten usw.
Wenn ich mal keinen find, is es aus, so auf die Art.

belbono

also so wie ich den entdeckt hat hat seine Wurzel keinen Inhalt sondern nur Verweise.

Jede Kante hat einen Buchstaben und in den Folgeknoten werden die zusammengesetzten Strings enthält
am Blatt findet man dann die fertigen Wörter

...ach hat er ja schon erklärt ... OK

Also ..is son ding dafür geeigne oder gehts gar noch besser irgendwie ?

Wolfibolfi

In Punkto Suchgeschwindigkeit ist das sicher super. Was ein Problem ist, ist wohl das aufbauen des Baumes. Wenn du da jetzt ein Wörterbuch einlesen musst, und das in den Baum speicherst, könnts dauern. Überleg dir also gleich ein gutes Datenformat, in das du einmal exportierst, und von dem man schnell wieder den Baum einlesn kann.

belbono

oh gott .... exportiert bzw. mit Dateien hab ich noch nie gearbeitet

und der brauch auch nur ganz wenige Wörter können ...damit das Prinzip halt rüberkommt....
Was mich aber noch interesseirt:
muss die wurzel dann wirklich schlimmstenfalls 26 kanten haben die zu andern Knoten gehen ?

Plantschkuh!

Zitat von belbono

muss die wurzel dann wirklich schlimmstenfalls 26 kanten haben die zu andern Knoten gehen ?

In einem "richtigen" Indexed Trie ja (der Packed Trie ist ein Spezialfall davon), aber den kannst du nicht verwenden, da du nicht Folgen von Buchstaben, sondern von Tastendrücken betrachtest.
Eine nicht perfekte, aber wohl ganz brauchbare trie-ähnliche Lösung wäre ein Baum, in dem jeder Knoten 8 mögliche Nachfolger hat (entsprechend den Handy-Tasten 2 bis 9) sowie eine Liste von Worten bzw. Wortpräfixen, die mit einer bestimmten Folge von Tastendrücken erzeugt werden können.
D.h. wenn man von der Wurzel aus den Kante 3, von dort Kante 6 und nochmal Kante 6 folgt, wäre man in einem Knoten, in dem (in meinem Handy) die Wortfetzen "dom", "don", "eno", "emo", "fon", "emm" und "foo" gespeichert sind.

Jetzt mitmachen!