기수 트리/패트리시아 트리의 접두사 검색
https://stackoverflow.com/questions/794601
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
저는 현재 기수 트리/패트리샤 트리(당신이 부르고 싶은 대로)를 구현하고 있습니다.성능이 매우 낮은 하드웨어에서 사전의 접두사 검색에 이 기능을 사용하고 싶습니다.자동 완성과 거의 비슷하게 작동한다고 가정합니다.이자형.입력한 접두사와 일치하는 단어 목록을 표시합니다.
내 구현은 다음을 기반으로 합니다. 이 기사에, 그러나 저자는 다음과 같이 말하지만 그 안의 코드에는 접두사 검색이 포함되어 있지 않습니다.
[...] 공통 접두사 "AB"가 있는 키를 가진 모든 노드를 열거한다고 가정해 보겠습니다.해당 루트에서 시작하여 뒤쪽 가장자리를 만날 때마다 중지하는 깊이 우선 검색을 수행할 수 있습니다.
그러나 나는 그것이 어떻게 작동하는지 알 수 없습니다.예를 들어, 다음 단어로 기수 트리를 만든다면:
병
상상의
상상력
상상하다
모방
즉각적인
즉시
엄청난
~에
접두사 "i"와 "in"에 대해 정확히 동일한 "최적 일치"를 얻을 것이므로 가장 일치하는 항목에서 트리를 탐색하는 것만으로는 일치하는 모든 단어를 수집하는 것이 어려워 보입니다.
추가적으로, Java의 기수 트리 구현 접두사 검색이 구현되어 있습니다. RadixTreeImpl.java.해당 코드는 모든 노드(특정 노드에서 시작)에서 접두사가 일치하는지 명시적으로 확인합니다. 실제로 바이트를 비교합니다.
기수 트리에서 접두사 검색 구현에 대한 자세한 설명을 알려줄 수 있는 사람이 있나요?Java 구현에 사용되는 알고리즘이 이를 수행하는 유일한 방법입니까?
해결책
트라이가 무엇을 인코딩하는지 생각해 보세요.각 노드에는 해당 노드로 연결되는 경로가 있으므로 예에서는 빈 문자열에 해당하는 루트 노드인 Λ(대문자 Lambda, 이 그리스 글꼴 종류는 짜증남)에서 시작합니다.Λ에는 사용된 각 문자에 대한 하위 항목이 있으므로 데이터 세트에는 "i"에 대한 하나의 분기가 있습니다.
- Λ
- Λ→"나는"
"i" 노드에는 두 개의 하위 노드가 있는데, 하나는 "m"에 대한 것이고 다른 하나는 "n"에 대한 것입니다.다음 문자는 "n"이므로 이를 취하세요.
- Λ→"i"→"n"
데이터 세트에서 "i", "n"으로 시작하는 유일한 단어이기 때문에 ~이다 "in", "n"의 자녀가 없습니다.그것은 일치합니다.
이제 데이터 세트에 "in" 대신 "infindibulum"이 있다고 가정해 보겠습니다.(내가 언급하고 있는 SF는 연습용으로 남겨둡니다.) 여전히 같은 방식으로 "n" 노드에 도달할 수 있지만, 다음 문자가 "q"이면 해당 단어가 나타나지 않는다는 것을 알 수 있습니다. "q" 분기가 없기 때문에 데이터 세트에 전혀 없습니다.그 시점에서 당신은 "좋아, 일치하지 않아"라고 말합니다. (그런 다음 응용 프로그램에 따라 단어를 추가하기 시작할 수도 있고 그렇지 않을 수도 있습니다.)
하지만 다음 문자가 "f"이면 계속 진행할 수 있습니다.하지만 약간의 기술을 사용하면 이를 단락시킬 수 있습니다.고유한 경로를 나타내는 노드에 도달하면 전체 문자열 해당 노드에서.해당 노드에 도달하면 문자열의 나머지 부분이 ~ 해야 하다 "findibulum"이므로 접두사를 사용하여 전체 문자열을 일치시키고 반환했습니다.
당신은 그것을 어떻게 사용합니까?이전 VAX DCL과 같은 많은 비 UNIX 명령 해석기에서는 명령의 고유한 접두사를 사용할 수 있습니다.따라서, ls(1) ~였다 DIRECTORY, 그러나 DIR로 시작되는 다른 명령은 없으므로 다음을 입력할 수 있습니다. DIR 그리고 그것은 전체 단어를 다하는 것만큼 좋았습니다.올바른 명령을 기억할 수 없다면 'D'만 입력하고 ESC를 누르십시오.DCL CLI가 당신을 반환할 것입니다 모두 다음으로 시작하는 명령 D, 매우 빠르게 검색할 수 있습니다.
다른 팁
표준 C ++ LIB의 GNU 확장에는 패트리샤 트리 구현이 포함되어 있습니다. 정책 기반 데이터 구조 확장에서 발견됩니다. 보다 http://gcc.gnu.org/onlinedocs/libstdc+ //ext/pb_ds/trie_based_containers.html
대체 알고리즘 : 단순한 바보를 유지하십시오!
키워드의 정렬 목록 만 만드십시오. 접두사가 있으면 바이너리 검색을 통해 해당 접두사가 목록에있는 위치를 찾으십시오. 가능한 모든 완료는 해당 지수부터 시작하여 액세스 할 수 있습니다.
이 알고리즘은 Patricia Trie 코드의 5% 만 필요하며 유지 관리, 이해 및 업데이트가 쉽습니다. 이 간단한 목록 검색도 더 효율적일 것입니다.
유일한 단점은 유사한 접두사를 가진 많은 수의 긴 키워드가있는 경우 모든 항목에 대해 전체 접두사를 유지할 필요가 없기 때문에 트리는 일부 저장소를 저장할 수 있습니다. 실제로, 수백만 단어 미만의 단어가 있다면, 나무의 포인터 오버 헤드가 지배적이기 때문에 이것은 절약이 아닙니다. 이 절약은 텍스트 키워드가 아닌 수백만 문자로 DNA 문자열 데이터베이스를 검색하는 것과 같은 응용 프로그램에 더 적합합니다.
또 다른 대안의 알고리는 a 3 배 검색 트리 (더 메모리 효율성) https://github.com/varunpant/ternarytree/tree/master/ternarytree
