Witam

Od pewnego czasu zastanawiam się jak zrobić skrypt, który wstawiony jako iframe (lub za pomocą js) na inną stronę, pobierałby z niej tekst i sprawdzał, na podstawie swojej bazy danych, czy występują na niej słowa kluczowe.

Problemem jest to że w bazie słowa kluczowe zapisywane są po kilka w każdym rekordzie oddzielone spacjami (rozdzielenie ich do tablicy z ID rekordu wymaga więcej czasu i pamięci).

Próbowałem robić to łącząc się za pomocą CURL ze stroną ($_SERVER['HTTP_REFERER']), następnie usuwając znaczniki html i wszystkie znaki interpunkcyjne i specjalne. Dalej dzielę wynik do tablicy przez spacje i teraz problem: dla każdego wpisu w tablicy muszę wykonać zapytanie do bazy, żeby sprawdzić czy nie jest on słowem kluczowym. Zajmuje to zdecydowanie za dużo czasu i obciąża serwer, szczególnie że nie jest to jedyne zadanie skryptu (dalej analizuje słowa kluczowa, zapisuje w bazie ich występowanie, itp.).

Może ma ktoś jakieś propozycje jak przyśpieszyć działanie skryptu i odciążyć serwer?

Daje kod jakim tworzę tą tablicę ze słowami, dalej w pętli porownuje z wpisami w bazie.

[PHP] pobierz, plaintext 
<?php
$url = $_SERVER['HTTP_REFERER'];
$curl = curl_init();
 
  $header[0] = 'Accept: text/xml,application/xml,application/xhtml+xml,';
  $header[0] .= 'text/html;q=0.9,text/plain;q=0.8,image/png,*/*;q=0.5';
  $header[] = 'Cache-Control: max-age=0';
  $header[] = 'Connection: keep-alive';
  $header[] = 'Keep-Alive: 300';
  $header[] = 'Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7';
  $header[] = 'Accept-Language: en-us,en;q=0.5';
  $header[] = 'Pragma: ';
 
  curl_setopt($curl, CURLOPT_URL, $url);
  curl_setopt($curl, CURLOPT_USERAGENT, 'Googlebot/2.1 (+http://www.google.com/bot.html)');
  curl_setopt($curl, CURLOPT_HTTPHEADER, $header);
  curl_setopt($curl, CURLOPT_REFERER, 'http://www.google.com');
  curl_setopt($curl, CURLOPT_RETURNTRANSFER, 1);
 
  $html = curl_exec($curl);
  curl_close($curl);
$search = array('/<?((?!?>).)*?>/s');
 
$html = strip_tags(preg_replace($search, '', $html));
$tab = array('&#x0105;' => 'a', '&#x0107;' => 'c', '&#x0119;' => 'e', '&#x0142;' => 'l', '&#x0144;' => 'n', '&#x00F3;' => 'o', '&#x015B;' => 's', '&#x017A;' => 'z', '&#x017C;' => 'z', 'ą' => 'a', 'ę' => 'e', 'ó' => 'o', 'ś' => 's', 'ł' => 'l', 'ż' => 'z', 'ź' => 'z', 'ć' => 'c', 'ń' => 'n');
		$html = strtr($html, $tab);
