Introduction to Information
Retrieval

Słownik termów i listy odwołań.
Parsowanie dokumentu



Jaki jest format?



pdf/word/excel/html?



Jaki jest język?



Jaki zbiór znaków jest użyty?

To są wszystko problemy klasyfikacji,
które będą omawiane później.

Ale te zadania są często wykonywane
heurystycznie …

Introduction to Information
Retrieval

Kompilacje: Format/język



Indeksowane dokumenty mogą zawierać

dokumenty w wielu różnych językach



Pojedynczy indeks może zawierać termy w kilku

językach.



Niekiedy dokument lub jego składowe mogą

zawierać wiele języków/formatów



Francuski email z niemieckim załącznikiem w pdf.



Co jest pojedynczym dokumentem?



Zbiór?



Email? (Być może jeden z wielu w skrzynce.)



Email z 5załącznikami?



Grupa zbiorów (PPT lub LaTeX jako strony HTML)

Introduction to Information
Retrieval

TOKENY I TERMY

Introduction to Information
Retrieval

Podział na tokeny



Input

: “Friends, Romans and

Countrymen”



Output

: Tokeny



Friends



Romans



Countrymen



Token

jest instancją sekwencji znaków



Każdy taki token jest teraz kandydatem na
wejście indeksu, po dalszym przetwarzaniu



Opis poniżej



Ale które tokeny są odpowiednie?

Introduction to Information
Retrieval

Podział na tokeny



Problemy z podziałem:



Finland’s capital



Finland? Finlands? Finland’s?



Hewlett-Packard  Hewlett i Packard

jako dwa tokeny?



state-of-the-art: rozbicie połączonej sekwencji.



co-education



lowercase, lower-case, lower case ?



To może być nieefektywne pozwolić użytkownikowi
wstawiać możliwe łączniki



San Francisco: jeden token czy dwa?



Jak podjąć decyzję, że to jeden token?

Introduction to Information
Retrieval

Liczby



3/20/91 Mar. 12, 1991 20/3/91



55 B.C.



B-52



My PGP key is 324a3df234cb23e



(800) 234-2333



Często mamy zagnieżdżone spacje



Starsze systemy IR nie mogły indeksować liczb



Ale czasem jest to bardzo wygodne: pomyślmy o
szukaniu kodów błędu/ścieżki webowe



(Odpowiedzią jest użycie n-gramów: później)



Będziemy często indeksować meta-dane oddzielnie



Opisy danych, format, itd.

Introduction to Information
Retrieval

Podział na tokeny: problemy
językowe



Francuski



L'ensemble  jeden token czy dwa?



L ? L’ ? Le ?



Czy l’ensemble ma odpowiadać un ensemble



Do 2003, nie było tego w Google



Międzynarodowość!



Niemieckie rzeczowniki złożone nie są dzielone



Lebensversicherungsgesellschaftsangestellter



‘pracownik firmy ubezpieczeń na życie’



Niemieckie systemy wyszukiwawcze najwięcej zyskują na
module compound splitter



Może być ok. 15% spadku wydajności dla niemieckiego

Introduction to Information
Retrieval

Podział na tokeny: problemy
językowe



Chiński i japoński nie mają spacji
między wyrazami:



莎莎莎莎莎莎莎莎莎莎莎莎莎莎莎莎莎莎莎莎



Nie zawsze jest gwarancja unikalnego
podziału na tokeny



Further complicated in Japanese, with
multiple alphabets intermingled



Daty/ilości w różnych formatach

フフフフフフ 500 フフフフフフフフフフフフフ $500K( フ 6,000 フフ )

Katakana Hiragana

Kanji Romaji

Użytkownik końcowy może całość wyrazić w hiragana!

Introduction to Information
Retrieval

Podział na tokeny: problemy
językowe



Arabski (lub hebrajski) są głównie pisane z
prawa na lewo, ale pewne elementy jak np.
liczby są pisane z lewa na prawo



Słowa są oddzielane, ale litery tworzą w słowach
skomplikowane zawijasy



← → ← → ←
start



‘Algeria odzyskała niepodległość w 1962 roku po
132 latach francuskiej okupacji.’



Kodowanie jest dość skomplikowane, ale postać w
pamieci jest prosta

Introduction to Information
Retrieval

Stop lista



Stop lista usuwa ze słownika słowa
pomocnicze. Intuicja:



Mają one małe znaczenia semantyczne: the, a, and, to, be



