T9 Wörterbuch

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

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.

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.

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.