Title

Introduction to Information
Retrieval

Słowniki i wyszukiwanie
tolerancyjne

Introduction to Information
Retrieval

Struktury danych słowników

dla indeksów odwrotnych



Pamiętają termy słownika, częstość
dokumentów, wskaźniki do każdej listy
wystąpień …

w jakiej strukturze danych?

Introduction to Information
Retrieval

Naiwny słownik



Jako tablica:

char[20] int Postings *

20 bajtów 4/8 bytes 4/8 bajtów



Jak pamiętać słownik efektywnie?



Jak możemy szybko przeglądać elementy w trakcie
przetwarzania pytania?

Introduction to Information
Retrieval

Struktury danych dla
słowników



Dwie główne możliwości:



Tablice haszujące



Drzewa



Jedne systemy IR używają tablice
haszujące, inne drzewa

Introduction to Information
Retrieval

Haszowanie



Każdy term słownika jest haszowany na liczbę
całkowitą



(Zakładamy, że wiecie coś o haszowaniu)



Szanse:



Przeszukiwanie jest szybsze niż dla drzew: O(1)



Ograniczenia:



Nie łatwo znaleźć najmniejszy warint:



judgment/judgement



Nie ma szukania przedrostków

[szukanie

tolerancyjne]



Jeżeli słownik szybko rośnie, potrzeba drogiej
operacji ponownego haszowania całości

Introduction to Information
Retrieval

Root

a-m

n-z

a-hu

hy-m

n-sh

si-z

Drzewo: drzewo binarne

Introduction to Information
Retrieval

Drzewo: B-drzewo



Defininicja: Każdy wewnętrzny węzeł ma
pewną liczbę dzieci w przedziale [a,b], gdzie a,
b to określone liczby naturalne, np.: [2,4].

a-hu

hy-m

n-z

Introduction to Information
Retrieval

Drzewa



Najprostsze: drzewo binarne



Częściej: B-drzewo



Drzewa wymagają standardowego uporządkowania
znaków a więc i ciągów … ale to mamy



Szanse:



Rozwiązuje problem przedrostków (termy
zaczynąjace się od hyp)



Ograniczenia:



Wolniejsze: O(log M) [i to wymaga

zrównoważonego

drzewa]



Ponowne równoważenie drzew binarnych jest
kosztowne



Ale B-drzewa łagodzą ten problem

Introduction to Information
Retrieval

Pytania z dziką kartą: *



mon*: znajdź wszystkie dokumenty
zawierające jakieś słowa zaczynające się od
“mon”.



Łatwe dla leksykonu będącego binarnym
drzewem (lub B-drzewem): wyszukaj
wszystkie słowa z zakresu: mon ≤ w < moo



*mon: znalezienie słów kończących się
“mon”: trudniejsze



Utrzymywanie dodatkowego B-drzewa dla
termów do tyłu.

Możemy wyszukać wszystkie słowa z zakresu: nom

≤ w < non.

Introduction to Information
Retrieval

Przetwarzanie pytań



Teraz mamy określone wszystkie termy,
które pasują do pytania z dziką kartą.



Ciągle jeszcze musimy wyszukać
wystąpienia dla każdego ze znalezionych
termów.



Np.: rozważmy pytanie:
se*ate AND fil*er
To może skutkować przetworzeniem wielu
boolowskich pytań AND.

Introduction to Information
Retrieval

Obsługa B-drzewami pytań z
termami z * na końcu



Jak możemy przetworzyć * w środku termu
pytania?



co*tion



Możemy wyszukać co* AND *tion w B-
drzewie i zrobić przecięcie tych dwóch
zbiorów termów



Drogie



Rozwiązanie: przekształć pytania z dziką
kartą tak aby * występowała na końcu



To przenosi nas do indeksu

permutacyjnego (Permuterm

Index).

Introduction to Information
Retrieval

Indeks permutacyjny



Dla termu hello, indeks:



hello$, ello$h, llo$he, lo$hel, o$hell

Gdzie: $ to symbol specjalny.



Pytania:



X szukaj dla X$ X* szukaj dla $X*



*X szukaj dla X$*

*X* szukaj dla X*



X*Y szukaj dla Y$X* X*Y*Z

Pytanie = hel*o

X=hel, Y=o

Szukaj o$hel*

