Announcement

**Hagen Reddmann** · 17.11.2002, 13:20

Hi Mario

Wof�r ben�tigst Du diese Kombinatorik in einem Scrabble Spiel ??
Wenn Du alle diese Kombinations durchgespielt hast dann bringt dich das auch nicht weiter, da viel zu viele Kombinationen KEINE g�ltigen W�rter sind. 

Besser w�re es sich auf eine effizient Wortdatenbank zu konzentrieren, und per Patternmatching alle g�ltigen W�rter rauszusuchen. 
Ich hatte ein �hnliches Problem und habe dazu ein DAWG = Directed Acyclic Word Graph, benutzt. Eine Wort List mit 544.000 W�rtern hat im Speicher ca. 1.6 Mb belegt. Die Pattern-Matching-Suche ist extrem schnell, ca. 0.02 ms bis 50 ms jenachdem was man sucht. 
Als Resultat hat man dann eine Liste der passenden und g�ltigen W�rter. 

Gru� Hage

**spectrumizer** · 17.11.2002, 13:35

Hi Hagen!

Danke f�r deine Antwort!

Ich benutze nebenher auch eine Wortliste, wo abgeglichen wird, ob die generierten Kombinationen darin vorkommen ... Aber du hast recht, is recht langsam und umst�ndlich, jedoch wars das erste, was mir dazu eingefallen is *g*

Kannst du das Pattern-Matching genauer erkl�ren? Es hat bei mir noch nich klick gemacht ...

Gr��e, Mari

**Hagen Reddmann** · 17.11.2002, 13:57

Pattern-Matching ist eine Suche nach Teilstrings, z.B. *HAUS, und der findet KRANKENHAUS usw. Beim Scrabble muss das Pattern-Matchning abge�ndert werden, so das f�r die Wildcards Buchstaben Set's benutzt werden. Z.b. auf dem Scrabble-Rack liegen 7 Buchstaben und man sucht alle W�rter die man daraus legen kann. 
Dies kann mit der falschen Datenstruktur f�r die Wortliste extrem ineffizient werden. Die schnellste Suche versprechen Datenstrukturen die die Wortliste als Baum repr�sentieren. D.h. es gibt z.B. eine Node zum Buchstaben 'A' als ersten Buchstaben des Wortes. D.h. man fasst die W�rter zusammen die mit gleichen Prefix beginnen. Eine Suche nach 'A*' w�rde mit einer Abfrage diejenige Node finden die ALLE Worte die mit 'A' beginnen enthalten, usw. usw. 
Nun die DAWG's sind daf�r die effizienteste Struktur. Eine 544.000 Wortliste w�rde 1.6 Mb verbrauchen, diese Wortliste als Textdatei aber 6.5 Mb. Um schnell suchen zu k�nnen ist die Kompressions-Dichte entscheidend um die komplette Wortliste im Speicher halten zu k�nnen. Eine sehr gro�e Wortliste ist wiederum entscheidend um dem Computergegner eine Vorteil gegen�ber dem Menschen zu verschaffen. An Intelligenz und Schnelligkeit in der Findung optimaler Z�ge wird man dem mensch. Hirn nicht das Wasser reichen k�nnen. Einzigste Vorteile eines Computer-Scrable Spielers sind:
<li>enorm gro�er Wortschatz ca. 250.000 W�rter zu ca. 2500 W�rtschatz des Menschens 
<li>Emotionslosigkeit des Computers, wir Menschen halten uns viel zu lange mit dem Versuch auf ein einmal gefundenes und sch�nes Wort auf dem Scrabblebrett irgendwie unterzubekommen

Der Computer versucht X'mal ein Wort unterzubekommen und dann nimmt er das n�chste Wort, der Inhalt oder die subjektive Bedeutung des Wortes ist ihm egal, er kennt sie nicht. 

Nun, da ich mich an Kreuzw�rtr�tsel-Code probiert habe, habe ich auch das DAWG und den Pattern-Matchning Code fertig. Ich k�nnte ihn dir mailen, inklusive der Wortlisten, f�r englisch,deutsch,franz�sisch. 
Eines ist noch wichtig. Ein DAWG trifft im Normalfalle eine JA/NEIN Entscheidung, sprich ist gesuchtes Wort vorhanden JA/NEIN. Es kann keinerlei zus�tzliche Informationen zum Wort speichern, keinen Index, keine verlinktes Object o.�. In jedem dieser F�lle w�rde ein DAWG ineffizient werden. Dies ist der Nachteil des DAWG's.

