[linux-l] python

Di Mai 28 12:14:56 CEST 2002

* 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?

> Es sollen also alle Wörter die geschrieben werden
> gespeichert werden. Dann soll das nächste Wort
> was eingetippt wird verglichen werden mit dehnen
> die schon geschrieben wurden. Wenn es mehrere Wörter
> gibt die passen, soll Das vorgeschlagen werden
> was bisher am häufigsten vor kamm.

Aha. Verstehe (glaub ich) :)

> geschrieben was es noch nicht im Array gibt wird
> es mit "x.insert(0, Wort)" an den Anfang gestellt. 

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.

> Was mir daran nicht gefällt ist, das der ganze
> Array im Speicher gehalten wird. 

Wie groß werden die Texte so? Ein paar tausend Zeichen sind
überhaupt kein Problem. 

> Und das es nach
> einer weile in dem Array aussieht wie in einen
> schweitzer Käse, weil ständig mittendrin Elemente 
> gelöscht werden.

Wer löscht mittendrin Elemente? Achso, wenn Du eins einfügen
möchtest, was schon drin steht?

> Und es wird immer länger.

Ja, logo, dadurch wird der Algorithmus immer besser...

> Die zweite Variante währe mit DBM. Das würde
> den Speicher schonen.

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.

> Und da könnte ich explizit zählen wie oft ein Wort bisher
> vorgekommen ist.  Aber dafür müsste ich im einer aufwendigen
> Sortierschleife den kompletten Hash (b.z.w."Dictionary")
> durchgehen. Was dann bei ensprächend vielen einträgen dauern
> kann.

Das wäre ja dann sequentiell, so: "für jedes Element schaue, ob
es mit xx anfängt".

> 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:

sub zeichenwert ($) {
	my $zeichen = shift;
	#lc: lowercase
	#ord: returned ASCII von zeichen
	#ord (buchstabe) - ord ('a') ist damit zwischen 0 und 25
	return ord ( lc ($zeichen) ) - ord 'a';
}

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...

Also, wenn man ein Blatt anlegt, muß man alle vorher
"drunterliegenden" Blätter mit auf seine Liste packen. Bei kurzen
Wörtern wird das dann auch ineffizient, Mist. Dann sucht man ja
wieder in einer langen Liste. Also läßt man vielleicht doch
lieber den Baum. Aber dann muß man alle Äste einsammeln....

Nochmal überlegen... Ach ja, man muß das noch erweitern, man muß
zwischen End- und Folgenodes unterscheiden können. 

Eine andere Idee wäre, wenn man die Algorithmus vereinfacht. Man
kann ja bestimmt sagen, die Ratefunktion beginnt erst, wenn zwei
Zeichen getippt wurden. Nun gibt es ja deutlich weniger Worte,
deren ersten beiden Buchstaben gleich sind. Diese Liste ist
vermutich kurz genug, um verdammt schnell durchsucht zu werden
(müßte man mal über einer großen Textdatei testen, ich schätze
mal, daß reicht). Dann macht man sich einen Hash, verwendet die
ersten beiden Bcuhstaben als Key. Der Wert ist eine Liste von
Wörtern und Anzahlen. Würde ich in dem Fall nach Alphabet
sortieren (oder auch gar nicht).

Beispieleintrag "dieser", "die", "die":

#weil wir ja keine Hashmap als zweite Ebene von wordindex wollen, 
#  müssen wir sowas machen:
$w1 = { 'wort' => "dieser",
        'anzahl' => 1 };

$w2 = { 'wort' => "die",
        'anzahl' => 1 };

push $wordindex { 'di' }, $w1;
push $wordindex { 'di' }, $w2;

Wenn man jetzt noch ein "die" hat, muß man addieren. Also vorher
gucken, ob's das Wort schon gibt. Könnte man vielleicht in so
einer Form machen:

#Algorithmus zum Anlegen von Einträgen

$wort = "die"; #das wort

$key = substr($wort, 0, 2); #ersten beiden Zeichen

my $found = 0;
if (!defined $wordindex { $key }) {
	$wordindex { $key } = (); #leere Liste
	#wir müssen jetzt nicht suchen, ist eh leer!
} else {
	#wir müssen mal suchen
	ADD:
	foreach $wortstruct ($wordindex { $key }) {
		if ($wortstruct{'wort'} eq $wort) {
			$wortstruct{'anzahl'}++;
			found = 1;
			last ADD;
		}
	}
}

if (!found) {
	#muß wohl ein neues Wort sein:
	$wortstruct { 'wort' => $wort,
		      'anzahl' => 1 }; #initialer stuct
	push $wordindex { $key }, $wortstruct; #speichern
}

So, jetzt hast Du schon perl code dafür :)

Das ist jetzt noch unsortiert, aber vermutlich einfach schon mal
schnell genug.

beim Suchen eines Wortes:

#Algorithmus zum Finden von Einträgen

$wort = "die"; #das wort
if (length ($wort) < 2) {
	return $wort; #keinen anderen Vorschlag
}

$key = substr($wort, 0, 2); #ersten beiden Zeichen
if (!defined $wordindex { $key }) {
	return $wort; #keinen anderen Vorschlag
}

#höchste Anzahl suchen
$besteswort = $wort;
$besteanzahl = 0;
foreach $wortstruct ($wordindex { $key }) {
	#wortteil genauso lang wie $wort (rest interssiert nicht)
	$wortteil = substring($wortstruct{'wort'}, 0, length ($wort));
	$anzahl = $wortstruct{'anzahl'}; #short cut
	if ($wortteil eq $word and $anzahl > $besteanzahl) {
		$besteswort = $wortstruct{'wort'};
		$besteanzahl = $anzahl;
	}
}

return $besteswort;

So, Kleinigkeiten wie $wort = lc ($wort); fehlen vielleicht noch,
aber ich denke, daß sollte so funktionieren und schnell sein.
Perl ist ja ein Compiler. Was Phyton (nimmst Du doch?) macht,
weiß ich nicht, sollte aber analog zu implementieren sein,
vermutlich heißen nur die Funktionen bißchen anders, wenn
überhaupt.

Wörter aus der Liste löschen würde ich überhaupt nicht und
niemals, wozu auch! Der Algorithmus könnte jedoch vielleicht bei
einem Leeren Text eine andere Datei als Initial-Werte verwenden,
irgenteinen Text eben, dann ist "die" und "und" automatisch
bekannt, auch wenn man es (selbst) noch nicht getippt hat. Eigene
Wörter sind dann trozdem bekannt.

Ich würde vermutlich noch wünschen, daß man nicht nur den besten
Treffer erhält, sondern aus den Treffer auswählen kann. Weiß
nicht, ob das mit den zwei Knöpfen machbar ist. Dann könnte man
beim Suchen einfach ne Liste aller Treffer, sortiert nach anzahl,
zurückgeben und ggf. durch diese Durchblättern, denn wenn man
z.B. "die" tippt, und "dieser" meint, aber "die" einmal mehr als
"dieser" verwendet wurde, würde ja immer "die" vorgeschlagen
werden. Nur mal als Idee.

So, ich hoffe, Dir hilft das was, hat nämlich richtig viel Zeit
gekostet, diese Mail...

oki,

Steffen

-- 
Dieses Schreiben wurde maschinell erstellt,
es trägt daher weder Unterschrift noch Siegel.