Das deutsche Python-Forum

moin leude!
habe folgendes problem: möchte T9 in python inkl. wörterbuch umsetzen.
inkl. grobalgorithmus & etc.
wollte mal fragen, ob mir da vielleicht wer weiterhelfen könnte.
besten dank im vorraus!

Ohne konkrete Fragestellung, bzw. überhaupt eine Fragestellung hab ich so meine zweifel ob man dir helfen kann ^^

also zunächst mal sollte das wörterbuch folgende eigenschaften erfüllen:

-leeres Wörterbuch anlegen
-neue Einträge einfügen
-Wörterbuch speichern
-Wörterbuch laden
-Einträge suchen
-Folgeeintrag suchen

und innerhalb des wörterbuchs sollten die einträge tabellarisch einträge angelegt werden, so das jeder tastenkombination ein oder mehrer wörter zugeschrieben werden, so z.B.
für:
284 = aus, bus
724853 = schule
etc.

eine weitere spalte für relative bzw. abosulte häufigkeit wäre ganz nützlich, damit das wörterbuch auch neue einträge lernt und passende treffer vorzieht. dies eignet sich vor allem, wenn es für eine zahlenkombination mehrer möglichkeiten gibt.

den grobalgorithmus für t9 habe ich mir in etwa wie folgt vorgestellt:

Das „Eingabewort“ und das „Ausgabewort“ haben zunächst keine Zeichen
Der Eingabemodus ist T9
Wiederhole
Taste abfragen
Wenn die Taste die Löschtaste ist,
dann lösche das letzte Zeichen des Eingabewortes
Wenn die Taste eine Buchstabentaste ist,
dann füge sie an das Eingabewort an
Wenn die Taste die Alternativentaste ist,
dann Alternativenzähler (modulo Anzahl) erhöhen
Ausgabewort und Alternativenanzahl aus Eingabewort bilden und anzeigen
Wenn die Taste die Buchstabiertaste ist,
dann ist der Eingabemodus „buchstabieren“
Wort buchstabieren lassen
bis Wort eingeben ist

es sollte nach möglcihkeit mit datenstrukturen gearbeitet werden.

Yo, klingt nicht schlecht! Mach das mal so.

also wie gesagt, ohne frage is' nix.
ich tippe mal, dass du so etwas brauchst wie
"schaue dir das modul re an".
aber wenn du kein problem hast, kann man dir nicht helfen
und sonst schreib doch einfach, was du umschrieben hast...

Der vorgeschlagene Algorithmus klingt ganz gut. Eine Anwendung für das `re`-Modul sehe ich eher nicht. Eine einfache Datenstruktur hat TomAss ja schon vorgeschlagen, das ist einfach ein `dict` mit Ziffern-Zeichenketten als Schlüsseln und Listen mit Worten als Werten.

Hi!

Sorry, wenn ich als Nicht-Informatiker was Wichtiges übersehe. Aber mit re sollte sich das recht einfach programmieren lassen: Der User gibt seine Zahlenfolge ein, das Programm erstellt aus der Zahl einen regulären Ausdruck und mit dem durchsucht man dann eine Liste mit bekannten Wörtern auf der Suche nach dazu passenden. Wenn man das Ganze so angeht, dann ähnelt es dem Problem aus http://www.python-forum.de/topic-7328.html (speziell dem dort von mir geposteten Code). Das ist dann schnell zusammenprogrammiert, aber jede eingegebene Ziffer führt dazu, dass alle bekannten Wörter durchsucht werden müssen.
Geschickter ist es wahrscheinlich, wenn man alle bekannten Wörter in einer Art Baumstruktur ablegt, so dass man nachher nur noch dem Baum folgen muss. Dann müssen neu hinzugefügte Wörter geschickter abgelegt werden, dafür ist jede einzelne Suche schneller.

Ich glaube, das ist eine Frage der Anzahl der bekannten Worte: Wenige hundert Worte sind mit re sehr schnell durchsucht. Viele Tausend sollte man vielleicht lieber in einer Baumstrukur abspeichern (?).

Beim T9 auf dem Handy ist es ja so, dass nicht nur Wörter vorgeschlagen werden, die exakt zur Ziffernkette passen, sondern auch solche, die mit der selben Ziffernkette anfangen, aber beliebig länger sein können, als die Ziffernkette. Ich glaube, mit einem Dict wäre das schwieriger zu lösen. Wahrscheinlich irre ich da aber...

Gruß,
Bernhard

