Title

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

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

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

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ń



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

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