wyszukiwarka, wydajna, z prawdziwego zdarzenia ;) Opcje

[chmolu]

Witam,

wiem, że takie tematy już były, ale nie znalazłem w nich żadnych konkretów.

Jak podeszlibyście do problemu zbudowania mechanizmu wyszukiwarki dla systemu, który nierzadko może obsługiwać spore ilości danych (w wielu tabelach)?

Interesuje mnie wszystko na ten temat - linki, artykuły, tutoriale.

Spotkałem się już w kilku aplikacjach z rozwiązaniem, które wyglądało mniej więcej tak:
treść tabeli, np. articles jest dzielona na słowa, np tekst:

To jest przykładowa treść artykułu

Zostanie podzielony na tablicę:

[PHP] pobierz, plaintext 
<?php
array('jest', 'przykładowa', 'treść', 'artykułu');
?>
[PHP] pobierz, plaintext 

Słowo "to" jest traktowane jako tzw. common word i pomijane.

Te słowa są wrzucane do osobnej tabeli, która ma mniej wiecej taką strukturę:

Kod

word_id
word_text

Do tego jest jeszcze jedna tabela, która łączy artykuł ze słowami:

Kod

article_id
word_id

Rozwiązanie ciekawe, ale zastanawia mnie, jak to jest z jego wydajnością. O ile liczba słów jest ograniczona, to druga tabela może się nieźle rozrosnąć. Pisał już ktoś coś takiego? Jakie są wasze sposoby na problem wyszukiwarki w CMSach?

[dtb]

http://www.phpsolmag.org/pl/modules/news2/....php?storyid=13 <- w gazecie jest art jak zrobic wyszykiwarke używając zbiorów (BITSET). polecam.

[chmolu]

Z tego, co pamiętam to rozszerzenie BitSet nie jest standardowo dołączane do php, więc takie rozwiązanie odpada.

Jak na razie najrosądniejszym rozwiązaniem byłoby zastosowanie FULLTEXT search MySQL'a. Jest jednak ten problem, że definitywnie tracę tu kompatybilność z innymi systemami RDBMS :/

[bela]

http://lucene.apache.org/ - Javove ale zawsze można popatrzeć.

[SongoQ]

Wyszukiwanie zalezy od rodzaju bazy, niektore wspomagaja takiego typu przeszukiwania. Odnosnie takiego schematu, to sam mam zaimplementowane w jednej aplikacji i indeksow slow jest chyba okolo 10 milionow i czasu sa bardzo zadowalajace. Wszystko zalezy od bazki i umiejetnosci dostrojenia zapytania.

[chmolu]

Niestety muszę wrócić do tej sprawy.

Przez głupi bug w mysqlu FULLTEXT mogę sobie o d**ę potłuc. I chyba nie zanosi się na szybkie naprawienie tego - bug został oznaczony jako "closed". Szkoda, bo w tej chwili wyszukiwarka u mnie to 2 zapytania...

Jak wyszukiwarki zaimplementowane są w IPB, ezPublish i innych tego typu systemach?

Jak sprawa wygląda na Postgresie? Czy można na nim zbudować jakąś wydajną wyszukiwarkę w miarę prosty sposób?

[bela]

Tsearch2?

[Bora]

Do tego jest jeszcze jedna tabela, która łączy artykuł ze słowami:

Kod

article_id
word_id

Rozwiązanie ciekawe, ale zastanawia mnie, jak to jest z jego wydajnością. O ile liczba słów jest ograniczona, to druga tabela może się nieźle rozrosnąć. Pisał już ktoś coś takiego? Jakie są wasze sposoby na problem wyszukiwarki w CMSach?

Może w takim razie zmienić sposób przechowywania danych w tej tabeli.
Np 1|34|43
albo nawet złączyć to w jedną tabele:
word_id | word | articles
potem tylko expolde albo coś w tym stylu. Żeby nie meczyć sie za bardzo wystarczy tylko dac odpowiednie API żeby przy każdym dodaniu/edycji/usunięciu modyfikowało odpowiednie rekordy.

