9Live Buchstaben Salat-Spiel

[NMR]

Hi,
ich hätte mal eine frage^^, ich würde gern ein Programm schreiben, dass ein Buchstabelsalt
zn gelvo in alle möglichen kombinationen wiedergibt.
hier z.b
gelvo
ogelv
vogel
lvoge
elvog

ich wollte die zeichenkette dann in array machen und bla..dann in einer schleife...aber ka irgenwie
klappt das nicht so ganz. Wär super wenn ihr mir dabei helfen könnten!!!
Danke euch schon mal jetzt
Bis dann
NMR

[Nicolai1234]

das sind aber nicht alle kombinationen...

Such am besten mal bei google nach Anagramm. Ich denke, das hilft mehr, als sich ein Programm ohen Wörterbuch etc. zu schreiben.

[NMR]

nee will das schon gerne selber schreiben ^^ das doch der spaß an der sache...

[3_of_8]

Die Anzahl der Möglichkeiten berechnet sich bei n Stellen immer nach n!. Also 1*2*3...*n

Bei 9 Stellen wären das dann 9! = 1*2*3*4*5*6*7*8*9 = 362880 Möglichkeiten.

Das nur so nebenbei.

Du musst einfach das Ding als Array nehmen und dann auf zufällige Stellen des Wortes zugreifen, wobei du aufpassen musst, auf keinen bereits verwendeten Buchstaben zu stoßen.

[omata]

<delphi>wegen Nichtbeachtung gelöscht</delphi>

[tn249]

Zitat:

Zitat von 3_of_8

Die Anzahl der Möglichkeiten berechnet sich bei n Stellen immer nach n!. Also 1*2*3...*n

Bei 9 Stellen wären das dann 9! = 1*2*3*4*5*6*7*8*9 = 362880 Möglichkeiten.

Das nur so nebenbei.

Du musst einfach das Ding als Array nehmen und dann auf zufällige Stellen des Wortes zugreifen, wobei du aufpassen musst, auf keinen bereits verwendeten Buchstaben zu stoßen.

Stimmt nicht wenn ein Buchstabe mehr als einmal vorkommt.

"Stamm" zB hat 5! / 2!.

Die 2! kommt daher, weil die "m"s in Stamm nicht unterscheidbar sind.

Gruß
Thomas

[leddl]

Diese Dinger nennen sich "Permutationen". Dazu gibts hier in der DP einige Codes, zB einen von Hagen (der wohl - so wie wir Hagen kennen - recht effizient sein dürfte ;)): http://www.delphipraxis.net/internal...ect.php?t=7561
Dann gibts in der CodeLib noch einen von glkgereon: http://www.delphipraxis.net/internal...ct.php?t=74277

Ich hab mir beide Codes jetzt nicht genauer angeschaut, aber du bekommst die Permutationen zB, indem du rekursiv in deiner Ausgangsfolge 2 Stellen vertauschst. Der Code dazu ist nichtmal allzu schwer. Ich denke aber mal, daß Hagen und glkgereon sich etwas mehr Gedanken gemacht und dann einen etwas performanteren Code entwickelt haben ;)

[NMR]

jo vielen dank klappt wunderbar!!!

[3_of_8]

Zitat:

Zitat von tn249

Stimmt nicht wenn ein Buchstabe mehr als einmal vorkommt.

"Stamm" zB hat 5! / 2!.

Die 2! kommt daher, weil die "m"s in Stamm nicht unterscheidbar sind.

Ich gebe zu, ich habe mich undeutlich ausgedrückt. Ich meinte "Man muss aufpassen, dass man nicht eine Stelle des Wortes, also ein Zeichen des Wortes zwei mal dran nimmt, im Sinne von dass man zwei mal den gleichen Index hat.

[Der Jan]

