Fartat.com

Algoritm de cautare si ordonare dupa relevanta in php

in Php, mysql si altele, Web - 02.10.2009

De curand am fost nevoit sa fac un algortim de cautare a unor produse ceva mai special. Iata ce idee mi-a venit si ce am reusit sa fac.

Sa zicem ca facem o cautare dupa “amplificator cablu si antena tv”. Facand aceasta cautare cu o simpla spargere in cuvinte si folosind LIKE ‘%cuvant%’ in mysql se pare ca nu vom obtine o ordine foarte ok, insa vom obtine rezultatele de care avem nevoie. Daca sa zicem cautarea a intors peste 100 de rezultate, trebuie afisate produsele cele mai apropiate de cautarea efectuata.

Dupa ce sunt puse rezultatele cautarii intr-un vector, algoritmul le prelucreaza astfel:

1. Primele inregistrari si cele mai importate vor fi cele care au toate cuvintele in titlu si in aceasi ordine (nu conteaza daca au intre ele caractere ciudate sau spatii, precum ignora si anumite cuvinte mici, gen: “si”, “ca”, “de”…)

2. Dupa aceea se fac urmatoarele combinatii de cuvinte: “amplificator cablu”, “amplificator antena”, “amplificator tv”, “amplificator cablu antena”, “amplificator cablu tv”, “amplificator antena tv”, “cablu antena”, “cablu antena tv”, “cablu tv”, “antena tv”. Cu alte cuvinte se formeaza combinatii intre cuvinte insa numai de la stanga spre dreapta. Un exemplu mai simplu: 1, 2, 3, 4. Combinatiile posibile vor fi 1 2, 1 3, 1 4, 1 2 3, 1 2 4, 1 3 4, 2 3, 2 4, 2 3 4, 3 4. Daca am face combinatii sau permutari intre cuvinte am obtine mai multe variante insa si multe irelevante (si-asa unele sunt irelevante), de exemplu am obtine “tv antena”, sau “tv amplificator” care in general sunt folosite invers. Am mers pe ideea ca la fel cum un user ii da un nume logic produsului sau, la fel si cautarea va fi destul de logica, insa de ce nu, la urma urmei pot fi incluse si acele combinatii de cuvinte.

Dupa ce am format un vector cu combinatiile obtinute, sortam elementele  in ordine descrescatoare a numerelor de cuvinte (intai cele cu 4 cuvinte, apoi cu 3 …) si pentru fiecare grup de cuvinte vedem daca sunt produse dupa aceeasi regula ca mai sus la punctul 1.

3. Acum se vor face combinatii de cuvinte ca la pasul 2 si sortate in functie de numarul de cuvinte descrescator, insa vor fi cautate separat, nu ca o intreaga sintagma. Adica, pentru combinatia “amplificator”, “cablu”, “tv” conditia ca produsul sa fie selectat este ca in titlu sa fie cuvantul “amplificator” si cuvantul “cablu” si cuvantul “tv”, nu conteaza in ce ordine.

4. Cautarea se face si pentru cate un sigur cuvant in ordinea descrescatoare a numarului de caractere:  “amplificator”, “antena”, “cablu”, “tv” si pentru fiecare cuvint scoate produsele care au acest cuvant in titlu (de ce in ordine descresctoare? pentru ca am vazut ca in general cuvintele mici sunt foarte comune,  in cazul nostru “tv” care ar aparea in multe alte tipuri de produse).

5. Dupa accea scoate restul de produse care au in descriere, dar nu in titlu (pentru ca automat au fost eliminate in situatiile de mai sus) sintagma completa cautata, sau cuvintele din sintagma.

Iata si scriptul. Evident ca scriptul poate fi imbunatatit. Se pot adauga sinonime (ex: “mobila”-”mobilier”), sau un mic dictionar de cuvinte gresite (ex: “erore”-”eroare”).

Astept pareri, idei noi, sugestii…

< ?
//functie pentru masurarea a 2 cuvinte
function cmp_len($a, $b){
	return (strlen($a) < strlen($b));
}

//functie pentru realizarea combinatiilor
function permute($array){
	$result=array();
	for($i=0;$i<count($array)-1;$i++){
		for($j=$i+1;$j<count($array);$j++){
			$val="";
			for($k=$i;$k<=$j;$k++){
				$val.=$array[$k]." ";
			}
			$result[]=$val;
		}
	}
	return $result;
}

//functie pentru crearea unui vector de permutari
function permute_as_array($array){
	$result=array();
	for($i=0;$ilgt;count($array)-1;$i++){
		for($j=$i+1;$j<count($array);$j++){
			$val=array();
			for($k=$i;$k<=$j;$k++){
				$val[]=$array[$k];
			}
			$result[]=$val;
		}
	}
	return $result;
}

//functie pentru sortarea vectorului permutat
function sort_array($array){
	$result=array();
	foreach($array as $key=>$val){
		$temp[$key]=count($val);
	}
	arsort($temp);
	foreach($temp as $key=>$val){
		$result[]=$array[$key];
	}
	return $result;
}

