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?

[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 (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

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

[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 (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

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.