Mam wiele dokumentów i mam sprawdzić czy dany tekst znajduje się w
którymś. Zamiast szukania wszystkich, lepiej skorzystać z indeksu. Stąd,
wyszukiwać będę całe słowa a nie części słów.
Algorytm szukania Google opisany jest:
rakaposhi.eas.asu.edu/cse494/notes/f05-google.ppt
infolab.stanford.edu/pub/papers/google.pdf
jak to wygląda? Jest lista alfabetyczna słów, albo jakaś zhaszowana. Dla
każdego słowa jest lista dokumentów? Jest to linked-list?
No dobrze, a co gdy mam szukać word1 AND word2 albo word1 - word2?
albo ważna kolejność: "word1 word2" ?

do góry

On Tuesday, June 7, 2016 at 2:34:29 PM UTC+2, Borneq wrote:
> Mam wiele dokumentów i mam sprawdzić czy dany tekst znajduje się w
> którymś. Zamiast szukania wszystkich, lepiej skorzystać z indeksu. Stąd,
> wyszukiwać będę całe słowa a nie części słów.
> Algorytm szukania Google opisany jest:
> rakaposhi.eas.asu.edu/cse494/notes/f05-google.ppt
> infolab.stanford.edu/pub/papers/google.pdf
> jak to wygląda? Jest lista alfabetyczna słów, albo jakaś zhaszowana. Dla
> każdego słowa jest lista dokumentów? Jest to linked-list?
> No dobrze, a co gdy mam szukać word1 AND word2 albo word1 - word2?
> albo ważna kolejność: "word1 word2" ?

Podstawą jest zahasowany słownik słów. Każde słowo ma listę stron na
których ono wstępuje. Lista jest uporządkowana według trafności. Trafność
liczą jakimś algorytmem - dobry algorytm wydaje się bardziej
problematyczny. Jeśli wyszukiwanie z minusem, to jeszcze strona musi
mieć zahasowany słownik słów. Jeśli z operatorem and, to część wspólna
urli. Problemem jest zrównoleglenie i osiągnięcie dużej wydajności.


Pozdrawiam

do góry

W dniu 07.06.2016 o 15:36, M.M. pisze:
> Podstawą jest zahasowany słownik słów. Każde słowo ma listę stron na
> których ono wstępuje. Lista jest uporządkowana według trafności. Trafność
> liczą jakimś algorytmem - dobry algorytm wydaje się bardziej
> problematyczny. Jeśli wyszukiwanie z minusem, to jeszcze strona musi
> mieć zahasowany słownik słów. Jeśli z operatorem and, to część wspólna
> urli. Problemem jest zrównoleglenie i osiągnięcie dużej wydajności.

jak to na przykładzie?
dokument 0: Ala ma kota
dokument 1: Tadek ma psa

leksykon słów :
Ala - 0
kota - 0
ma - 0,1
psa - 1
Tadek -1
dla danego słowa może być bardzo dużo:
the - 0,1,2,3,4,6,7,8,9,10..
is - 0,1,2,3,4,5,6,7,9,10..
teraz operacja [the AND is] może trwać długo
Nie wiem na przykład dlaczego w
http://webserver2.tecgraf.puc-rio.br/eda/referencias
/Google-petteri_huuhka_google_paper.pdf
w Forward barrels nhits jest 8 bitowe a w inverted barrels tylko 5 bitowe.

do góry

On Tuesday, June 7, 2016 at 3:44:29 PM UTC+2, Borneq wrote:
> W dniu 07.06.2016 o 15:36, M.M. pisze:
> > Podstawą jest zahasowany słownik słów. Każde słowo ma listę stron na
> > których ono wstępuje. Lista jest uporządkowana według trafności. Trafność
> > liczą jakimś algorytmem - dobry algorytm wydaje się bardziej
> > problematyczny. Jeśli wyszukiwanie z minusem, to jeszcze strona musi
> > mieć zahasowany słownik słów. Jeśli z operatorem and, to część wspólna
> > urli. Problemem jest zrównoleglenie i osiągnięcie dużej wydajności.
>
> jak to na przykładzie?
> dokument 0: Ala ma kota
> dokument 1: Tadek ma psa
>
> leksykon słów :
> Ala - 0
> kota - 0
> ma - 0,1
> psa - 1
> Tadek -1
Bo jak inaczej?


