GADDAG

GADDAG je struktura podataka prezentovana od strane Stivena Gordona 1994, da bi se koristila za generisanje poteza uScrabble i drugim sličnim igricama u kojima potezi zahtevaju da se reči ugradjuju u druge reči. Često je kontrast algoritmima koji koriste Directed Acyclic Word Graph (DAWG), kao u igrici Maven. Generalno je duplo brži od tradicionalnih DAWG algoritama, ali je potrebno 5 puta više prostora za regulisanje Scrabble rečnika.

• Quackle koristi GADDAG za generisanje poteza.

Opis

GADDAG je specijalizacija data strukture drveta, koje sadrži grane i čvorove drugih GADDAG-ova. Ona je različita za skladištenje svakog obrnutog prefiksa svake reči u rečniku. To znači da svaka reč ima toliko reprezentacija koliko ima slova; prosečna reč u većini Scrabble rečnika je 5 slova duga, ovo čini GADDAG oko 5 većim nego jednostavni DAWG.

Definicija

Za svaku reč u rečniku koja je formirana od nepraznog prefiksa x i sufiksa y, GADDAG sadrži direktan, deterministički put za svaki string REV(x)৳y, gde je ৳ operator za konkataciju.

Na primer za reč "explain," GADDAG sadrži direktnu putanju do stringova "e৳xplain," "xe৳plain," "pxe৳lain," "lpxe৳ain," "alpxe৳in," "ialpxe৳n," i "nialpxe."

Korišćenje u generisanju pokreta

Svaki algoritam generisanja pokreta mora da sadrži 3 vrste ograničenja:

• Ograničenja table: Može se graditi jedino povezivanje na već postojeća slova na tabli. Dodatno, jedino se mogu popločati prazni kvadrati.
• Ograničenja postolja: Možete jedino dodavati pločice sa slovima sa svog postolja.
• Ograničenje rečnika: Sve reči nastala smeštanjem pločica potiču iz rečnika igre.

DAWG algoritma ubrzava i koristi prednosti drugog i trećeg ograničenja: DAWG je napravljen oko rečnika, i prolazite ga koristeći jedino pločice sa svog postolja. Ne uspeva da adresira prvo ograničenje: pretpostavimo da želite da nadovežete slovo P u HARPY, i tabla ima 2 mesta pre P, morate pretražiti rečnik za sve reči koje sadrže slova sa vašeg postolja gde je treće slovo P. Ovo nije deterministički kada pretražujemo kroz DAWG, jer pretrage groz drvo neće uroditi plodom.

Ovo je adresirano od GADDAG-ovog skladišta prefiksa: dok prolaze P granu GADDAG-a, vidite sve reči koje imaju P negde u svom sastavu, i mogu da pretraže prefikse za formu od slova sa Vašeg postolja. Dodajete pločice sa svog postolja dok su odgovarajuće, putujući unazad kroz reč dok ne naiđete na ৳, što znači da ste kompletirali prefiks. Kompletirate potez dodajući ga na početak reči sa sufiksom

Spoljašnje veze

• Steven Gordon's 1993 Paper describing the GADDAG.
• Mention of GADDAG in Quackle.