Leider gibt es ja in Delphi keine STL :) Dort gibt es die Funktionen "next_permutation" und "prev_permutation" genau für diese Zwecke.
Allerdings gibt es doch für Delphi ähnliche Containerklassen wie in der STL, hab ich mal irgendwo gelesen, glaub sogar von den JEDIs. Oder ich irre mich komplett... :gruebel: Aber falls nicht, könnte es dort doch auch solche Funktionen geben.
btw: ein Kleines Prog für Buchstaben-Salat: Wortsuche

[3_of_8]

Eine einfach verkettete, zyklische Liste, die wäre hierfür perfekt geeignet.

[lizardking]

Zitat:

Zitat von leddl

Ich denke aber mal, daß Hagen und glkgereon sich etwas mehr Gedanken gemacht und dann einen etwas performanteren Code entwickelt haben ;)

*g* Spaetestens beim zweiten Beitrag hab ich auch direkt an Hagen gedacht. Ich wette, er hat sogar noch ein paar Tips parat, wie man Anzahl der sinnvollen Permutation noch weiter einschraenken kann.
Wenn man z.B. davon ausgeht, dass es nur um deutsche Worte geht, koennte man z.B. davon ausgehen, dass die Buchstaben "p" und "t" selten hintereinander stehen.
Bei den angesprochenen 9 Stellen, die die Buchstaben "p" und "t" enthalten, koennte die direkte Kombination "pt" 8 mal auftauchen. Die restlichen 7 Buchstaben koennen wieder in 7! Kombinationen auftauchen, also 5040 Kombinationen. Das mal 8, dann haben wir 35280 moegliche Worte.
Also durch EINE einfache Regel direkt ueber 90(!)% der moeglichen Worte ausgeschlossen. Taucht "p" oder "t" doppelt auf, dann geht's noch weiter runter etc. pp.

Aehm. Problematisch wird's bei zusammengesetzten Worten. Da kann natuerlich auch oefter mal ein "pt" auftauchen. Aber ich denke durch solche Sprachspielereien bekommt man schon relativ gute Wortlisten mit guter Trefferquote ;-)

Gruesse,

Lizzy

P.S.: Wenn ich irgendwo Rechenfehler drin hab, bitte melden ;-)

[negaH]

Probiere mal das Attachment.

0.) ZIP entpacken
1.) Project1.exe starten
2.) Button "Dawg laden" klicken
3.) Test.dawg auswählen
4.) in Edit "Kombinatorische Suche" deine Buchstaben eingeben (Groß/Kleinschreibung irrelevant)
5.) in Edit "min. Länge" zb. 5 eingeben
6.) Checkbox "Suche anzeigen" anhacken
7.) Button "Wörter erzeugen" anklicken

Nun zur Theorie:

Die Basis ist eine ganz spezielle Form einer Baumstruktur -> Directed Acyclic Word Graph -> DAWG in der dann ca. 200.000 deutsche Wörter gespeichert sind. Eine solche Liste als Textdatei würde ungefähr 3 Mb benötigen und ist als DAWG nur noch 800 Kb groß. Zusätzlich kann man in diesem DAWG Tree nun sehr schnell und effizient suchen. Neben der Komprimierung des Wörterbuches und der vollständigen Entfernung der redundanten Prefixes und Suffixe der Wörter ist die schnelle Suche die Hauptaufgabe dieses DAWG.

Das Program demonstriert nun wie man in einem solchen DAWG schnell suchen kann. Einerseits ein Pattern-Matching das Wildcards unterstützt, zb. für Rechtschreibprüfungen etc.pp. Und eine weitere Suchfunktion ist die kombinatorische Suche (Permutationen), wie zb. beim Scrabble, Kreuzworträtseln oder eben 9Live nötig.

Ich benutze dieses kleine Projekt immer wenn ich mal interessante Rätsel auf 9Live (beim Durch-Zappen wohlgemerkt :) ) sehe.

Die Organisation solcher Wortlisten in einem DAWG ist der/die beste und effizienteste Algorithmus/Datenstruktur die ich für diese Aufgabe kenne. Die Zielsetzung meinerseits für die Entwicklung dieses Source war es eben die performanteste Lösung zu kreieren. Ich kenne keine andere Tree-Implementierung die schneller ist. Und bei der weiteren Entwicklung von zb. Kreuzworträtseln oder meiner Scrabble Engine benötigte ich eben eine enorm schnelle Suche, auch kombinatorisch, über sehr große Wortlisten.

