엔진 덮개 이더넷: 섹션 4(Trie)

업데이트:구문 수정
이 시리즈는 Part-1, 두 번째 부분, Part -3을 읽었다고 가정합니다. 아직 읽지 않으셨다면 본문을 읽기 전에 읽으십시오.이번 회 제목은'더 트리'(Patricia Merkle Trie)가 아닌'더 트리'(PMT)다.직접 PMT에 뛰어들기보다는 시도를 먼저 이해할 필요가 있다고 생각한다.바로 시작하겠습니다.
다음과 같은 내용을 논의합니다.

Trie 및 그 응용 프로그램은?

Trie의

에 대해 자세히 알아보기

이더리움과 Trie의 관계

예제

다음은요?

팁: 나는 중점을 강조하거나 주의를 끌기 위해 굵은 글씨체로 몇 개의 단어를 표시했다.

Trie와 그 응용 프로그램은?:

우리는 시도부터 시작한다.Trie에 관한 글이 많아서 위키에서 마음대로 훑어볼 수 있습니다.Trie는 val을 빠르게 검색하기 위한 데이터 구조이기 때문에'Trie'라고 부른다.trie 데이터 구조를 사용하는 실제 용례는 채팅 세션을 할 때 자동으로 수정하거나 자동으로 수정하는 기능인데 다음과 다르다. -)
출처: 자동 수정 실패.일반 도메인 이름 형식
자동 충전이나 자동 정정에 있어서 우리는 여러 가지 가능성을 가진 빠른 검색이 필요하다. 주어진 접두사의 값을 저장하고 검색하는 것은 매우 빨라야 한다. 이것이 바로 Trie가 이런 용례의 유용한 데이터 구조인 이유이다.

시도에 대한 심도 있는 이해:

다음 그림을 보십시오. 주어진 문자 그룹을 주어진 단어 그룹의 간소화된 Trie 데이터 구조로 비추는 것입니다.
기본 테스트
단순화 Trie에서는 각 원이 특정 속성이 있는 노드로 간주됩니다.단순화trie에는 세 가지 노드 1) 루트 노드(녹색) 2) 문자 노드(파란색) 3) Nil 노드(주황색)가 있습니다.이제 고개를 돌려 우리가 익숙한 이태방 세계의 속성을 더해 보자.
모든 노드 유형(파란색, 녹색, 주황색)에는 다음 세 가지 기본 속성 중 하나의 값이 있을 수 있습니다.

고유 Id.

은 하위 노드와 상위 노드를 가리키는 단일 문자와 포인터입니다.

상태 id.

앞의 두 속성은 말하지 않아도 알 수 있지만 속성 #3: 상태 Id는 사람을 흥분시키는 기본적인 속성이다. 이를 시간 표시로 간주하거나 전역 상태 Id를 유지하는 정렬 시스템을 간단하게 놓을 수 있다. 왜냐하면 e:g:State->0은 초기 상태이고 다음 상태->1이기 때문이다.
가령 우리가 추가하고자 하는 첫 번째 단어는'abba'이고 두 번째 단어는'abs'이다. 데이터 구조는 다음과 같을 수 있다.
{word=“abba”,*state_id=1*}
{word=“abs”,*state_id=2*}
누가 먼저 무엇을 하고 무엇을 할지 결정하는 것이 다른 날의 이야기입니다. 우리는 다음 시리즈에서 이 문제를 토론할 것입니다. 그러나 이 생각을 견지해 주십시오.이 점을 감안하여 우리는 현재 간단한 데이터 구조를 가지고 있는데 다음과 같다.우리를 위한 간단한 시도.우리는 간소화된trie 함수에 세 개의 매개 변수를 보낼 것이다.
기본Trie
주의:trie에 대한 정보를 더 알고 싶으면 이 우수한 article을 보십시오.

이태방과 트리의 관계는 어떻습니까?

위의 episodes 이더리움 RLP 두 개를 기억하면 RLP를 사용하여 값을 인코딩/디코딩합니다. 예를 들어 [83646f 67]로 인코딩된 문자열 "dog"과 [83646967]로 인코딩된 "dig"은 [83646967]로 인코딩됩니다.이런 인코딩 값 검색은 빠른 접근이 필요하다.
참고: 개의 16진수 변환은 646f 67입니다.
"dog"및 "dig"은 단순화된 Trie로 설명됨
위의trie를 보면 데이터 유형을 알 수 있고 데이터 형식과 그 중 몇 개가 trie의 왼쪽에 있는지 확인할 수 있다. 숫자'83'은 RLP 인코딩 규범에 의해 지정된 데이터 형식 문자열을 대표하고 두 개가 있다.
Google의 간소화 Trie는 세 가지 주요 기능이 있습니다. 하나는 추가하고, 하나는 삭제하고, 셋은 삭제합니다.Trie의 프레임 코드를 보려면 다음과 같이 하십시오.
Trie에 함수 뼈대 코드 추가하기

_function_ **trie\_add** (trie, word, state_id){

//traverse through trie
     //add whatever character node not available in the trie
     //provide parent node id to child idto the new child node.
     //add 'nil' node if applicable and map it to state_id

return status;

}

Trie 검색 기능 프레임워크 코드:

_function_ **trie\_search** (trie, word){

//Start from Root "/"
     //Retrieve all child nodes from "/"
     //verify if there is a match   
     //repeat until match completes

return status;

}

이태방으로 돌아가라. 우리가 이야기한 이태방의 세계 상태를 기억한다면, 그것은 본질적으로 키 값이 맞는 산열이다.아래에서 보듯이:
출처:
만약 종료 문자를 충당하는nil 노드에'45'와 같은 숫자가 있다고 가정하면 나는 여기서 너무 간단해진다. 그러나 그림을 볼 수 있다. 이더리움 전역 상태 Stack exchange에서 키 접두사'a77d'를 찾을 때 우리는 {1.00 ETH, 0.12 ETH}를 얻을 수 있다.우리는 이렇게 표현할 수 있다.
[{"a77d337": "1.00미"}, {"a77d397": "0.12미"}]
σ은 다음과 같이 액세스를 정의합니다.
yellow paper 황서 제4.1절, 그중 a는 주소, b는 잔액

하나의 예는 다음과 같습니다.

다음은 Python에서 Trie의 코드 세션입니다. (감사합니다 ) 간단한 프로그램을 만드실 수 있도록 격려합니다.
Vijay 출처: GitHub: @coolcalbeans
출력, Github: @coolcalbeans
우리 멈추고 좀 쉬자.

다음 단계

나는 네가 참고 자료를 자세히 읽어서 네가 어떻게 시도했는지 이해할 것을 건의한다.다음 절에서는 Patrica Merkle Trie라는 Trie의 업그레이드 버전과 이태방과의 관계에 대해 논의한 뒤 계속 공부할 예정이다.

참조 자료:

Trying to Understand Tries

What is the difference between trie and radix trie data structures?

자료 출처: