Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl

> Zasady pisania na forum Pro

Tematy na forum Pro mogą zakładać jedynie moderatorzy. W otwartych tematach może pisać każdy, kto ma coś fachowego do powiedzenia. Wszystkie posty nie wnoszące nic do tematu będą natychmiast usuwane, a ich autorzy dostaną ostrzeżenie.
Jeśli uważasz, że jakiś temat jest warty dyskusji na tym forum, zgłoś go w temacie Propozycje.

3 Stron V   1 2 3 >  
Reply to this topicStart new topic
> wyszukiwarka, wydajna, z prawdziwego zdarzenia ;)
chmolu
post 4.12.2005, 00:48:17
Post #1





Grupa: Zarejestrowani
Postów: 179
Pomógł: 0
Dołączył: 8.10.2004

Ostrzeżenie: (0%)
-----


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:
Cytat
To jest przykładowa treść artykułu

Zostanie podzielony na tablicę:
  1. <?php
  2. array('jest', 'przykładowa', 'treść', 'artykułu');
  3. ?>

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?
Go to the top of the page
+Quote Post
dtb
post 4.12.2005, 10:18:37
Post #2





Grupa: Zarejestrowani
Postów: 476
Pomógł: 1
Dołączył: 5.11.2005
Skąd: Bieruń city

Ostrzeżenie: (0%)
-----


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


--------------------
Go to the top of the page
+Quote Post
chmolu
post 4.12.2005, 10:36:23
Post #3





Grupa: Zarejestrowani
Postów: 179
Pomógł: 0
Dołączył: 8.10.2004

Ostrzeżenie: (0%)
-----


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 :/
Go to the top of the page
+Quote Post
bela
post 4.12.2005, 10:42:11
Post #4


Administrator PHPedia.pl


Grupa: Developerzy
Postów: 1 102
Pomógł: 2
Dołączył: 14.09.2003

Ostrzeżenie: (0%)
-----


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


--------------------
Go to the top of the page
+Quote Post
SongoQ
post 4.12.2005, 12:58:23
Post #5





Grupa: Przyjaciele php.pl
Postów: 2 923
Pomógł: 9
Dołączył: 25.10.2004
Skąd: Rzeszów - studia / Warszawa - praca

Ostrzeżenie: (0%)
-----


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.


--------------------
Go to the top of the page
+Quote Post
chmolu
post 15.01.2006, 11:50:36
Post #6





Grupa: Zarejestrowani
Postów: 179
Pomógł: 0
Dołączył: 8.10.2004

Ostrzeżenie: (0%)
-----


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?
Go to the top of the page
+Quote Post
bela
post 15.01.2006, 15:09:04
Post #7


Administrator PHPedia.pl


Grupa: Developerzy
Postów: 1 102
Pomógł: 2
Dołączył: 14.09.2003

Ostrzeżenie: (0%)
-----


Tsearch2?


--------------------
Go to the top of the page
+Quote Post
Bora
post 15.01.2006, 16:37:31
Post #8





Grupa: Zarejestrowani
Postów: 270
Pomógł: 0
Dołączył: 15.06.2003

Ostrzeżenie: (0%)
-----


Cytat(chmolu @ 2005-12-04 00:48:17)
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
Go to the top of the page
+Quote Post
ActivePlayer
post 15.01.2006, 19:39:19
Post #9





Grupa: Przyjaciele php.pl
Postów: 1 224
Pomógł: 40
Dołączył: 6.07.2004
Skąd: Wuppertal

Ostrzeżenie: (0%)
-----


a jak wyliczyc trafność ?
Go to the top of the page
+Quote Post
chmolu
post 15.01.2006, 20:16:25
Post #10





Grupa: Zarejestrowani
Postów: 179
Pomógł: 0
Dołączył: 8.10.2004

Ostrzeżenie: (0%)
-----


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 smile.gif

Ten post edytował chmolu 15.01.2006, 21:22:26
Go to the top of the page
+Quote Post
SongoQ
post 15.01.2006, 22:31:51
Post #11





Grupa: Przyjaciele php.pl
Postów: 2 923
Pomógł: 9
Dołączył: 25.10.2004
Skąd: Rzeszów - studia / Warszawa - praca

