Double Array Trie 는 TRIE 나무의 변형 으로 TRIE 트 리 의 검색 속 도 를 확보 하 는 전제 에서 공간 이 용 률 을 높이 기 위해 제 시 된 데이터 구조 로 본질 적 으로 유한 한 자동 동기 (deterministic finite automation, 약칭 DFA) 를 확정 하 는 것 이다.
DFA 란 상태 이동 이 가능 한 자동 동기 다.주어진 이 자동 동기 에 속 하 는 상태 와 이 자동 동기 알파벳 에 속 하 는 상태Σ미리 정 해진 이동 함수 에 따라 다음 상태 로 이동 할 수 있 습 니 다.
Double Array Trie (이하 DAT 로 약칭) 에 대해 각 노드 는 자동 동기 의 한 상 태 를 나타 내 고 변수 에 따라 상태 이동 을 하 며 종료 상태 에 도달 하거나 이동 할 수 없 을 때 조 회 를 완성 한다.
1. Double Array Trie 가 무엇 입 니까? 2 DAT 구조 2.1 DAT 정의 2.2 DAT 매 칭 2.3 DAT 구조 2.4 DAT 개선 방안 2 참고 자료 Double Array Trie 가 뭐 예요?
Double Array Trie 는 TRIE 나무의 변형 으로 TRIE 트 리 의 검색 속 도 를 확보 하 는 전제 에서 공간 이 용 률 을 높이 기 위해 제 시 된 데이터 구조 로 본질 적 으로 유한 한 자동 동기 (deterministic finite automation, 약칭 DFA) 를 확정 하 는 것 이다.
DFA 란 상태 이동 이 가능 한 자동 동기 다.주어진 이 자동 동기 에 속 하 는 상태 와 이 자동 동기 알파벳 에 속 하 는 상태Σ미리 정 해진 이동 함수 에 따라 다음 상태 로 이동 할 수 있 습 니 다.
Double Array Trie (이하 DAT 로 약칭) 에 대해 각 노드 는 자동 동기 의 한 상 태 를 나타 내 고 변수 에 따라 상태 이동 을 하 며 종료 상태 에 도달 하거나 이동 할 수 없 을 때 조 회 를 완성 한다.
DAT 구조 DAT 정의
DAT 는 두 개의 선형 배열 (base [] 와 check []) 을 사용 하고 base 와 check 배열 은 일치 하 는 하 표를 가지 고 있 습 니 다. (하 표) 즉 DFA 의 모든 상태, 즉 TRIE 트 리 에서 말 하 는 노드 입 니 다. base 배열 은 상 태 를 확인 하 는 데 사 용 됩 니 다. check 배열 은 이동 의 정확성 을 검증 하 는 데 사 용 됩 니 다.따라서 상태 s 입력 c 에서 상태 t 로 의 이전 은 다음 과 같은 조건 을 만족 시 켜 야 한다.
base[s] + c == t
check[base[s] + c] == s
DAT 도 다음 과 같이 설명 할 수 있다.
주어진 상태 s 에 대해 n 개의 상태 (문자 c1, c2,..., cn) 의 이동 이 있 으 면 base 배열 에서 빈자리 t1, t2,... tn 을 찾 아야 합 니 다. t1 - c1, t2 - c2,... tn - cn 은 모두 base 배열 에서 s 로 표 시 된 값 입 니 다. 여기 t1, t2,.. tn 이 반드시 base 배열 에서 연속 되 는 것 은 아 닙 니 다.
이전 상태 t1, t2,..., tn 에 대해 다음 표 시 를 할 때 check [t1], check [t2], check [tn] 의 값 은 모두 상태 s 입 니 다.
이해 하기 편 하도록 256 포크 트 리 의 그림 이 있 습 니 다.
그림 의 맨 위 에 256 개의 부모 노드 가 있 고 모든 부모 노드 는 256 개의 키 노드 가 있다.그러면 한자 와 자모 에 관 계 없 이 256 개의 키 노드 에 분포 할 수 있 지만 단어 가 app 과 apple, banana 세 개의 단어 만 있 으 면 256 개의 부모 노드 가 낭비 되 고 실제 적 으로 2 개의 부모 노드 만 있 으 면 된다.
만약 에 노드 의 유형 이 정형 이 라면 우 리 는 모든 노드 를 번 호 를 매기 고 단어의 이니셜 ascii 코드 를 직접 노드 로 한다. 97, 98 이라는 두 부모 노드 는 사용 되 고 나머지 부모 노드 는 불필요 하 며 빈 지침 을 사용 하면 된다.
256 포크 트 리 의 정의 에 따 르 면 97 과 98 에 도 256 개의 키 노드 가 있 지만 단어의 두 번 째 자모 에 따 르 면 97 의 다음 노드 는 p (112) 노드 만 있 고 98 의 다음 노드 는 a (97) 노드 만 있 으 며 나머지 노드 는 비어 있다. 그러면 트 리 형 알고리즘 의 복잡 도 는 On 이기 때문에 최대 n 번 일치 하면 한 번 의 검색 을 완성 할 수 있다.우 리 는 사용 하지 않 는 노드 를 생략 하고 공간의 여가 율 을 낮 출 수 있다.
DAT 매 칭 상기 정 의 를 바탕 으로 DAT 의 일치 과정 은 다음 과 같 습 니 다. 현재 상 태 를 s 라 고 가정 하면 입력 한 문자 c 에 대해 다음 과 같 습 니 다.
t = base[s] + c;
if check[t] = s then
next state = t;
else
fail;
endif
DAT 가 일치 하 는 과정 은 상대 적 으로 간단 하고 이해 하기 쉽다. DAT 구조
우선 DAT 의 메모리 관 리 를 알 아야 합 니 다.
DAT 의 구조 과정 에서 보통 두 가지 구조 방법 이 있다.
이미 알 고 있 는 모든 단어, 정태 구조 더 블 배열;
이 방법 을 구축 할 때 모든 단 어 를 메모리 에 넣 고 단어 에 있 는 모든 부모 노드 와 그 아래 의 하위 노드 를 각각 정렬 (보통 ASCII 코드 정렬) 하여 최초의 부모 노드 수량 과 몇 개의 서로 다른 부분 포인트 가 있 는 지 찾 아 메모리 에 대한 분 배 를 편리 하 게 한다.이러한 장점 은 서브 노드 공간 을 찾 으 면 서브 노드 를 충분히 수용 할 수 있 고 앞으로 확장 할 필요 가 없 으 며 상대 적 으로 복잡 도가 낮 고 구축 속도 가 상대 적 으로 빠르다 는 것 이다.단점 은 앞으로 단 어 를 추가 하 는 것 이 원활 하지 않 고 매번 재 구축 이 필요 하 다 는 것 이다.
동적 입력 단어, 동적 구조 더 블 배열.
n 개의 단어 가 더 블 배열 을 구축 하려 고 할 때 먼저 하나의 단어 cat 를 추가 하 는 것 을 예 로 들 면 더 블 배열 에서 base [1024] 배열 의 뿌리 노드 는 0 (기본 값, 물론 '개인 취미' 에 따라 마음대로 지정 할 수 있 습 니 다) 이 고 아래 는 0 으로 표 시 됩 니 다. 단어 cat 의 첫 글자 인 'c' (99) 에 적당 한 위 치 를 찾 습 니 다. 예 를 들 어 위치 100, 즉:
base[0] = 100;
여기 서 base [100] 의 위치 에 문자 'c' 의 ascii 를 추가 하면 다음 상태 (t) 의 위치 (199) 에 갈 수 있 습 니 다. 그리고 적당 한 위치 (남 은 위치) 197 에서
base[199]+'a'=197;
그러면 상태 (t), 즉 base [199] 의 수 치 는 상기 공식 을 통 해 100
을 얻 을 수 있다.
주의해 야 할 것 은 상태 (f), 현재 문자 't' 입 니 다. 끝 날 때 그 value 값 은 다음 과 같이 처리 할 수 있 습 니 다. 상태 (f) 가 끝나 고 하위 노드 가 없 으 면
base(f)=-1 * f;
상태 (t) 가 끝나 도 여러 개의 키 노드 가 있 으 면 base 배열 은
로 표 시 됩 니 다.
base(f)=-1 * base(f);
두 번 째 단어 camera 를 입력 할 때 상기 방식 으로 진행 합 니 다. 문자 a 가 진행 되 었 을 때 문자 a 위치 아래 표 시 는 197 이 고 check [base [197] + 'm'] 가 빈 자리 인지 확인 합 니 다.
빈자리 라면 base [197] 의 값 은 100 일 수 있 습 니 다.
그렇지 않 으 면 두 개의 빈 자 리 를 다시 찾 아야 한다.Ψ(base[197]+'m')，λ(base [197] + 't'), base [base [197] + 'm'] = - 1 (- 1 은 빈자리 상태, 'm' 는 camera 의 세 번 째 문자) 과 base [base [197] + 't'] = - 1 ('t' 는 cat 의 세 번 째 문자), 즉 두 번 째 노드 a 뒤의 두 개의 새 노드 는 위치 에 새로운 오프셋 을 저장 하고 check [base [197] + 'm'] = 197 과 check [base [197] + 't'] = 197 을 저장 하면 됩 니 다. 그러면 base [197]새로운 위치 로 다시 가리 키 기 (Ψ+λ-'m'-'t')/2。
이어서 다음 두 노드 의 DAT 구 조 를 계속 재 구축 하고 첫 번 째 노드 의 구조 구조 가 완성 되면 원래 의 구축 을 제거 해 야 한다.
동적 구조 쌍 배열 은 단 어 를 편리 하 게 동적 으로 삽입 할 수 있 고 전체 TRIE 트 리 를 재 구성 할 필요 가 없 지만 실현 하 는 논 리 는 상대 적 으로 복잡 하 다.
초기 상태 에서 신청 한 배열 의 크기 가 부족 할 경우 확장 하고 원래 의 배열 을 새로 추 가 된 배열 에 복사 해 야 하 며 원래 의 배열 은 보통 메모리 방출 을 해 야 한다. 다음 과 같은 그림
DAT 구조 에서 check 배열 은 부모 노드, 즉 base 배열 에서 부모 노드 의 아래 표 시 를 가리 키 면 됩 니 다. 여기 약도 가 있 습 니 다. DAT 쌍 배열 을 구성 하 는 방식 을 묘 사 했 습 니 다.
DAT 개선 방안
DAT 는 일반 트 리 에 비해 공간의 이 용 률 을 높 였 지만 공간 이 용 률 이 가장 좋 은 것 은 아니다.
예 를 들 어 단어 elephant (8 글자) 는 모든 단어 중에서 e 로 시작 하 는 단어 가 하나 밖 에 없다 면 보통 우 리 는 trie 의 구 조 를 실현 한다
.
struct BC_st
{
int base;
int check;
};
그러면 전체 단어 가 DAT 에서 차지 하 는 공간 은 4 * 2 * 8 = 64 바이트 입 니 다. 사실 저장 소 는 그렇게 많은 공간 을 낭비 할 필요 가 없습니다. DAT 구조 에서 lephant 를 7 개의 바이트 로 저장 할 수 있 습 니 다. 조회 할 때 lephant 는 바이트 검색 을 실현 하면 됩 니 다.
DAT 는 나무 모양 의 구조 로 끊임없이 발산 되 는 구조 이다. 만약 에 맞은편 에서 똑 같은 구 조 를 실현 하면 상대 적 으로 공간 부 피 를 절반 으로 줄 일 수 있다. 그림 에서 보 듯 이
물론 상술 한 구 조 는 이미 누군가가 실현 한 적 이 있 고 실현 이 비교적 복잡 하 다.
또한 DAT 더 블 배열 에서 많은 여유 공간 이 충분히 이용 되 지 못 했 기 때문에 링크 를 통 해 사용 되 지 않 은 공간 을 연결 시 켜 더욱 합 리 적 으로 이용 하고 데이터 밀집 도 를 높 일 수 있다.
참조 연결
http://linux.thai.net/~thep/datrie/datrie.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
