[linux-l] python

Oliver Bandel oliver at first.in-berlin.de
Mi Mai 29 15:49:00 CEST 2002


Moin,

On Tue, 28 May 2002, Steffen Dettmer wrote:

> * Olaf Radicke wrote on Mon, May 27, 2002 at 20:37 +0000:
> > ich bin hier gerade am grübeln. In den Editor
> > den ich gerade proge wollte ich eine Auto-Wort-
> > Komplementierung integrieren. Sprich: das Prog
> > soll versuchen zu erraten was ich gerade schreiben 
> > will.
> 
> Also nach Häufigkeit?
[...]
> Du mußt ja die Häufigkeit mitspeichern. Die Position ist hier
> nicht ausreichend, denn es kann ja ein Wort gerade eben gekommen
> sein, aber es ist unwahrscheinlich, daß es gleich nochmal kommt.
> 
> > Existiert es schon wird es, wenn es nicht am Anfang
> > steht, dort hin verschoben. Die nicht so häufig
> > verwendeten Wörter wandern so allmählich zum ende.
> 
> Nein, die die häufigen, die stünden dann eben nur mehrfach drin.
> 
> > Das geschriebene Wort wird dann mit den Elementen
> > des Array, von Vorne nach hinten verglichen. Das
> > erste Element das eine Übereinstimmung hat wir
> > vorgeschlagen, da es am Anfang der Liste war hat
> > es die größte Wahrscheinlichkeit richtig zu sein,
> > weil es bisher am häufigsten geschrieben wurde.
> 
> Falsch, es wurde als letzes verwendet. Würde lieber wirklich nach
> Häufigkeiten sortieren.
[...]
> In dem Moment, wo es nicht mehr in den Speicher paßt, wird es
> extrem langsam... Außerdem kannst Du dann die DBM nicht
> sequentiell durchsuchen, sobald Du nicht sinnvoll hashen kannst,
> ist die Performance weg.
[...]
> > Ich hatte auch schon an ein zwei demensionales
> > Array gedacht, aber das würde nur die Nachteile
> > der beiden Lösungen von Oben vereinen.
> 
> Na, mal überlegen. Wir brauchen Worte und deren Anzahl.
> Erschwerend kommt hinzu, daß wir Wortanfänge brauchen, also ist
> ein Hash über die Worte sinnlos. Wir könnten die Wörter
> alphabetisch sortieren und effizient finden, nur leider müssen
> wir nach Anzahlen sortieren. Hier braucht man dann - wenn es
> wirklich performant sein soll - einen Baum. Bespiel für ein
> drei-Buchstaben-Alphabet:
> 
> 
>      Wurzel
>          
>    d       e        i     
>  e  i     r ...    ...
> r    e
> 
> usw. Ist groß und Klein wichtig? Na ja, da man vermutlich genug
> Speicher hat, braucht man erstmal ne Abbildung Zeichen --> Zahl,
> in pseudocode:
[...]
> Damit kann man dann einen Baum über Arrays bauen. Dazu trägt man
> in ein Array an den Index meistens ein weiteres Array ein. Am
> Blatt, wenn also ein Wort fertig ist, trägt man eine Liste von
> Wort und dessen Anzahl ein. Erschwerend kommt hinzu, daß sich die
> Struktur mit neuen Wörter ändern kann. Steht z.B. "dieser" als
> Blatt drin, und kommt "dies" hinzu, so ist nicht mehr "dieser"
> ein Blatt, sondern "dies", welches "dies" und "dieser" enthält.
> Nicht ganz einfach...
[...]


Man nehme Markoffketten und die Übergangswahrscheinlichkeit
von einem Buchstaben zum nächsten innnerhalb einer gegebenen
Sprache (z.B. deutsch), ergänze diesen Ansatz mit der
Bedingung, die Übergangswahrscheinlichkeiten in Abhängigkeit
von den den bereits vorliegenden Buchstaben eines Wortes
zu ermitteln (also kein pures Markoffketten-Prinzip ohne
gedächtnis, sondern schon etwas aufwendiger) und schlage
die aus einer Wortliste wahrscheinlichste (oder alle
Worte aus einer Liste mit abnehmender Wahrscheinlichkeit)
vor.

Man beachte dabei noch, daß die Wahrscheinlichkeiten für
bestimmte Texte sich durchaus von denen des allgemeinen Worrtschatzes
unterscheiden und daher auch die entsprechenden Wahrscheinlichkeitstabellen.

Neben der Buchstabenübergangswahrscheinlichkeit kann man dann
auch noch die Wortübergangswahrscheinlicheeit berücksichtigen
(das wäre dann das, was Du mit "das Wort war gerade und wird nicht
sehr wahrscheinlich gleich nochmal auftreten" gemeint hast).

Und dann nehme man noch eine Menge anderer Ingredenzien und
der Rechner schreibt gleich den ganzen Text alleine. ;-)



> So, jetzt hast Du schon perl code dafür :)
[...]

Wie war das mit dem papier und dem Bleistift? ;-)


Ciao,
   Oliver

-- 
     http://www.belug.org/~ob




Mehr Informationen über die Mailingliste linux-l