Introduction to Information
Retrieval

KOMPRESJA INDEKSU

Introduction to Information
Retrieval

Dlaczego kompresujemy
(ogólnie)?



Użycie mniejszej przestrzeni dyskowej



Oszczędzenie nieco pieniędzy



Trzymamy więcej rzeczy w pamięci



Wzrasta prędkość



Rośnie prędkość transferu danych z dysku do
pamięci



[czytanie skompresowanych danych |
dekompresja] jest szybsze niż [czytanie
nieskompresowanych danych]



Założenie: Algorytmy dekompresji są szybkie



Prawdziwe dla stosowanych tu algorytmów

Introduction to Information
Retrieval

Dlaczego kompresja dla
indeksów odwrotnych?



Słownik



Zmniejszenie ich do wielkości mieszczącej się w PO



Takie zmniejszenie aby jakieś listy wystąpień też
zmieściły się w PO



Zbiór (zbiory) wystąpień



Redukcja potrzebnej przestrzeni dyskowej



Zmniejszenie czasu potrzebnego do czytania list
wystąpień z dysku



Duże search engines trzymają znaczącą część listy
wystąpień w pamięci.



Kompresja pozwala trzymać więcej w pamięci



Omówimy różne specyficzne dla IR metody
kompresji

Introduction to Information
Retrieval

Przypomnienie kolekcji Reuters
RCV1



symbol statystyka wartość



N documents 800,000



L avg. # tokens per doc 200



M terms (= word types) ~400,000



avg. # bytes per token6

(incl. spaces/punct.)



avg. # bytes per token4.5

(without spaces/punct.)



avg. # bytes per term 7.5



non-positional postings
100,000,000

Introduction to Information
Retrieval

Parametry indeksu vs. co
indeksujemy

(szczegóły IIR Table 5.1,

p.80)

rozmiar

Typ słowo

(termy)

Wystąpienia

niepozycyjne

Wystąpienia

pozycyjne

dictionary

non-positional index positional index

Size

(K)

∆

cumul

Size (K)

∆

cumu

l %

Size (K) ∆

cumul

Unfiltered

484

109,971

197,87

No numbers

474

-2

-2 100,680

-8

179,15

-9

Case folding

392

-19

96,969

-3

-12

179,15

-9

stopwords

391

-0

-19

83,390

-24

121,85

-38

150

stopwords

391

-0

-19

67,002

-39

94,517

-52

stemming

322

-33

63,812

-4

-42

94,517

-52

Introduction to Information
Retrieval

Bezstratna vs. stratna
kompresja



Bezstratna kompresja: Cała informacja jest
zachowana.



To przeważnie stosujemy w IR.



Stratna kompresja: tracimy pewne informacje



Kilka kroków preprocesingu można uważać za
stratną kompresję: tylko małe litery, stop słowa,
stemming, eliminacja liczb.



Później: Przycinanie wejść do wystąpień
mających małe szanse być wśród k na początku
list odpowiedzi.



Prawie brak strat jakości dla k najwyższych
odpowiedzi.

Introduction to Information
Retrieval

Słownik vs. Rozmiar kolekcji



Jak duży jest słownik termów?



To znaczy ile różnych słów tam jest?



Czy możemy przyjąć górne ograniczenie?



W rzeczywistości nie: co najmniej 70

= 10

różnych słów o długości 20



W praktyce, słownik rośnie ze wzrostem
rozmiarów kolekcji

Introduction to Information
Retrieval

Słownik vs. Rozmiar kolekcji



Prawo Heapsa: M = kT



M to rozmiar słownika, T jest liczbą
tokenów w kolekcji



Typowe wartości: 30 ≤ k ≤ 100 i b ≈ 0.5



Na wykresie log-log rozmiaru słownika M
od T, prawo Heapsa przewiduje linię z
nachyleniem około ½



To jest najprostsza możliwa relacja między
dwiema wartościami w log-log przestrzeni



Empiryczne określenie (“empirycznego
prawa”)

Introduction to Information
Retrieval

Prawo Heapsa

Dla RCV1, linia kropkowana

log

M = 0.49 log

T + 1.64

jest najlepszym dop.

min

średni błąd kwadratowy.
Więc,

M = 10

1.64

0.49

k =

1.64

≈ 44 i b = 0.49.

Dobre empiryczne
dopasowanie dla Reuters
RCV1 !
Dla pierwszych 1,000,020
tokenów, prawo przewiduje
38,323 termów; aktualnie
jest, 38,365 termów

Introduction to Information
Retrieval

Prawo Zipfa



Prawo Heapsa podaje rozmiar słownika dla
kolekcji.