Der DWAG Source demonstriert

- Konstruktion eines DWAG Tree, als azyklische Datenstrukturen, Nodebäume mit multiplen Verlinkungen
- die dynamische und sequientielle "just in time" Erzeugung solcher Tree's
- Verwendung eines eigenen inplaced Speichermanagers für die Node Strukturen
- Verwendung simpler boolscher Algebra innerhalb der Nodes für deren hierarischem Aufbau, dh. die Treenodes sind keine dynaisch allozierten Datenstrukturen wie Records oder Objekte
- Verwendung von Hashfunktionen (nicht die kryptographischen Hashfunktion) bei der Komprimierung eines solchen Tree's -> entfernen der redundanten Wort Suffixe, dh. Wörter mit gleichen Endungen werden zusammengefasst
- Suche per multiplem Patternmatching und Wildcards
- Suche per Kombinatorik -> Permutation von Buchstaben
- sowohl iterative wie auch rekusive Algorithmen
- Enumeration per Callbacks in einem solchen Tree

Essentiell geht es, im Sinne dieses Threads, darum das man mit Hilfe einer Wörterdatenbank die erzeugten und möglichen Permutationen der Buchstaben auf sinnvolle Weise einschränkt. Man erzeugt also nur die Wörter die es auch in einer jeweiligen Sprache gibt. Technologisch wäre ein DAWG wie in meinem Beispiel nun eine Lösung die effizient in der algorithmischen Komplexität und im Speicherverbrauch ist.


Gruß Hagen


PS: hier ein Auszug aus dem Source
PPS: Tippfehler beseitigt

Delphi-Quellcode:

function TDawg.Search(const Pattern: String; Found: TDawg; WithLength: Integer): Boolean;
// search all words to pattern and insert into Dawg Found
// sample patterns
//  '*A*' , search any words with one or more 'A'
//  'A*'  , search words with leading 'A'
//  '*A'  , search words with trailing 'A'
//  '?A*' , search words with second char is 'A'
//  '*#*' , search words with a number
// Patterns can be concatenated, like
//  '*A,A*,*B,*B'

