anagrams에서 사전 단어를 찾을 수있는 프로그램은 어떻게 작동합니까?

Question

예 : http://www.thewordfinder.com/, http://www.anagram-solver.org/ 또는 Friends with Words와 같은 아나그램 기반 게임에서 "부정 행위"에 대한 다양한 응용 프로그램이 있습니다.

Swift를 사용하여 비슷한 기능을 가진 응용 프로그램을 만들려한다면 어디에서 시작해야할까요?

이 질문에 답을 얻은 것처럼 보이므로 누군가이 질문에 가장 적합한 곳을 말해 줄 수 있습니까?

Answer 1

단어 목록을 접두어 트리 (특히 희소 배열을 방지하기 위해 추가 메모리를 사용하는 단어)로 변환하면 검색의 전체 분기가 빠르게 제거 될 수 있으므로 입력 단어의 모든 순열을 효율적으로 검사 할 수 있어야합니다.

간단한 예를 들어 보겠습니다. 우리 사전에 aab, abb 및 abc이라는 단어가 포함되어 있다고 가정하십시오. 접두어 트리로 변환하면 다음과 같이 표시됩니다.

a 
    ab 
    b 
     b 
     c 

들여 쓰기는 위 행의 하위를 나타냅니다. 사전에있는 모든 단어는 a으로 시작하고 ab 또는 b으로 시작하고 후자의 경우 b 또는 c이옵니다. 보시다시피, 우리는 모든 편지가 아니라 오히려 대안에 의존합니다. 이렇게하면 트리 크기를 줄이는 데 도움이됩니다. 이제

, 우리는 우리의 입력 워드 cba의 모든 순열을 반복하는 경우 :

abc 
acb 
bac 
bca 
cab 
cba 

우리의 접두사 트리 루트에 일치하는 항목이 없기 때문에 신속하게 제거 할 수있다 a 이외의 문자로 시작되는 모든 변경 수평. acb은 두 번째 검사에서 제거 될 수 있습니다. 즉, abc은 일치 항목을 찾습니다. 순열을 생성하기위한 알고리즘에 수표를 통합하는 경우 점진적으로 일치시킬 수 있으며 탐색중인 트리의 현재 분기와 일치하지 않는 부분 순열을 생성하지 않을 수 있습니다.

스파 스 나무를 피하는 것에 대한 의견은 현재 분기의 하위와 일치하는 데 이진 검색을 사용하지 않아도된다는 것입니다. 오히려 문자의 ASCII 값으로 색인 된 26 개 요소의 배열 (대문자 또는 소문자를 선택하고 일관성을 유지해야 함)은 추가 메모리 비용으로 매우 빠른 조회가 가능해야합니다.