Ten post edytował Bora 15.01.2006, 16:38:35

[ActivePlayer]

a jak wyliczyc trafność ?

[chmolu]

A jak ma się sprawa z LIKE %cośtam%?

Czy jeśli mam napchaną tabelę, w której przeszukiwać chcę 2 pola o wielkości 1-4 zdań, to LIKE będzie bardzo zabójcze dla bazy?

edit:
znalazłem fajny tutorial: http://www.symfony-project.com/askeet/21
Chyba zaimplementuję sobie coś takiego. Więcej roboty, baza się rozrośnie, ale może będzie działało, jak należy

Ten post edytował chmolu 15.01.2006, 21:22:26

[SongoQ]

LIKE jest zabojczy dla baz

[ergo]

ja chyba czegos nie rozumiem , bo o ile mi sie wydaje to dal kazdego slowa ktore mialo by byc umieszczone generowane jest zapytanie ? pozatym trzeba by sprawdzic czy slowo znajduje sie w bazie, w jaki sposob to wygodnie zaimplementowac ?

Ten post edytował ergo 3.03.2006, 13:55:44

[pawkow]

Według was należy ograniczać używanie LIKE. Rozumiem. A może używać LIKE i zapisywać w bazie otrzymane wyniki. Wtedy jeśli pojawiło by się nowe słowo, tworzony byłby nowy rekord. Przykład:

internauta poszukuje słowa "analfabetyzm" na naszej stronie.

1. Jeżeli ktoś już szukał tego słowa wcześniej, to mamy problem z głowy.
2. Jeśli nie baza przeszukuje artykuły, i zapisuje id artykułów w bazie w tabeli o strukturze jak niżej:

Kod

| search_id | search_result |

W search_id wiadomo, w search result oddzielone jakimś znakiem, np: "|" id konkretnego artykułu. Potem tylko explode w wypadku kolejnego wyszukania tego słowa i mamy gotowe wyniki.

Gorzej, jeżeli chcemy umożliwić przeszukiwanie całego portalu, np. newsów, userów i artykułów. Jednak i to można rozwiązać, zapuisując wyniki np. w takiej postaci: a1|a17|a26|n4|n78|n54|u14|u56|u8

Były by to:
artykuły o id 1, 17, 26
newsy o id 4, 78, 54
userzy o id 14, 56, 8


Może komuś się takie rozwiązanie spodoba

// EDT do postu wyżej

Może być jedno zapytanie np: LIKE %slowo 1% AND LIKE %slowo 2%

Ten post edytował pawkow 19.03.2007, 16:26:04

[Sedziwoj]

pawkow to rozwiązanie jest kiepskie, ponieważ przy pojawieniu się nowego artykułu, nie masz możliwości usunięcia bufora. A jakbyś to robił, to by było takie samo obciążenie, jak przy użyciu samego LIKE. Przy każdym wybraniu musiał byś rozdzielać dane, co też generuje obciążenie.
Jeszcze sam nie wnikałem w ten problem, ale przy tym co się chwile zastanowiłem, to chyba najlepsze rozwiązanie to
word | id_article
przy czym unikalne jedynie mogło by być połączenie obu.
Przy założeniach szukania samego artykułu bez cytatu.
Bo chyba jednak problem nie może być rozwiązany aby był mało obciążający pamięciowo i obliczeniowo.

[Turgon]

W mojej opinii otagowywać i na ich podstawie szukać. Obecnie sam piszę przeszukiwarkę artów, to napiszę coś więcej.

[Martio]

a jak wyliczyc trafność ?