{ follow some benchmarks,
  - used a Dawg with 200023 german words,
  - this Dawg need 811 Kb memory, as text file it require 2.54 Mb
  - my machine is a P4 1.5 GHz 512 Mb
  - loading this textfile wordlist with .LoadWordsFromFile() take 127 ms
  - packing this Dawg take 134 ms, so both actions take 261 ms
  - Dawg binary load 4 ms, save 23 ms
  - unpacking with .Unpack take 32 ms
  - save this Dawg as textfile wordlist take 71 ms

pattern                    time      entries found

"haus"                   0.003 ms,          1
"haus?"                  0.004 ms,          2
"haus??"                 0.008 ms,          5
"haus???"                0.014 ms,          7
"haus????"               0.032 ms,         35
"haus?????"              0.039 ms,         37
"haus*"                  0.211 ms,        333
"haus*e"                 0.122 ms,         65
"haus*e*"                0.300 ms,        258
"haus?e*"                0.040 ms,         65
"?haus"                  0.010 ms,          0
"??haus"                 0.073 ms,          1
"???haus"                0.490 ms,          4
"????haus"               1.454 ms,         27
"?????haus"              2.899 ms,         31
"*haus"                 41.880 ms,        144
"*haus*"                42.224 ms,        672
"?a*haus*"               5.579 ms,         70
"*a*haus*"              66.794 ms,        136
"*a*haus*,*b*haus*"    118.996 ms,        172
"a*"                    14.242 ms,      21493
"k*"                     7.241 ms,      10373
"z*"                     5.541 ms,       8333
"*a"                    40.221 ms,        828
"*k"                    40.719 ms,       1709
"*z"                    40.697 ms,       1116
"*a*"                  126.564 ms,      97243
"*k*"                   73.401 ms,      41656
"*z*"                   61.417 ms,      27220
"#*"                     0.003 ms,          0
"*#*"                   43.483 ms,          0
"*#"                    40.526 ms,          0
"*"                    146.523 ms,     200023
"?"                      0.007 ms,         15
"??"                     0.060 ms,        121
"???"                    0.307 ms,        511
"????"                   1.316 ms,       1672
"?????"                  3.588 ms,       3917
"??????"                 6.868 ms,       6810
"???????"               10.748 ms,       9724
"????????"              16.141 ms,      13943
"?????????"             22.812 ms,      19172
"??????????"            28.357 ms,      22876
"???????????"           32.665 ms,      25113
"?,??"                   0.063 ms,        136
"?,??,???"               0.377 ms,        647
"?,??,???,????"          1.717 ms,       2319

follow searches search only words with 7 chars, eg. param WithLength = 7

"haus"                   0.002 ms,          0
"haus?"                  0.003 ms,          0
"haus??"                 0.006 ms,          0
"haus???"                0.015 ms,          7
"haus????"               0.011 ms,          0
"haus?????"              0.011 ms,          0
"haus*"                  0.013 ms,          7
"haus*e"                 0.019 ms,          0
"haus*e*"                0.021 ms,          3
"haus?e*"                0.008 ms,          2
"?haus"                  0.010 ms,          0
"??haus"                 0.071 ms,          0
"???haus"                0.478 ms,          4
"????haus"               1.469 ms,          0
"?????haus"              2.890 ms,          0
"*haus"                  9.834 ms,          4
"*haus*"                 9.776 ms,         15
"?a*haus*"               1.401 ms,          1
"*a*haus*"              13.499 ms,          1
"*a*haus*,*b*haus*"     24.725 ms,          2
"a*"                     0.835 ms,        775
"k*"                     0.535 ms,        572
"z*"                     0.292 ms,        304
"*a"                     9.511 ms,        124
"*k"                     9.389 ms,         87
"*z"                     9.319 ms,         56
"*a*"                   14.088 ms,       3753
"*k*"                   11.280 ms,       1497
"*z*"                   10.491 ms,        849
"#*"                     0.002 ms,          0
"*#*"                    9.892 ms,          0
"*#"                    10.190 ms,          0
"*"                     11.265 ms,       9724

}

[Luckie]

Darf ich das zu deinem DEC auf meiner Homepage packen? Deinen Beitragstext würde ich dann als Dwag.txt dazu hochladen.

Btw. Das Spiel heisst Scrabble. ;)

[negaH]

Hi Luckie,

ja natürlich.
Und meine ständigen Tippfehler dürften dir ja bekannt sein ;) Wir beide haben die Schule zu einer Zeit runter gerissen als Schreibmachine lernen noch unbekannt war.

Gruß Hagen

[Luckie]

Danke. Das gehört nämlich zu den Perlen, die nur allzuleicht wieder verloren gehen hier im Forum. Genau wie der API-Hook von toms oder einige Sachen von Nico.

[negaH]

Übrigens alle Rätsel die ich auf 9Live oder auch SAT1 in dieser Form gesehen habe, konnte ich mit der 200.000 Wörtern umfassenden Wortliste im DAWG lösen. Ich hatte also noch kein einzigsten Fall bei dem die Wortliste unvollständig war !