> dla danego słowa może być bardzo dużo:
> the - 0,1,2,3,4,6,7,8,9,10..
> is - 0,1,2,3,4,5,6,7,9,10..
Może jeśli słowo ma więcej niż 100tys stron, to jest trafia do osobnej
hash-table?


> teraz operacja [the AND is] może trwać długo
Bo ja wiem... To dobrze działa w środowisku
rozproszonym. Tego bym się nie bał. Trudniej zrobić
dobry page-rank. Trudniej zapewnić aktualizację w
locie, albo redundancję, typu N% komputerów padło a
wyszukiwarka poprawnie działa z prawdopodobieństwem
powyżej M%.


> Nie wiem na przykład dlaczego w
> http://webserver2.tecgraf.puc-rio.br/eda/referencias
/Google-petteri_huuhka_google_paper.pdf
> w Forward barrels nhits jest 8 bitowe a w inverted barrels tylko 5 bitowe.

Nie wiem, trzaby się wczytać.

Pozdrawiam

do góry

W dniu 2016-06-07 o 15:44, Borneq pisze:
> jak to na przykładzie?
> dokument 0: Ala ma kota
> dokument 1: Tadek ma psa
>
> leksykon słów :
> Ala - 0
> kota - 0
> ma - 0,1
> psa - 1
> Tadek - 1
słowa w leksykonie sprowadza się zwykle do jakiejś podstawowej postaci
(ang. stemming), np. kota, kotu, kocie -> kot

> dla danego słowa może być bardzo dużo:
> the - 0,1,2,3,4,6,7,8,9,10..
> is - 0,1,2,3,4,5,6,7,9,10..
słowa, które występują bardzo często i nie wnoszą żadnej informacji
do wyszukiwania się po prostu pomija

do góry

W dniu 07.06.2016 o 17:34, Piotr Chamera pisze:
> słowa w leksykonie sprowadza się zwykle do jakiejś podstawowej postaci
> (ang. stemming), np. kota, kotu, kocie -> kot

Tu też potrzebny jakiś algorytm aby nie trzeba używać całej bazy
polimorfologika

> słowa, które występują bardzo często i nie wnoszą żadnej informacji
> do wyszukiwania się po prostu pomija

Chociaż tu z pomijaniem byłbym ostrożny, bo w Google podoba mi się to,
że nie pomija nawet częstych słów, a w wyszukiwaniu na forach
internetowych nie podoba mi się gdy zgłasza się "to słowo zbyt często
występuje"

do góry

W dniu 07.06.2016 o 22:31, Borneq pisze:
> Tu też potrzebny jakiś algorytm aby nie trzeba używać całej bazy
> polimorfologika
>
>> słowa, które występują bardzo często i nie wnoszą żadnej informacji
>> do wyszukiwania się po prostu pomija

Tu praca nlp.ipipan.waw.pl/~adamp/msc/janus.daniel/praca.pdf.
gz
pokazuje że bitowe indeksy są niepraktyczne:
"Jednak to dla dużych korpusów zalety indeksowania są najbardziej
widoczne, a wtedy ten sposób przechowywania indeksów jest zupełnie
niepraktyczny. Dla próbki Korpusu IPI PAN (por. tabela 4.2), zajmującej
w postaci binarnej
bez indeksów 303 MB, sam tylko indeks form literalnych reprezentowany w
ten sposób miałby
rozmiar 670475?30002374/8 B = 2,29 TB, czyli blisko 8000-krotnie (!)
więcej niż wyjściowy korpus."

Bo binarne indeksy wzrastają kwadratowo z wielkością tekstu.

do góry

W dniu 07.06.2016 o 17:34, Piotr Chamera pisze:
> słowa w leksykonie sprowadza się zwykle do jakiejś podstawowej postaci
> (ang. stemming), np. kota, kotu, kocie -> kot
https://github.com/morfologik/morfologik-stemming

do góry