맞춤법 추천을 확인하기 위해 Trie를 트래버스하는 좋은 알고리즘은 무엇입니까?

Question

사전 단어의 일반적인 트라이가 작성되었다고 가정하면 순회 중 대체, 삭제, 바꾸기 및 삽입 등 철자 오류의 4 가지 경우를 확인하는 가장 좋은 방법은 무엇입니까?

한 가지 방법은 주어진 단어의 n 편집 거리 내의 모든 단어를 찾아내어 Trie에서 검사하는 것입니다. 이것은 나쁜 선택은 아니지만 여기에 더 나은 직관은 탐색 중에 단어를 수정 한 후 가장 좋은 하위 시험을 결정하는 동적 프로그래밍 (또는 재귀 적 등가) 방법을 사용하는 것 같습니다.

어떤 아이디어라도 환영합니다!

추신 : 답변에있는 링크가 아닌 실제 입력을 주시면 감사하겠습니다.

Answer 1

는 사실이 다른 일 할 수있는 몇 가지 코드 작성 :

https://bitbucket.org/teoryn/spell-checker/src/tip/spell_checker.py

그것은 피터 노빅 (http://norvig.com/spell-correct.html)에 의해 코드를 기반으로가 아니라 주어진 편집 내에서 단어를 찾기위한 트라이에 사전을 저장 거리가 더 빠릅니다.

알고리즘은 입력 단어의 문자를 소비함으로써 각 단계에서 가능한 편집 내용을 재귀 적으로 적용합니다. 재귀 호출의 매개 변수는 얼마나 많은 편집을 할 수 있는지를 나타냅니다. trie는 주어진 접두사에서 실제로 도달 할 수있는 문자를 확인하여 검색 공간을 좁히는 데 도움이됩니다. 예를 들어 문자를 삽입 할 때 각 문자를 알파벳으로 추가하는 대신 현재 노드에서 도달 할 수있는 문자 만 추가합니다. 편집하지 않는 것은 입력 단어의 현재 문자를 따라 트리의 현재 노드에서 분기를 가져 오는 것과 같습니다. 그 지점이 없다면 실제 단어가없는 큰 공간을 뒤돌아 검색하지 않아도됩니다.

Answer 2

두 시퀀스 간의 거리를 찾는 동적 프로그래밍 솔루션을 제공하는 Levenshtein distance을 계산합니다.

Answer 3

나는 나무에서 간단한 너비 우선 검색으로 이것을 할 수 있다고 생각합니다 : 찾고있는 오류 수의 임계 값을 선택하고, 한 번에 하나씩 일치시킬 단어의 문자를 실행하고, 접두사 일치까지 도달 (접두사, subtrie) 쌍의 세트를 생성하고, 당신이 당신의 오류 임계 값 아래에있는 동안, 다음 하위 목표의 당신의 세트에 추가

이

1. 이 문자 장소 없음 오류 : subgoal 추가 단어의 다음 문자에서 트라이의 숫자
2. 여기에 삽입, 삭제 또는 대체 된 문자가 있습니다. 적절한 위치에서 트라이를 찾고 오류 수를 증가시킵니다.
3. 추가 목표는 없지만 전환은 이전 삭제 또는 삽입과 일치하는 삽입 또는 삭제입니다.이 테스트가 유지되면 오류 수를 증가시키지 마십시오.

이것은 꽤 순진한 것처럼 보입니다. 동적 프로그래밍을 생각하게 만드는 문제가 있습니까?

Answer 4

단어의 연속 된 각 문자를 트리의 한 레벨을 나타내는 것으로 가정하면 각 문자를 확인하는 5 가지 경우 (일치, 삭제, 삽입, 대체 및 조옮김)가 있습니다. 전치가 두 개의 인접한 문자라고 가정합니다.

확인할 트리 노드와 문자를 허용하는 함수 (CheckNode)가 필요합니다. 일치를 나타내는 (자식/그랜드 자식) 노드 집합을 반환해야합니다.

단어를 허용하는 함수 (CheckWord)가 필요합니다. 노드 집합과 차례로 각 문자를 검사합니다. 일치하는 단어를 나타내는 (리프) 노드 집합을 반환합니다.

트리의 각 레벨 (자식, 그랜드 자식 등)은 단어의 문자 위치와 일치한다는 개념입니다. 최상위 트리 노드 인 레벨 0을 호출하면 레벨 1, 레벨 2 등이됩니다.

오류가없는 단어의 경우 문자 위치와 레벨이 일대일로 일치합니다. 나무.

삭제의 경우 트리에서 수준을 건너 뛸 필요가 있습니다.

삽입의 경우 단어의 문자는 건너 뜁니다.

대체 할 경우 레벨과 문자를 건너 뛸 필요가 있습니다.

전조의 경우 단어의 문자를 일시적으로 바꿔야합니다.