Ich hatte sogar mal ein zweites Program geschrieben das die 2D Wortsuch-Rätsel auf ähnliche Weise gelösst hat. Bei diesem Rätsel gibt es ein 2D Feld aus lauter Buchstaben und man soll dann zb. 5 Städtenamen oder Automarken finden.
Leider finde ich die Sourcen nicht mehr. Es war aber so programmiert das alle Buchstaben einer Zeile und Spalte dieses 2D Gitters als Suchpattern der kombinatorische Suche dienten. Man erzeugt also pro Spalte/Zeile aus diesen Buchstaben alle Wörter/Städtenamen/Automarken die möglich waren. Dann wurde diese erzeugte Liste einfach mit der Such-Spalte/Zeile abgeglichen.
Interessant dabei war folgendes: Alle diese Rätsel enthielten weit mehr als 5 gültige Namen. Dh. im Rätsel selber sind zb. 7 verschiedene Städtenamen versteckt. Macht bei 5 richtigen also insgesammt 210 mögliche richtige Antworten. Es ist damit ein leichtes für 9Live/SAT1 also erstmal 209 Lösungen abzuwarten und zu behaupten das keine dieser Lösung richtig ist. Die Frage lautet ja auch "finden sie die 5 Städtenamen die wir suchen !". Sehr geschickte Abzocke ;)

Gruß Hagen

[Luckie]

Da isses: http://www.michael-puff.de/dirindex....agen_Reddmann/ :)

[SubData]

Jedesmal wenn ich einen von Hagens Beiträgen lese, komme ich mir so endlos dumm vor -g-

[Mackhack]

Zitat:

Zitat von SubData

Jedesmal wenn ich einen von Hagens Beiträgen lese, komme ich mir so endlos dumm vor -g-

Jepp er weis ne Menge und ich lese gerne seine Beitraege!!! Er ist halt wie ne Library und hoffe er wird uns noch viel helfen!!!

Danke auch von mir an dich Hagen!

[3_of_8]

:shock:

Schon wieder eins von Hagens hyperoptimierten Superprogrammen.

Da kommt man sich wirklich total dumm vor...

[Luckie]

Hagen ist auch mehr als doppelt so alt wie du. Du hast also noch viel Zeit zum Lernen. :zwinker:

[pszopp]

Zitat:

Zitat von negaH

Ich hatte sogar mal ein zweites Program geschrieben das die 2D Wortsuch-Rätsel auf ähnliche Weise gelösst hat.
...
Leider finde ich die Sourcen nicht mehr.

Wir hatten das zufälligerweise heute in einer unserer Abschlussprüfungen als Aufgabe gestellt.
Ich habe meine Lösung mal als Anhang reingehängt.
Da die Klausur zeitlich auf 2 Stunden begrenzt ist und wir das alles auf Papier machen
müssen (inkl. Programmbeschreibung und Diagrammen),
ist der Code sicher nicht optimal, reicht aber für den Anfang.

Gruß
pszopp

[Luckie]

Zitat:

Zitat von negaH

Ich benutze dieses kleine Projekt immer wenn ich mal interessante Rätsel auf 9Live (beim Durch-Zappen wohlgemerkt :) ) sehe.

Gerade bei Live: enthaaroung. Da findet dein Programm nichts. :(

[Matze]

Hi,
irgendwie bin ich zu dumm für das Programm (das von pszopp). *g*

Ich dachte, wenn Luckie 9live guckt, kann ich ja auch mal hineinschalten :mrgreen: , Kommentare zu dem Sender äußere ich keine, nur soviel, ich gucke sowas nicht, aber dort ist gerade das Rätsel:

CLUB
HERZ
LIST

Man soll das Wort suchen. Dann habe ich versucht dein Programm zu nutzen, das sah dann so aus:

Code:

Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

C:\Dokumente und Einstellungen\mhielscher>d:

D:\>cd 9live

D:\9live>console
Bitte geben Sie eine Zeile der Matrix ein, oder beenden Sie die Eingabe mit eine
m leeren String:
CLUB
Bitte geben Sie eine Zeile der Matrix ein, oder beenden Sie die Eingabe mit eine
m leeren String:
HERZ
Bitte geben Sie eine Zeile der Matrix ein, oder beenden Sie die Eingabe mit eine
m leeren String:
LIST
Bitte geben Sie eine Zeile der Matrix ein, oder beenden Sie die Eingabe mit eine
m leeren String:

Bitte geben Sie das zu suchende Wort ein:

Nun steht da ja

Zitat:

Bitte geben Sie das zu suchende Wort ein:

Woher soll ich denn wissen, was das gesuchte Wort ist? Wenn ich das wüsste, bräuchte ich dein Programm doch nicht. :duck:

Habe mir den Code jetzt allerdings nicht angesehen.

[Luckie]

Hagens Programm sagt: Schutzbrille. :mrgreen:

[pszopp]

Zitat:

Zitat von Matze

Woher soll ich denn wissen, was das gesuchte Wort ist?

Wie gesagt: Wir hatten das gestern als Prüfungsaufgabe und da war das Wort halt vorgegeben.
Es war ein Wortfeld gegeben:

tghe
hemj
ulsx
opst

Dieses ist quadratisch und in diesem Feld soll ein bestimmtes Wort gesucht werden.
Zum Beispiel test.

Gruß,
pszopp

[Nicolai1234]

Zitat:

Zitat von Luckie

Zitat:

Zitat von negaH

Ich benutze dieses kleine Projekt immer wenn ich mal interessante Rätsel auf 9Live (beim Durch-Zappen wohlgemerkt :) ) sehe.