//functie pentru eliminarea(inlocuirea) caracterelor special
function generate_name($string)  {
	$to_be_replaced = array('ă'=>'a', 'ţ' => 't', 'î' => 'i', 'ş' => 's');  //aici mai pot fi adaugate multe caractere
	$string = strip_tags($string);
	$string = htmlentities($string, ENT_COMPAT, 'utf-8');
	$string = str_replace( array_keys($to_be_replaced), array_values($to_be_replaced), $string );
	$string = preg_replace("@[^A-Za-z0-9\-]+@i","-",$string);
	$string = preg_replace("@[\-]+@i","-",$string);
	return strtolower(trim($string, '-'));
}  

//cuvintele care vor fi ignorate
$cuvinte_mici = array("pentru", "si", "cu", "de", "la", "pe", "se", "intre", "in", "din", "sa", "fie", "ar", "un");

//incepem cautarea in baza de date
$cautare="amplificator cablu si antena tv";
$words_searched = explode("-",generate_name($cautare)); //scoatem caracterele ",.;:' ...
$fields = array("title","description"); //in ce campuri vom cauta in baza de date

$and_SEARCH = "WHERE ( 0 ";

//cautam intai dupa intreaga sintagma in toate campurile
foreach ($fields as $val){
	$and_SEARCH.=" OR `".$val."` LIKE '%".$cautare."%'";
}

//apoi dupa fiecare cuvant in parte in toate campurile
foreach ($words_searched as $value){
	foreach ($fields as $val){
		if(strlen($value)>1){ //nu ne intereseaza cuvintele care au doar o litera
			$and_SEARCH.=" OR `".$val."` LIKE '%".$value."'";
			$and_SEARCH.=" OR `".$val."` LIKE '%".$value."%'";
			$and_SEARCH.=" OR `".$val."` LIKE '".$value."%'";
		}
	}
}

$and_SEARCH .= ")";   //incheiem sql-ul

//executam interogarea
$produse = mysql_query("SELECT * FROM `produse`".$and_SEARCH, $conn) or die(mysql_error());
//punem inregistrarile intr-un vector
do{
	$all_prod[]=$row_produse;
}while($row_produse = mysql_fetch_array($produse));

//scoatem cuvintele marunte si generale din sintagma noastra
foreach($words_searched as $key_prod => $val_search){
	if(!in_array($val_search, $cuvinte_mici)){
		$new_words_searched[]=$val_search;
	}
}

//formam un nou vector cu ordinea dorita, eliminand ce am gasit din vectorul initial
//cautam intreaga sintagma
foreach ($all_prod as $key_prod=>$val_prod){
	$pozitie = stripos(generate_name($val_prod['title']), generate_name($all_words));
	if ($pozitie !== false) {
		$new_prd[]=$val_prod;
		unset($all_prod[$key_prod]);
	}
}

//sintagma pe bucatele de cuvinte
$search_combination=permute($new_words_searched);  //facem permutarile
usort($search_combination, "cmp_len"); //sortam in ordinea descrescatoare

//acum pentru fiecare sintagma de cuvinte combinate cautam produsele
foreach($search_combination as $val_search){
	foreach ($all_prod as $key_prod=>$val_prod){
		$pozitie = stripos(generate_name($val_prod['title']), generate_name($val_search));
		if ($pozitie !== false) {
			$new_prd[]=$val_prod;
			unset($all_prod[$key_prod]);
		}
	}
}

//combinatii de cuvinte dar cautate separat
$search_combination=permute_as_array($new_words_searched);
$search_combination=sort_array($search_combination);

foreach($search_combination as $val_search){
	foreach ($row_prod_get_de_aranjat as $key_prod=>$val_prod){
		$use_this = 1;
		foreach($val_search as $val_search_deep){
			$pozitie = stripos(generate_name($val_prod['title']), generate_name($val_search_deep));
			if ($pozitie === false) {
				$use_this = 0;
			}
		}
		if ($use_this == 1) {
			$new_prd[]=$val_prod;
			unset($row_prod_get_de_aranjat[$key_prod]);
		}
	}
}

//fiecare cuvant din sintagma in parte sortate in ordinea descrescatoare a marimii cuvantului
usort($new_words_searched, "cmp_len");

foreach($new_words_searched as $val_search){
	foreach ($all_prod as $key_prod=>$val_prod){
		$pozitie = stripos($val_prod['title'], $val_search);
		if ($pozitie !== false) {
			$new_prd[]=$val_prod;
			unset($all_prod[$key_prod]);
		}
	}
}

//ce a mai ramas in vectorul initial sunt cele cu cuvintele casite in descriere
foreach ($all_prod as $key_prod=>$val_prod){
	$new_prd[]=$val_prod;
}

//si acum se pot afisa
print_r($new_prd);
?>