$f = array('&nbsp;', '|', ',', '.', '?', '!', '@', '#', '  , '%', '^', '&', '*', '(', ')', '-', '_', '=', '+', '\', '/', ']', '[', '{', '}', ';', ':', '`', '~');
$html = str_replace($f, ' ', $html);
$html = ereg_replace('[[:space:]]+', ' ', $html);
 
$keys = explode(' ', $html);
$html = '';
?>
[PHP] pobierz, plaintext 

A może znacie inny sposób na sprawdzenie czy na stronie występują słowa z bazy?

Pozwolę sobie zacząć od krytyki zastosowanego rozwiązania. Pamiętanie kilku słów kluczowych w jednej komórce w tabeli w bazie danych łamie podstawową zasadę baz danych: atomowość danych w komórkach. Co to oznacza? Oznacza to, że każda dana w komórce powinna być w miarę możliwości daną podstawową i niepodzielną w ramach zastosowania, do którego jest potrzebna. Zbiór słów, z których każde ma oddzielne, separowalne znaczenie, nie jest taką daną. Dlaczego w twoim przypadku jest to takie ważne? Ponieważ, jak się domyślam, do wyszukiwania słów używasz operacji LIKE '%slowo%'. Ta operacja jest znacznie wolniejsza niż zwykły operator porównania =. Powinieneś mieć jedno słowo w każdej komórce.

Jak poprawić szybkość:
Jeżeli chcesz w prosty sposób przyśpieszyć wyszukiwanie słów: musisz mieć jedno słowo w komórce oraz nałożyć na kolumnę zawierającą te słowa indeks. W celu zaznajomienia się z indeksami zapraszam do manuala MySQL (szukaj pod INDEX). Należy się jednak liczyć ze zwiększeniem liczby miejsca zajmowanego na dysku przez tablicę.

Analiza rozwiązania: złożoność liniowa (n operacji porównań, gdzie n to liczba słów w bazie)

Inne rozwiązania są bardziej wyrafinowane i właściwie powinienem odesłać cię do odpowiednich podręczników z wyszukiwania danych oraz struktur danych, jednak po krótce opiszę dwa podstawowe pomysły znacznie przyśpieszające wyszukiwanie słów.

Pierwszy pomysł opiera się o strukturę drzewiastą. Wyobraź sobie drzewo, gdzie każdemu węzłowi odpowiada litera oraz liczba. Każdy poziom drzewa przedstawia literę na danej pozycji w słowie.

Przykład :
Załóżmy, że mamy drzewo
poziom 0: ................korzen
......................----------------------
......................|..................|.........|
poziom 1:........A 0 ..............B 0.......C 0
....................-------............------......-
...................|........|..........|.......|......|
poziom 2: ....A 0......L 0 ......U 0....X 2...O 1
.................----.........-
.................|...|........|
poziom 3:..A 5.O 4....M 3
(kropki to spacje)
I teraz rozpatrujemy czy dane słowo znajduje się w bazie danych oraz gdzie się znajduje. Załóżmy, że szukamy słowa ALA.
Zaczynamy od korzenia.
Bierzemy pierwszą literę słowa (A) i idziemy w to miejsce według drzewa (czyli do A na poziomie 1). Następnie bierzemy drugą literę słowa (L) i idziemy od miejsca gdzie jesteśmy do tej litery w drzewie (czyli L na poziomie 2). Następnie bierzemy 3 literę słowa (A) i idziemy od L na poziomie 2 do A na poziomie 3. Przy A znajduje się liczba 5, która mówi, że dane słowo znajduje się w bazie danych pod indeksem 5 (może również oznaczać inne rzeczy). Jeżeli nie będziemy mieli gdzie pójść lub dojdziemy do końca słowa i będzie przy danej literce 0 oznacza to, że nie ma danego słowa w bazie (sprawdź dla COŚ i BU).

Jakie są zalety tego rozwiązania? Złożoność log(n) (bardzo mała), mała pamięć potrzebna do przechowania całego drzewa.
Wady? Trudno takie drzewo pamiętać i odtwarzać z bazy.

Inne rozwiązanie:
Masz krótką funkcję hashującą (która może przyjąć na przykład maksymalnie 1000 różnych wartości). Dla każdego słowa liczysz funkcję hashującą i umieszczasz je w odpowiedniej liście słów.

Przykład:
hash1 -> ala, burek, kotek
hash2 -> piesek, miska, koń
hash3 -> krowa, piłka, boisko, muzyka

Sprawdzanie czy słowo znajduje się w słowniku:
1. Liczysz hash słowa (ala -> hash1)
2. Idziesz do słów z danym hashem (hash1 -> ala, burek, kotek)
3. Sprawdzasz czy słowo znajduje się w danej liście (w przykładzie tak)

Zalety: złożoność zależy od działania funkcji hasującej ale jest mniejsza niż n (liniowa). Łatwiejsze do zaimplementowania w bazie danych.
Wady: troche gorsze niż drzewo podane jako rozwiązanie 1.

Dzięki Cotter za wykład
Napewno z niego skorzystam, jednak myślę jeszcze nad cache'owaniem wyników z wyszukiwania słów na stronach.
Wtedy zapisywałoby ID rekordu, w którym znajduje się dane słowo (jedno słowo - jeden rekord), do plików .txt
Pliki byłyby zapisywane zgodnie ze schematem cache/(domena)/(nazwa katalogu lub pliku).txt

Dane w cache byłyby sprawdzane raz lub dwa razy na tydzień (cron), a nowe dodawane gdy szuka słów kluczowych na nieznanej stronie.

Powinno to trochę odciążyć bazę danych, szkoda tylko że dysk przy tym oberwie. Ogólnie skrypt szukający słów kluczowych byłby wywoływany ok. 50k razy (uq wyświetlenia) i przeszło 250k wyśw (dane ze statystyk) dziennie na różnych stronach, a ta wartość rośnie dosyć szybko.
Bez tego baza danych mogłaby nie wyrobić.

Myślisz, że takie rozwiązanie zmieni coś przy wybieraniu słów kluczowych? Dzięki temu powinno przeszukiwać każdą stronę raz lub dwa razy w tygodniu a nie kilkaset razy dziennie, tylko czy przy większej ilości adresów (w końcu każda podstrona ma swój plik z ID słów kluczowych) nie obciąży to zbytnio procesora?

I jeszcze: podany przeze mnie sposób pobierania słów ze strony jest dobry? Czy można go przyśpieszyć (napewno można, tylko jak)? Przy cache'owaniu będzie wywoływany ok. 500-1k razy dziennie (w dniu cron'a skoczy do ok. 10k, zależnie od ilości podstron zapisanych w plikach) więc różnica nawet niecałej sekundy może dużo dać.