자동 제안 : 부분 문자열 일치

Question

TST (Ternary Search Tree)를 사용하여 자동 제안을 구현하려고하지만 TST는 접두사 검색을 찾을 때 유용합니다. 어떻게 하위 문자열 일치에 대한 자동 제안도 구현할 수 있습니까? 사용할 수있는 다른 데이터 구조가 있습니까?

일치하는 부분 문자열 예 : 자동 제안을 사용하여 UML을 검색하려고 할 때 "UML 용 초보자 안내서"문자열도 일치해야합니다.

Answer 1

이 내 머리의 상단에서입니다되지 않은 적절하고 검증 된 데이터 구조/알고리즘 :

1. 은 편의상 (N 심볼에 대한 모든 법적 문자의 매핑을 선택합니다 : 라틴어 문자와 26 개 문자 대/소문자를 구분하지 않는 유사한 비 라틴 문자 + 글자가 아닌 경우 = 1 = 총 27 자).

2. 사전에서 최대 분수 계수 N (즉, 상당히 높음) 인 얕은 트리를 만듭니다. 리프 노드는 루트에서 해당 리프까지 이어지는 기호 콤보를 포함하는 모든 단어에 대한 참조를 포함합니다 (중간 노드는 리프 노드의 깊이보다 짧은 단어에 대한 참조를 포함 할 수도 있고, 그 짧은 단어를 무시할 수도 있습니다).

3. 트리의 깊이는 아마도 1..4의 범위 내에서 가변적 일 수 있으므로 각 리프 노드는 거의 동일한 수의 단어를 포함 할 것입니다 (물론 MAT와 같은 MATCH, ATC , 나무 깊이가 3 일 경우 TCH).

4. 사용자가 문자를 입력 할 때 상대적으로 작은 단어 집합이 남을 때까지 트리를 따라 가십시오. 그런 다음 트리의 리프에있는 나머지 단어를 선형 필터링하여 사용자가 더 많은 텍스트를 입력하여 일치시킵니다. 선택적으로 필터링 기호는 사용자가 ao0에 들어갈 때 또한 äöO 일치 좋을 수도 있지만 실제로 문자 기호

5. 최적화 번호는 당신이 좋은 분기 요인을 가지고 당신의 문자를 매핑 등, 일치되지 않는 일치 나무. 트리의 리프에 도달 한 후 선형 적으로 필터링 할 단어가 너무 많지 않으면 서 리프마다 단어를 최적화하여 메모리 사용량을 적절히 조정하십시오.

---

물론 Aho–Corasick 및 Rabin–Karp 같은 텍스트의 큰 조각에 (당신이 일치 할 모든 문구/단어), 문자열 (어떤 사용자가 입력) 찾기위한 실제 연구 알고리즘은 거기에있는 아마도 조사 할 가치가 있습니다.