EliasFano符号

EliasFano 10th StringBeginners → Kanda → K and A → K & A → K ampersand A →

⟫ × n × i.e., S[i-1] ≤ S[i] for each 0 < i < n S[0,n) ⟫ × Access / Predecessor / Successor × Predecessor(10) = 7 S Access(4) = 42 Successor(43) = 44 0 1 2 3 4 5 6 7 2 7 18 28 42 43 44 59 2

log EliasFano log $ S 2 0 7 18 n=8 0 28 42 100 43 010 000 111 1 010 010 1 011 100 101 010 101 011 101 100 111 011 3 0 44 59 000 2 001 110 u 2 0 1 1 0 3 1 0 1 log ( H = 110 0 10 10 0 1110 0 10 ( L = 010 111 010 100 010 011 100 011 % & ) ) 3

2" + " log S ' ( 0 1 2 3 4 5 6 7 2 7 18 28 42 43 44 59 ) log " EliasFano L = 010 111 010 100 010 011 100 011 H = 110 0 10 10 0 1110 0 10 " ' " log ( 2" 2 *+, ( ≈ " 4

2" + " log [0,u) ⟫ ' ( n (i.e. n u 2 45 S 2 4 5 8 ) 89 0010110011 9 ' ( log ' ( 5

2" + " log [0,u) ⟫ ' ( n n u+n 2 S 2 4 4 5 8 8 9 0010011010001010 9 ( log 44 5 ')( ( ) ≈ " log ')( ( ')( ( Less than half a bit per element away (Quasi-succinct) 6

O(1) ⟫ Access(i) = S[i] ⟫ Predecessor(x) = max{S[i] : S[i] ≤ x} ⟫ Successor(x) = min{S[i] : S[i] > x} $ O(log ) % Access(4) = 42 S 0 1 2 3 4 5 6 7 2 7 18 28 42 43 44 59 Predecessor(10) = 7 Successor(43) = 44 7

Access ⟫ O(1) Access(4) = 42 = 101 0102 ① !"# $ % i L = 010 111 010 100 010 011 100 011 ② !"# % Select1(i) – i H = 110 0 10 10 0 1110 0 10 Select1(4) – 4 = 9 – 4 = 5 = 1012 H Select Selectb(H, i) H i o(n) b 8

$ Successor O(log ) % Successor(43) = 44 = 101 1002 5 101 0112 ⟫ ① &'( * Select Select0(4) = 8 Select0(5) = 12 H = 110 0 10 10 0 1110 0 10 3 × (Select0(4) – 4) = 12 3 × (Select0(5) – 5) = 21 L = 010 111 010 100 010 011 100 011 log $ % =3 ② ) * O(&'( ) 9

EliasFano ⟫ × × × TRIE × 0 a t e 1 t 2 a 5 4 8 t 6 e 9 a c 3 7 c 10 10