Polecam komponent Zend_Search z frameworka Zend Framework oparty o projekt Apache Lucene. Jest to najbardziej optymalne rozwiązanie, gdyż opiera się w całości na indeksacji danych w systemie plików. Wyszukiwanie w bazie danych ma wiele wad: czas wyszukiwania różni się od ilość danych, jest to spore obciążenie dla samej bazy danych, itd.

W wynikach wyszukiwania masz już obliczone trafność wyszukiwania, a mierzy się to następującym wzorem:

[PHP] pobierz, plaintext 
<?php
score(q,d) = sum( tf(t in d) * idf(t) * getBoost(t.field in d) * lengthNorm(t.field in d) ) * coord(q,d) * queryNorm(q)
?>
[PHP] pobierz, plaintext 

[zbig]

Mysle , ze temat wyszukiwarek jest zbyt wielki zeby wszystkie watpliwosci rozwiac podczas dyskusji na forum.
Pracuje kilka lat w niemieckiej firmie specjalizujacej sie w aplikacjach webowych i moge jedynie napisac kilka slow o naszym sposobie. Przede wszystkim na podstawie danych ktore moga byc wyszukiwane przez uzytkownikow generujemy specjany text index , ktory pozwala na natychmiastowe (prawie) znalezienie danych.
Text index to tylko nazwa tak naprawde dane dla wyszukiwarki moga byc trzymane w tabeli w bazie. Najwazniejsza jednak rzecz to budowa indexu w taki sposob aby mozna bylo uzyc algorytmu DFA do jego przeszukiwania.
Jest to standartowy algorytm uzywany przez MYSQL do tworzenia text indexow przy FULLTEXT , ale w naszym przypadku FULLTEXT MYSQL tworzy zbyt ogolny text index, dlatego tworzymy sobie wlasny absolutnie indywidualny dla naszych danych. Nastepnym krokiem jest wlasnie owa wyszukiwarka ktora zgodnie z DFA przeszuka caly text index i zwroci nam resultat , counter i tym podobne rzeczy. Text index jest odswiezany raz dziennie , czyli tak na prawde dane wprowadzone dzisiaj moga byc widoczne, dopiero nastepnego dnia.

W naszym przypadku potrzebne sa trzy aplikacje
1. tworzaca indexy (Java lub C++)
2. nasluchujaca (Java lub C++)
3. przeszkujaca indexy wg DFA (Java lub C++)

no i oczywiscie cos co to wszystko wyswietli (PHP)
Do komunikacji PHP z Java uzywamy JavaBridge ,z C++ Ajaxa z responseXML

Na podobnej zasadzie (ale na 100% o wiele lepiej pracujacej) bazuja Google, mam na mysli algorytm DFA
A tak na marginesie nalezy dodac ze Google rowniez uzywaja MYSQL-a , co powinno zakonczyc dyskusje na temat waznosci swiat Bozego Narodzenia na Wielka Noca

Powinienem dodac , ze text index w naszym przypadku trzymany jest w pamieci aplikacji nasluchujacej ,ale jest to indywidualny wybor, dane mozna trzymac w tabelach chociaz chodzi to nieco wolniej.

Nasza wyszukiwarka przeszkuje baze danych 2 milionow firm polaczonych z kategoriami , oraz 40 milionach danych adresowych . Musze przyznac ze textindexy osigaja kilkugigowe rozmiary ale algorytm pozwala absolutnie szybko eliminowac niepotrzebne kroki podczas wyszukiwania.

Na zakonczenie chcialbym dodac , ze nie widze absolutnie zadnego prolemu w napisaniu calego mechanizmu w PHP

Wyszukiwarka ta pracuje na stronie http://city24.de/YellowPages
Wiecej szczegolow podac niestety nie moge ale zachecam do zapoznania sie z DFA i mam nadzieje ze pomysly z jego wykorzystanim nasuna sie Wam same

Pozdrawiam

[Riklaunim]