Jest ich dużo: ~30% odwołań dla 30 najczęstszych słów



Ale obecny trend to unikanie stop listy:



Dobre techniki kompresji powodują, że przestrzeń
potrzebna na stop listę jest bardzo mała (później)



Dobre techniki optymalizacji pytania pozwalają na krótki
czas przetwarzania stop listy (później).



Potrzebujemy te słowa dla:



Pytania o frazy: “King of Denmark”



Różne tytuły piosenek, itd.: “Let it be”, “To be or not to be”



“Pytania relacyjne”: “flights to London”

Introduction to Information
Retrieval

Normalizacja do termów



Musimy „normalizować” słowa w indeksowanych
tekstach do postaci takiej jak słowa w pytaniach



Musimy dopasować U.S.A. i USA



Rezultatem są termy :

term

jest

znormalizowanym typem słowa, który jest
wejściem do słownika w IR



Zwykle definiujemy klasy równoważności
termów, np.:



Skreślając kropki



U.S.A., USA

 USA



Skreślając łączniki



anti-discriminatory, antidiscriminatory

 antidiscriminatory

Introduction to Information
Retrieval

Normalizacja: różne języki



Akcenty: np.: francuski résumé i resume.



Umlauts: np.: niemiecki: Tuebingen i Tübingen



Muszą być równoważne



Najważniejsze kryterium:



Jak nasi użytkownicy lubią pisać pytania dla tych
słów?



Nawet dla języków które standardowo mają
akcenty użytkownicy często ich nie piszą



Niekiedy najlepiej znormalizować do termów bez
akcentów



Tuebingen, Tübingen, Tubingen  Tubingen

Introduction to Information
Retrieval

Normalizacja: różne języki



Normalizacja dla formatu daty



7 フ 30 フ vs. 7/30



Japończyk użyje kana vs. Chinese characters



Tokenizacja i normalizacja może zależeć od
języka i może to wymagać rozpoznania języka



Najważniejsze: musimy znormalizować
indeksowany tekst i termy pytania do tej
samej postaci

Morgen will ich in MIT …

Czy to niemieckie“

mit”?

Introduction to Information
Retrieval

Duże i małe litery



Redukujemy wszystkie litery do
małych



wyjątek: duże litery w środku zdania?



e.g., General Motors



Fed vs. fed



SAIL vs. sail



Często najlepiej używać małe litery
bo użytkownicy i tak piszą małymi…



Google example:



Query C.A.T.



#1 wynik jest dla “cat” (well,
Lolcats) not Caterpillar Inc.

Introduction to Information
Retrieval

Normalizacja do termów



Alternatywą dla klas równoważności jest
rozwiniecie asymetryczne



Przykład zastosowania



Enter: window

Search: window, windows



Enter: windows

Search: Windows, windows,

window



Enter: Windows

Search: Windows



Potencjalnie lepsze, ale mniej efektywne

Introduction to Information
Retrieval

Tezaurusy i soundex



Czy obsłużymy synonimy i homonimy?



Np.: dla klas równoważności



car = automobile color = colour



Możemy



Jeśli dokument zawiera automobile, indeksować go

car-automobile (i odwrotnie)



Lub możemy rozbudować pytanie



Jeśli pytanie zawiera automobile, szukać także car



Co z błędami spellingu?



Jednym z podejść jest soundex, tworzący klasy

równoważności oparte na heurystykach

fonetycznych



Więcej później

Introduction to Information
Retrieval

Lemmatization



Redukcja różnych form do form
podstawowych



Np.:



am, are, is  be



car, cars, car's, cars'  car



the boy's cars are different colors  the

boy car be different color



Lemmatization zakłada właściwą redukcję
do form słownikowych

Introduction to Information
Retrieval

Stemming



Redukcja termów do rdzeni przed
indeksowaniem



“Stemming” sugeruje obcinanie



Zależy od języka



np.: automate(s), automatic, automation
redukujemy do automat.

for example compressed
and compression are both
accepted as equivalent to
compress.

for exampl compress and
compress ar both accept
as equival to compress

Introduction to Information
Retrieval

Algorytm Portera



Powszechnie używany dla stemmingu
angielskiego



Wyniki pokazują że jest co najmniej tak dobry
jak inne algorytmy



Konwencje + 5 faz redukcji



Fazy są stosowane sekwencyjnie



Każda faza zawiera zbiór komend



