있습니까 트라이 과 기수 트라이 데이터 구조는 같은 일?
동일하다면 기수 트라이 (AKA Patricia trie)의 의미는 무엇입니까?
답변
기수 트리는 trie의 압축 버전입니다. 트라이에서는 각 가장자리에 단일 문자를 쓰고 PATRICIA 트리 (또는 기수 트리)에서는 전체 단어를 저장합니다.
이제, 당신은 단어를 가지고 가정 hello, hat그리고 have. trie에 저장하려면 다음과 같습니다.
e - l - l - o
/
h - a - t
\
v - e
그리고 9 개의 노드가 필요합니다. 노드에 문자를 배치했지만 실제로는 가장자리에 레이블을 지정합니다.
기수 트리에는 다음이 있습니다.
*
/
(ello)
/
* - h - * -(a) - * - (t) - *
\
(ve)
\
*
5 개의 노드 만 필요합니다. 위의 그림에서 노드는 별표입니다.
따라서 전반적으로 기수 트리는 메모리를 덜 차지 하지만 구현하기가 더 어렵습니다. 그렇지 않으면 둘 다의 사용 사례는 거의 동일합니다.
답변
내 질문은 Trie 데이터 구조와 Radix Trie 가 동일한 지 여부입니다.
요컨대, 아닙니다. 카테고리 기수 그래서 답장 의 특정 카테고리에 대해 설명 트리는을 하지만, 그 모든 시도는 기수 시도 것을 의미하지 않습니다.
같지 않다면 Radix trie (일명 Patricia Trie)의 의미는 무엇입니까?
나는 당신이 글을 쓰려고 한 것이 당신의 질문에 있지 않으므로 내 정정을 가정합니다.
마찬가지로 PATRICIA는 특정 유형의 기수 트라이를 나타내지 만 모든 기수 시도가 PATRICIA 시도 인 것은 아닙니다.
트라이는 무엇입니까?
“Trie”는 연관 배열로 사용하기에 적합한 트리 데이터 구조를 설명합니다. 여기서 분기 또는 모서리 는 키의 일부 에 해당합니다. 부분 의 정의는 여기에서 다소 모호합니다. 시도의 다른 구현은 에지에 대응하기 위해 다른 비트 길이를 사용하기 때문입니다. 예를 들어, 이진 트라이에는 0 또는 1에 해당하는 노드 당 2 개의 에지가있는 반면, 16 방향 트라이에는 4 비트에 해당하는 노드 당 16 개의 에지가 있습니다 (또는 16 진수 : 0x0에서 0xf까지).
Wikipedia에서 가져온이 다이어그램은 ‘A’, ‘to’, ‘tea’, ‘ted’, ‘ten’및 ‘inn’키가 (적어도) 삽입 된 트라이를 묘사하는 것 같습니다.
이 시도가 ‘t’, ‘te’, ‘i’또는 ‘in’키에 대한 항목을 저장하려면 nullary 노드와 실제 값이있는 노드를 구분하기 위해 각 노드에 추가 정보가 있어야합니다.
기수 트라이는 무엇입니까?
“Radix trie”는 Ivaylo Strandjev가 그의 답변에서 설명한 것처럼 공통 접두사 부분을 압축하는 trie의 한 형태를 설명하는 것 같습니다. 다음 정적 할당을 사용하여 “smile”, “smiled”, “smiles”및 “smiling”키를 색인화하는 256-way trie를 고려하십시오.
root['s']['m']['i']['l']['e']['\0'] = smile_item;
root['s']['m']['i']['l']['e']['d']['\0'] = smiled_item;
root['s']['m']['i']['l']['e']['s']['\0'] = smiles_item;
root['s']['m']['i']['l']['i']['n']['g']['\0'] = smiling_item;
각 첨자는 내부 노드에 액세스합니다. 즉 smile_item, 검색 하려면 7 개의 노드에 액세스해야합니다. 8 개의 노드 액세스는 smiled_item및에 해당 smiles_item하고 9 개 는에 해당 합니다 smiling_item. 이 4 개 항목에는 총 14 개의 노드가 있습니다. 그러나 이들은 모두 처음 4 바이트 (처음 4 개 노드에 해당)를 공통으로 가지고 있습니다. 이 4 바이트를 압축하여 root에 해당하는 을 생성함으로써 ['s']['m']['i']['l']4 개의 노드 액세스가 최적화되었습니다. 이는 메모리와 노드 액세스가 적다는 것을 의미하며 이는 매우 좋은 표시입니다. 불필요한 접미사 바이트에 액세스 할 필요성을 줄이기 위해 최적화를 반복적으로 적용 할 수 있습니다. 결국, 트라이에 의해 색인 된 위치에서 검색 키와 색인 된 키의 차이점 만 비교하는 지점에 도달합니다.. 이것은 기수 트라이입니다.
root = smil_dummy;
root['e'] = smile_item;
root['e']['d'] = smiled_item;
root['e']['s'] = smiles_item;
root['i'] = smiling_item;
항목을 검색하려면 각 노드에 위치가 필요합니다. 검색 키가 “smiles”이고 a root.position가 4이면에 액세스 root["smiles"[4]]합니다 root['e']. 우리는 이것을라는 변수에 저장합니다 current. current.position차이의 위치 인, 5 "smiled"및 "smiles"다음 액세스 것이다 있도록 root["smiles"[5]]. 이렇게하면 smiles_item, 및 문자열의 끝으로 이동합니다. 검색이 종료되고 8 개가 아닌 3 개의 노드 액세스만으로 항목이 검색되었습니다.
PATRICIA 트라이는 무엇입니까?
PATRICIA 트리는 항목 n을 포함하는 데 사용되는 노드 만 있어야하는 기수 시도의 변형입니다 n. 위의 조잡 입증 기수 트라이 의사 코드에서, 총 다섯 개 노드있다 : root(a null의 노드이며, 이는 실제 값을 포함하지 않음), root['e'], root['e']['d'], root['e']['s']및 root['i']. PATRICIA 트라이에는 4 개만 있어야합니다. PATRICIA는 이진 알고리즘이기 때문에이 접두사를 이진법으로 보면 어떻게 다른지 살펴 보겠습니다.
smile: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0000 0000 0000 0000
smiled: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0110 0100 0000 0000
smiles: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0111 0011 0000 0000
smiling: 0111 0011 0110 1101 0110 1001 0110 1100 0110 1001 0110 1110 0110 0111 ...
노드가 위에 제시된 순서대로 추가되었다고 생각해 보겠습니다. smile_item이 나무의 뿌리입니다. 조금 더 쉽게 알아볼 수 있도록 굵게 표시된 차이점 "smile"은 비트 36 의 마지막 바이트에 있습니다 .이 시점까지 모든 노드는 동일한 접두사를 갖 습니다 . smiled_node에 속합니다 smile_node[0]. 차이 "smiled"와 "smiles"비트 (43)에서 발생 "smiles"하므로, ‘1’비트를 가지고 smiled_node[1]있다 smiles_node.
오히려 사용하는 것보다 NULL검색 종료가, 가지가 다시 연결할 때 지점 및 / 또는 표시하기 위해 별도의 내부 정보로 최대 트리 어딘가에 시험 오프셋 검색 종료 그래서, 감소 하기보다는 증가. 아래에 언급 된 Sedgewick의 책에 포함 된 이러한 트리 의 간단한 다이어그램이 있습니다 (PATRICIA는 실제로 트리보다 순환 그래프에 가깝지만).
PATRICIA의 기술적 속성 중 일부가 프로세스에서 손실되지만 변형 길이의 키를 포함하는 더 복잡한 PATRICIA 알고리즘이 가능합니다 (즉, 모든 노드에 이전 노드와 함께 공통 접두사가 포함됨).
이와 같이 분기하면 여러 가지 이점이 있습니다. 모든 노드에는 값이 있습니다. 그것은 루트를 포함합니다. 결과적으로 코드의 길이와 복잡성은 실제로 훨씬 짧아지고 아마도 조금 더 빨라질 것입니다. 항목을 찾기 위해 적어도 하나의 분기와 최대 k분기 (여기서는 k검색 키의 비트 수)를 따릅니다. 노드는 각각 두 개의 분기 만 저장하기 때문에 매우 작기 때문에 캐시 지역성 최적화에 상당히 적합합니다. 이러한 속성 덕분에 지금까지 PATRICIA가 가장 좋아하는 알고리즘이되었습니다.
내 임박한 관절염의 중증도를 줄이기 위해 여기서는이 설명을 짧게 자르겠습니다.하지만 PATRICIA에 대해 더 알고 싶다면 Donald Knuth의 “The Art of Computer Programming, Volume 3″과 같은 책을 참조 할 수 있습니다. , 또는 Sedgewick의 “{your-favourite-language}, part 1-4″로 된 알고리즘 “
답변
TRIE :
전체 검색 키를 기존의 모든 키 (예 : 해시 스키마)와 비교하는 대신 검색 키의 각 문자를 비교할 수도있는 검색 스키마를 가질 수 있습니다. 이 아이디어에 따라“ dad ”,“ dab ”및” cab ”의 세 가지 기존 키가있는 구조 (아래 그림 참조)를 구축 할 수 있습니다 .
[root]
...// | \\...
| \
c d
| \
[*] [*]
...//|\. ./|\\... Fig-I
a a
/ /
[*] [*]
...//|\.. ../|\\...
/ / \
B b d
/ / \
[] [] []
(cab) (dab) (dad)
이것은 본질적으로 [*]로 표시되는 내부 노드와 []로 표시되는 리프 노드가있는 M-ary 트리입니다. 이 구조를 trie 라고합니다 . 각 노드의 분기 결정은 알파벳의 고유 기호 수 (예 : R)와 동일하게 유지 될 수 있습니다. 소문자 영어 알파벳의 경우 az, R = 26; 확장 ASCII 알파벳의 경우 R = 256 및 이진 숫자 / 문자열의 경우 R = 2입니다.
Compact TRIE :
일반적으로 trie 의 노드는 size = R 인 배열을 사용하므로 각 노드에 에지가 적을 때 메모리 낭비가 발생합니다. 메모리 문제를 피하기 위해 다양한 제안이 이루어졌습니다. 이러한 변형을 기반으로 trie 는“ compact trie ”및“ compression trie ” 라고도 합니다. 일관된 명명법은 드물지만 노드에 단일 에지가있을 때 모든 에지를 그룹화 하여 가장 일반적인 버전의 컴팩트 트라이 가 형성됩니다. 이 개념을 사용하여 “dad”, “dab”및 “cab”키가 있는 위의 (그림 -I) 트라이 는 아래 형식을 취할 수 있습니다.
[root]
...// | \\...
| \
cab da
| \
[ ] [*] Fig-II
./|\\...
| \
b d
| \
[] []
‘c’, ‘a’및 ‘b’는 각각 해당 상위 노드에 대한 유일한 에지이므로 단일 에지 “cab”으로 통합됩니다. 마찬가지로 ‘d’와 a ‘는 “da”라는 레이블이 붙은 단일 모서리로 병합됩니다.
기수 트라이 : 수학에서 기수
라는 용어 는 숫자 시스템의 밑을 의미하며 본질적으로 해당 시스템에서 숫자를 나타내는 데 필요한 고유 기호의 수를 나타냅니다. 예를 들어, 10 진수 시스템은 기수 10이고 이진 시스템은 기수 2입니다. 유사한 개념을 사용하여 기본 표현 시스템의 고유 한 기호 수로 데이터 구조 또는 알고리즘을 특성화하는 데 관심이있을 때 개념에 “기수”라는 용어를 붙입니다. 예를 들어 특정 정렬 알고리즘의 경우 “기수 정렬”입니다. 동일한 논리 줄에서 모든 변형의 trie그 특성 (예 : 깊이, 메모리 필요, 검색 실패 / 적중 런타임 등)이 기본 알파벳의 기수에 의존하는 경우 기수 “trie ‘s”라고 부를 수 있습니다. 예를 들어, 알파벳 az를 사용할 때 압축되지 않은 트라이 뿐만 아니라 압축되지 않은 트라이를 기수 26 트라이 라고 부를 수 있습니다 . 두 개의 기호 (전통적으로 ‘0’및 ‘1’) 만 사용하는 모든 트라이를 기수 2 트라이 라고 할 수 있습니다 . 그러나 어떻게 든 많은 문헌에서 압축 된 트라이에 대해서만“Radix Trie”라는 용어의 사용을 제한했습니다 .
PATRICIA Tree / Trie의 전주곡 :
키로서의 문자열조차도 이진 알파벳을 사용하여 표현할 수 있다는 점에 주목하면 흥미로울 것입니다. ASCII 인코딩을 가정하면 ‘d’, ‘a’및 ‘a’의 이진 형식을 작성 하여 ” 01100100 01100001 01100100 ” 과 같이 순서대로 각 문자의 이진 표현을 작성하여 키 “dad”를 이진 형식으로 작성할 수 있습니다. ‘d’. 이 개념을 사용하여 Trie (Radix Two 포함)를 구성 할 수 있습니다. 아래에서는 문자 ‘a’, ‘b’, ‘c’, ‘d’가 ASCII가 아닌 더 작은 알파벳에서 왔다는 간단한 가정을 사용하여이 개념을 설명합니다.
그림 -III에 대한 참고 사항 : 언급했듯이 설명을 쉽게하기 위해 4 개의 문자 {a, b, c, d} 만있는 알파벳과 해당 이진 표현이 “00”, “01”, “10”및 각각“11”. 이를 통해 문자열 키 “dad”, “dab”및 “cab”은 각각 “110011”, “110001”및 “100001”이됩니다. 이에 대한 트라이는 아래 그림 -III에 나와 있습니다 (문자열이 왼쪽에서 오른쪽으로 읽는 것처럼 비트는 왼쪽에서 오른쪽으로 읽음).
[root]
\1
\
[*]
0/ \1
/ \
[*] [*]
0/ /
/ /0
[*] [*]
0/ /
/ /0
[*] [*]
0/ 0/ \1 Fig-III
/ / \
[*] [*] [*]
\1 \1 \1
\ \ \
[] [] []
(cab) (dab) (dad)
PATRICIA Trie / Tree : 단일 에지 압축을 사용하여
위의 이진 트라이 (그림 -III)를 압축하면 위에 표시된 것보다 훨씬 적은 노드가 있지만 노드는 여전히 포함 된 키 수인 3보다 많을 것입니다. . Donald R. Morrison 은 (1968 년) N 개의 노드 만 사용하는 N 개의 키를 나타내는 이진 트라이 를 사용하는 혁신적인 방법을 발견 했으며이 데이터 구조를 PATRICIA 라고 명명했습니다.. 그의 trie 구조는 본질적으로 단일 모서리 (단방향 분기)를 제거했습니다. 그렇게함으로써 그는 두 종류의 노드, 즉 어떤 키도 묘사하지 않는 내부 노드와 키를 묘사하는 리프 노드라는 개념도 제거했습니다. 위에서 설명한 압축 논리와 달리 그의 트라이는 분기 결정을 내릴 때 건너 뛸 키의 비트 수에 대한 표시를 각 노드에 포함하는 다른 개념을 사용합니다. 그의 PATRICIA trie의 또 다른 특징은 키를 저장하지 않는다는 것입니다. 즉, 이러한 데이터 구조는 주어진 접두사와 일치하는 모든 키를 나열하는 것과 같은 질문에 답하는 데 적합하지 않지만 키가 있는지 또는 트라이에. 그럼에도 불구하고 Patricia Tree 또는 Patricia Trie라는 용어는 그 이후로 콤팩트 트라이 [NIST]를 나타내거나 기수 2가있는 기수 트라이를 나타 내기 위해 (미묘하게 표시된대로) 여러 가지 다르지만 유사한 의미에서 사용되었습니다. WIKI의 길] 등등.
기수 시도가 아닐 수있는 시도 : TST 가 데이터 구조 ( J. Bentley 및 R. Sedgewick에서 제안)이므로 종종 축약되는
Ternary Search Trie (일명 Ternary Search Tree) 는 3 방향 분기가있는 trie와 매우 유사합니다. 이러한 트리의 경우 각 노드에는 특성 알파벳 ‘x’가 있으므로 키의 문자가 ‘x’보다 작은 지, 같은지 또는 큰지에 따라 분기 결정이 이루어집니다. 이 고정 된 3 방향 분기 기능으로 인해 특히 R (기수)가 유니 코드 알파벳과 같이 매우 큰 경우 trie에 대한 메모리 효율적인 대안을 제공합니다. 흥미롭게도 TST는 (R-way) trie 와 달리 R의 영향을받는 특성이 없습니다. 예를 들어 TST에 대한 검색 누락은 ln (N)입니다.R-way Trie에 대한 반대 log R (N) . R-way trie 와 달리 TST의 메모리 요구 사항은 R 의 함수 도 아닙니다 . 따라서 우리는 TST를 기수 트라이라고 부르도록주의해야합니다. 나는 개인적으로 그것을 기수 트라이라고 부르지 말아야한다고 생각한다. 왜냐하면 그 특성 중 어떤 것도 기본 알파벳의 기수 R에 영향을받지 않기 때문이다.