jest też Xapian - http://www.xapian.org/ który ma API dostępne dla Ruby, Pythona, PHP i innych. Ostatnio bawiłem się API pythonowym, wersja PHP w planach i działa całkiem fajnie Problemem może być brak "przyjaznych" tutoriali. (+ konieczność zainstalowania xapiana i xapian-bindings na serwerze)

[SHiP]

pawkow to rozwiązanie jest kiepskie, ponieważ przy pojawieniu się nowego artykułu, nie masz możliwości usunięcia bufora. A jakbyś to robił, to by było takie samo obciążenie, jak przy użyciu samego LIKE. Przy każdym wybraniu musiał byś rozdzielać dane, co też generuje obciążenie.
Jeszcze sam nie wnikałem w ten problem, ale przy tym co się chwile zastanowiłem, to chyba najlepsze rozwiązanie to
word | id_article
przy czym unikalne jedynie mogło by być połączenie obu.
Przy założeniach szukania samego artykułu bez cytatu.
Bo chyba jednak problem nie może być rozwiązany aby był mało obciążający pamięciowo i obliczeniowo.

Można cachować zapytania wyszukiwarki i to w bardzo prosty sposób, wystarczy do każdego artykułu dodać jedno pole "searchid"

I tłumaczac na przykładzie:
1. Dodajemy artykuł i przypisujemy mu searchid=1
2. Nic nie mamy zcachowane wiec nasza zmienna w wyszukiwarce, $cache=1,
3. Następuje pierwsze wyszukiwanie wszystkich artykułów których searchid >= $cache
4. Zwiększamy naszą zmienną wyszukiwarki $cache do 2,
5. Dodajemy artykuł, tym razem jako searchid dodajemy wartosc naszej zmiennej $cache czyli dwa
6. Następuje kolejne wyszukiwanie, cachujemy artykuły o searchid>=$cache
I tak w kółko

W przypadku usuwania artykułów sprawa jest prosta, w przypadku edycji po prostu zmieniamy searchid w artykulu na $cache+1

Lepszego sposobu nie wymysliłem, jedyny problem to przechowywanie zmiennej $cache gdzies w globalnym miejscu aby zapytania łatwo mogły się do niej odwołac.

[rashid]

W naszym przypadku potrzebne sa trzy aplikacje
1. tworzaca indexy (Java lub C++)
2. nasluchujaca (Java lub C++)
3. przeszkujaca indexy wg DFA (Java lub C++)

no i oczywiscie cos co to wszystko wyswietli (PHP)
Do komunikacji PHP z Java uzywamy JavaBridge ,z C++ Ajaxa z responseXML

No bez perwy... Google daje rade indeksowac skryptami w Pythonie, wiec nie widze najmniejszego problemu z zaprzegnieciem PHP do tej samej funkcji, szczegolnie do indeksowania danych stanowiacych jakis pikoprocent danych, na ktorych operuje Google.

Na podobnej zasadzie (ale na 100% o wiele lepiej pracujacej) bazuja Google, mam na mysli algorytm DFA
A tak na marginesie nalezy dodac ze Google rowniez uzywaja MYSQL-a , co powinno zakonczyc dyskusje na temat waznosci swiat Bozego Narodzenia na Wielka Noca

MySQL nie jest uzywany do przechowywania indeksu Google. Jest uzywany w innych aplikacjach, np. do gromadzenia statystyk Google Analytics (strzelam tutaj bazujac na tym, ze Urchin stanowiacy baze dla GA korzystal z tego).


Odpowiadajac na glowne pytanie tego watku, jesli ktos chce pisac samodzielnie wydajna wyszukiwarke, to polecam http://labs.google.com/papers.html (tutaj miedzy innymi artykuly o sposobie przechowywania danych glownego indeksu Google). Dla wiekszosci powaznych rozwiazan lepsze na dluzsza mete bedzie skorzystanie z gotowca, czyli http://www.google.com/enterprise/mini/.

PS. Nie mam ochoty na dyskusje o nieosiagalnosci Mini z powodow finansowych.