Przykład konwencji: Z zasad w złożonej
komendzie wybierz tę, która się stosuje do
najdłuższej końcówki.

Introduction to Information
Retrieval

Typowe reguły Portera



sses  ss



ies  i



ational  ate



tional  tion



Wagi dla reguł zależnych od słów



(m>1) EMENT →



replacement → replac



cement → cement

Introduction to Information
Retrieval

Inne algorytmy stemmingu



Np.: Lovins stemmer



http://www.comp.lancs.ac.uk/computing/research/stemming/general/lovins.ht
m



Pojedyncze przejście, usuwanie najdłuższych
przyrostków (około 250 reguł)



Pełna analiza morfologiczna daje co najwyżej
wymierne korzyści dla wyszukiwania



Czy wykonywać stemming i inne normalizacje?



Angielski: bardzo różne efekty. Podnosi kompletność dla
pewnych pytań, ale psuje precyzję dla innych



Np.: operative (dentistry) ⇒ oper



Definitywnie użyteczne dla hiszpańskiego, niemieckiego,
fińskiego, …



30% wzrostu wydajności dla fińskiego!

Introduction to Information
Retrieval

Specyfika językowa



Wiele omawianych transformacji jest



Specyficznych dla języków i



Często też specyficznych dla aplikacji



Istnieją dodatki “plug-in” do procesu
indeksowania



Są dostępne plug-in open source i
komercyjne

Introduction to Information
Retrieval

Wejścia słownika – pierwsze
podejście

ensemble.french

フフ .

japanese

MIT.english

mit.german

guaranteed.english

entries.english

sometimes.english

tokenization.english

Można

grupować wg

języka (lub nie

…).

Wiecej przy

ranking/przetwa

-rzanie pytań.

Introduction to Information
Retrieval

SZYBSZE ŁĄCZENIE
WYSTĄPIEŃ:
SKIP WSKAŹNIKI/SKIP
LISTY

Introduction to Information
Retrieval

Przypomnienie podstawowego
łączenia



Przejdź przez dwie listy jednocześnie w
czasie liniowym od całkowitej liczby
wystąpień

128

Brutus

Caesar

Jeśli długości list to m i n, to łączenie wymaga O(m+n)
operacji.

Czy można lepiej?
Tak (jeśli indeks nie zmienia się zbyt szybko).

Introduction to Information
Retrieval

Zwiększanie wystąpień z
pomocą

skip pointers

(w czasie

indeksowania)



Dlaczego?



Aby pominąć wystąpienia które nie
figurują w wynikach wyszukiwania.



Jak?



Gdzie umieszczamy skip pointers?

128

Introduction to Information
Retrieval

Przetwarzanie pytań z użyciem

skip pointers

128

Przyjmijmy że przeszliśmy przez listy aż
przetworzyliśmy 8 na każdej liście. Dopasowaliśmy je i
idziemy dalej.

Mamy wtedy 41 i 11 na niższej. 11 jest mniejsze.

Ale następnik 11 na niższej liście to 31, więc pominąć
pośrednie wystąpienia.

Introduction to Information
Retrieval

Gdzie możemy umieścić
przeskoki?



Kompromis:



Więcej przeskoków  krótszy rozstaw

przeskoków  bardziej prawdopodobny

przeskok. Ale dużo porównań dla skip
pointers.



Mniej przeskoków  mało porównań

wskaźników, ale długie przeskoki  mniej

skutecznych przeskoków.

Introduction to Information
Retrieval

Umiejscowienie przeskoków



Prosta heurystyka: dla długości listy L, użyć L

równomiernie rozłożonych skip pointers.



To nie uwzględnia rozkładu termów w
pytaniach.



Dobrze jeśli indeks jest raczej statyczny; gorzej
jeśli L się zmienia ponieważ są aktualizacje.



To definitywnie zwykle pomaga; ale dla
nowoczesnego sprzętu nie zawsze (Bahle et al.
2002) chyba, że przetwarzamy w pamięci



Koszt ładowania I/O większej listy wystąpień może
przekroczyć zyski z szybszego łączenia w pamięci!

Introduction to Information
Retrieval

PYTANIA O FRAZY I

INDEKSY POZYCYJNE

Introduction to Information
Retrieval

Pytania o frazy



Chcemy odpowiadać na pytania takie jak
“stanford university” – jako fraza



Więc zdanie “I went to university at
Stanford” nie pasuje