Badamy także względną częstość termów.



W językach naturalnych: jest bardzo mało
bardzo częstych słów i bardzo wiele bardzo
rzadkich słów.



Prawo Zipfa: i-ty najbardziej częsty term ma
częstość proporcjonalną do 1/i .



∝ 1/i = K/i gdzie K jest stałą normalizującą



jest częstością kolekcji: liczbą wystąpień

termu t

w kolekcji.

Introduction to Information
Retrieval

Konsekwencje prawa Zipfa



Jeśli najczęstszy term (the) wystąpi cf

razy



To drugi najczęstszy term (of) wystąpi cf

/2 razy



Trzeci najczęstszy (and) wystąpi cf

/3 razy …



Równoważnie: cf

= K/i gdzie K jest stałą

normalizującą, więc



log cf

= log K - log i



Liniowa zależność między log cf

i log i



To kolejne prawo potęgowe

Introduction to Information
Retrieval

Prawo Zipfa dla Reuters RCV1

Introduction to Information
Retrieval

Kompresja



Obecnie rozpatrzymy kompresję dla
słownika i wystąpień



Tylko dla podstawowego indeksu
boolowskiego



Bez studiowania pozycyjnych
indeksów, itd.



Rozpatrzymy schematy kompresji

Introduction to Information
Retrieval

KOMPRESJA SŁOWNIKA

Introduction to Information
Retrieval

Po co kompresować słownik?



Wyszukiwanie zaczyna się od słownika



Chcemy go trzymać w pamięci



Konkurowanie o pamięć z innymi
aplikacjami



Embedded/mobile urządzenia mogą mieć
bardzo mało pamięci



Nawet gdy słownik nie jest pamięci,
chcemy aby był mały dla szybszego
szukania



Więc kompresja słownika jest ważna

Introduction to Information
Retrieval

Pamięć słownika – pierwsze
cięcie



Tablice ze stałym rozmiarem wejść



~400,000 terms; 28 bytes/term = 11.2 MB.

Struktura wyszukiwawcza

słownika

20 bajtów 4 bajty każdy

Introduction to Information
Retrieval

Termy o ustalonej długości są
marnotrawstwem



Większość bajtów kolumnie Term jest
zmarnowanych – przypisujemy 20 bajtów dla
termów 1-literowych.



I ciagle nie możemy obsłużyć
supercalifragilisticexpialidocious lub
hydrochlorofluorocarbons.



Pisany angielski to średnio ~4.5
znaków/słowo.



Średnie słowo w słowniku angielskim: ~8
znaków



Jak możemy użyć ~8 znaków na term słownika?



Krótkie słowa dominują wśród tokenów.

Introduction to Information
Retrieval

Kompresowanie listy termów:
Słownik jako string

….systilesyzygeticsyzygialsyzygyszaibelyiteszczecinszomo….

Freq.

Postings ptr. Term ptr.

126

Całkowita długość łańcucha =

400K x 8B = 3.2MB

Wskaźniki potrzebne dla 3.2M

wystąpień: log

3.2M =

22bits = 3bytes



Pamiętaj słownik jako (długi) łańcuch znaków:



Wskaźnik do następnego słowa pokazuje

koniec bieżącego słowa



Nadzieja na oszczędzenie 60% poj. słownika.

Introduction to Information
Retrieval

Przestrzeń dla słownika jako
łańcucha



4 bajty na term dla Freq.



4 bajty na term dla wskaźnika do
wystąpień.



3 bajty na wskaźnik termu



Średnio 8 bajty na term w łańcuchu



400K termów x 19  7.6 MB (zamiast

11.2MB dla stałej długości)

 Teraz śr. 11

 bytes/term,

 nie 20.

Introduction to Information
Retrieval

Blokowanie



Pamiętaj wskaźniki do każdego kth
łańcucha termów.



Przykład poniżej: k=4.



Trzeba pamiętać długości termów (1
dodatkowy bajt)

….

systile

syzygetic

syzygial

syzygy

szaibelyite

szczecin

szomo….

Freq.

Postings ptr. Term ptr.

126

Oszczędzamy 9

 bajtów na 3
 wskaźnikach.

Tracimy 4 bajty na

długości termów.

Introduction to Information
Retrieval

Zysk netto



Przykład dla rozmiaru bloku k = 4



Gdy użyliśmy 3 bajtów/wskaźnik bez
blokowania



3 x 4 = 12 bajtów,

Teraz używamy 3 + 4 = 7 bajtów.

Wyrwaliśmy kolejne ~0.5MB. To redukuje
rozmiar słownika z 7.6 MB do 7.1 MB.
Możemy oszczędzić więcej dla większego k.

