Wyszukiwarka słów Scrabble z symbolami wieloznacznymi

Ty nie. Tabela relacyjnej bazy danych nie jest odpowiednią strukturą danych do rozwiązania tego problemu tak skutecznie, jak to konieczne.

Zamiast tego tworzysz trie struktura danych ze słownika (lub, jeśli naprawdę jesteś buffem, budujesz dawg -- skierowany acykliczny wykres słów -- który jest rodzajem skompresowanej próby.)

Po próbie/dawg bardzo tanie staje się testowanie każdego słowo w słowniku względem danego stojaka, ponieważ możesz „wyciąć” całe ogromne gałęzie słownika, do których stojak nie jest w stanie dopasować.

Spójrzmy na mały przykład. Załóżmy, że masz słownik „OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS” Z tego zbudujesz tę próbę:(Węzły z $ to te, które są oznaczone jako „słowo może się tutaj kończyć” .

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

i masz stojak "OPS" - co robisz?

Najpierw mówisz „czy mogę zejść w dół gałęzią O?” Tak, możesz. Więc teraz problemem jest dopasowanie "PS" do gałęzi O. Czy możesz zejść w dół podgałęzi P? Tak. Czy ma znacznik końca słowa? Tak, więc OP to dopasowanie. Teraz problemem jest dopasowanie „S” do gałęzi OP. Czy możesz zejść w dół gałęzi T? Nie. Czy możesz zejść do gałęzi S? Tak. Teraz masz pusty stojak i musisz dopasować go do oddziału OPS. Czy ma znacznik końca słowa? Tak! Więc OPS również pasuje. Teraz cofnij się do korzenia.

Czy możesz zejść w dół gałęzi P? Tak. Teraz problemem jest dopasowanie systemu operacyjnego do gałęzi P. Zejdź w dół gałęzi PO i dopasuj S – to się nie powiedzie. Wróć do korzenia.

I znowu widzisz, jak to idzie. W końcu idziemy w dół gałęzi SOP i znajdujemy koniec słowa na SOP, więc „SOP” pasuje do tego stojaka. Nie schodzimy w dół gałęzi ST, ponieważ nie mamy T.

Wypróbowaliśmy wszystkie możliwe słowa w słowniku i odkryliśmy, że OP, OPS i SOP pasują do siebie. Ale nigdy nie musieliśmy badać OPTS, POTS, STOP lub STOPS, ponieważ nie mieliśmy T.

Widzisz, jak ta struktura danych sprawia, że ​​jest bardzo wydajny? Po ustaleniu, że nie masz liter na stojaku, aby rozpocząć początek jednym słowem, nie musisz badać żadnego słowa ze słownika, które zaczynają się od tego początku. Jeśli masz PO, ale nie masz T, nie musisz badać POTSHERD, ZIEMNIAK, POTASH, POTLATCH lub POTABLE; wszystkie te drogie i bezowocne wyszukiwania znikają bardzo szybko.

Dostosowanie systemu do „dzikich” płytek jest dość proste; jeśli masz OPS?, po prostu uruchom algorytm wyszukiwania 26 razy, na OPSA, OPSB, OPSC... Powinno być na tyle szybkie, że zrobienie tego 26 razy jest tanie (lub zrobienie tego 26 x 26 razy, jeśli masz dwa puste miejsca). )

Jest to podstawowy algorytm, z którego korzystają profesjonalne programy Scrabble AI, choć oczywiście muszą również radzić sobie z takimi rzeczami, jak pozycja płytki, zarządzanie stojakami i tak dalej, co nieco komplikuje algorytmy. Ta prosta wersja algorytmu będzie wystarczająco szybka, aby wygenerować wszystkie możliwe słowa na stojaku.

Nie zapominaj, że oczywiście wystarczy policzyć triadę/dawg raz jeśli słownik nie zmienia się w czasie. Tworzenie wersji próbnej ze słownika może być czasochłonne, więc warto to zrobić raz a następnie wymyśl sposób na przechowywanie wersji na dysku w formie umożliwiającej szybkie odbudowanie jej z dysku.

Możesz zoptymalizować użycie pamięci, budując DAWG z triady. Zauważ, że jest dużo powtórzeń, ponieważ w języku angielskim wiele słów koniec tak samo, tak samo jak wiele słów zaczyna się to samo. Próba świetnie radzi sobie z udostępnianiem węzłów na początku, ale kiepską pracą jest udostępnianie ich na końcu. Możesz na przykład zauważyć, że wzorzec „S$ bez dzieci” jest niezwykle powszechny i ​​zamienić to trio na:

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

Zapisanie całego stosu węzłów. A potem możesz zauważyć, że dwa słowa kończą się teraz na O-P$-S$, a dwa słowa kończą się na T$-S$, więc możesz je dalej skompresować do:

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

A teraz mamy minimalny DAWG dla tego słownika.

Dalsza lektura:

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

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

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