Gerade bei Live: enthaaroung. Da findet dein Programm nichts. :(

Das einzige wäre evtl. Orangenhaut aber irgendwie bezweifel ich, dass die solche Wörter nehmen.

[Luckie]

Doch genau das wird es gewesen sein. :wall:

[negaH]

Orangenhaut ist in meinem DAWG mit 200.023 Wörtern nicht enthalten, so'n Mist ;)

orange
orangefarbenem
orangefarbenen
orangefarbener
orangen
orangenbaum
orangenblüte
orangenernte
orangenmarmelade
orangensaft
orangensaftes
orangenschale
orangensekt
orangerie
orangeroter


gruß Hagen

[Der Jan]

Zitat:

Zitat von Nicolai1605

Zitat:

Zitat von Luckie

Zitat:

Zitat von negaH

Ich benutze dieses kleine Projekt immer wenn ich mal interessante Rätsel auf 9Live (beim Durch-Zappen wohlgemerkt :) ) sehe.

Gerade bei Live: enthaaroung. Da findet dein Programm nichts. :(

Das einzige wäre evtl. Orangenhaut aber irgendwie bezweifel ich, dass die solche Wörter nehmen.

oder: Haartoenung :)

[vlees91]

So
ich habe sowas vor wenigen Wochen für sowas ähnliches gemacht. Und zwar habe ich ein Array mit 150k Wörtern die im Deutschen gebräuchlich sind und habe anschließend die Wörter verglichen
Sodass es schnell geht habe ich alle "a" im eingabe-wort gezählt
alle b
usw
dann das gleiche bei den Wörtern im array
und wo eine übereinstimmung war, wurde es ausgegeben
das ganze war in php, wird in Delphi aber bestimmt auch ganz gut gehen

[Der Jan]

@vlees: Sowas macht das klar schneller. Um zu testen, ob ein Wort mit einem Buchstabensalat übereinstimmt, muß man nicht tausende Permutationen bilden. Bei mir mach ich es einfach so, das ich pro Buchstabe einen Flag setze, wenn alle gesetzt sind, passt es :)

[vlees91]

Meine Funktion in einem lahmen PHP (XAMPP), der auf einem Intel Pentium III 933Mhz läuft, der irgendwie gaaaaaanz langsam ist, brauche ich 5 Sekunden um alle Wörter durchzugehen. Also wie auch der Jan sagte: es ist schnell! ;)

Hier mal mein Code: (Die Funktion um die Buchstaben zu zählen ist von PHP (ich glaube das ist schneller für PHP als eine eigene Schleife), aber es wäre sehr einfach sowas selber zu machen)

Code:

<html>
<head>
<title>Char-Sorter</title>
<style type="text/css">
<!--
body {
 font-family: Tahoma;
}
-->
</style>
</head>
<body>
<?php
  $word = trim($_GET['word']);
  $word2 = count_chars($word, 1);
  include 'list.php';
  echo 'Es sind [b]'. count($wordlist) .'[/b] Wörter in der Liste vorhanden.