Dlaczego nie zwiększyć k?

Introduction to Information
Retrieval

Przeszukiwanie słownika bez bloków



Zakładając, że każdy
term słownika jest
jednakowo
prawdopodobny w
pytaniu (nie jest tak w
rzeczywistości!), średnia
liczba porównań =

(1+2∙2+4∙3+4)/8 ~2.6

Introduction to Information
Retrieval

Przeszukiwanie słownika z
blokami



Binarne szukanie do 4-termowych bloków;



Następnie liniowe szukanie termów blokach.



Bloki 4 termowe (drzewo binarne), średnio
=

(1+2∙2+2∙3+2∙4+5)/8 = 3 porównania

Introduction to Information
Retrieval

Kodowanie frontowe



kodowanie frontowe:



Sortowane słowa zwykle mają długie
przedrostki – pamiętaj tylko różnice



(dla ostatnich k-1 w bloku o długości k)

automata

automate

automatic

automati



automat*a

e

ic

io

koduje automat

Dodatkowa długość
poza automat.

Zaczyna przypominać ogólną kompresję łańcuchów.

Introduction to Information
Retrieval

Podsumowanie kompresji
słownika RCV1

Technika

Rozmiar w

Ustalona długość

11.2

Słownik jako łańcuch ze wskaźnikami
do każdego termu

7.6

To samo z blokowaniem k = 4

7.1

To samo z blokowaniem + kodowanie

frontowe

5.9

Introduction to Information
Retrieval

KOMPRESJA WYSTĄPIEŃ

Introduction to Information
Retrieval

Kompresja wystąpień



Zbiór wystąpień jest znacznie większy niż słownik,
co najmniej 10 razy.



Główna zasada: pamiętaj każde wystąpienie
zwięźle.



Wystąpienie dla naszych celów to docID.



Dla Reuters (800,000 dokumentów), możemy
użyć 32 bity na docID jeśli użyjemy 4-bajtowych
integer.



Alternatywnie, możemy użyć log

800,000 ≈ 20

bitów na docID.



Nasz cel: uzycie o wiele mniej niż 20 bitów na
docID.

Introduction to Information
Retrieval

Wystąpienia: dwie
przeciwstawne tendencje



Term taki jak arachnocentric zdarzy się
może raz na milion dokumentów –
możemy pamiętać to wystąpienie stosując
log

1M ~ 20 bits.



Term taki jak the zdarzy się w każdym
doc, więc 20 bitów/wystąpienie jest zbyt
drogie.



Preferowany jest wektor 0/1 w tym przypadku

Introduction to Information
Retrieval

Wejścia do zbioru wystąpień



Pamiętamy listę docs zawierających term
w rosnacym porządku docID.



computer: 33,47,154,159,202 …



Konsekwencja: wystarczy pamiętać
odstępy.



33,14,107,5,43 …



Nadzieja: wiekszość odstępów może być
kodowana/pamiętana na znacznie mniej
niż 20 bitach.

Introduction to Information
Retrieval

Trzy wejścia dla wystąpień

Introduction to Information
Retrieval

Kodowanie zmiennej długości



Cel:



Dla arachnocentric, użyjemy ~20 bitów/wejście
odstępu .



Dla the, użyjemy ~1 bit/wejście odstępu.



Jeśli średnii odstęp dla termu jest G, chcemy
użyć ~log

G bitów/wejście odstępu.



Główne wyzwanie: kodować każdy integer
(odstęp) za pomocą około tak małej liczby bitów
ile potrzeba dla tego integer.



To wymaga

kodowania zmiennej długości



Kodowanie zmiennej długości uzyskujemy przez
użycie krótkich kodów dla małych liczb

Introduction to Information
Retrieval

Kodowanie Variable Byte (VB)



Dla odstępu o wartości G, chcemy użyć najmniej
bajtów potrzebnych do pamiętania log

G bitów



Zaczynamy od jednego bajtu do pamiętania G i
poświęcamy 1 bit jako kontynuacyjny bit c



Jeśli G ≤127, koduj binarnie na 7 dostępnych
bitach i ustaw c =1



W przeciwnym przypadku koduj G’s mniej
znaczących 7 bitów i następnie użyj
dodatkowych bajtów do kodowania bardziej
znaczących bitów stosując ten sam algorytm



Na koniec ustaw kontynuacyjny bit w ostatnim
bajcie na 1 (c =1) – a dla pozostałych bajtów c
= 0.

Introduction to Information
Retrieval

Przykład

docIDs

824

829

215406

odstępy

214577

kodowanieVB

00000110

10111000

10000101

00001101

00001100

10110001

