Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28632 > unrolled thread

Algorytm szukania podobny do Google

Back to article view | Back to pl.comp.programming

Contents

  Algorytm szukania podobny do Google Borneq <borneq@antyspam.hidden.pl> - 2016-06-07 14:34 +0200
    Re: Algorytm szukania podobny do Google "M.M." <mmarszik@gmail.com> - 2016-06-07 06:36 -0700
      Re: Algorytm szukania podobny do Google Borneq <borneq@antyspam.hidden.pl> - 2016-06-07 15:44 +0200
        Re: Algorytm szukania podobny do Google "M.M." <mmarszik@gmail.com> - 2016-06-07 07:53 -0700
        Re: Algorytm szukania podobny do Google Piotr Chamera <piotr_chamera@poczta.onet.pl> - 2016-06-07 17:34 +0200
          Re: Algorytm szukania podobny do Google Borneq <borneq@antyspam.hidden.pl> - 2016-06-07 22:31 +0200
            Re: Algorytm szukania podobny do Google Borneq <borneq@antyspam.hidden.pl> - 2016-06-08 10:32 +0200
          Re: Algorytm szukania podobny do Google Borneq <borneq@antyspam.hidden.pl> - 2016-06-08 11:41 +0200

#28632 — Algorytm szukania podobny do Google

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" ?

[toc] | [next] | [standalone]

#28633

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

[toc] | [prev] | [next] | [standalone]

#28634

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.

[toc] | [prev] | [next] | [standalone]

#28635

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

[toc] | [prev] | [next] | [standalone]

#28636

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

[toc] | [prev] | [next] | [standalone]

#28637

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"

[toc] | [prev] | [next] | [standalone]

#28639

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.

[toc] | [prev] | [next] | [standalone]

#28640

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

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web