Introduction to Information
Retrieval

Permutacyjne przetwarzanie
pytań



Przesuwaj dziką kartę na prawo



Następnie stosuj przeglądanie B-drzewa
jak poprzednio.



Permuterm problem: ≈ Rozmiar leksykonu
podniesiony do kwadratu

Empiryczna obserwacja dla

języka angielskiego.

Introduction to Information
Retrieval

Indeksy bigram (k-gram)



Wylicz wszystkie k-gramy (sekwencje k
znaków) występujące w każdym termie



Np.: z tekstu “April is the cruelest
month” otrzymujemy 2-gramy (bigramy)



$ to specjalny symbol graniczny słowa



Utrzymuj drugi indeks odwrotny od
bigramów do termów słownika, który
pasuje do każdego bigramu.

$a,ap,pr,ri,il,l$,$i,is,s$,$t,th,he,e$,$c,cr,ru,
ue,el,le,es,st,t$, $m,mo,on,nt,h$

Introduction to Information
Retrieval

Przykład indeksu bigramu



k-gram indeks znajduje termy opierając
się na pytaniu zawierające k-gramy (tutaj
k=2).

among

mace

among

amortize

madden

around

Introduction to Information
Retrieval

Przetwarzanie dzikich kart



Pytanie mon* może być przetwarzane teraz jako



$m AND mo AND on



Daje termy które pasują do wersji AND naszego
pytania z dziką kartą.



Ale wymieniliśmy moon.



Musimy przefiltrować te termy względem pytania.



Te z wymienionych termów, które zostały są
następnie z indeksu odwrotnego term-dokument.



Szybkie, efektywne pamięciowo (w porównaniu do
permuterm).

Introduction to Information
Retrieval

Przetwarzanie pytań z dziką
kartą



Jak poprzednio, musimy przetworzyć pytanie
boolowskie dla każdego wymienionego,
odfiltrowanego termu.



Dzikie karty powodują drogie przetwarzanie pytań
(bardzo duże dysjunkcje…)



pyth* AND prog*



Jeśli zachęcimy “leniwych” ludzi to odpowiedzą!

Type your search terms, use ‘*’ if you need to.
E.g., Alex* will match Alexander. Niektóre wyszukiwarki –
w zaawansowanych bo mało kto zagląda.

Introduction to Information
Retrieval

Korekta spellingu



Dwa główne podejścia



Korekcja indeksowanych dokumentów



Korekcja pytań użytkowników aby uzyskać dobre
odpowiedzi



Dwa główne problemy:



Izolowane słowa



Sprawdzanie każdego słowa na błędy



Nie wyłapiemy błędów maszynowych w poprawnych
słowach



np.: from



form



Zależność od kontekstu



Patrz na otaczające słowa,



Np.: I flew form Heathrow to Narita.

Introduction to Information
Retrieval

Korekta dokumentu



Specjalnie wymagana dla dokumentów po
OCR



Korygujace algorytmy są do tego strojone: rn/m



Można użyć specjalistycznej wiedzy dziedzinowej



Np.: OCR może pomylić częściej O i D niż O oraz I
(sąsiadujące na klawiaturze QWERTY, więc częściej
mylone przy pisaniu).



Ale także: strony webowe i nawet materiały
drukowane mają literówki



Cel: słownik zawierający mało literówek



But often we don’t change the documents
but aim to fix the query-document mapping

Introduction to Information
Retrieval

Literówki w pytaniach



Nasz główny problem



Np.: pytanie Alanis Morisett



Możemy



Wyszukać dokumenty indeksowane poprawnie,
OR



Zwrócić kilka alternatywnych sugestii
poprawnego pytania



Co sądzicie … ?

Introduction to Information
Retrieval

Korekta izolowanych słów



Podstawowy warunek – istnieje leksykon z
poprawną pisownią



Dwa główne podejścia



Standardowy leksykon taki jak



Webster’s English Dictionary



“industry-specific” Leksykon – utrzymywany ręcznie



Leksykon indeksowanego korpusu



Np.:, wszystkie słowa w web



Wszystkie nazwy, akronimy itd.



(zawierające literówki)

Introduction to Information
Retrieval

Korekta izolowanych słów



Mając dany leksykon i ciąg znaków Q,
znaleźć w leksykonie słowo najbliższe do Q



