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

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

Sys Inf 03 Manning w 03

Document Outline