가다그

GADDAG

GADDAG는 1994년 스티븐 고든이 제시한 데이터 구조이며, 스크래블 및 기타 단어 생성 게임용 무브 생성에 사용됩니다. 이러한 무브에는 기존 단어에 "연결"하는 단어가 필요합니다.이는 종종 Maven이 사용하는 것과 같은 DAWG(Directed ascyclic word graph)를 사용하는 이동 생성 알고리즘과는 대조적이다.일반적으로 기존 DAWG 알고리즘보다 2배 빠르지만 규제 스크래블 [1]사전에는 약 5배 더 많은 공간을 차지합니다.

오픈 소스 스크래블 프로그램인 Quackle은 [2]이동을 생성하기 위해 GADDAG를 사용합니다.

묘사

GADDAG라는 이름은 유도 비순환 그래프에 대한 DAG에서 유래했으며, 그 앞에 [1]역순으로 접두사가 붙습니다.

GADDAG는 Trie의 전문화로서 다른 GADDAG에 대한 상태와 브랜치를 포함합니다.이것은 사전에 있는 모든 단어의 반전 접두사를 저장하기 때문에 구별된다.즉, 모든 단어는 글자 수만큼 표현됩니다.대부분의 스크래블 규제 사전의 평균 단어는 5글자이므로 GADDAG는 단순한 DAWG보다 약 5배 커집니다.

정의.

사전에서 비어 있지 않은 접두사 x와 접미사 y로 구성된 단어에 대해 GADDAG에는 임의의 문자열 REV(x)+y에 대한 직접 결정론적 경로가 포함됩니다. 여기서 +는 연결 연산자입니다.

예를 들어, "desplain"이라는 단어의 경우 GADDAG는 문자열에 대한 직접 경로를 포함합니다.

e+xplain xe+lain lpxe+ain alpxe+in ialpxe+n nialpxe

이 설정을 사용하면 단어에 포함된 모든 문자를 검색할 수 있습니다.

이동 생성에서 사용

이동 생성 알고리즘은 다음 3가지 유형의 제약을 준수해야 합니다.

  • 보드의 제약사항: 보드의 기존 글자에 '걸기'하는 방법으로만 구축할 수 있으며, 빈 정사각형 위에만 타일을 배치할 수 있습니다.
  • 랙의 제약사항: 랙에 글자가 적힌 타일을 올려놓기만 하면 됩니다.
  • 사전 제약 조건: 타일 배치로 인한 모든 단어가 게임 사전에 존재합니다.

DAWG 기반 알고리즘은 두 번째와 세 번째 제약을 활용합니다.DAWG는 사전을 중심으로 구축되며 랙 내 타일을 사용하여 통과됩니다.단, 첫 번째 제약조건에는 대응하지 않습니다.HARPY에서 문자 P에 '훅'하고 보드 앞에 공백이 2개 있고, 세 번째 문자가 P인 랙에서 문자를 포함하는 모든 단어를 사전에 검색해야 합니다.이는 DAWG를 통해 검색할 때 비효율적이며, 트라이를 통한 많은 검색은 효과가 없습니다.

이는 GADDAG의 프리픽스 스토리지에 의해 해결됩니다.GADDAG의 P 브런치를 통과하면 구성 중 어딘가에 P가 있는 모든 단어를 볼 수 있으며 프리픽스를 "이동"하여 랙 내의 타일을 사용하여 단어를 형성할 수 있습니다.§ Definition 섹션의 예를 사용하려면 P를 검색하면 "pxe+lain"이 표시됩니다.P와 + 사이의 글자는 보드의 P 위에 배치하고 나머지는 보드 아래에 배치할 수 있습니다(보드의 공간이 허락하는 경우).

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Gordon, Steven A. (1994). "A faster Scrabble move generation algorithm" (PDF). Software: Practice and Experience. 24 (2): 219–232. doi:10.1002/spe.4380240205.
  2. ^ Jason Katz-Brown; John O'Laughlin. "How Quackle Plays Scrabble". Retrieved 2018-07-02.