Co znaczy najbliższe?



Omówimy kilka alternatywnych podejść



Edycyjna odległość (Levenshtein distance)



Ważona edycyjna odległość



Nakładanie n-gramów

Introduction to Information
Retrieval

Odległość edycyjna



Dla dwóch stringów S

i S

, to minimalna liczba

operacji do przekształcenia jednego w drugi



Operacje są typowe dla znaków



Insert, Delete, Replace

, (Transposition)



Np.: edycyjna odległość od dof do dog jest 1



Od cat do act jest 2

(Just 1 with transpose.)



Od cat do dog jest 3.



Ogólnie znajdywane przez programowanie
dynamiczne.



Patrz

http://www.merriampark.com/ld.htm

dobry przykład i applet.

Introduction to Information
Retrieval

Ważona odległość edycyjna



Jak poprzednio, ale waga operacji zależy
od rodzaju znaków



Tzn. dla błędów OCR lub klawiatury, np.: m jest
bardziej prawdopodobnie pomylone z n niż z q



Więc, wymiana m na n ma mniejszą odległość
edycyjną niż na q



Może to być sformułowane jako model
probabilistyczny



Wymaga macierzy wag jako wejścia



Zmodyfikowane programowanie
dynamiczne do określenia wag

Introduction to Information
Retrieval

Zastosowanie odległości
edycyjnych



Dla danego pytania, utwórz wszystkie sekwencje
znaków z określoną (ważoną) odległością (np.: 2)



Przetnij ten zbiór z listą „poprawnych” słów



Pokaż termy, które znalazłeś jako sugestie



Alternatywnie,



Możemy przejrzeć wszystkie możliwe korekty w zbiorze
inwersyjnym i zwrócić wszystkie dokumenty… wolne



Możemy przetwarzać z pojedynczą najbardziej
prawdopodobną korektą



Alternatywy ubezwłasnowolnią użytkownika, ale
wzmocnią interakcję z nim

Introduction to Information
Retrieval

Odległość edycyjna do wszystkich
termów słownika?



Dla danego (przekłamanego) pytania – czy
możemy obliczyć odległość edycyjną do
wszystkich termów słownika?



Drogie i wolne



Alternatywa?



Jak możemy zmniejszyć zbiór
kandydackich termów?



Jedna z możliwości to użycie nakładania n-
gramów do tego celu



To można użyć także do korekcji spellingu.

Introduction to Information
Retrieval

Nakładanie n-gramów



Określ wszystkie n-gramy w stringu
pytania i w leksykonie



Użyj indeks n-gramów (wywołaj
wyszukiwanie dla dzikiej karty) aby
wyszukać wszystkie termy leksykonu
pasujące do każdego z n-gramów pytania



Określ próg liczby pasujących n-gramów



Warianty – wagi dla typów klawiatur, etc.

Introduction to Information
Retrieval

Przykład dla trigramów



Przyjmijmy tekst november



Trigramy to nov, ove, vem,

emb, mbe, ber



Pytanie to december



Trigramy to dec, ece, cem,

emb, mbe, ber



Więc 3 trigramy się nakładają (z 6 w
każdym termie)



Jak możemy to przekształcić w
znormalizowaną miarę nakładania?

Introduction to Information
Retrieval

Jedna opcja – współczynnik

Jaccarda(J.C.)



To powszechnie używana miara nakładania



Niech X i Y będą dwoma zbiorami; wtedy J.C.
to



Równy 1 jeśli X i Y mają te same elementy
oraz 0 jeśli są rozłączne



X i Y nie muszą być tych samych rozmiarów



Zawsze przypisujemy liczbę między 0 i 1



Teraz próg decyduje czy mamy dopasowanie



Np.: Jeżeli J.C. > 0.8, to deklarujemy dopasowanie



 /

Introduction to Information
Retrieval

Dopasowanie trigramów



Rozpatrzmy pytanie lord – chcemy
zidentyfikować słowa pasujące do 2 z tych
3 bigramów (lo, or, rd)

alone

lor
d

sloth

lor
d

morbid

border card

border

ardent

Standardowe “merge” dla wystąpień określi …

Zastosuj tu miarę Jaccarda (lub inną).

Introduction to Information
Retrieval

