빠른 사전 구현에 사용할 수있는 트라이 나무를 D 언어와 파이썬으로 작성해 보았습니다.

트라이 나무란?

트라이 (Trie) 트리라는 데이터 구조를 아십니까?
Tri Tree는 빠른 사전 구현에 사용할 수 있는 데이터 구조입니다. LOUDS라는 데이터 구조를 사용하여 구현하면 매우 적은 메모리로 나무를 표현할 수 있다는 이점이 있습니다. 트라이 나무는 예를 들어 가나 한자 변환 (Google 일본어 입력 등)에서 국어 사전을 메모리에 유지하는 데 사용됩니다.

트라이 나무는 이런 형태를하고 있습니다.

(그림은 Wikipedia 보다 인용)

다른 나무와 다른 점은 나무의 "분지"에 해당하는 부분에 레이블이 붙어 있다는 것입니다.

이것을 사전으로 사용하려면 어떻게해야합니까?
"in"을 검색해 봅시다. 간단합니다. i -> n 을 따라가면 됩니다. 「5」가 검색 결과로서 꺼낼 수 있네요.
"inn"을 검색해 봅시다. 지금 있는 '5'의 위치에서 아래로 움직이면 됩니다. "9"가 결과로 꺼낼 수 있습니다.

트라이 나무의 특징

빠른 검색 가능

이 트라이 나무, 무엇이 대단한가 하면, 검색을 굉장히 고속으로 할 수 있습니다. 트라이 트리에서 검색 속도는 검색하는 키의 크기에 비례합니다. 그리고 나무의 크기에 비례하지 않습니다!

예를 들어, 트라이 나무로 국어 사전을 구현했다고 가정합니다.
그 국어 사전에서 12문자의 '짚짖는 곳에는 후쿠키타루'를 검색하려면 3문자 '짚신'을 검색하는 경우 대략 4(=12/3)배의 시간이 걸립니다.
그러나 사전에 100단어 들어가지만 100만단어 들어가지만 같은 단어를 조사한다면 이론상 검색 속도는 변하지 않습니다. 대단하네요.

쓸데없는 검색을 줄일 수 있습니다.

또한, 공통 부분이 있는 문자열을 검색하는 경우, 검색을 도중부터 재개시킴으로써 낭비적인 검색을 줄일 수 있습니다.
예를 들어 이전에 "inn"을 검색했을 때는, "in"을 검색한 결과의 "5"의 노드로부터 검색을 재개하는 것으로, 신속하게 "inn"의 검색 결과를 찾을 수 있었습니다.

LOUDS에 의한 구현

트라이 나무를 구조체나 포인터를 사용해 아무것도 생각하지 않고 실장하면 굉장히 메모리를 먹습니다. 메모리 확보가 너무 바빠서 헤타하면 머신이 정지합니다.
그래서 LOUDS라는 데이터를 표현하는 방법을 사용합니다.
LOUDS를 사용하면 노드 하나를 2비트 정도로 표현할 수 있습니다.
처음에 나타낸 그림과 같은 노드가 11개 있는 나무라도 단 23비트로 표현할 수 있어 무려 long형의 변수 1개에 들어가 버립니다.

여기서 LOUDS의 설명이라고 가고 싶은 곳입니다만, 간결 데이터 구조 LOUDS 설명 가 매우 알기 쉬웠으므로 그쪽에 양보합니다.

코드

코드는 다음과 같습니다. D 언어와 Python 각각으로 구현했습니다.
기주 b. 코 m / 이타 타케시 / ぉ ds-T 리에
코멘트는 많이 쓴 생각이므로, 상기 링크의 LOUDS의 해설을 읽고 나서 코드를 읽으면 이해할 수 있다고 생각합니다.
의문점이나 이상하다고 생각한 점이 있으면 코멘트 하는지 twitter로 말해 주시면 대응합니다.

패키지 버전

D언어의 패키지 관리 시스템 DUB로 취급할 수 있도록 했습니다.
DUB 페이지
소스 코드