Търсене на думи със скраб с заместващи знаци

Вие не го правите. Таблицата на релационна база данни не е подходяща структура от данни за решаване на този проблем толкова ефективно, колкото е необходимо.

Това, което правите вместо това, е да създавате опит структура на данните извън речника (или, ако наистина сте любители, създавате dawg -- насочена ациклична словна графика -- която е нещо като компресиран опит.)

След като опитате/дауг, става много евтино да тествате всеки дума в речника срещу дадена поставка, защото можете да „изрежете“ цели огромни клонове на речника, които поставката не може да съвпадне.

Нека разгледаме малък пример. Да предположим, че имате речника "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS" От това изграждате този опит:(Възлите с $ са тези, които са маркирани като "дума може да свърши тук" .

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

и имате багажника "OPS" -- какво правите?

Първо казвате "Мога ли да сляза по клона O?" Да, можеш. Така че сега проблемът е съпоставянето на "PS" с O клон. Можете ли да отидете надолу по подклона P? да. Има ли маркер за край на думата? Да, значи OP е съвпадение. Сега проблемът е съпоставянето на "S" срещу клона на OP. Можеш ли да слезеш по Т клона? Не. Можеш ли да слезеш по S клона? да. Сега имате празния багажник и трябва да го съпоставите с клона на OPS. Има ли маркер за край на думата? Да! Така че OPS също съвпада. Сега се върнете обратно до корена.

Можеш ли да слезеш по клона P? да. Сега проблемът е да съпоставим OS с P клон. Отидете надолу по клона на ПО и съпоставете S - това се проваля. Върнете се към корена.

И отново виждате как става това. В крайна сметка отиваме надолу в клона на SOP и намираме край на думата на SOP, така че "SOP" съответства на този багажник. Не слизаме по клона ST, защото нямаме T.

Опитахме всяка възможна дума в речника и открихме, че OP, OPS и SOP съвпадат. Но никога не се налагаше да разследваме OPTS, POTS, STOP или STOPS, защото нямахме T.

Виждате ли как тази структура от данни я прави много ефективна? След като сте определили, че нямате буквите на багажника, за да направите началото с една дума, не е нужно да разследвате никое думи от речника, които започват с това начало. Ако имате PO, но нямате T, не е нужно да разследвате POTSHERD или POTATO или POTASH или POTLATCH или POTABLE; всички тези скъпи и безплодни търсения изчезват много бързо.

Адаптирането на системата за справяне с "диви" плочки е доста лесно; ако имате OPS?, тогава просто стартирайте алгоритъма за търсене 26 пъти, на OPSA, OPSB, OPSC... Трябва да е достатъчно бързо, че да го направите 26 пъти е евтино (или да го направите 26 x 26 пъти, ако имате две празни места. )

Това е основният алгоритъм, който използват професионалните програми за изкуствен интелект Scrabble, въпреки че, разбира се, те също трябва да се справят с неща като позиция на дъската, управление на стелаж и така нататък, което донякъде усложнява алгоритмите. Тази проста версия на алгоритъма ще бъде достатъчно бърза, за да генерира всички възможни думи на стелаж.

Не забравяйте, че разбира се, трябва само да изчислите trie/dawg веднъж ако речникът не се променя с течение на времето. Може да отнеме време да изградите изпробването от речника, така че може да искате да го направите веднъж и след това измислете някакъв начин да съхраните опита на диск във форма, която може да го възстанови бързо от диск.

Можете да оптимизирате използването на паметта, като създадете DAWG от опита. Забележете как има много повторения, защото на английски има много думи end същото, точно както много думи започват същото. Опитът върши страхотна работа за споделяне на възли в началото, но лоша работа с споделянето им в края. Можете да забележите например, че моделът „S$ без деца“ е изключително често срещан и да превърнете опита в:

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

Спестяване на цяла купчина възли. И тогава може да забележите, че две думи сега завършват на O-P$-S$ и две думи завършват на T$-S$, така че можете да ги компресирате допълнително до:

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

И сега имаме минималния DAWG за този речник.

Допълнително четене:

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

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

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