Local Database

Dekodowanie skrótów i prefiksów haszowych

Wszystkie listy są dostarczane przy użyciu specjalnego kodowania, aby zmniejszyć ich rozmiar. To kodowanie działa dzięki temu, że listy Bezpiecznego przeglądania Google zawierają teoretycznie zbiór hasz lub prefiksów hasz, które są statystycznie nie do odróżnienia od losowych liczb całkowitych. Gdybyśmy posortowali te liczby całkowite i obliczyli różnicę między sąsiednimi elementami, ta różnica byłaby w jakimś sensie „mała”. Kodowanie Golomb-Rice wykorzystuje tę niewielką wielkość.

Załóżmy, że 3 wyrażenia prefiksów ścieżki z sufiksem hosta, a mianowicie a.example.com/, b.example.com/ i y.example.com/, mają być przesyłane za pomocą 4-bajtowych prefiksów haszowanych. Załóżmy też, że parametr Rice’a, oznaczony jako k, ma wartość

1. Serwer najpierw oblicza pełny ciąg znaków dla tych ciągów, które są odpowiednio:

291bc5421f1cd54d99afcc55d166e2b9fe42447025895bf09dd41b2110a687dc  a.example.com/
1d32c5084a360e58f1b87109637a6810acad97a861a7769e8f1841410d2a960c  b.example.com/
f7a502e56e8b01c6dc242b35122683c9d25d07fb1f532d9853eb0ef3ff334f03  y.example.com/

Następnie serwer tworzy 4-bajtowe prefiksy skrótu dla każdego z tych elementów. Są to pierwsze 4 bajty 32-bajtowego pełnego skrótu interpretowanego jako 32-bitowa liczba całkowita w systemie big-endian. Wielkiendianizm odnosi się do faktu, że pierwszy bajt pełnego hasha staje się najbardziej znaczącym bajtem 32-bitowej liczby całkowitej. W wyniku tego kroku otrzymasz liczby całkowite 0x291bc542, 0x1d32c508 i 0xf7a502e5.

Serwer musi posortować te 3 prefiksy haszowane według alfabetu (co jest równoznaczne z sortowaniem numerycznym w systemie big endian). Wynikiem takiego sortowania jest 0x1d32c508, 0x291bc542, 0xf7a502e5. Pierwszy prefiks haszowany jest przechowywany w polu first_value bez zmian.

Następnie serwer oblicza 2 sąsiednie różnice, które wynoszą odpowiednio 0xbe9003a i 0xce893da3. Ponieważ k jest równe 30, serwer dzieli te 2 liczby na części iloraza i reszty, które mają odpowiednio 2 i 30 bitów. W przypadku pierwszego numeru część ilorazową jest 0, a pozostałość to 0xbe9003a; w przypadku drugiego numeru część ilorazową jest 3, ponieważ 2 najważniejsze bity w systemie dwójkowym to 11, a pozostałość to 0xe893da3. W przypadku danego ilorazu q jest on kodowany w wartości (1 << q) - 1 za pomocą dokładnie 1 + q bitów; reszta jest kodowana bezpośrednio za pomocą k bitów. Część iloraza pierwszego numeru jest zakodowana jako 0, a część reszty jest w formacie binarnym 001011111010010000000000111010; część iloraza drugiego numeru jest zakodowana jako 0111, a część reszty jest równa 001110100010010011110110100011.

Gdy te liczby zostaną utworzone w postaci ciągu bajtów, zostanie użyty format little-endian. Koncepcyjnie łatwiej sobie wyobrazić długi ciąg bitów tworzony od najmniej znaczących bitów: bierzemy część ilorazową pierwszego numeru i dołączamy do niego resztę pierwszego numeru; następnie dołączamy część ilorazową drugiego numeru i dołączamy resztę. Powinieneś otrzymać taką dużą liczbę (przerwy między wierszami i komentarze zostały dodane w celu ułatwienia zrozumienia):

001110100010010011110110100011 # Second number, remainder part
0111 # Second number, quotient part
001011111010010000000000111010 # First number, remainder part
0 # First number, quotient part

W jednym wierszu wyglądałoby to tak:

00111010001001001111011010001101110010111110100100000000001110100

Oczywiście liczba ta znacznie przekracza 8 bitów dostępnych w pojedynczym bajcie. Kodowanie little endian pobiera następnie 8 najmniej istotnych bitów tej liczby i wyprowadza je jako pierwszy bajt, który ma postać 01110100. Dla ułatwienia możemy podzielić powyższy ciąg bitów na grupy po 8 bitów, zaczynając od najmniej znaczących bitów:

0 01110100 01001001 11101101 00011011 10010111 11010010 00000000 01110100

Kodowanie little-endian pobiera każdy bajt z prawej strony i umieszcza go w ciągu bajtów:

01110100
00000000
11010010
10010111
00011011
11101101
01001001
01110100
00000000

Widać, że ponieważ nowe części są dodawane do dużej liczby po lewej stronie (czyli dodawane są kolejne znaczące bity), a kodowanie i dekodowanie odbywa się od prawej strony (czyli od najmniej znaczących bitów), kodowanie i dekodowanie może być wykonywane stopniowo.

W efekcie

additions_four_bytes {
  first_value: 489866504
  rice_parameter: 30
  entries_count: 2
  encoded_data: "t\000\322\227\033\355It\000"
}

Aby odkodować prefiksy skrótu, klient wykonuje opisane powyżej czynności w odwrotnej kolejności.

Dekodowanie indeksów usunięcia

Indeksy usuwania są kodowane tą samą metodą co powyżej, czyli za pomocą 32-bitowych liczb całkowitych.