텍스트 처리 소개: Python으로 빠른 사전을 만들어 봅시다(2부)

Double 배열 만들기

이중 배열은 Trie 트리를 어떻게 구현합니까?

먼저 "base"라는 정수의 1차원 배열을 준비합니다.
이 배열의 각 요소는 단일 노드를 나타냅니다.
기본 배열의 인덱싱은 1부터 시작합니다. (0 위치는 사용되지 않습니다)
즉, 노드 번호 1은 루트입니다. 여기에 1이 있습니다.
밑변[1] = 1.

이전 예에서 표제어의 첫 글자는 "で"와 "ど"입니다.
그렇다면, 루트가 "at"에 의해 전환되는 다음 노드는 어디에 있습니까?

준비하려면 표제어의 각 문자에 식별 번호를 할당합니다.
일부 인코딩의 문자 코드를 그대로 사용할 수 있습니다.
문자 수가 적기 때문에 여기서는 1부터 시작하여 문자 ID를 적절하게 할당합니다.
단어와 문자가 나타나는 순서는 다음과 같습니다.

그리고: 1밀리미터: 2하다: 3이: 4피: 5나중: 6(나): 7예: 8

"De"는 이제 1이고 "Do"는 이제 3입니다. 코드['in']=1, 코드['도']=3.
그건 그렇고, 나중에 설명하겠지만 문자 ID의 숫자 0은 단어의 끝입니다 (리프 노드로의 전환).
리프 노드에 대해 이야기했으므로 단어가 나타나는 순서대로 단어에 ID를 할당하겠습니다.

소굴:1어디:2땅:3돈찬:4꾸준히:5돈베:6

이제 이런 식으로 루트에서 문자 "at"으로 전환되는 노드의 위치는 다음과 같습니다.
root base의 값과 문자 ID를 사용합니다. 무슨 뜻인가요:

밑[1] + 코드['in'] = 1 + 1 = 2

에 옵니다. "do"의 경우에도 동일하게 수행하십시오.

밑[1] + 코드['도'] = 1 + 3 = 4

이렇게 하면 기본 배열 번호 2와 4가 새로 채워집니다.
이런 식으로 전환 대상의 노드 위치는 "기본 값 + 문자 ID"의 값입니다.
정말 놀랍습니다. 텍스트 정보는 "전환 이동량"에 흡수되었습니다.

여기서 문제는 base[1] 값에 임의의 문자 ID 값을 추가함으로써
루트에서 모든 노드로 전환할 수 있습니다.
다음 문자가 "で"와 "ど"가되는 것은 원하지 않기 때문에 이것이 문제입니다.
따라서 "check"라는 또 다른 1차원 정수 배열을 준비합니다.
그리고 체크에서, 그것이 어디에서 왔는지 (= 부모 노드의 인덱스)를 넣으십시오.
부모 노드가 루트인 경우 1입니다. 또한 루트 자체를 0으로 설정해야 합니다. 수식에 작성하면 :

체크[1] = 0
체크[2] = 1
체크[4] = 1

이러한 방식으로 Trie 트리는 base와 check의 두 배열로 표시됩니다.
여기에서 "이중 배열"이라는 이름이 유래했습니다.
"이중 배열의 노드에는 위치 정보, 기본 구성 요소 및 검사 구성 요소가 있습니다"라고 생각하십시오.
좋을 수 있습니다.
지금까지의 표를 살펴 보겠습니다.

현재 노드 1, 2 및 4가 채워져 있습니다. 3은 아직 비어 있습니다.
숫자 2와 4의 기본 값은 여전히 존재하지만 어떻게 결정합니까?

문자 c에 의해 위치 s에서 위치 t로 전환 할 때 다음과 같습니다.

t = 밑[s] + 코드[c]
체크[t] = s

base[s]의 값을 원하는대로 결정하면 앞으로 노드 수가 자꾸자꾸 증가 할 때,
기존 노드가 있는 포지션 타격이 발생합니다.
반대로, 이런 일이 발생하지 않도록, 즉 다음 노드가 비어있는 곳으로 전환되도록합니다.
base[s]의 값이 결정됩니다.

표제: "굴", "어디서", "돈", "돈찬", "돈돈", "돈베",
예를 들어, "don"의 두 번째 문자 "n"에서 "단어의 끝", "chi", "do", "be"입니다
자식 노드에는 4개의 분기가 있으므로 모두 서로 충돌하지 않도록 해야 합니다.
기본 구성 요소를 오프셋 값이라고 부를 수 있다고 생각합니다.
일반적으로 오프셋 값, 즉 대상 조합의 왼쪽을 가능한 한 최소화하도록 선택해야 합니다.
이중 배열의 성장과 함께 왼쪽부터 공간이 채워지는 것 같습니다.

이제 double array의 성장을 한 번에 한 단계씩 살펴보겠습니다.
사실, 설명해야 할 중요한 개념은 리프 노드 처리뿐이니 진정하시기 바랍니다.
처음에는 이해하지 못해도 필기하면서 여러 번 읽으면 분명 머리에 잡힐 것입니다.

덧붙여서, 이번에는 워드 ID 순으로 등록하므로,
이것은 깊이 우선 창작물임을 의미합니다.
또는 먼저 모든 표제어에 대해 루트에서 첫 번째 문자로의 전환을 등록한 다음 다음을 사용할 수 있습니다.
모든 표제어에서 첫 번째 문자→ 두 번째 문자의 전환을 등록하는 것도 가능합니다.
이 경우 너비 우선 생성이 됩니다.

