Scrabble-woordzoeker met jokertekens

Jij niet. Een relationele databasetabel is geen geschikte gegevensstructuur om dit probleem zo efficiënt op te lossen als nodig is.

In plaats daarvan bouw je een trie gegevensstructuur uit het woordenboek (of, als je echt fan bent, bouw je een dawg -- een gerichte acyclische woordgrafiek -- wat een soort gecomprimeerde trie is.)

Als je eenmaal een poging hebt gedaan, wordt het erg goedkoop om elke . te testen woord in het woordenboek tegen een bepaald rek, omdat je hele enorme takken van het woordenboek kunt "snoeien" die het rek onmogelijk kan evenaren.

Laten we een klein voorbeeld bekijken. Stel dat je het woordenboek "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS" hebt. Van daaruit bouw je deze trie:(Knooppunten met een $ zijn die gemarkeerd als "woord kan hier eindigen" .

           ^root^
           /  |  \
         O    P    S
         |    |   / \
         P$   O  O   T   
        / \   |  |   |
       T$  S$ T$ P$  O
       |      |  |   |
       S$     S$ S$  P$
                     |
                     S$

en je hebt het rek "OPS" -- wat doe je?

Eerst zeg je "kan ik de O-tak afgaan?" Ja, dat kan. Dus nu is het probleem het matchen van "PS" met de O-tak. Kun je de P-subtak afdalen? Ja. Heeft het een einde-van-woord-markering? Ja, dus OP is een match. Nu is het probleem het matchen van "S" met de OP-tak. Kun je langs de T-tak gaan? Nee. Kun je langs de S-tak gaan? Ja. Nu heb je het lege rack en moet je het matchen met de OPS-tak. Heeft het een einde-van-woord-markering? Ja! Dus OPS komt ook overeen. Ga nu terug naar de root.

Kun je de P-tak afgaan? Ja. Het probleem is nu om het besturingssysteem te vergelijken met de P-tak. Ga naar de PO-tak en match S - dat mislukt. Terug naar de root.

En nogmaals, je ziet hoe dit gaat. Uiteindelijk gaan we door de SOP-tak en vinden een einde-van-woord op SOP, dus "SOP" komt overeen met dit rek. We gaan niet door de ST-tak omdat we geen T hebben.

We hebben elk mogelijk woord in het woordenboek geprobeerd en ontdekten dat OP, OPS en SOP allemaal overeenkomen. Maar we hoefden nooit OPTS, POTS, STOP of STOPS te onderzoeken omdat we geen T hadden.

Zie je hoe deze datastructuur het erg efficiënt maakt? Als je eenmaal hebt vastgesteld dat je de letters niet op het rek hebt om het begin te maken, van een woord hoeft u geen . te onderzoeken woordenboekwoorden die met dat begin beginnen. Als je PO hebt maar geen T, hoef je POTSHERD of POTATO of POTASH of POTLATCH of POTABLE niet te onderzoeken; al die dure en vruchteloze zoekopdrachten verdwijnen heel snel.

Het systeem aanpassen om met "wilde" tegels om te gaan is vrij eenvoudig; als je OPS hebt?, voer dan het zoekalgoritme 26 keer uit, op OPSA, OPSB, OPSC... Het zou snel genoeg moeten zijn dat 26 keer doen goedkoop is (of 26 x 26 keer doen als je twee lege plekken hebt. )

Dit is het basisalgoritme dat professionele Scrabble AI-programma's gebruiken, hoewel ze natuurlijk ook te maken hebben met zaken als bordpositie, rackbeheer enzovoort, wat de algoritmen enigszins compliceert. Deze eenvoudige versie van het algoritme zal snel genoeg zijn om alle mogelijke woorden op een rek te genereren.

Vergeet niet dat je de trie/dawg natuurlijk maar één keer hoeft te berekenen als het woordenboek in de loop van de tijd niet verandert. Het kan tijdrovend zijn om de trie uit het woordenboek op te bouwen, dus misschien wilt u dit eenmalig doen en bedenk dan een manier om de trie op schijf op te slaan in een vorm die geschikt is om het snel opnieuw op te bouwen vanaf schijf.

U kunt het geheugengebruik optimaliseren door een DAWG uit de trie te bouwen. Merk op hoe veel herhalingen zijn, want in het Engels, veel woorden end hetzelfde, net zoals veel woorden beginnen hetzelfde. De tri doet geweldig werk door in het begin knooppunten te delen, maar een slechte taak om ze aan het einde te delen. U kunt bijvoorbeeld zien dat het patroon "S$ zonder kinderen" heel gebruikelijk is, en de triangel veranderen in:

           ^root^
          / |  \
        O   P    S
        |   |   / \
        P$  O  O   T   
       /  \ |  |   |
      T$  | T$ P$  O
      |    \ | |   |
       \    \| /   P$
        \    |/    |
         \   |    /
          \  |   /  
           \ |  /
            \| /  
             |/
             |       
             S$

Een hele stapel knooppunten opslaan. En dan merk je misschien dat twee woorden nu eindigen op O-P$-S$, en twee woorden eindigen op T$-S$, dus je kunt het verder comprimeren tot:

           ^root^
           / | \
          O  P  S
          |  | / \
          P$ O \  T   
         /  \|  \ |
         |   |   \|
         |   |    O
         |   T$   |
          \  |    P$
           \ |   /
            \|  /  
             | /
             |/   
             S$

En nu hebben we de minimale DAWG voor dit woordenboek.

Verder lezen:

http://dl.acm.org/citation.cfm?id=42420

http://archive.msdn.microsoft.com/dawg1

http://www.gtoal.com/wordgames/scrabble.html