Das geht natürlich. Aber man könnte auch einfach ein Wörterbuch einmal einlesen und dabei ein Dictionary aufbauen. Und zwar eines das einfach Ziffernketten auf Listen mit passenden Wörtern abbildet, das reicht schon. Eine Baumstruktur ist nicht nötig. Nach jedem Tastendruck kann man einfach in O(1) Zeit nachsehen welche Wörter auf die bisher eingegebene Ziffernfolge passen.

Und Wort->Ziffernkette geht mit `str.translate()`, da braucht man keine regulären Ausdrücke.

@blackjack:
geht das aber nicht schneller, wenn man wikipedia und co mit re durchsucht?
man kann natürlich auch an allen leerzeichen splitten, aber ich dachte, dass das immer langsamer wäre.

murph hat geschrieben:geht das aber nicht schneller, wenn man wikipedia und co mit re durchsucht?

Was willst du damit finden? Das gesammelte Wissen der Menschheit, sammt aller möglichen Rechtschreibfehler?
Wenn du sowas planst, dann ist das Performanceproblem nicht so sehr wegen den Regulären Ausdrücken gegeben als von der Geschwindigkeit der Wikipedia, die nicht immer besonders schnell reagiert. Davon abgesehen, wären die Admins dort sicher nicht besonders erfreut von der Idee, wenn jemand dort 300000 Artikel abruft, nur damit er dort alle möglichen Wörter in eine Datenbank übernehmen kann.

irgendwas muss man ja nehmen, niemand wäre erfreut...
einfach nicht machen, außer wenn einer einem die laus ins ohr gesetzt hat, T9 zu verwirklichen. ich glaube kaum, dass man diese Datenbank selbst erstellen möchte, sondern eher, dass ein skript viele texte durchließt und dann aus den buchstaben die zahlenwerte ermittelt und dann einträgt...

Och murph, vielleich nimmt man ja auch einfach eine fertige Wortliste zur gewünschten Sprache, wie man sie zum Beispiel in den Wörterbüchern von ispell, aspell oder hunspell findet. Die Mühe Wortlisten für freie Rechtschreibprüfungen zusammenzustellen haben sich schon Leute gemacht. Da muss man nicht gegen die Robot-Regeln von Wikipedia verstossen. Die haben das nämlich wirklich nicht gerne wenn man die Webseite "abgrast".

Und dann ist es sicher schneller *einmal* so eine Wortliste einzulesen und dann direkt in O(1) Zeit von einer Ziffernfolge zu einer passenden Wortliste zu kommen, als jedesmal mit einem regulären Ausdruck alle Worte in der Liste durchsuchen zu müssen.

ich wusste gar nicht, dass es wortlisten frei verfügbar im internet UND in sinnvollen datentypen gibt

@blackjack:

dann aus den buchstaben die zahlenwerte ermittelt und dann einträgt...

das hört sich für mich danach an, dass ich die zahlenwerte auch eintrage.
natürlich will ich das ganze klamunzel nicht bei jedem (programmstart/ausführen einer funktion) machen...

(ich hoffe, dir geht es genauso: es ist nicht persönlich gemeint^^)

murph hat geschrieben:ich wusste gar nicht, dass es wortlisten frei verfügbar im internet UND in sinnvollen datentypen gibt

Falls Du ein Linux verwendest, dann schau mal unter `/usr/share/dict/`, da gibt's traditionell mindestens eine `words` Datei mit englischen Worten und auf deutschen Systemen höchstwahrscheinlich `ngerman` und `ogerman` für neue und alte Rechtschreibung.

@blackjack:

dann aus den buchstaben die zahlenwerte ermittelt und dann einträgt...

das hört sich für mich danach an, dass ich die zahlenwerte auch eintrage.
natürlich will ich das ganze klamunzel nicht bei jedem (programmstart/ausführen einer funktion) machen...

Doch beim Programmstart könnte ich mir das schon vorstellen. Ich würde die 308575 Worte aus der deutschen Liste einmal einlesen und bei jedem "T9-Tastendruck" eine einfachen Zugriff auf ein `dict` durchführen.

Dein `re`-Vorschlag klingt danach, das Du für jeden Tastendruck alle 308575 Worte mit dem regulären Ausdruck durchsuchen möchtest. Was ist wohl schneller!?

gerade dieses habe ich versucht auszudrücken.
ich würde genauso wie du vorgehen.
ich will doch viel lieber eine datei einlesen,
als jedes mal wieder mit der re rüberzugehen!
das mit der re war nur auf das erstellen des wörterbuches bezogen.
das ist aber jetzt bei mir unter linux kein problem

jau, herzlichen dank für eure hilfe...hab da mal ein paar ansätze und werde euch mal meine erfolgserlebnisse verkünden