Odwołania pamiętane jako konkatenancja bajtów

000001101011100010000101000011010000110010110001

Kluczowa własność: VB-kodowane wystąpienia są
jednoznacznie dekodowalne metodą prefiksową.

Dla małych odstępów (5),
VB używa całych bajtów.

Introduction to Information
Retrieval

Inne zmienne kody
jednostkowe



Zamiast bajtów, możemy także użyć inne
“jednostki przypisania”: 32 bitowe (words), 16 bits,
4 bits (nibbles).



Zmienne bajtowe przypisania pojemność jeśli
mamy wiele małych odstępów – nibbles są wtedy
lepsze.



Kodowane zmienno bajtowe:



Używane przez wiele komercyjnych/naukowych
systemów



Dobre do kodowania zmiennej długości i dobre do
porównań (vs. Kodowanie na poziomie bitów - później).



Są też niedawne prace na temat pakowania
zmiennej liczby odstępów do jednego słowa

Introduction to Information
Retrieval

Kod jedynkowy



Przedstaw n jako n jedynek z końcowym zerem.



Jedynkowy kod dla 3 to 1110.



Jedynkowy kod dla 40 to

111111111111111111111111111111111111111

10 .



Jedynkowy kod dla 80 to:

111111111111111111111111111111111111111

1111111111111111111111111111111111111
11110



Nie wyglada to obiecująco, ale….

Introduction to Information
Retrieval

Kody Gamma



Możemy dobrze kompresować na poziomie bitów



Kod Gamma jest najlepszy ze znanych.



Przedstaw odstęp G jako parę długość i offset



offset to G binarnie, z początkowym bitem
usuniętym



Np.: 13 → 1101 → 101



długość to długość przesunięcia (offsetu)



Dla 13 (offset 101), to jest 3.



Kodujemy długość kodem jedynkowym: 1110.



Gamma kod dla 13 to konkatenancja długości i
offset: 1110101

Introduction to Information
Retrieval

Gamma code examples

number

length

offset

-code

none

10,0

10,1

110

110,00

1110

001

1110,001

1110

101

1110,101

11110

1000

11110,1000

511

111111110

11111111

111111110,11111111

1025

11111111110 000000000

11111111110,000000000

Introduction to Information
Retrieval

Własności kodu Gamma



G jest kodowane z użyciem 2 log G + 1 bitów



Długość offsetu jest log G bitów



Zakodowanie długości wymaga log G + 1 bitów



Wszystkie kody gamma nieparzystą liczbę
bitów



Prawie zawsze ze współczynnikiem 2 najlepsze
możliwe, log



Kod gamma jest jednoznacznie dekodowalny
przedrostkowo, jak VB



Kod gamma może być stosowany dla
dowolnego rozkładu



Kod gamma nie ma parametrów

Introduction to Information
Retrieval

Gamma jest praktyczne rzadko
używany



Maszyny mają długości słów – 8, 16, 32, 64
bitów



Operacje, które działają na różnych słowach są
wolniejsze



Kompresja i manipulowanie na poziomie bitów
może być wolna



Kodowanie zmienno bajtowe jest bardziej
dopasowane a więc potencjalnie efektywniejsze



Pominąwszy efektywność, zmienne bity są
koncepcyjnie prostsze a wzrost pamięci jest
niewielki

Introduction to Information
Retrieval

Kompresja RCV1

Struktura danych

Rozmiar

w MB

słownik, ustalona długość

11.2

słownik, wskaźniki termów w łańcuchu

7.6

Z blokowaniem, k = 4

7.1

Z blokowaniem & kodowaniem frontowym

5.9

Kolekcja (text, xml markup itd)

3,600.0

Kolekcja (text)

960.0

Term-doc macierz incydencji

40,000.0

wystąpienia, bez kompresji (32-bit words)

400.0

wystąpienia, bez kompresji (20 bits)

250.0

wystąpienia, kodowanie zmienno bajtowe

116.0

wystąpienia, kodowanie

101.0

Introduction to Information
Retrieval

Kompresja indeksu -
podsumowanie



Możemy zbudować indeks dla bardzo
efektywnego wyszukiwania boolowskiego z
bardzo różną efektywnością użycia pamięci



Tylko 4% całego rozmiaru kolekcji



Tylko 10-15% całkowitego rozmiaru text w
kolekcji



Jednak zignorowaliśmy informację o
pozycjach



Więc oszczędność pamięci dyskowej jest
mniejsza w praktyce



Ale stosowane techniki są w zasadzie takie same.

Document Outline

Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38
Slide 39
Slide 40
Slide 41

Sys Inf 03 Manning w 05

Document Outline