source: trunk/include/functions_search.inc.php @ 10340

Last change on this file since 10340 was 10340, checked in by rvelices, 13 years ago

feature:2248 Improve quick/query search results

  • Property svn:eol-style set to LF
File size: 19.2 KB
Line 
1<?php
2// +-----------------------------------------------------------------------+
3// | Piwigo - a PHP based photo gallery                                    |
4// +-----------------------------------------------------------------------+
5// | Copyright(C) 2008-2011 Piwigo Team                  http://piwigo.org |
6// | Copyright(C) 2003-2008 PhpWebGallery Team    http://phpwebgallery.net |
7// | Copyright(C) 2002-2003 Pierrick LE GALL   http://le-gall.net/pierrick |
8// +-----------------------------------------------------------------------+
9// | This program is free software; you can redistribute it and/or modify  |
10// | it under the terms of the GNU General Public License as published by  |
11// | the Free Software Foundation                                          |
12// |                                                                       |
13// | This program is distributed in the hope that it will be useful, but   |
14// | WITHOUT ANY WARRANTY; without even the implied warranty of            |
15// | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU      |
16// | General Public License for more details.                              |
17// |                                                                       |
18// | You should have received a copy of the GNU General Public License     |
19// | along with this program; if not, write to the Free Software           |
20// | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, |
21// | USA.                                                                  |
22// +-----------------------------------------------------------------------+
23
24
25/**
26 * returns search rules stored into a serialized array in "search"
27 * table. Each search rules set is numericaly identified.
28 *
29 * @param int search_id
30 * @return array
31 */
32function get_search_array($search_id)
33{
34  if (!is_numeric($search_id))
35  {
36    die('Search id must be an integer');
37  }
38
39  $query = '
40SELECT rules
41  FROM '.SEARCH_TABLE.'
42  WHERE id = '.$search_id.'
43;';
44  list($serialized_rules) = pwg_db_fetch_row(pwg_query($query));
45
46  return unserialize($serialized_rules);
47}
48
49/**
50 * returns the SQL clause from a search identifier
51 *
52 * Search rules are stored in search table as a serialized array. This array
53 * need to be transformed into an SQL clause to be used in queries.
54 *
55 * @param array search
56 * @return string
57 */
58function get_sql_search_clause($search)
59{
60  // SQL where clauses are stored in $clauses array during query
61  // construction
62  $clauses = array();
63
64  foreach (array('file','name','comment','author') as $textfield)
65  {
66    if (isset($search['fields'][$textfield]))
67    {
68      $local_clauses = array();
69      foreach ($search['fields'][$textfield]['words'] as $word)
70      {
71        array_push($local_clauses, $textfield." LIKE '%".$word."%'");
72      }
73
74      // adds brackets around where clauses
75      $local_clauses = prepend_append_array_items($local_clauses, '(', ')');
76
77      array_push(
78        $clauses,
79        implode(
80          ' '.$search['fields'][$textfield]['mode'].' ',
81          $local_clauses
82          )
83        );
84    }
85  }
86
87  if (isset($search['fields']['allwords']))
88  {
89    $fields = array('file', 'name', 'comment', 'author');
90    // in the OR mode, request bust be :
91    // ((field1 LIKE '%word1%' OR field2 LIKE '%word1%')
92    // OR (field1 LIKE '%word2%' OR field2 LIKE '%word2%'))
93    //
94    // in the AND mode :
95    // ((field1 LIKE '%word1%' OR field2 LIKE '%word1%')
96    // AND (field1 LIKE '%word2%' OR field2 LIKE '%word2%'))
97    $word_clauses = array();
98    foreach ($search['fields']['allwords']['words'] as $word)
99    {
100      $field_clauses = array();
101      foreach ($fields as $field)
102      {
103        array_push($field_clauses, $field." LIKE '%".$word."%'");
104      }
105      // adds brackets around where clauses
106      array_push(
107        $word_clauses,
108        implode(
109          "\n          OR ",
110          $field_clauses
111          )
112        );
113    }
114
115    array_walk(
116      $word_clauses,
117      create_function('&$s','$s="(".$s.")";')
118      );
119
120    array_push(
121      $clauses,
122      "\n         ".
123      implode(
124        "\n         ".
125              $search['fields']['allwords']['mode'].
126        "\n         ",
127        $word_clauses
128        )
129      );
130  }
131
132  foreach (array('date_available', 'date_creation') as $datefield)
133  {
134    if (isset($search['fields'][$datefield]))
135    {
136      array_push(
137        $clauses,
138        $datefield." = '".$search['fields'][$datefield]['date']."'"
139        );
140    }
141
142    foreach (array('after','before') as $suffix)
143    {
144      $key = $datefield.'-'.$suffix;
145
146      if (isset($search['fields'][$key]))
147      {
148        array_push(
149          $clauses,
150
151          $datefield.
152          ($suffix == 'after'             ? ' >' : ' <').
153          ($search['fields'][$key]['inc'] ? '='  : '').
154          " '".$search['fields'][$key]['date']."'"
155
156          );
157      }
158    }
159  }
160
161  if (isset($search['fields']['cat']))
162  {
163    if ($search['fields']['cat']['sub_inc'])
164    {
165      // searching all the categories id of sub-categories
166      $cat_ids = get_subcat_ids($search['fields']['cat']['words']);
167    }
168    else
169    {
170      $cat_ids = $search['fields']['cat']['words'];
171    }
172
173    $local_clause = 'category_id IN ('.implode(',', $cat_ids).')';
174    array_push($clauses, $local_clause);
175  }
176
177  // adds brackets around where clauses
178  $clauses = prepend_append_array_items($clauses, '(', ')');
179
180  $where_separator =
181    implode(
182      "\n    ".$search['mode'].' ',
183      $clauses
184      );
185
186  $search_clause = $where_separator;
187
188  return $search_clause;
189}
190
191/**
192 * returns the list of items corresponding to the advanced search array
193 *
194 * @param array search
195 * @return array
196 */
197function get_regular_search_results($search, $images_where)
198{
199  global $conf;
200  $forbidden = get_sql_condition_FandF(
201        array
202          (
203            'forbidden_categories' => 'category_id',
204            'visible_categories' => 'category_id',
205            'visible_images' => 'id'
206          ),
207        "\n  AND"
208    );
209
210  $items = array();
211  $tag_items = array();
212
213  if (isset($search['fields']['tags']))
214  {
215    $tag_items = get_image_ids_for_tags(
216      $search['fields']['tags']['words'],
217      $search['fields']['tags']['mode']
218      );
219  }
220
221  $search_clause = get_sql_search_clause($search);
222
223  if (!empty($search_clause))
224  {
225    $query = '
226SELECT DISTINCT(id)
227  FROM '.IMAGES_TABLE.' i
228    INNER JOIN '.IMAGE_CATEGORY_TABLE.' AS ic ON id = ic.image_id
229  WHERE '.$search_clause;
230    if (!empty($images_where))
231    {
232      $query .= "\n  AND ".$images_where;
233    }
234    $query .= $forbidden.'
235  '.$conf['order_by'];
236    $items = array_from_query($query, 'id');
237  }
238
239  if ( !empty($tag_items) )
240  {
241    switch ($search['mode'])
242    {
243      case 'AND':
244        if (empty($search_clause))
245        {
246          $items = $tag_items;
247        }
248        else
249        {
250          $items = array_values( array_intersect($items, $tag_items) );
251        }
252        break;
253      case 'OR':
254        $before_count = count($items);
255        $items = array_unique(
256          array_merge(
257            $items,
258            $tag_items
259            )
260          );
261        break;
262    }
263  }
264
265  return $items;
266}
267
268
269if (function_exists('mb_strtolower'))
270{
271  function transliterate($term)
272  {
273    return remove_accents( mb_strtolower($term) );
274  }
275}
276else
277{
278  function transliterate($term)
279  {
280    return remove_accents( strtolower($term) );
281  }
282}
283
284function is_word_char($ch)
285{
286  return ($ch>='0' && $ch<='9') || ($ch>='a' && $ch<='z') || ($ch>='A' && $ch<='Z') || ord($ch)>127;
287}
288
289/**
290 * analyzes and splits the quick/query search query $q into tokens
291 * q='john bill' => 2 tokens 'john' 'bill'
292 * Special characters for MySql full text search (+,<,>,~) appear in the token modifiers.
293 * The query can contain a phrase: 'Pierre "New York"' will return 'pierre' qnd 'new york'.
294 */
295function analyse_qsearch($q, &$qtokens, &$qtoken_modifiers)
296{
297  $q = stripslashes($q);
298  $tokens = array();
299  $token_modifiers = array();
300  $crt_token = "";
301  $crt_token_modifier = "";
302  $state = 0;
303
304  for ($i=0; $i<strlen($q); $i++)
305  {
306    $ch = $q[$i];
307    switch ($state)
308    {
309      case 0:
310        if ($ch=='"')
311        {
312          $tokens[] = $crt_token; $token_modifiers[] = $crt_token_modifier;
313          $crt_token = ""; $crt_token_modifier = "q";
314          $state=1;
315        }
316        elseif ( $ch=='*' )
317        { // wild card
318          if (strlen($crt_token))
319          {
320            $crt_token .= $ch;
321          }
322          else
323          {
324            $crt_token_modifier .= '*';
325          }
326        }
327        elseif ( strcspn($ch, '+-><~')==0 )
328        { //special full text modifier
329          if (strlen($crt_token))
330          {
331            $tokens[] = $crt_token; $token_modifiers[] = $crt_token_modifier;
332            $crt_token = ""; $crt_token_modifier = "";
333          }
334          $crt_token_modifier .= $ch;
335        }
336        elseif (preg_match('/[\s,.;!\?]+/', $ch))
337        { // white space
338          if (strlen($crt_token))
339          {
340            $tokens[] = $crt_token; $token_modifiers[] = $crt_token_modifier;
341            $crt_token = ""; $crt_token_modifier = "";
342          }
343        }
344        else
345        {
346          $crt_token .= $ch;
347        }
348        break;
349      case 1: // qualified with quotes
350        switch ($ch)
351        {
352          case '"':
353            $tokens[] = $crt_token; $token_modifiers[] = $crt_token_modifier;
354            $crt_token = ""; $crt_token_modifier = "";
355            $state=0;
356            break;
357          default:
358            $crt_token .= $ch;
359        }
360        break;
361    }
362  }
363  if (strlen($crt_token))
364  {
365    $tokens[] = $crt_token;
366    $token_modifiers[] = $crt_token_modifier;
367  }
368
369  $qtokens = array();
370  $qtoken_modifiers = array();
371  for ($i=0; $i<count($tokens); $i++)
372  {
373    if (strstr($token_modifiers[$i], 'q')===false)
374    {
375      if ( substr($tokens[$i], -1)=='*' )
376      {
377        $tokens[$i] = rtrim($tokens[$i], '*');
378        $token_modifiers[$i] .= '*';
379      }
380    }
381    if ( strlen($tokens[$i])==0)
382      continue;
383    $qtokens[] = $tokens[$i];
384    $qtoken_modifiers[] = $token_modifiers[$i];
385  }
386}
387
388
389/**
390 * returns the LIKE sql clause corresponding to the quick search query
391 * that has been split into tokens
392 * for example file LIKE '%john%' OR file LIKE '%bill%'.
393 */
394function get_qsearch_like_clause($tokens, $token_modifiers, $field)
395{
396  $clauses = array();
397  for ($i=0; $i<count($tokens); $i++)
398  {
399    $token = trim($tokens[$i], '%');
400    if (strstr($token_modifiers[$i], '-')!==false)
401      continue;
402    if ( strlen($token==0) )
403      continue;
404    $token = addslashes($token);
405    $token = str_replace( array('%','_'), array('\\%','\\_'), $token); // escape LIKE specials %_
406    $clauses[] = $field.' LIKE \'%'.$token.'%\'';
407  }
408
409  return count($clauses) ? '('.implode(' OR ', $clauses).')' : null;
410}
411
412/**
413 * returns the search results corresponding to a quick/query search.
414 * A quick/query search returns many items (search is not strict), but results
415 * are sorted by relevance unless $super_order_by is true. Returns:
416 * array (
417 * 'items' => array(85,68,79...)
418 * 'qs'    => array(
419 *    'matching_tags' => array of matching tags
420 *    'matching_cats' => array of matching categories
421 *    'matching_cats_no_images' =>array(99) - matching categories without images
422 *      ))
423 *
424 * @param string q
425 * @param bool super_order_by
426 * @param string images_where optional aditional restriction on images table
427 * @return array
428 */
429function get_quick_search_results($q, $super_order_by, $images_where='')
430{
431  global $user, $conf;
432
433  $search_results =
434    array(
435      'items' => array(),
436      'qs' => array('q'=>stripslashes($q)),
437    );
438  $q = trim($q);
439  if (empty($q))
440  {
441    return $search_results;
442  }
443 
444  analyse_qsearch($q, $tokens, $token_modifiers);
445
446  $q_like_field = '@@__db_field__@@'; //something never in a search
447  $q_like_clause = get_qsearch_like_clause($tokens, $token_modifiers, $q_like_field );
448
449  // Step 1 - first we find matches in #images table ===========================
450  $where_clauses='MATCH(i.name, i.comment) AGAINST( \''.$q.'\' IN BOOLEAN MODE)';
451  if (!empty($q_like_clause))
452  {
453    $where_clauses .= '
454    OR '. str_replace($q_like_field, 'CONVERT(file, CHAR)', $q_like_clause);
455    $where_clauses = '('.$where_clauses.')';
456  }
457  $where_clauses = array($where_clauses);
458  if (!empty($images_where))
459  {
460    $where_clauses[]='('.$images_where.')';
461  }
462  $where_clauses[] .= get_sql_condition_FandF
463      (
464        array( 'visible_images' => 'i.id' ), null, true
465      );
466  $query = '
467SELECT i.id,
468    MATCH(i.name, i.comment) AGAINST( \''.$q.'\' IN BOOLEAN MODE) AS weight
469  FROM '.IMAGES_TABLE.' i
470  WHERE '.implode("\n AND ", $where_clauses);
471
472  $by_weights=array();
473  $result = pwg_query($query);
474  while ($row = pwg_db_fetch_assoc($result))
475  { // weight is important when sorting images by relevance
476    if ($row['weight'])
477    {
478      $by_weights[(int)$row['id']] =  2*$row['weight'];
479    }
480    else
481    {//full text does not match but file name match
482      $by_weights[(int)$row['id']] =  2;
483    }
484  }
485
486
487  // Step 2 - search tags corresponding to the query $q ========================
488  $transliterated_tokens = array();
489  $token_tags = array();
490  foreach ($tokens as $token)
491  {
492    $transliterated_tokens[] = transliterate($token);
493    $token_tags[] = array();
494  }
495
496  // Step 2.1 - find match tags for every token in the query search
497  $all_tags = array();
498  $query = '
499SELECT id, name, url_name, COUNT(image_id) AS nb_images
500  FROM '.TAGS_TABLE.'
501    INNER JOIN '.IMAGE_TAG_TABLE.' ON id=tag_id
502  GROUP BY id';
503  $result = pwg_query($query);
504  while ($tag = pwg_db_fetch_assoc($result))
505  {
506    $transliterated_tag = transliterate($tag['name']);
507
508    // find how this tag matches query tokens
509    for ($i=0; $i<count($tokens); $i++)
510    {
511      if (strstr($token_modifiers[$i], '-')!==false)
512        continue;// ignore this NOT token
513      $transliterated_token = $transliterated_tokens[$i];
514
515      $match = false;
516      $pos = 0;
517      while ( ($pos = strpos($transliterated_tag, $transliterated_token, $pos)) !== false)
518      {
519        if (strstr($token_modifiers[$i], '*')!==false)
520        {// wildcard in this token
521          $match = 1;
522          break;
523        }
524        $token_len = strlen($transliterated_token);
525
526        $word_begin = $pos;
527        while ($word_begin>0)
528        {
529          if (! is_word_char($transliterated_tag[$word_begin-1]) )
530            break;
531          $word_begin--;
532        }
533
534        $word_end = $pos + $token_len;
535        while ($word_end<strlen($transliterated_tag) && is_word_char($transliterated_tag[$word_end]) )
536          $word_end++;
537
538        $this_score = $token_len / ($word_end-$word_begin);
539        if ($token_len <= 2)
540        {// search for 1 or 2 characters must match exactly to avoid retrieving too much data
541          if ($token_len != $word_end-$word_begin)
542            $this_score = 0;
543        }
544        elseif ($token_len == 3)
545        {
546          if ($word_end-$word_begin > 4)
547            $this_score = 0;
548        }
549
550        if ($this_score>0)
551          $match = max($match, $this_score );
552        $pos++;
553      }
554
555      if ($match)
556      {
557        $tag_id = (int)$tag['id'];
558        $all_tags[$tag_id] = $tag;
559        $token_tags[$i][] = array('tag_id'=>$tag_id, 'score'=>$match);
560      }
561    }
562  }
563  $search_results['qs']['matching_tags']=$all_tags;
564
565  // Step 2.2 - reduce matching tags for every token in the query search
566  $score_cmp_fn = create_function('$a,$b', 'return 100*($b["score"]-$a["score"]);');
567  foreach ($token_tags as &$tt)
568  {
569    usort($tt, $score_cmp_fn);
570    $nb_images = 0;
571    $prev_score = 0;
572    for ($j=0; $j<count($tt); $j++)
573    {
574      if ($nb_images > 200 && $prev_score > $tt[$j]['score'] )
575      {// "many" images in previous tags and starting from this tag is less relevent
576        $tt = array_slice( $tt, 0, $j);
577        break;
578      }
579      $nb_images += $all_tags[ $tt[$j]['tag_id'] ]['nb_images'];
580      $prev_score = $tt[$j]['score'];
581    }
582  }
583
584  // Step 2.3 - get the images for tags
585  for ($i=0; $i<count($token_tags); $i++)
586  {
587    $tag_ids = array();
588    foreach($token_tags[$i] as $arr)
589      $tag_ids[] = $arr['tag_id'];
590
591    if (!empty($tag_ids))
592    {
593      $query = '
594SELECT image_id
595  FROM '.IMAGE_TAG_TABLE.'
596  WHERE tag_id IN ('.implode(',',$tag_ids).')
597  GROUP BY image_id';
598      $result = pwg_query($query);
599      while ($row = pwg_db_fetch_assoc($result))
600      { // weight is important when sorting images by relevance
601        $image_id=(int)$row['image_id'];
602        @$by_weights[$image_id] += 1;
603      }
604    }
605  }
606
607  // Step 3 - search categories corresponding to the query $q ==================
608  $query = '
609SELECT id, name, permalink, nb_images
610  FROM '.CATEGORIES_TABLE.'
611    INNER JOIN '.USER_CACHE_CATEGORIES_TABLE.' ON id=cat_id
612  WHERE user_id='.$user['id'].'
613    AND MATCH(name, comment) AGAINST( \''.$q.'\' IN BOOLEAN MODE)'.
614  get_sql_condition_FandF (
615      array( 'visible_categories' => 'cat_id' ), "\n    AND"
616    );
617  $result = pwg_query($query);
618  while ($row = pwg_db_fetch_assoc($result))
619  { // weight is important when sorting images by relevance
620    if ($row['nb_images']==0)
621    {
622      $search_results['qs']['matching_cats_no_images'][] = $row;
623    }
624    else
625    {
626      $search_results['qs']['matching_cats'][$row['id']] = $row;
627    }
628  }
629
630  if ( empty($by_weights) and empty($search_results['qs']['matching_cats']) )
631  {
632    return $search_results;
633  }
634
635  // Step 4 - now we have $by_weights ( array image id => weight ) that need
636  // permission checks and/or matching categories to get images from
637  $where_clauses = array();
638  if ( !empty($by_weights) )
639  {
640    $where_clauses[]='i.id IN ('
641      . implode(',', array_keys($by_weights)) . ')';
642  }
643  if ( !empty($search_results['qs']['matching_cats']) )
644  {
645    $where_clauses[]='category_id IN ('.
646      implode(',',array_keys($search_results['qs']['matching_cats'])).')';
647  }
648  $where_clauses = array( '('.implode("\n    OR ",$where_clauses).')' );
649  if (!empty($images_where))
650  {
651    $where_clauses[]='('.$images_where.')';
652  }
653  $where_clauses[] = get_sql_condition_FandF(
654      array
655        (
656          'forbidden_categories' => 'category_id',
657          'visible_categories' => 'category_id',
658          'visible_images' => 'i.id'
659        ),
660      null,true
661    );
662
663  $query = '
664SELECT DISTINCT(id)
665  FROM '.IMAGES_TABLE.' i
666    INNER JOIN '.IMAGE_CATEGORY_TABLE.' AS ic ON id = ic.image_id
667  WHERE '.implode("\n AND ", $where_clauses)."\n".
668  $conf['order_by'];
669
670  $allowed_images = array_from_query( $query, 'id');
671
672  if ( $super_order_by or empty($by_weights) )
673  {
674    $search_results['items'] = $allowed_images;
675    return $search_results;
676  }
677
678  $allowed_images = array_flip( $allowed_images );
679  $divisor = 5.0 * count($allowed_images);
680  foreach ($allowed_images as $id=>$rank )
681  {
682    $weight = isset($by_weights[$id]) ? $by_weights[$id] : 1;
683    $weight -= $rank/$divisor;
684    $allowed_images[$id] = $weight;
685  }
686  arsort($allowed_images, SORT_NUMERIC);
687  $search_results['items'] = array_keys($allowed_images);
688  return $search_results;
689}
690
691/**
692 * returns an array of 'items' corresponding to the search id
693 *
694 * @param int search id
695 * @param string images_where optional aditional restriction on images table
696 * @return array
697 */
698function get_search_results($search_id, $super_order_by, $images_where='')
699{
700  $search = get_search_array($search_id);
701  if ( !isset($search['q']) )
702  {
703    $result['items'] = get_regular_search_results($search, $images_where);
704    return $result;
705  }
706  else
707  {
708    return get_quick_search_results($search['q'], $super_order_by, $images_where);
709  }
710}
711?>
Note: See TracBrowser for help on using the repository browser.