1단계: "안에" → "굴"

전이 소스 s = 2로부터의 전이입니다. 문자 ID는 code['ん'] = 2입니다.
base[2] = 1인 경우 전환 대상은 t = base[s] + code[c ] = 1 + 2 = 3입니다.
빈 위치(맨 왼쪽)로 전환할 수 있습니다. 거기에 체크에 부모 노드 위치를 넣으십시오.
체크[3] = s = 2

이제 "den"이라는 단어의 끝에 도달했습니다. "Den..." 뒤에 오는 다른 표제어가 없기 때문에
전환에는 분기가 없습니다(리프 노드에는 형제 노드가 없음).
일반적으로 전환 대상을 code[leaf node] = 0으로 간주하여 리프 노드를 만듭니다.
분기가 없으면 리프 노드를 만드는 데 신경 쓰지 말고 추가하십시오.
ID라는 단어의 부호를 거꾸로 음수로 넣으십시오.
메모리를 절약하고 검색 속도를 약간 높입니다.
"den"의 단어 ID는 1이므로 base[3] = -1입니다
위의 표에서 "de"→ "den" 사이의 전환은 "→"로 단순화되었습니다.

2단계: "하다" → "어디서" "돈"

전이 소스 s = 4로부터의 전이입니다.
"do", "ko" 및 "n"에는 두 가지 전환 대상이 있습니다.
code['こ'] = 4 및 code['Γ'] = 2이므로 base[4] = 3이면
대상 노드 위치가 잘 결정되어 있습니다. 각각을 살펴 보겠습니다.

"해야 한다" → "어디서"
t = base[4] + code['ko'] = 3 + 4 = 7로 전환하므로 check[7] = s = 4
나는 "where"라는 단어의 끝에 왔지만 분기가 없습니다 ( "where ..."다음에 다른 표제어가 없습니다), 그래서
이전과 마찬가지로 ID 2라는 단어는 base[4] = -2가 되도록 반전됩니다.

"Do" → "Don"
t = base[4] + code['n'] = 3 + 2 = 5로 전환하므로 check[5] = s = 4
나는 "don"이라는 단어의 끝에 왔지만 "don"에서 "chi", "do"및 "be"로 분기됩니다.
base[t]에 ID(역 부호)라는 단어를 넣을 수 없으므로 새 리프 노드가 생성됩니다.
지금은 그대로 두고 다음 단계에서 생각하겠습니다.

이런 식으로 double 배열에서는 깊이 우선 방식으로 생성하더라도 사용할 수 있습니다.
항상 연결 너비 (분기 수)를 고려해야합니다. 왠지 흥미로운데요.

3단계: "돈" → "돈(단어의 끝)", "돈치", "돈도", "돈베"

전이 소스 s = 5로부터의 전이입니다.
코드[end] = 0, 코드['ち'] = 5, 코드['ど'] = 3, 코드['べ'] = 7.
base[5] = 6은 대상 노드 위치를 결정하는 좋은 방법입니다.
각각을 살펴 보겠습니다.

단어의 끝 → "don"
제가 아까 미뤄뒀던 과정입니다.
t = base[5] + code[end] = 6으로 전환하므로 check[6] = s = 5
단어의 끝이기 때문에 "돈"의 단어 ID의 3의 부호가 반전됩니다.
밑변[6] = -3
브랜치가 있으면 다음과 같이 새 리프 노드를 만든 다음
ID(거꾸로 된 기호)라는 단어를 넣으면 있습니다.
이것은 분기가 없는 경우와 비교하여 처리의 차이입니다.

"돈" → "돈치"
t = base[5] + code['chi'] = 6 + 5 = 11로 전환하므로 check[11] = s = 5

"돈" → "돈도"
t = base[5] + code['do'] = 6 + 3 = 9로 전환하므로 check[9] = s = 5

"돈" → "돈베"
t = base[5] + code['be'] = 6 + 7 = 13으로 전환하므로 check[13] = s = 5

4단계: "돈치" → "돈차" → "돈찬"

지금까지는 한 글자씩 진행해 왔지만 "Donchi"→ "Donchan"은 분기되지 않습니다.
그 설명을 두 글자로 요약하겠습니다.

"돈치" → "돈차"
전이 소스 s = 11. code['΃'] = 6이므로 base[11] = 2이면 t = base[11] + code['΃'] = 8로 전환합니다.
그래서 check [8] = 11

"돈차" → "돈짱"
전이 소스 s = 8. code['ん'] = 2이므로 base[8] = 8이면 t = base[8] + code['ん'] = 10으로 전환합니다.
그래서 check [10] = 8
나는 단어의 끝에 왔지만 리프 노드로의 전환에도 분기가 없습니다. ID라는 단어는 4이므로
밑[10] = -4가 되도록 부호를 뒤집습니다.

5단계: "돈도" → "돈베", "돈베" → "돈베"

double 배열이 완료되었습니다. (아, 설명...?) 함께해주셔서 감사합니다.
마지막으로, double 배열을 만드는 방법에 대해 알아야 할 몇 가지 중요한 사항이 있습니다.

1234코드