gru� Hage

**Robert Marquardt** · 17.11.2002, 14:21

Es bietet sich auch ein Trie an. Das ist ein Baum aus Woertern. Der erste Knoten enthaelt den ersten Buchstaben des alphabetisch ersten Wortes. Die Verzweigung nach unten gibt den naechsten ersten Buchstaben eines Wortes. Nach rechts geht es zum zweiten Buchstaben. 
Alle Worte des Woerterbuchs werden jetzt so in den Baum eingetragen. Das erste Wort waere "ab". Also erster Knoten 'a'. Nach rechts 'b'. Das zweite Wort "ach" hat den Knoten 'c' unter dem 'b'. Das 'h' ist rechts vom 'b'. 
Jetzt muss man nur mit den vorhandenen Scrabblebuchstaben den Baum entlang klettern. Erreicht man ein Endezeichen (ein #0 bietet sich an) so hat man ein Wort gefunden

**Hagen Reddmann** · 17.11.2002, 16:25

Hi Robert

ein DAWG ist ein Trie, aber mit dem Unterschied das er kompakter als ein Trie ist. Im Trie werden nur die gemeinsamen Wort-Prefixe zusammengefasst, in einem DAWG werden zus�tzlich noch die gemeinsammen Wort-Suffixe zusammengefasst.
Das Ende-Zeichen kann man sich sparen. In meinem DAWG benutze ich pro Buchstaben 1 Cardinal. 8 Bits f�r's Symbol, 1 Bit f�r EON = End of Node, 1 Bit f�r EOW = End of Word und 22 Bits als Index/Offset f�r die Childnode. 
W�rdest Du ein #0 Zeichen als Endezeichen setzen bekommst Du probleme da der Trie eben nicht mehr gemeinsamme Wortprefixe speichern kann. Angenommen: 'MIT'#0, und 'MITTAG'#0. Ohne #0 k�nnen 'MIT' und 'MIT'-'TAG' die beiden 'MIT' als ein Nodebaum mit 3 Nodes gespeichrt werden.
Dann k�me das #0 aus 'MIT'#0 und 'MITTAG' hat aber kein #0. Besser ist es zu Node das EOW zu speichern. D.h. wir h�tten: 
'M' + 'I' + 'T' or EOW + 'T' + 'A' + 'G' or EOW;

gru� Hage

**Robert Marquardt** · 17.11.2002, 16:47

Ich hatte eigentlich an #0 als Zeichen gedacht = eigener Node. C strings eben. Als Optimierung kann man jedem Node eine Zeichenkette zum Verwalten geben. Man kann dann alle waagrechten Knotenketten zusammenfassen, bei denen keine Verkettung nach unten besteht. Das optimiert dann viele Suffixe laengerer Worte. 
Ich glaube dir aber unbesehen das die DAWG-Struktur besser ist. Ich habe versucht eine einfachere Struktur praktisch zu erklaeren, damit man sie auch implementieren kann

**Hagen Reddmann** · 17.11.2002, 18:27

Ja, aber genau das ist doch das Problem. Angenommen das Wort "EIN"#0 w�rde aus 4 Nodes zusammengesetzt, also Node "E" -> Node "I" -> Node "N" -> Node "#0". Das Wort "EINER"#0 w�rde in den ersten drei Nodes mit "EIN" identisch sein. Dann als zweite Childnode bek�me Node "N" die Childs Node "E" -> Node "R" -> Node "#0". Damit heist das, da� wir immer auf Node #0 verzichten k�nnen wenn wir zur Node noch ein Wort-Stopbit f�hren.

Gru� Hage

**spectrumizer** · 17.11.2002, 20:43

Reges treiben hier

Danke f�r eure Antworten!

W�rde mich freuen, wenn du mir den Code + Wordlist mailen k�nntest, Hagen. Wollte dich in meiner ersten Antwort schon fragen (aber nur nach der Wordlist :P). Meine Mail ist: [email protected]

tHx
Mari

**Hagen Reddmann** · 17.11.2002, 21:51

Du bist dir aber �ber die gr��e der mail schon im klaren ?

**spectrumizer** · 17.11.2002, 22:48

Wie gro� w�re sie denn?

Ich hab auch an einen Algorithmus gedacht, der die Buchstaben der W�rter im Wordbook einzeln mit dem Buchstabenpool vergleicht, z.B.
das Wort LIEBE mit dem Buchstabenpool NEIBEL ...

Kommt ein L im Pool vor? -> Ja
Kommt ein I im Pool vor? -> Ja
Kommt ein E im Pool vor? -> Ja
...
Alle Ja? Wort gefunden ... eins Nein? N�chstes Wort ... verstehst du, was ich meine?

Gr��e,
Mari

**Hagen Reddmann** · 18.11.2002, 21:12

Also erstmal zum eigentlichen Problem 

<pre>

<code>procedure DoCombi(Pattern,Pos,Stop: PChar);
// Erzeuge alle Kombinationen ohne Duplikate aus Pattern von der
// Zeichenposition Pos angefangen bis zur Zeichenposition Stop.
// Pattern mu� alpha. sortiert sein.
// 'AABCDEEXYZ' ist korrekt, aber 'KABA..' ist falsch.
// Pattern enth�lt nach Rückkehr von DoCombi() wieder die ursprüngliche
// Sortierung, wird aber w�hrend der Rekursion modifiziert.
// Die Kombinationen werden alpha. aufsteigend enumeriert.
var
Cur: PChar;
Tmp,Last: Char;
begin
if Pos >= Stop then
begin
WriteLn( Pattern );
Exit;
end;
Last := #0;
Cur := Pos;
while Cur <= Stop do
begin
Tmp := Cur^; Cur^ := Pos^; Pos^ := Tmp;
if Tmp > Last then
// verhindere Duplikate !
// Falls alle Kombinationen, inklusive Duplikate enumeriert werden sollen
// mu� diese Abfrage entfernt werden. Die Restriktion der alpha. Sortierung
// ist dann auch nicht mehr erforderlich.
begin
DoCombi(Pattern, Pos +1, Stop);
Last := Tmp;
end;
Inc(Cur);
end;
Tmp := Pos^;
while Pos < Stop do
begin
Pos^ := Pos[1];
Inc(Pos);
end;
Pos^ := Tmp;
end;
 
var
Test: String;
begin
Test := 'ABCDEEN';
DoCombi(@Test[1], @Test[1], @Test[Length(Test)]);
end;

</code></pre>
&#10

**Hagen Reddmann** · 18.11.2002, 21:18

obiger Code kann auch �ber Teilmengen die Kombinationen berechnen, z.B. 

<pre>

Test := 'ABCDE';
DoCombi(@Test[1], @Test[2], @Test[4]);

</pre>

enumierert nur die Kombinationen von 'BCD' und erzeugt 

<pre>

ABCDE
ABDCE
ACBDE
ACDBE
ADBCE
ADCBE

</pre>

Gru� Hagen

</pre&gt

**spectrumizer** · 19.11.2002, 00:51

Krass kurzer und schneller Algo! Ich hab viiieeel komplizierter gedacht, als n�tig gewesen w�re. *g* Vielen Dank!

Wie gro� w�re denn die Wordlist? Hab zwar eine, aber die hat nur ~ 100.000 Worte.

Gr��e,
Mari

**Hagen Reddmann** · 19.11.2002, 18:35

Was heist nur ?? Meines hat auch "nur" 200000 Worte. Das sch�ne am Scrabble ist das auch jede Beugungsform, Mehrzahlen usw. der W�rter erlaubt sind. Im W�rterbuch sollten nat�rlich auch diese W�rter enthalten sein. 
Die Mail hab ich rausgeschickt. 
Interessant w�re wenn wir aus den 100000 + 200000 eine gemeinsamme Wortliste erzeugen w�rden.

Gru� Hage

Announcement

Kombinatorik-Problem: Zeichen in 2-dimensionalem Array miteinander kombinieren

Kombinatorik-Problem: Zeichen in 2-dimensionalem Array miteinander kombinieren

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment