Tutaj jest informacja o kodowaniu z Polski którego ponoć używa Apple, Facebook i Google: ... nia-swiat/
Na Wikipedii ( ... al_Systems ) zaczyna się od najprostszego "wariantu uABS", którym chyba można bezpośrednio kodować kombinacje:
Kodowanie symbolu s o prawdopodobieństwie o Pr(s=1)=p do liczby x:
if s = 0 then x = ceil((x+1)/(1-p)) - 1
if s = 1 then x = floor(x/p)
Dekodowanie s:
s = ceil((x+1)*p) - ceil(x*p) // 0 if fract(x*p) < 1-p, else 1
if s = 0 then x = x - ceil(x*p)
if s = 1 then x = ceil(x*p)
Dla p=1/2 dostajemy właściwie zwykły system dwójkowy, s ląduje na ostatnim bicie.
Natomiast dla innych prawdopodobieństw p też rzeczywiście działa - dekodowanie odwraca kodowanie nawet dla dużych liczb x, ale jest wyraźna asymetria między s=0 i s=1.
Jednak kolejne warianty są bardziej skomplikowane i materiały są chyba tylko po angielsku - może ktoś mógłby to na spokojnie wytłumaczyć?-- 9 lip 2017, o 18:10 --Poniżej jest prosty program w Mathematice który generuje wszystkie kombinacje (n, k) i koduje je powyższym uABS i zwykłym dwójkowym - po kombinacji jest liczba naturalna kodująca w uABS, potem standardowo binarnie.
Niekoniecznie uABS daje mniejszy kod, ale średnio rzeczywiście jest lepszy - dolny wiersz zawiera sumę logarytmów wszystkich kodów.
Asymptotycznie ta średnia powinna być entropią Shannona (h[k/n]), tutaj jest ciut gorzej, ale poprawia się dla większych wartości.
Ciekawe czy da się uogólnić tą metodę dla przypadku więcej niż 2 symboli?
Coś takiego robi wariant rANS, ale w dużo bardziej brutalny sposób.
h[p_] := -p*Log[2., p] - (1 - p) Log[2., 1 - p];
k = 2; n = 9; mx = Binomial[n, k]; p = k/n; sx = sy = 0.;
Print[mx, " kombinacji, ", h[p], " bitów na symbol"];
Do[l = k;
t = Table[b = Binomial[n - i, l]; If[v < b, 0, v -= b; l--; 1], {i, n}]; (* generuj kombinację nr v *)
x = y = 1; Do[y = 2 y + t[], {i, n}]; (* koduj binarnie *)
Do[ x = If[t[] == 0, Ceiling[(x + 1)/(1 - p)] - 1, Floor[x/p]], {i, n}]; (* koduj uABS *)
Print[Row[t], " ", x, " ", y]; sx += Log[2, x]; sy += Log[2, y] , {v, 0, mx - 1}];
Print[sx/mx/n, " ", sy/mx/n]
36 kombinacji, 0.764205 bitów na symbol
000000011 382 515
000000101 369 517
000000110 365 518
000001001 346 521
000001010 341 522
000001100 335 524
000010001 310 529
000010010 307 530
000010100 305 532
000011000 298 536
000100001 292 545
000100010 290 546
000100100 285 548
000101000 280 552
000110000 275 560
001000001 229 577
001000010 226 578
001000100 224 580
001001000 222 584
001010000 212 592
001100000 208 608
010000001 216 641
010000010 214 642
010000100 210 644
010001000 204 648
010010000 200 656
010100000 196 672
011000000 190 704
100000001 153 769
100000010 151 770
100000100 150 772
100001000 146 776
100010000 138 784
100100000 132 800
101000000 131 832
110000000 119 896
0.870422 1.02995
ps. temat znowu trafił na główną na Wykopie: https://www.wykop.pl/link/3818701/googl ... na-reddit/