PHP-dictionary-Klasse? oder alternative?

Im Grunde, was ich Suche, ist eine Art von Klasse oder Methode zu implementieren, die ein Wörterbuch in PHP.
Wenn ich mich zum Beispiel war der Bau eines word unscrambler - können sagen, ich verwendet die Buchstaben "a,e,l,p,p' -. Die Anzahl der Möglichkeiten der Anordnung ist riesig - wie kann ich nur diese anzeigen, die tatsächlichen Worte (Apfel, blass etc )?

Dank!

  • Sind Sie sich der Tatsache bewusst, dass in PHP, irgendwelche assoziativen array ist in der Tat ein Wörterbuch?
InformationsquelleAutor Rohan | 2010-02-09
  1. 3

    Klassisch-Wort-lookup-Probleme effizient gelöst werden können mit einem Trie.

    Ich würde vorschlagen, die Suche nach einer word-Liste mit, sagen wir, von WordNet, speichern Sie es in einem Trie, und führen Sie dann schnell lookups der möglichen Wörter.

    Eine Lösung wäre von der form:

    1. laden Sie die word-Liste
    2. speichern Sie die Wortliste in einem trie
    3. Eingaben akzeptieren, um ein Wort zu entschlüsseln,

    4. versuchen Permutationen i=1..N

      ein. lookup permutation, die ich mit dem trie

      b. wenn es ein positives Ergebnis, speichern Sie diese für die Anzeige

      c. iterate (i++)

    5. wiederholen von 3.

    edit:

    Einer Seite beachten Sie hier, dass für alle N Länge Zeichen Wort, es könnte sein, N! benötigte Suchvorgänge (für 7 Zeichen, wäre 5040). Sollten Sie in Erwägung ziehen, einige Optimierungen an der trie-lookup-Algorithmus. Zum Beispiel, Sie gewinnen erhebliche Effizienz durch den Ausschluss ungültig Teilstrings zu früh und nicht zu wiederholen, Ende Permutationen.

    z.B. das Wort apple, wenn Sie hatte die Mutation, bei der Sie ausgewählte "ppl" als die ersten drei Zeichen, kein Wort wird gefunden werden. Also, egal wie Sie permutiert das a und das e am Ende kann man nicht konstruieren, ein Wort. Die vorzeitige Beendigung von Permutationen kann wichtig sein, dass Ihr Algorithmus die Effizienz.

    • Dies hilft nicht mit gerührte Worte, aber. Sie müssen zuerst normalisiert werden, wie in zerkms' Antwort
    • Nein, probieren Sie einfach alle Permutationen. Da die Trie-lookups wird unglaublich schnell die Strafe für die Suche mehrere Male niedrig sein wird; gewährt für lange strings kann es eine große Anzahl von Permutationen, und diese Lösung wird nicht Sinn machen, mit Worten, die viel größer ist als, sagen wir, 7 Zeichen
    InformationsquelleAutor Mark Elliot
  2. 3

    Ah, und die andere Antwort:

    Wenn Sie nur wollen, um alle realen Wörter - suchen Sie dann ein großes Wörterbuch. dann speichern Sie es in der Art von:

    Wort | hash

    wo word word selbst-und hash-alphabetisch sortiert, Buchstaben:

    für apple-Hashwert: aelpp oder aelp2

    dann für gegeben, Buchstaben Durchlaufen alle Kombinationen mit dem gleichen Algorithmus für das hashing und durchsuchen diese Tabelle.

    • "hash" ist das falsche Wort. "key" wäre besser, wie in verwenden Sie es als Schlüssel in einem hashtable.
    • vereinbart, "Schlüssel" ist hier relevant
    • Meine Frage ist, wo bekomme ich das große Wörterbuch?
    • für die erste - Sie analysieren können aspell/ispell-Wörterbücher. wir wissen nicht, wie groß genug sein sollte Wörterbücher für Sie.
    • Ich habe diese Methode vor. Es hat sehr gut geklappt, da alle, die ich tun wollte, war, zu entschlüsseln, bekannte Wörter in meinem Wörterbuch.
    InformationsquelleAutor zerkms
  3. 2

    können Sie auch prüfen, pspell

    http://php.net/manual/en/book.pspell.php

    $ps = pspell_new("en");
foreach(array('alppe', 'plape', 'apple') as $word)
   if(pspell_check($ps, $word))
      echo $word;
    InformationsquelleAutor user187291
  4. 0

    Speichern Sie eine Liste von Wörtern in einer Datei oder einer Datenbank, und dann einfach versuchen, alle Kombinationen. Sie könnte auch prüfen, die wahrscheinliche position der Vokale vs. Konsonanten potenziell beschleunigen. Anstatt dass Sie Ihre eigenen Wort-Liste, könnten Sie so etwas wie WordNet.

    InformationsquelleAutor Stephen Cross
  5. 0

    Eigentlich mag ich zerkms Lösung besser, aber hier ist noch eins

    erstellen 2 Tabellen

    words
-----
word_id (primary key)
word


letter_index
-----
letter (idx)
word_id (idx)

    Wenn Sie ein Wort hinzufügen zu den Worten, Tabelle, müssen Sie einen Eintrag in der letter_index für jeden einzelnen Brief. letter_index hat einen primär-Schlüssel basierend auf den Brief und die word_id.

    Worte zu finden, bestehend aus einer Gruppe von Buchstaben, die Sie erstellen eine Abfrage so etwas wie:

    SELECT word FROM words w
//for each letter in the search
INNER JOIN letter_index i ON ( w.word_id = i.word_id AND i.letter = letter_1 )
INNER JOIN letter_index i ON ( w.word_id = i.word_id AND i.letter = letter_2 )
INNER JOIN letter_index i ON ( w.word_id = i.word_id AND i.letter = letter_3 )
...
INNER JOIN letter_index i ON ( w.word_id = i.word_id AND i.letter = letter_n )
    InformationsquelleAutor meouw
  6. 0

    oder Sie können die developer.dictionary.com api und nur ein Wort-lookup für die Validierung. können auch Zauber überprüft.

    InformationsquelleAutor hookedonit
Schreibe einen Kommentar