';
  $possible = array();
  $i = 0;
  while ($i < count($wordlist)) {
    if ($word2 == count_chars($wordlist[$i], 1)) {
      $possible[] = $wordlist[$i];
    }
    $i++;
  }
  if (count($possible)) {
    echo 'Möglichkeiten:
';
    $i = 0;
    while ($i < count($possible)) {
      echo ($i + 1) .': [b]'. $possible[$i] .'[/b]
';
      $i++;
    }
  }
  $word2 = count_chars(strtolower($word), 1);
  $possible = array();
  $i = 0;
  while ($i < count($wordlist)) {
    if ($word2 == count_chars($wordlist[$i], 1)) {
      $possible[] = $wordlist[$i];
    }
    $i++;
  }
  if (count($possible)) {
    echo 'Möglichkeiten (kleingeschrieben):
';
    $i = 0;
    while ($i < count($possible)) {
      echo ($i + 1) .': [b]'. $possible[$i] .'[/b]
';
      $i++;
    }
  }
  $possible = array();
  $i = 0;
  while ($i < count($wordlist)) {
    if ($word2 == count_chars(strtolower($wordlist[$i]), 1)) {
      $possible[] = $wordlist[$i];
    }
    $i++;
  }
  if (count($possible)) {
    echo 'Möglichkeiten (verglichen mit kleingeschriebener Wortliste):
';
    $i = 0;
    while ($i < count($possible)) {
      echo ($i + 1) .': [b]'. $possible[$i] .'[/b]
';
      $i++;
    }
  }
?>
</body>
</html>

EDIT: in der list.php steht <? $wordlist = array(.......); ?>

[vlees91]

zu Hagen: ist das ein DWAG oder ein DAWG

zur anfänglichen Frage: Du kannste jetzt z.B. den Code von mir nehmen und eine Wortliste aus dem Internet (ich habe eine die frei verfügbar ist, und eigentlich als Wörterbuch dient, ich habe sie aber missbracuht ;)) oder Hagens aus dem DAWG oder dem DWAG (wer weiß)
Dann wartest du, bis 9Live/DSF/etc. wieder losgeht und dann rufst du da ann und nennst denen 50 Wörter! :P

[negaH]

DAWG ist richtig, heist ja auch Directed Acyclic Word Graph -> gerichteter azyklischer Wörter Baum.

Übrigens enthält mein mitgeliefertes DAWG 200000 Wörter und alle diese Wörter zu durchsuchen, sprich die Suchmaske '*' zb. dauert 250 Millisekunden. Das ist aber der absolute Worstcase denn wer sucht schon ALLE Wörter auf einmal. Und so ergibt sich zb. bei der Suche aller Wörter die mit A anfangen eine Zeit von ca. 14 Millisekunden und er findet 21493 Wörter dabei. Das DAWG wird nun deutlich schneller je mehr man die Suchmaske einschränkt. Bei der Kombinatorischen Suche heist dies, das zb. bei 7 Buchstaben die gesucht werden sollen, im Durchschnitt weniger als 1 Millisekunde benötigt wird, es sind sogar meistens so um die 0,02 Millisekunden, sprich ca. 20 Mikrosekunden.

20 Mikrosekunden zu 5 Sekunden ist ein sehr deutlicher Unterschied in der Effizienz. In einigen Fällen benötigt man eine so enorme Performance, zb. wenn man Millionen von möglichen Kombinationen in einem Kreuzworträtzel oder bei einem Scrabble-Computer-Gegner pro Sekunde durchrechnen möchte. Also quasi in einer KI eines Wortbasierten Spieles.

In Falle des Problemes hier dürfte aber das nicht so entscheidend sein.
Ich möchte halt nur betonen das ein Vergleich zwischen meinem DAWG und einer simplen PHP Lösung ein Vergleich zwischen Äpfeln und Birnen sein muß, auch wenn beide Algorithmen im Endeffekt das gleiche Resultat liefern.

