간결한 데이터 구조

컴퓨터 과학에서, 간결한 데이터 구조는 정보 이론 하위에 "가까운" 공간을 사용하는 데이터 구조이지만, (다른 압축 표현과 달리) 여전히 효율적인 쿼리 연산을 가능하게 한다.이 개념은 원래 [1] Jacobson에 의해 비트 벡터, (라벨이 없는) 트리 및 평면 그래프를 인코딩하기 위해 도입되었습니다.일반적인 무손실 데이터 압축 알고리즘과 달리 간결한 데이터 구조는 먼저 압축을 풀지 않고 내부에서 사용할 수 있습니다.관련 개념은 데이터 구조의 크기가 표현되는 특정 데이터에 따라 달라지는 압축 데이터 구조의 개념입니다.

Z $(\displaystyle$ Z $)$ 가 $Z$ 일부 데이터를 저장하는 데 필요한 정보 이론상 최적의 비트 수라고 가정합니다.이 데이터의 표현은 다음과 같습니다.

Z $Z+O(1)$ + $Z+O(1)$ ( $Z+O(1)$ ) $Z+O(1)$ { $displaystyle$ Z + $O$ (1 $)$ }비트의 $Z+O(1)$ 공간이 $Z+O(1)$ 한 경우 암묵적으로 사용합니다.
Z $Z+o(Z)$ + $Z+o(Z)$ ( $Z+o(Z)$ ) { $displaystyle$ Z + $o$ ( $Z$ ) }비트의 $Z+o(Z)$ 공간이 $Z+o(Z)$ 한 경우 간결하게 표시됩니다.
O( $)$ { $displaystyle$ O $(Z)}$ 비트의 $O(Z)$ 공간이 $O(Z)$ 한 경우 컴팩트합니다.

예를 들어 2개의 $(디스플레이$ 스타일 $2Z)$ 비트를 $2Z$ $2Z$ 하는 데이터 구조는 콤팩트하고 $Z+{\sqrt {Z}}$ $Z+{\sqrt {Z}}$ + $Z+\lg Z$ ( $디스플레이$ 스타일 Z $+{\sqrt$ {Z $}})$ 비트는 $Z+\lg Z$ 하며, $Z+\lg Z$ Z + lg $Z+\lg Z$ Z( $디스플레이$ 스타일 Z $+\$ $lg$ Z $)$ 비트는 $Z+\lg Z$ 간결하며 $Z+3$ $Z+3$ + $(디스플레이 스타일$ Z+3) 비트는 $Z+3$ 암묵적입니다.

따라서 암묵적 구조는 일반적으로 입력 데이터의 치환을 사용하여 정보를 저장하는 것으로 축소됩니다. 가장 잘 알려진 예는 힙입니다.

간결한 사전

