2018-11-04
((resource:IMG_20181104_113322__01.jpg|Resource Description for IMG_20181104_113322__01.jpg))
((resource:IMG_20181104_113328__01.jpg|Resource Description for IMG_20181104_113328__01.jpg))
((resource:IMG_20181104_113336__01.jpg|Resource Description for IMG_20181104_113336__01.jpg))
Consider the posting list [89, 101, 112, 122, 130, 145]. Suppose the corpus size is 200 documents. Compute
(a) Δ-list
(12, 11, 10, 8, 15)
(b) a γ-code
(0000 1100, 0000 1011, 0000 1010, 000 100, 0000 1111)
(c) Golumb-code
N_t = 6, N = 200
M = (log(1.97))/(-log(0.97))
M = (0.978)/(0.044)
M = 22.23
use M=23
So for
k = 12, q(k) = 0, r(k) = 11, 01 1011
k = 11, q(k) = 0, r(k) = 10, 01 1010
k = 10, q(k) = 0, r(k) = 9, 01 101
k = 8, q(k) = 0, r(k) = 8, 01 100
k = 15, q(k) = 0, r(k) = 14, 01 1110
Consider the posting list [89, 101, 112, 122, 130, 145]. Suppose the corpus size is 200 documents. Compute
(a) Δ-list
(12, 11, 10, 8, 15)
(b) a γ-code
(0000 1100, 0000 1011, 0000 1010, 000 100, 0000 1111)
(c) Golumb-code
N_t = 6, N = 200
M = (log(1.97))/(-log(0.97))
M = (0.978)/(0.044)
M = 22.23
use M=23
So for
k = 12, q(k) = 0, r(k) = 11, 01 1011
k = 11, q(k) = 0, r(k) = 10, 01 1010
k = 10, q(k) = 0, r(k) = 9, 01 101
k = 8, q(k) = 0, r(k) = 8, 01 100
k = 15, q(k) = 0, r(k) = 14, 01 1110
Given posting list = [89,101,112,122,130,145]
a) gap list = [89,12,11,10,8,15]
b) γ-code
γ(89) = 0000001011001 γ(12) = 0001100 γ(11) = 0001011 γ(10) = 0001010 γ(8) = 0001000 γ(15) = 0001111
c) Golomb code : Optimal M value = log(2-6/200)/-log(1-6/200)
log(1.97)/-log(0.97) = 0.978/0.043 = 22.55 => [ceiling of 22.55] => 23
M = 23
Given posting list = [89,101,112,122,130,145]
a) gap list = [89,12,11,10,8,15]
b) γ-code
<pre>
γ(89) = 0000001011001
γ(12) = 0001100
γ(11) = 0001011
γ(10) = 0001010
γ(8) = 0001000
γ(15) = 0001111
</pre>
c) Golomb code : Optimal M value = log(2-6/200)/-log(1-6/200)
log(1.97)/-log(0.97) = 0.978/0.043 = 22.55 => [ceiling of 22.55] => 23
M = 23
((resource:IMG-6821.jpg|Resource Description for IMG-6821.jpg))
((resource:IMG-6822.jpg|Resource Description for IMG-6822.jpg))
a) Δ-list = [89, 12, 11, 10, 8, 15] b) γ-code = [0000001 011001, 0001 100, 0001 011, 0001 010, 0001 000, 0001 111] c) Golumb-code N_t=6, N=200 M_opt=[log(2-N_T/N)/-log(1-N_T/N)], M=22.26 use M=23. q(k)=(k-1)/M, r(k)=(k-1) mod M
| k | q(k) | r(k) | Q(k+1) in unary followed by r(k) in binary |
|---|---|---|---|
| 89 | 3 | 19 | 0001 10011 |
| 12 | 0 | 11 | 1 1011 |
| 11 | 0 | 10 | 1 1010 |
| 10 | 0 | 9 | 1 1001 |
| 8 | 0 | 7 | 1 1111 |
| 15 | 0 | 14 | 1 1110 |
<pre>
a) Δ-list = [89, 12, 11, 10, 8, 15]
b) γ-code = [0000001 011001, 0001 100, 0001 011, 0001 010, 0001 000, 0001 111]
c) Golumb-code N_t=6, N=200 M_opt=[log(2-N_T/N)/-log(1-N_T/N)], M=22.26 use M=23.
q(k)=(k-1)/M, r(k)=(k-1) mod M
</pre>
{|
|-
! k !! q(k) !! r(k) !! Q(k+1) in unary followed by r(k) in binary
|-
| 89|| 3 || 19 || 0001 10011
|-
| 12|| 0 || 11 || 1 1011
|-
| 11|| 0 || 10 || 1 1010
|-
| 10|| 0 || 9 || 1 1001
|-
| 8 || 0 || 7 || 1 1111
|-
| 15|| 0 || 14 || 1 1110
|}
Golomb code = 000110011 11011 11010 11001 11111 11110
a) <Δ> list = < 89,12,11,10,8,15>`ceil(log(2 - Nt/N) / -log(1-Nt/N))` = `ceil(log(2- 6/200)/-log(1 - 6/200))` = `ceil( 0.678/0.03)` = ceil(22.6) = 23
b) <Γ> code = < 0000001 011001, 0001 100, 0001 011, 0001 010, 0001 000, 0001 111>
c) Mopt =
(here log base is taken as 10 and not 2, as only rice code uses base 2)
To find Golomb code:
for each k, q(k) = ⌊k−1/M⌋,r(k)=(k−1)modM; q(k)+1 in unary followed by r(k) as a ⌊log(M)⌋ bit or ⌈log(M)⌉ bit number
89 => ⌊89−1/23⌋ (89−1)mod23 = 3+1, 19 => {0001, 10011}
12 => ⌊12−1/23⌋,r(k)=(12−1)mod23 = 0+1, 11 => {1, 01011}
11 => ⌊11−1/23⌋,r(k)=(11−1)mod23 = 0+1, 10 => {1, 01010}
10 => ⌊10−1/23⌋,r(k)=(10−1)mod23 = 0+1, 9 => {1, 01001}
8 => ⌊8−1/23⌋,r(k)=(8−1)mod23 = 0+1, 7 => {1, 00111}
15 => ⌊15−1/23⌋,r(k)=(15−1)mod23 = 0+1, 14 => {1, 01110}
Goloumb code = 000110011, 101011, 101010, 101001, 100111 ,101110
(Edited: 2018-11-05) <pre>
a) <Δ> list = < 89,12,11,10,8,15>
<br/>
b) <Γ> code = < 0000001 011001, 0001 100, 0001 011, 0001 010, 0001 000, 0001 111>
<br/>
c) Mopt =
</pre>
@BT@ceil(log(2 - Nt/N) / -log(1-Nt/N))@BT@ = @BT@ceil(log(2- 6/200)/-log(1 - 6/200))@BT@ = @BT@ceil( 0.678/0.03)@BT@ = ceil(22.6) = 23
<pre>
(here log base is taken as 10 and not 2, as only rice code uses base 2)
To find Golomb code:
for each k, q(k) = ⌊k−1/M⌋,r(k)=(k−1)modM; q(k)+1 in unary followed by r(k) as a ⌊log(M)⌋ bit or ⌈log(M)⌉ bit number
89 => ⌊89−1/23⌋ (89−1)mod23 = 3+1, 19 => {0001, 10011}
12 => ⌊12−1/23⌋,r(k)=(12−1)mod23 = 0+1, 11 => {1, 01011}
11 => ⌊11−1/23⌋,r(k)=(11−1)mod23 = 0+1, 10 => {1, 01010}
10 => ⌊10−1/23⌋,r(k)=(10−1)mod23 = 0+1, 9 => {1, 01001}
8 => ⌊8−1/23⌋,r(k)=(8−1)mod23 = 0+1, 7 => {1, 00111}
15 => ⌊15−1/23⌋,r(k)=(15−1)mod23 = 0+1, 14 => {1, 01110}
Goloumb code = 000110011, 101011, 101010, 101001, 100111 ,101110
</pre>
((resource:20181105_110946.jpg|Resource Description for 20181105_110946.jpg))
(c) 2024 Yioop - PHP Search Engine