Ostrzeżenie: (0%)
-----


LIKE jest zabojczy dla baz tongue.gif


--------------------
Go to the top of the page
+Quote Post
ergo
post 3.03.2006, 13:53:54
Post #12





Grupa: Zarejestrowani
Postów: 79
Pomógł: 0
Dołączył: 8.03.2005

Ostrzeżenie: (0%)
-----


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


--------------------
Go to the top of the page
+Quote Post
pawkow
post 19.03.2007, 16:24:40
Post #13





Grupa: Zarejestrowani
Postów: 76
Pomógł: 7
Dołączył: 30.09.2006

Ostrzeżenie: (0%)
-----


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 winksmiley.jpg

// 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
Go to the top of the page
+Quote Post
Sedziwoj
post 26.03.2007, 23:24:19
Post #14





Grupa: Zarejestrowani
Postów: 793
Pomógł: 32
Dołączył: 23.11.2006
Skąd: Warszawa

Ostrzeżenie: (0%)
-----


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.


--------------------
Algorytmy w PHP, czy ktoś o tym słyszał?
Dlaczego tak mało kobiet programuje? ponieważ nie zajmują się głupotami.
Go to the top of the page
+Quote Post
Turgon
post 27.03.2007, 17:32:19
Post #15





Grupa: Zarejestrowani
Postów: 800
Pomógł: 0
Dołączył: 26.11.2005
Skąd: Nowy Sącz

Ostrzeżenie: (0%)
-----


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


--------------------
Jah Music Is On My Mind !
Go to the top of the page
+Quote Post
Martio
post 3.05.2007, 08:30:46
Post #16





Grupa: Zablokowani
Postów: 167
Pomógł: 2
Dołączył: 15.02.2004

Ostrzeżenie: (30%)
XX---


Cytat(ActivePlayer @ 15.01.2006, 20:39:19 ) *
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:

  1. <?php
  2. 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)
  3. ?>
Go to the top of the page
+Quote Post
zbig
post 5.05.2007, 13:55:38
Post #17





Grupa: Zarejestrowani
Postów: 144
Pomógł: 30
Dołączył: 5.05.2007
Skąd: Mannheim

Ostrzeżenie: (0%)
-----


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


--------------------
Flash Flex PHP JAVA RED5 http://www.easyweb24.net
Go to the top of the page
+Quote Post
Riklaunim
post 5.05.2007, 19:32:41
Post #18





Grupa: Zarejestrowani
Postów: 640
Pomógł: 44
Dołączył: 8.02.2004

Ostrzeżenie: (0%)
-----


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 smile.gif Problemem może być brak "przyjaznych" tutoriali. (+ konieczność zainstalowania xapiana i xapian-bindings na serwerze)


--------------------
Biblioteki: Skrypty, CMS | Kurs PHP | Python
Go to the top of the page
+Quote Post
SHiP
post 8.05.2007, 19:09:19
Post #19





Grupa: Zarejestrowani
Postów: 697
Pomógł: 47
Dołączył: 19.12.2003
Skąd: Lublin

Ostrzeżenie: (0%)
-----


Cytat(Sedziwoj @ 26.03.2007, 22:24:19 ) *
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.


--------------------
Warsztat: Kubuntu, PhpStorm, Opera
Go to the top of the page
+Quote Post
rashid
post 10.05.2007, 10:11:48
Post #20





Grupa: Zarejestrowani
Postów: 27
Pomógł: 0
Dołączył: 22.11.2003

Ostrzeżenie: (0%)
-----


Cytat(zbig @ 5.05.2007, 14:55:38 ) *
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.

Cytat(zbig @ 5.05.2007, 14:55:38 ) *
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 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.


--------------------
Robert Janeczek
G-Forces Web Management Polska
robert.janeczek@gforces.pl
Go to the top of the page
+Quote Post

3 Stron V   1 2 3 >
Reply to this topicStart new topic
1 Użytkowników czyta ten temat (1 Gości i 0 Anonimowych użytkowników)
0 Zarejestrowanych:

 



RSS Wersja Lo-Fi Aktualny czas: 29.03.2024 - 00:11