Może to wchodzić w skład “advanced search” i
użytkownicy to akurat rozumieją



Wiele pytań to pośrednie pytania o frazę



Dlatego nie wystarczy pamiętać tylko

<term : docs> entries

Introduction to Information
Retrieval

Pierwsze podejście: indeksy z
parami słów



Indeksowanie każdej kolejnej pary termów
w tekście jako frazy



Np.: tkst “Friends, Romans, Countrymen”
może generować pary



friends romans



romans countrymen



Każda z tych par jest teraz termem w
słowniku



Przetwarzanie pytań -fraz z dwóch słów
jest teraz proste.

Introduction to Information
Retrieval

Pytania o dłuższe frazy



Dłuzsze frazy przetwarzamy jak wild-card:



stanford university palo alto można
podzielić na pary:

stanford university AND university palo

AND palo alto

Bez analizy dokumentów nie możemy ustalić

czy dokumenty pasujące do pytania
zawierają tę frazę.

Mogą być fałszywe odpowiedzi!

Introduction to Information
Retrieval

Poszerzone pary słów



Parsuj indeksowany tekst i utwórz wystąpienia wg

części mowy.



Połącz termy np. wg rzeczowników (N) i

przedimków/przyimków (X).



Nazwij każdy string termów w postaci NX*N

poszerzony biword.



Każdy taki poszerzony biword jest termem w

słowniku.



Np.: catcher in the rye

N X X N



Przetwarzanie pytań: parsuj do N-ek i X-ów



Podziel pytanie na ulepszone pary słów



Szukaj w indeksie: catcher rye

Introduction to Information
Retrieval

Problemy dla indeksów par
słów



Fałszywe wynik – jak poprzednio



Eksplozja indeksu ze względu na większy
słownik



Niemożliwe dla więcej niż par słów (np.: trójek)



Indeksy biword nie są standardowym
rozwiązaniem ale czasami są częścią
złożonej strategii

Introduction to Information
Retrieval

Rozwiązanie 2: indeksy
pozycyjne



W wystąpieniach pamiętaj dla każdego
termu pozycje na których jest jego token:

<term, liczba dokumentów zawierających term;
doc1: position1, position2 … ;
doc2: position1, position2 … ;
itd.>

Introduction to Information
Retrieval

Pytania z odległością



LIMIT! /3 STATUTE /3 FEDERAL /2 TORT



Ponownie tutaj /k znaczy “w k słowach”.



Oczywiście: pozycyjne indeksy mogą być
użyte dla takich pytań a indeksy biword
nie.

Introduction to Information
Retrieval

Rozmiar indeksu pozycyjnego



Możemy kompresować
wartość/przesunięcie: później



Jednak indeks pozycyjny zwiększa pamięć
istotnie



Mimo to indeks pozycyjny jest
standardowo używany ze względu na jego
moc i przydatność do frazowych pytań i
pytań z odległością … w systemach z
rankingiem.

Introduction to Information
Retrieval

Rozmiar indeksu pozycyjnego



Potrzebujemy wejście dla każdego
wystąpienia – nie tylko dla dokumentu



Rozmiar indeksu zależy od średniego
rozmiaru dokumentu



Średnia strona web ma <1000 termów



SEC filings, książki, nawet poematy … łatwo
100,000 terms



Rozpatrzmy częstość termów 0.1%

dlaczego?

100

100,000

1000

Wystąpienia

pozycji

Wystąpienia

Rozmiar dokumentu

Introduction to Information
Retrieval

Reguły kciuka



Pozycyjny indeks jest 2–4 większy niż
niepozycyjny indeks



Pozycyjny indeks ma 35–50% oryginalnego
tekstu



Ostrzeżenie: wszystko to jest prawdziwe
dla jezyków typu angielski

Introduction to Information
Retrieval

Schematy złożone



Te dwa podejścia mogą z pożytkiem połączone



Dla szczególnych fraz (“Michael Jackson”,
“Britney Spears”) jest nieefektywne
utrzymywanie list pozycyjnych



Tym bardziej dla fraz jak “The Who”



Williams et al. (2004) oceniają bardziej
skomplikowane mieszane schematy
indeksowania



Typowa mieszanka pytań webowych dla tych
skomplikowanych schematów potrzebowała ¼
czasu wymaganego dla indeksu pozycyjnego



Wymagała jednak 26% więcej pamięci niż dla
indeksu pozycyjnego

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 02

Document Outline