Sprawdzanie na stronie słów kluczowych Opcje

[than]

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?

[Cotter]

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.

Ten post edytował Cotter 22.01.2008, 23:13:40