Korekta spellingu
uwzględniająca kontekst



Tekst: I flew from Heathrow to Narita.



Rozpatrzmy pytanie o frazę “flew form
Heathrow”



Chcemy odpowiedzieć

Chodziło Ci o “flew from Heathrow”?

Ponieważ żaden dokument nie pasuje do

pytania o frazę.

Introduction to Information
Retrieval

Korekta uwzględniająca
kontekst



Potrzebujemy tekstu z otoczenia aby

rozpoznać kontekst.



Pierwszy pomysł: wyszukać ze słownika termy

zbliżone (w ważonej odległości edycyjnej) do

każdego termu w pytaniu



Teraz próbuj wszystkie możliwe wynikowe frazy

z jednym „ustalonym” słowem danej próbie



flew from heathrow



fled form heathrow



flea form heathrow



Korekta oparta na trafieniach: Sugeruj

alternatywy mające najwięcej trafień.

Introduction to Information
Retrieval

Inne podejście



Podziel pytanie o frazę na koniunkcję
biwords (wykład poprzedni).



Wyszukaj pary słów, które potrzebują
korekty tylko jednego termu.



Wymień frazy i … ustaw wg rankingu!

Introduction to Information
Retrieval

Główne problemy w korekcie
spellingu



Określamy wiele alternatyw dla “Did you mean?”



Potrzeba wybrania, które przedstawimy
użytkownikowi



Stosujemy heurystyki



Alternatywne dokumenty z największą liczbą trafień



Analiza logów pytań + „podrasowanie”



Dla najbardziej popularnych najwyższych pytań



Korekta spellingu jest droga obliczeniowo



Unikanie rutynowego przetwarzania dla każdego
pytania?



Przetwarzanie tylko pytań pasujących do kilku
dokumentów

Introduction to Information
Retrieval

Soundex



Klasyfikacja heurystyk dla poszerzenia
pytania o

fonetyczny

równoważnik



Specyfikacja językowa – głównie dla nazwisk



Np.: chebyshev  tchebychef



Wymyślone dla dyplomów amerykańskich
… w 1918

Introduction to Information
Retrieval

Soundex – typowy algorytm



Przekształć każdy token do 4-znakowej
formy zredukowanej



Wykonaj to samo z termami pytania



Zbuduj i przeszukuj indeks dla tej
zredukowanej postaci



(Jeśli pytanie wymaga dopasowania soundex)



http://www.creativyst.com/Doc/Articles/SoundEx1/SoundEx1.htm#Top

Introduction to Information
Retrieval

Soundex – typowy algorytm

Zapamiętaj pierwszą literę słowa.

Zastąp wszystkie wystąpienia

następujacych liter na '0' (zero):

'A', E', 'I', 'O', 'U', 'H', 'W', 'Y'.

Zamień litery na cyfry jak poniżej:



B, F, P, V  1



C, G, J, K, Q, S, X, Z  2



D,T  3



L  4



M, N  5



R  6

Introduction to Information
Retrieval

Soundex c.d.

Usuń wszystkie pary kolejnych cyfr.

Usuń wszystkie zera z ciągu wynikowego.

Uzupełnij wynikowy ciąg końcowymi
zerami i zwróć cztery pierwsze pozycje,
które są wynikiem w postaci <uppercase
letter> <digit> <digit> <digit>.

Np.: Herman becomes H655.

Czy hermann generuje ten sam kod?

Introduction to Information
Retrieval

Soundex



Soundex jest klasycznym algorytmem,
wykorzystywanym przez większość baz
danych (Oracle, Microsoft, …)



Jak użyteczny jest soundex?



Not very – for information retrieval



Dobry dla zadań o dużej kompletności (np.:
Interpol), jednak gorszy dla nazwisk
określonych narodowości



Zobel i Dart (1996) opisują inne algorytmy
dla fonetycznego dopasowania znacznie
lepsze dla wyszukiwania informacji

Introduction to Information
Retrieval

Jakie pytania możemy
przetwarzać?



Mamy



Pozycyjny indeks odwrotny z pomijającymi
wskaźnikami



Indeks dla dzikiej karty



Korektę spellingu



Soundex



Pytania takie jak

(SPELL(moriset) /3 toron*to) OR

SOUNDEX(chaikofski)

Document Outline