순위/선택 사전이라고도 하는 간결한 색인화 사전은 이진 트리, $\style$ k $\$ ary $k$ 트리 및 멀티셋,^[2] 접미사 트리 및 ^[3]배열 등 많은 간결한 표현 기술의 기초를 형성한다.기본적인 문제는 $U=[0\dots n)=\{0,1,\dots ,n-1\}$ U $U=[0\dots n)=\{0,1,\dots ,n-1\}$ [ $U=[0\dots n)=\{0,1,\dots ,n-1\}$ $U=[0\dots n)=\{0,1,\dots ,n-1\}$ $U=[0\dots n)=\{0,1,\dots ,n-1\}$ ] $U=[0\dots n)=\{0,1,\dots ,n-1\}$ { $U=[0\dots n)=\{0,1,\dots ,n-1\}$ , $U=[0\dots n)=\{0,1,\dots ,n-1\}$ , $U=[0\dots n)=\{0,1,\dots ,n-1\}$ , $U=[0\dots n)=\{0,1,\dots ,n-1\}$ - $U=[0\dots n)=\{0,1,\dots ,n-1\}$ { $displaystyle$ U = [ $U=[0\dots n)=\{0,1,\dots ,n-1\}$ $0$ \ $dots$ n ) $=$ \ { $0$ , 1 $,$ $\ dots$ , n - 1 \ $U=[0\dots n)=\{0,1,\dots ,n-1\}$ }의 $S$ 를 $S$ 저장하는 것입니다.여기서 보통 비트 $B[0\dots n)$ B $B[0\dots n)$ [ $B[0\dots n)$ $B[0\dots n)$ $B[0\dots n)$ ]{ 0 . n } { \ $dots }$ 로 $B[0\dots n)$ 표시됩니다 $.$ $i\in S.$ 인덱스 가능한 사전은 사전에서 일반적인 메서드(쿼리 및 동적 대소문자의 삽입/삭제)와 다음 작업을 지원합니다.

$\mathbf {rank} _{q}(x)= \{k\in [0\display x]:B[k]=q\$
$\mathbf {select} _{q}(x)=\min\{k\in [0\display n]:\mathbf {rank} _{q}(k)=x\$

$q\in \{0,1\}$ { $q\in \{0,1\}$ , $}$ { $display style$ q \ $in$ \ { $0$ , $1$ \ } $q\in \{0,1\}$ 。

즉, r $\mathbf {rank} _{q}(x)$ $\mathbf {rank} _{q}(x)$ q ( $\mathbf {rank} _{q}(x)$ ) _ ${displaystyle$ \ $mathbf {rank$ $}$ _ ${q}(x$ $)}$ 는 $\mathbf {rank} _{q}(x)$ $q$ $\mathbf {select} _{q}(x)$ x $(\displaystyle$ x $)$ 까지 $x$ q에 $q$ 하는 요소의 수를 반환하고 $\mathbf {select} _{q}(x)$ $\mathbf {select} _{q}(x)$ $\mathbf {select} _{q}(x)$ ( $)$ 는 x(\ $displaystyle$ $\mathbf {select}$ _ ${q})$ 의 $x$ 발생 $x$ 를 반환합니다 $.$ $q$ { $display style$ q $q$ } $。$

n $n+o(n)$ + $n+o(n)$ ( $n+o(n)$ n ) $n+o(n)$ \ $displaystyle$ n + $o$ ( $n$ ) of $n+o(n)$ space (공간(원래 비트 배열 및 $o(n)$ ( $o(n)$ n ) \ $displaystyle o$ ( n $o(n)$ )보조구조)를 $n+o(n)$ 하여 일정시간 랭크와 선택을 지원하는 간단한 표현이^[4] 있습니다.범위 최소 쿼리와 유사한 아이디어를 사용합니다. 제한된 크기의 하위 문제에서 중지되기 전에 반복 횟수가 일정합니다.비트 $배열$ B $(\displaystyle$ B $)$ 는 $B$ l $l=\lg ^{2}n$ 2 $l=\lg ^{2}n$ ${\displaystyle$ l=\ $lg ^{2}n$ 비트의 큰 블록과 s $=$ $s=\lg n/2$ (\ $displaystyle$ s=\ $lg n$ /2 $)$ $s=\lg n/2$ 의 $s=\lg n/2$ 작은 블록으로 분할됩니다.각 대형 블록에 대해 첫 번째 비트의 랭크는 별도의 $R_{l}[0\dots n/l)$ $R_{l}[0\dots n/l)$ l [ $R_{l}[0\dots n/l)$ $R_{l}[0\dots n/l)$ / $R_{l}[0\dots n/l)$ $(n/l)\lg n=n/\lg n$ ]({ $display style R_{l}$ [ 0 \ $dots n/$ $(n/l)\lg n=n/\lg n$ $R_{l}[0\dots n/l)$ 에 저장됩니다.이러한 엔트리는 $(n/l)\lg n=n/\lg n$ ${\$ $\lg n$ \ $display style$ \ $lg$ n $\lg n$ $n$ / $(n/l)\lg n=n/\lg n$ \ $display n =$ lg n / $lg$ \ display n / $lg$ $(n/l)\lg n=n/\lg n$ lg n / lg = lg \ display n / lg \ display $style$ n큰 블록 내의 다른 $R_{s}[0\dots l/s)$ $R_{s}[0\dots l/s)$ [ $R_{s}[0\dots l/s)$ $R_{s}[0\dots l/s)$ / $R_{s}[0\dots l/s)$ ]{ $displaystyle R_{s$ }[ $0\dots$ l/ $s]$ 에는 $R_{s}[0\dots l/s)$ 포함된 각 l $l/s=2\lg n$ $l/s=2\lg n$ $l/s=2\lg n$ lg † $l/s=2\lg n$ \ $displaystyle$ l $/s= 2\lg$ n $l/s=2\lg n$ } $l/s=2\lg n$ 의 $l/s=2\lg n$ 작은 블록의 순위가 저장됩니다.여기서의 차이는 lg $\lg l=\lg \lg ^{2}n=2\lg \lg n$ = lg $\lg l=\lg \lg ^{2}n=2\lg \lg n$ = $\lg l=\lg \lg ^{2}n=2\lg \lg n$ 2 $\lg l=\lg \lg ^{2}n=2\lg \lg n$ n $\lg l=\lg \lg ^{2}n=2\lg \lg n$ $\lg l=\lg \lg ^{2}n=2\lg \lg n$ lg $=$ $\lg l=\lg \lg ^{2}n=2\lg \lg n$ lg ⁡ $\lg l=\lg \lg ^{2}n=2\lg \lg n$ $\lg l=\lg \lg ^{2}n=2\lg \lg n$ { $displaystyle \lg$ l=\ $lg ^{2}n=2\lg$ \ $lg$ n $}$ 비트만 $\lg l=\lg \lg ^{2}n=2\lg \lg n$ $\lg l=\lg \lg ^{2}n=2\lg \lg n$ 하면 된다는 점입니다.따라서 이 표는 총 ( $(n/s)\lg l=4n\lg \lg n/\lg n$ $(n/s)\lg l=4n\lg \lg n/\lg n$ lg $(n/s)\lg l=4n\lg \lg n/\lg n$ $(n/s)\lg l=4n\lg \lg n/\lg n$ $(n/s)\lg l=4n\lg \lg n/\lg n$ $(n/s)\lg l=4n\lg \lg n/\lg n$ lg $(n/s)\lg l=4n\lg \lg n/\lg n$ n / $(n/s)\lg l=4n\lg \lg n/\lg n$ n / lg n ${\$ n \ $displaystyle$ ( $n/s$ )\ $lg$ l $(n/s)\lg l=4n\lg \lg n/\lg n$ = $4$ n / $lg$ n $(n/s)\lg l=4n\lg \lg n/\lg n$ 비트를 $(n/s)\lg l=4n\lg \lg n/\lg n$ 사용합니다.그런 다음 lg $i\in [0,s)$ [ $i\in [0,s)$ $]({$ $displaystyle$ i $\in [0,s$ 의 비트 문자열s(\ $displaystyle$ s $)$ 에 $s$ 가능한 모든 순위 쿼리에 대한 답변을 저장하는 룩업 $테이블$ $Rp(\$ $displaystyle$ R_ ${p})$ 를 $R_{p}$ 사용할 수 있습니다 $.$ 이 $R_{p}$ $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ lg $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ display n lg display n lg display n lg display n lg display n lg display n lg $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ display lg display lg display $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ display n lg display n display n $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ display n\ $lg$ n $)}$ 비트의 $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ 스토리지 공간 $.$ 따라서 이러한 보조 테이블은 각각 $o(n)$ ( $o(n)$ n )\ $displaystyle o$ ( n ) $o(n)$ 이므로 $o(n)$ 이 데이터 구조는 O $O(1)$ ( $)\displaystyle O ($ 1)타임 $O(1)$ $n+o(n)$ n + $n+o(n)$ ( $n+o(n)$ $)\displaystyle n$ + $o$ ( n )비트의 $O(1)$ 에서의 순위 쿼리를 지원합니다.

r $\mathbf {rank} _{1}(x)$ $\mathbf {rank} _{1}(x)$ ( $\mathbf {rank} _{1}(x)$ x $){displaystyle \mathbf {rank} _{1}(x)}$ 에 $\mathbf {rank} _{1}(x)$ $\mathbf {rank} _{1}(x)$ 쿼리에 일정 시간 응답하기 위해 정수 시간 알고리즘은 다음을 계산합니다.

$\mathbf {rank} _{1}(x)=R_{l}[\lfloor x/l\rfloor]+R_{s}[\lfloor x/s\rfloor,x{\text{mod }s}}$

실제로 룩업 $R_{p}$ $R_{p}$ ${$ $displaystyle R_{p}$ 은 $R_{p}$ 비트 연산 및 작은 블록에 설정된 비트 수를 찾는 데 사용할 수 있는 작은 테이블로 대체할 수 있습니다.간결한 데이터 구조가 대규모 데이터 세트에서 사용되기 때문에 캐시 누락이 훨씬 잦아지고 검색 테이블이 더 가까운 CPU 캐시에서 제거될 가능성이 ^[5]높아집니다.랭크에 사용되는 보조구조와 동일한 바이너리 검색을 실행하면 선택 쿼리를 쉽게 지원할 수 있지만 최악의 경우 O $O(\lg n)$ $O(\lg n)$ n $)\displaystyle$ O $(\lg$ n $)}$ 시간이 $O(\lg n)$ $O(\lg n)$ . $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ / $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ lg $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ n + $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ ( $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ lg $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ n $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ ( $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ ) $=$ o ( n ) { $display 3n$ / \ $lg$ \ $lg$ n + O ( { \ $sqrt$ { n $} }$ \ $lg n = o$ ( n )비트를 사용한 보다 복잡한 구조를 사용하여 일정 시간 ^[6]내에 선택할 수 있다.실제로 이러한 솔루션의 대부분은 점근적 이점이 $O(\cdot )$ 나타나기 전에 O $displaystyle$ O $(\cdot)$ $O(\cdot )$ 에 $O(\cdot )$ 숨겨진 상수를 가지고 있습니다.광대어 연산 및 단어 정렬 블록을 사용한 구현은 실제로 ^[7]더 나은 성능을 발휘하는 경우가 많습니다.

엔트로피 압축 사전

$n+o(n)$ + $n+o(n)$ ( $n+o(n)$ n ) $\textstyle {\binom {n}{m}}$ { $display style$ $\textstyle {\binom {n}{m}}$ n + $o$ ( $n+o(n)$ n )스페이스 어프로치는 [ $n]($ $또는$ 길이 n ${$ $display$ $style$ n $}{m})$ 의 $\textstyle {\binom {n}{m}}$ $[n)$ 구별되는 m{\ $display style$ m} - 서브셋이 $m$ $[n)$ [n](또는 $길이$ n{ $display style$ n $}$ 의 $n$ 이진 문자열)에 $정확히$ m {\display style n}이 $\textstyle {\binom {n}{m}}$ 있는 것에 주목함으로써 개선할 수 있습니다.} 1 $m$ 's)와 같이 $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ n $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ ) $=$ $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ ( $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ n $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ m ) $、$ \ $display style$ \ $textstyle$ { $B$ } ( m , n $)=\lceil$ \ $lg$ \ $binom$ { $n$ } { $m}$ \ $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ rceil $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ }는B를 $B$ 하는 데 필요한 비트 수에 대한 이론상 하한을 나타내는 $정보$ 입니다 $.$ ( $B$ ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ , ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ ) + ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ ( ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ ( ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ , ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ ) ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ { $displaystyle$ { $mathcal$ { $B }$ ( $m$ , $n$ ) + $o$ ( { \ $mathcal$ { $B$ } ( $m$ , $n$ ) } )^[8]스페이스 ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ 이 구조는 랭크 및 선택 쿼리를 지원하도록 ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ 할 수 있으며 B ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ ( ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ m , ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ ) + ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ ( ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ + ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ lg ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ lg ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ n / ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ n ) \ $display$ { $b }$ ( m , $n$ ) + $O$ ( $m$ + $n$ \ $lg$ n / $lg$ n )스페이스를 ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ 합니다.^[2]그러나 이 구조에서 올바른 순위 쿼리는 최소 완전 해시 함수의 작동 방식과 유사하게 집합에 포함된 요소로 제한됩니다.이 바운드는 사전의 저장 공간을 ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ ( ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ , n ) ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ + ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ ( ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ / ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ t ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ n + ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ 3 ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ / ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ ) ( \ $display$ { $mathcal$ { $B$ } （ $m$ , $n$ ） + $O$ ( $nt$ ^ { $t$ } / \ $lg$ ^ { $t$ } + n $^ 3$ / $4$ )로 ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ 줄임으로써 공간/ 시간 트레이드오프( )로 줄일 수 있습니다 $.$

예

Null 종단 문자열(C 문자열)은 Z + 1 공간을 차지하므로 암묵적입니다.임의의 길이(Pascal 문자열)의 문자열은 Z + log(Z) 공간을 차지하므로 간결합니다.2 = 4 GiB의 데이터가 매우 긴 문자열이고⁶⁴ 2 = 16 EiB의 데이터가 실제 문자열보다 크기 때문에³² 최대 길이가 있는 문자열이 있는 경우, 길이가 있는 문자열도 암묵적이며 여기서 k는 최대 길이를 나타내는 데이터 수(예: 64비트)입니다.

일련의 가변 길이 항목(문자열 등)을 부호화할 필요가 있는 경우는, 다양한 가능성이 있습니다.직접적 접근법은 길이와 항목을 각 레코드에 저장하는 것입니다. 그런 다음 이러한 항목을 차례로 배치할 수 있습니다.이를 통해 k번째 항목을 찾을 수 없지만 다음으로는 효율적입니다.다른 방법으로는 구분 기호(예: null-terminated 문자열)를 사용하여 항목을 정렬하는 것입니다.이 방법에서는 길이 대신 딜리미터가 사용되며 시퀀스 전체에서 딜리미터를 스캔해야 하므로 속도가 상당히 느립니다.둘 다 공간 효율적입니다.또 하나의 방법은 아웃오브밴드 분리입니다.구분자는 구분하지 않고 항목을 차례로 배치할 수 있습니다.그런 다음 항목 경계를 이 시퀀스에 길이 또는 더 나은 오프셋의 시퀀스로 저장할 수 있습니다.또는 항목이 시작되는 위치에 1s로 구성되고 다른 위치에 0s로 구성되는 별도의 이진 문자열이 항목과 함께 인코딩됩니다. $이$ 문자열을 지정하면 인덱스를 ^[10]지정하면 $각$ 항목이 어디에서 시작되는지 $빠르게$ 판단할 수 있습니다 $.$ 2Z 공간, 즉 O(Z)를 사용하기 때문에 콤팩트하지만 간결하지는 않습니다.

또 다른 예는 바이너리 트리의 표현입니다 $.$ n개의 \ $displaystyle$ $n노드상의$ 임의의 바이너리 트리는 $2n$ + $o$ n ) $2n+o(n)$ 표시할 수 $있습니다$ .또한 부모, 왼쪽 및 오른쪽 자식 찾기, 서브트리 크기 반환 등 임의의 노드에서 다양한 조작을 지원합니다.일정한 시간 안에n개 $노드$ 의 $서로$ 다른 바이너리트리 수는 ( $){displaystyle$ { $tbinom {2n}{n}}$ $/(n+1)$ / ( $/(n+1)$ $/(n+1)$ 1 $){displaystyle$ / ( $n+1$ 입니다 $.$ $큰$ n $(\displaystyle$ n $n$ 의 경우 약 $(\$ 4 $^{n$ 입니다.따라서 이를 인코딩하려면 로그 $\log _{2}(4^{n})=2n$ µ $\log _{2}(4^{n})=2n$ $=$ $(\display$ style $\log$ _ ${2$ }( $4^{n$ })= $2n}$ 가 $\log _{2}(4^{n})=2n$ 필요합니다.따라서 간결한 바이너리 트리는 노드당 $2비트$ 를 $2$ $차지합니다.$

「」를 참조해 주세요.

최소 완전 해시 함수

레퍼런스

^ Jacobson, G. J (1988). Succinct static data structures (Ph.D. thesis). Pittsburgh, PA: Carnegie Mellon University.
^ ^a ^b Raman, R.; V. Raman; S. S Rao (2002). "Succinct indexable dictionaries with applications to encoding k-ary trees and multisets". Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 233–242. arXiv:0705.0552. CiteSeerX 10.1.1.246.3123. doi:10.1145/1290672.1290680. ISBN 0-89871-513-X.
^ Sadakane, K.; R. Grossi (2006). "Squeezing succinct data structures into entropy bounds" (PDF). Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. pp. 1230–1239. ISBN 0-89871-605-5. Archived from the original (PDF) on 2011-09-29.
^ Jacobson, G. (1 November 1989). Space-efficient static trees and graphs (PDF). 30th IEEE Symposium on Foundations of Computer Science. doi:10.1109/SFCS.1989.63533. Archived from the original (PDF) on 2016-03-12.
^ González, R.; S. Grabowski; V. Mäkinen; G. Navarro (2005). "Practical implementation of rank and select queries" (PDF). Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). pp. 27–38.
^ Clark, David (1996). Compact pat trees (PDF) (Ph.D. thesis). University of Waterloo.
^ Vigna, S. (2008). Broadword implementation of rank/select queries (PDF). Experimental Algorithms. Lecture Notes in Computer Science. Vol. 5038. pp. 154–168. CiteSeerX 10.1.1.649.8950. doi:10.1007/978-3-540-68552-4_12. ISBN 978-3-540-68548-7.
^ Brodnik, A.; J. I Munro (1999). "Membership in constant time and almost-minimum space" (PDF). SIAM J. Comput. 28 (5): 1627–1640. CiteSeerX 10.1.1.530.9223. doi:10.1137/S0097539795294165.
^ Pătraşcu, M. (2008). "Succincter" (PDF). Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on. pp. 305–313.
^ Belazzougui, Djamal. "Hash, displace, and compress" (PDF).

[jacobson1988succinct-1] Jacobson, G. J (1988). Succinct static data structures (Ph.D. thesis). Pittsburgh, PA: Carnegie Mellon University.

[raman2002succinct-2] Raman, R.; V. Raman; S. S Rao (2002). "Succinct indexable dictionaries with applications to encoding k-ary trees and multisets". Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 233–242. arXiv:0705.0552. CiteSeerX 10.1.1.246.3123. doi:10.1145/1290672.1290680. ISBN 0-89871-513-X.

[sadakane2006squeezing-3] Sadakane, K.; R. Grossi (2006). "Squeezing succinct data structures into entropy bounds" (PDF). Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. pp. 1230–1239. ISBN 0-89871-605-5. Archived from the original (PDF) on 2011-09-29.

[jacobson1989space-4] Jacobson, G. (1 November 1989). Space-efficient static trees and graphs (PDF). 30th IEEE Symposium on Foundations of Computer Science. doi:10.1109/SFCS.1989.63533. Archived from the original (PDF) on 2016-03-12.

[gonzález2005practical-5] González, R.; S. Grabowski; V. Mäkinen; G. Navarro (2005). "Practical implementation of rank and select queries" (PDF). Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). pp. 27–38.

[clark1998compact-6] Clark, David (1996). Compact pat trees (PDF) (Ph.D. thesis). University of Waterloo.

[vigna2008broadword-7] Vigna, S. (2008). Broadword implementation of rank/select queries (PDF). Experimental Algorithms. Lecture Notes in Computer Science. Vol. 5038. pp. 154–168. CiteSeerX 10.1.1.649.8950. doi:10.1007/978-3-540-68552-4_12. ISBN 978-3-540-68548-7.

[brodnik1999membership-8] Brodnik, A.; J. I Munro (1999). "Membership in constant time and almost-minimum space" (PDF). SIAM J. Comput. 28 (5): 1627–1640. CiteSeerX 10.1.1.530.9223. doi:10.1137/S0097539795294165.

[patrascu2008succincter-9] Pătraşcu, M. (2008). "Succincter" (PDF). Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on. pp. 305–313.

[10] Belazzougui, Djamal. "Hash, displace, and compress" (PDF).

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[10]

Search

간결한 데이터 구조

네임스페이스

더

목차

간결한 사전

엔트로피 압축 사전

예

「」를 참조해 주세요.

레퍼런스

Search

간결한 데이터 구조

간결한 사전

엔트로피 압축 사전

예

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.