웨이블렛 트리

"abracadabra" 줄에 있는 파랑나무.각 노드에서 문자열의 기호는 알파벳의 두 칸막이에 투영되며 비트벡터는 각 기호가 속하는 칸막이를 나타낸다.비트 벡터만 저장되며, 노드의 문자열은 오직 설명 목적으로만 저장된다는 점에 유의하십시오.

Wavelet Tree는 압축된 공간에 문자열을 저장하는 간결한 데이터 구조다.임의 알파벳 비트벡터에 정의된 r n k ${\displaystyle {\mathbf{q}}_{}}$ ${\$ 및$$ $s{\displaystyle {\mathbf{}}_{}}$ e ${\displaystyle {\mathbf{l}}_{}}$ ${\displaystyle {\mathbf{e}}_{}}$ ${\displaystyle {\mathbf{c}}_{}}$ t ${\displaystyle {}_{}}$ ${\$ 연산을$$ 일반화한다.

원래 압축 접미사 배열을 나타내기 위해 도입되었으며,^[1] 여러 맥락에서 응용 프로그램을 찾았다.^[2][3]트리는 알파벳을 하위 집합의 쌍으로 재귀적으로 분할하여 정의된다. 잎은 알파벳의 개별 기호에 해당하며, 각 노드에서 비트벡터는 문자열의 기호가 한 하위 집합에 속하는지 다른 하위 집합에 속하는지 여부를 저장한다.

이 이름은 신호용 파장 변환기와 유사하게, 신호를 저주파 및 고주파 구성 요소로 재귀적으로 분해하는 데서 유래한다.

특성.

Let ${\displaystyle \Sigma }$ be a finite alphabet with ${\displaystyle \sigma = \Sigma }$. By using succinct dictionaries in the nodes, a string ${\displaystyle s\in \Sigma ^{*}}$ can be stored in ${\displaystyle nH_{0}(s)+o( s \log \sigma )}$, where $$${\displaystyle H_{}}$ ${\displaystyle {0\mathrm{}}_{}}$( ${\displaystyle s}$) ${\displaystyle H_{0}(s)}$은(는) $s{\displaystyle }$ ${\displaystyle s}$의 경험적 엔트로피 입니다$.$

If the tree is balanced, the operations ${\displaystyle \mathbf {access} }$, ${\displaystyle \mathbf {rank} _{q}}$, and ${\displaystyle \mathbf {select} _{q}}$ can be supported in ${\displaystyle O(\log \sigma )}$ time.

액세스 작업

물결표 트리는 문자열의 비트맵 표현을 포함한다.만약 우리가 알파벳 집합을 안다면, 정확한 문자열은 나무에서 비트를 추적함으로써 유추될 수 있다.문자열의^th i 위치에서 문자를 찾으려면:-

알고리즘 액세스 입력: - 문자열을 알고자 하는 문자열의 위치 1. - 문자열을 나타내는 물결표 트리의 상단 노드 W:위치 I에 있는 편지

W.isLeafNode가 W.bitvector[i] = 0 반환 액세스(i - 순위(i.bitvector, i), W.left)인 경우 W.letter를 반환하는 경우, 다른 반환 액세스(rank(W.bitvector, i), W.rif)

이러한 맥락에서 비트벡터 $b{\displaystyle }$ ${\displaystyle b}$에서 $위치{\displaystyle }$ i ${\displaystyle i}$의 순위는 $b{\displaystyle }$ ${\displaystyle b}$의 첫 $번째{\displaystyle }$ i ${\displaystyle i}$ 위치에$$ 나타나는 순위의 수입니다$$$.$ 간결한 사전을 사용하여 O(1)로 순위를 계산할 수 있기 때문에 문자열 S의 모든 S[i]에 $액세스할{\displaystyle }$ 수 있다${\displaystyle .}$${\displaystyle \mathrm{로그}\log }$) ${\displaystyle O(\log \sigma )}$시간$$^[3](트리가 균형을 유지하는 한).

확장

문헌에는 기본 구조에 대한 몇 가지 연장이 제시되어 있다.트리의 높이를 줄이기 위해 이진 대신 다중 노드를 사용할 수 있다.^[2]데이터 구조는 문자열의 임의 지점에서의 삽입과 삭제를 지원하는 동적으로 만들 수 있다. 이 기능은 동적 FM-색인의 구현을 가능하게 한다.^[4]이것은 더 일반화될 수 있으며, 업데이트 작업으로 기본 알파벳을 변경할 수 있다: Wavelet Trie는^[5] 동적 트리 수정을 가능하게 하기 위해 문자열의 알파벳에 트리 구조를 이용한다.

추가 읽기

• 파도타기 나무.웨이브 트리의 구조를 예시와 함께 설명하는 블로그 게시물.

웨이블렛 트리는 지리학적 검색과 같은 다른 영역에서 많은 유인물을 가지고 있다.연구진은 지리정보검색용 웨이블렛트리(GIR)를 기반으로 한 이중 인덱싱 기법을 제시했다.인터넷상의 지리적 정보의 양이 많기 때문에 정보 검색 중에 인덱싱이 어려웠으며, 정보 검색은 자원 집합에서 우리의 필요에 따라 정보 집합을 검색하는 활동으로 정의된다.효율적인 인덱싱 기법은 오늘날의 정보 검색 시스템에 존재하는 많은 데이터를 처리하는 데 필수적인 요건이다.이것은 초기에는 더 작은 크기와 더 높은 비용으로 구성되었던 메인 메모리에 비해 2차 메모리에 주로 초점을 맞춘 여러 가지 다른 인덱싱 구조의 설계와 개발에 대한 동기였다. 그러나 메인 메모리 가격의 급격한 하락으로 인해 메인 메모리 내의 인덱스가 크게 감소되었다.오리는 또한 1차 메모리 기반 인덱싱 구조를 개발하도록 이끌었다.^[6]

듀얼 인덱싱 기법은 텍스트와 공간 인덱싱 모두에 웨이브릿 트리 데이터 구조를 사용하며 인덱스 구성 시 동적 삽입 시 MBR을 사용할 수 있다.광범위한 데이터 세트가 포함된 경우 병렬 컴퓨팅을 지원할 수 있는 장점이 있다.이는 한 기계에서 텍스트 데이터를 검색할 수 있고 다른 기계의 공간 데이터를 검색할 수 있어 검색 시간과 저장 공간을 줄일 수 있으므로 이 방법은 이전에 제안된 방법에 비해 훨씬 효율적이다.순수 공간 인덱싱을 사용할 경우 검색 시간 복잡성이 감소하고 이전에 도입한 R-트리 또는 R*-트리 방법을 사용하여 수행된 공간 인덱싱의 3분의 1도 안 되는 시간이 소요된다는 실험 결과가 이를 뒷받침한다.또한 파월트리를 이용한 이중 인덱싱(텍스트·공간)의 경우 검색 질의 길이가 2개 키워드 이상인 경우 B/R, B/R* 등의 다른 기법에 비해 검색 시간이 절반으로 줄어든다.^[6]

참조

외부 링크

• Wikimedia Commons의 Wavelet Tree 관련 미디어