Gruß Hagen

[vlees91]

dein programm ist bei mir langsamer dann deine werte. naja. mein php-server läuft ja auch nicht optimal

[Olli]

... langsamer sicher nur, weil der Hagen einen total schnieken und neuen Multiprozessor-Compi mit superviel RAM und einem getunten Betriebssystem hat - du aber nur eine 386er-Möhre mit 64MB RAM :mrgreen:

Fragt mich nicht woher ich es weiß, ich sage nur: Telepathie

Was wir oft vergessen ist, daß die Laufzeit eines Programms zu einem nicht geringen Teil von der Prozessorleistung abhängt.

[negaH]

Das ist schon richtig, bezieht sich aber NICHT auf die Komplexität eines Algorithmus ansich.

Das mein DAWG Algo. langsammer als eine Scriptsprache wie PHP sein soll die dann sogar noch einen Algo benutzt der von seiner Komplexität wesentlich schlechter sein muß, halte ich für ein Gerücht. Sorry das ich das so deutlich sagen muß, das hat nichts mit einem persönlichen Angriff zu tuen.

Du sagst das du mit einem sortierten Array arbeitest. Gut, denn die Suchkomplexität in einem solchen Array ist O(ln n). Das ist defakto die gleiche Komplexität wie in einem Baum auf eine Node bezogen. Mit dem Unterschied das das Array[] als solches ja linear alle Einträge enthält der Baum aber linear alle Einträge zu einem Buchstaben. Somit ist die Gesamtkomplexität eines Suchbaumes abhängig von dem Alphabeth mit 256 Elementen mindestens 256 mal schneller als ein solches Array ! Das ist aber der Worstcase, denn in einer Wortliste werden ja nur 26+10 Buchstaben des Alphabeths tatsächlich benutzt. Wenn also bei einer Patternsuche oder kombinatorischen Suche in einem solchen Baum die Entscheidung für einen gefundenen Buchstaben gefallen ist so heist dies das alle nachfolgenden Kombinationen von vornherein 255/256'tel==99.6% aller Wörter ausgeschließen. Bei einem simplen sortierten Array ist dies nicht zwangsläufig der Fall.

Nun das DAWG ist ein solcher Suchbaum, aber mit der besonderen Eigenschaft der zusätzlich hohen Komprimierung im Vergleich zu einem Array[].

Wie gesagt ich kann es mir nicht vorstellen das eine Scriptsprache wie PHP mit einem schlechteren Algorithmus schneller sein sollte als eine nativ kompilierte Anwendung die einen mathematisch besseren Algo verwendet.

Sollte das tatsächlich der Fall sein so gibt es ein gewaltig großes Beben in meinem Glauben ;)

Gruß Hagen

[negaH]

Sag mal, ich bin ja nicht sooo fit in PHP, aber kann es sein das dein Code nur alle Wörter raussucht die zb. 7 Buchstaben enthalten ? Also wir haben 7 Buchstaben wie "AACDHIK" und suchen nun alle Wörter die exakt aus diesen 7 Buchstaben bestehen. Kann es sein das es deinem PHP Code schnuppe ist welche 7 Buchstaben gesucht werden und einfach alle Wörter mit 7 Buchstaben raussucht ??

Wenn ja, sind das Äpfel mit Birnen verglichen, denn meine kombinatorische DAWG Suche findet nur die Wörter die sich aus diesen 7 Buchstaben bilden lassen, also gültige Wörter !

Für eine Suche wie die deinige wäre es angebrachter einfach eine Listenstruktur zu benutzen die nach Anzahl der Buchstaben im Wort sortiert ist. Klar das der einfachste Fall eine Liste aus allen Wörtern mit zb. 7 Buchstaben wäre. In diesem Falle muß man garnichts mehr suchen sondern nur diese Liste komplett laden und als reguläre Antwort zählen.

Gruß Hagen