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

Last change on this file since 18464 was 18207, checked in by rvelices, 12 years ago

quick search - better handling of wildcard begin/end in tag names (technically rewrote parts of query analser)
still to do: exclusion of matching tags
  • Property svn:eol-style set to LF
File size: 20.7 KB
Line 
1<?php
2// +-----------------------------------------------------------------------+
3// | Piwigo - a PHP based photo gallery                                    |
4// +-----------------------------------------------------------------------+
5// | Copyright(C) 2008-2012 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
269function is_word_char($ch)
270{
271  return ($ch>='0' && $ch<='9') || ($ch>='a' && $ch<='z') || ($ch>='A' && $ch<='Z') || ord($ch)>127;
272}
273
274function is_odd_wbreak_begin($ch)
275{
276  return strpos('[{<=*+', $ch)===false ? false:true;
277}
278
279function is_odd_wbreak_end($ch)
280{
281  return strpos(']}>=*+', $ch)===false ? false:true;
282}
283
284define('QST_QUOTED',   0x01);
285define('QST_NOT',      0x02);
286define('QST_WILDCARD_BEGIN',0x04);
287define('QST_WILDCARD_END',  0x08);
288define('QST_WILDCARD', QST_WILDCARD_BEGIN|QST_WILDCARD_END);
289
290
291/**
292 * analyzes and splits the quick/query search query $q into tokens
293 * q='john bill' => 2 tokens 'john' 'bill'
294 * Special characters for MySql full text search (+,<,>,~) appear in the token modifiers.
295 * The query can contain a phrase: 'Pierre "New York"' will return 'pierre' qnd 'new york'.
296 */
297function analyse_qsearch($q, &$qtokens, &$qtoken_modifiers)
298{
299  $q = stripslashes($q);
300  $tokens = array();
301  $token_modifiers = array();
302  $crt_token = "";
303  $crt_token_modifier = 0;
304
305  for ($i=0; $i<strlen($q); $i++)
306  {
307    $ch = $q[$i];
308    if ($crt_token_modifier&QST_QUOTED==0)
309    {
310        if ($ch=='"')
311        {
312          if (strlen($crt_token))
313          {
314            $tokens[] = $crt_token; $token_modifiers[] = $crt_token_modifier;
315            $crt_token = ""; $crt_token_modifier = 0;
316          }
317          $crt_token_modifier |= QST_QUOTED;
318        }
319        elseif ( strcspn($ch, '*+-><~')==0 )
320        { //special full text modifier
321          if (strlen($crt_token))
322          {
323            $crt_token .= $ch;
324          }
325          else
326          {
327            if ( $ch=='*' )
328              $crt_token_modifier |= QST_WILDCARD_BEGIN;
329            if ( $ch=='-' )
330              $crt_token_modifier |= QST_NOT;
331          }
332        }
333        elseif (preg_match('/[\s,.;!\?]+/', $ch))
334        { // white space
335          if (strlen($crt_token))
336          {
337            $tokens[] = $crt_token; $token_modifiers[] = $crt_token_modifier;
338            $crt_token = "";
339          }
340          $crt_token_modifier = 0;
341        }
342        else
343        {
344          $crt_token .= $ch;
345        }
346    }
347    else // qualified with quotes
348    {
349      if ($ch=='"')
350      {
351        if ($i+1 < strlen($q) && $q[$i+1]=='*')
352        {
353          $crt_token_modifier |= QST_WILDCARD_END;
354          $i++;
355        }
356        $tokens[] = $crt_token; $token_modifiers[] = $crt_token_modifier;
357        $crt_token = ""; $crt_token_modifier = 0;
358        $state=0;
359        break;
360      }
361      else
362        $crt_token .= $ch;
363    }
364  }
365  if (strlen($crt_token))
366  {
367    $tokens[] = $crt_token;
368    $token_modifiers[] = $crt_token_modifier;
369  }
370
371  $qtokens = array();
372  $qtoken_modifiers = array();
373  for ($i=0; $i<count($tokens); $i++)
374  {
375    if (strstr($token_modifiers[$i], 'q')===false)
376    {
377      if ( substr($tokens[$i], -1)=='*' )
378      {
379        $tokens[$i] = rtrim($tokens[$i], '*');
380        $token_modifiers[$i] .= '*';
381      }
382    }
383    if ( strlen($tokens[$i])==0)
384      continue;
385    $qtokens[] = $tokens[$i];
386    $qtoken_modifiers[] = $token_modifiers[$i];
387  }
388}
389
390
391/**
392 * returns the LIKE sql clause corresponding to the quick search query
393 * that has been split into tokens
394 * for example file LIKE '%john%' OR file LIKE '%bill%'.
395 */
396function get_qsearch_like_clause($tokens, $token_modifiers, $field)
397{
398  $clauses = array();
399  for ($i=0; $i<count($tokens); $i++)
400  {
401    $token = trim($tokens[$i], '%');
402    if ($token_modifiers[$i]&QST_NOT)
403      continue;
404    if ( strlen($token)==0 )
405      continue;
406    $token = addslashes($token);
407    $token = str_replace( array('%','_'), array('\\%','\\_'), $token); // escape LIKE specials %_
408    $clauses[] = $field.' LIKE \'%'.$token.'%\'';
409  }
410
411  return count($clauses) ? '('.implode(' OR ', $clauses).')' : null;
412}
413
414/**
415 * returns the search results corresponding to a quick/query search.
416 * A quick/query search returns many items (search is not strict), but results
417 * are sorted by relevance unless $super_order_by is true. Returns:
418 * array (
419 * 'items' => array(85,68,79...)
420 * 'qs'    => array(
421 *    'matching_tags' => array of matching tags
422 *    'matching_cats' => array of matching categories
423 *    'matching_cats_no_images' =>array(99) - matching categories without images
424 *      ))
425 *
426 * @param string q
427 * @param bool super_order_by
428 * @param string images_where optional aditional restriction on images table
429 * @return array
430 */
431function get_quick_search_results($q, $super_order_by, $images_where='')
432{
433  global $user, $conf;
434
435  $search_results =
436    array(
437      'items' => array(),
438      'qs' => array('q'=>stripslashes($q)),
439    );
440  $q = trim($q);
441  analyse_qsearch($q, $tokens, $token_modifiers);
442  if (count($tokens)==0)
443  {
444    return $search_results;
445  }
446  $debug[] = '<!--'.count($tokens).' tokens';
447 
448  $q_like_field = '@@__db_field__@@'; //something never in a search
449  $q_like_clause = get_qsearch_like_clause($tokens, $token_modifiers, $q_like_field );
450
451  // Step 1 - first we find matches in #images table ===========================
452  $where_clauses='MATCH(i.name, i.comment) AGAINST( \''.$q.'\' IN BOOLEAN MODE)';
453  if (!empty($q_like_clause))
454  {
455    $where_clauses .= '
456    OR '. str_replace($q_like_field, 'CONVERT(file, CHAR)', $q_like_clause);
457    $where_clauses = '('.$where_clauses.')';
458  }
459  $where_clauses = array($where_clauses);
460  if (!empty($images_where))
461  {
462    $where_clauses[]='('.$images_where.')';
463  }
464  $where_clauses[] .= get_sql_condition_FandF
465      (
466        array( 'visible_images' => 'i.id' ), null, true
467      );
468  $query = '
469SELECT i.id,
470    MATCH(i.name, i.comment) AGAINST( \''.$q.'\' IN BOOLEAN MODE) AS weight
471  FROM '.IMAGES_TABLE.' i
472  WHERE '.implode("\n AND ", $where_clauses);
473
474  $by_weights=array();
475  $result = pwg_query($query);
476  while ($row = pwg_db_fetch_assoc($result))
477  { // weight is important when sorting images by relevance
478    if ($row['weight'])
479    {
480      $by_weights[(int)$row['id']] =  2*$row['weight'];
481    }
482    else
483    {//full text does not match but file name match
484      $by_weights[(int)$row['id']] =  2;
485    }
486  }
487  $debug[] = count($by_weights).' fulltext';
488  $debug[] = 'ft score min:'.min($by_weights).' max:'.max($by_weights);
489
490
491  // Step 2 - search tags corresponding to the query $q ========================
492  $transliterated_tokens = array();
493  $token_tags = array();
494  foreach ($tokens as $token)
495  {
496    $transliterated_tokens[] = transliterate($token);
497    $token_tags[] = array();
498  }
499
500  // Step 2.1 - find match tags for every token in the query search
501  $all_tags = array();
502  $query = '
503SELECT id, name, url_name, COUNT(image_id) AS nb_images
504  FROM '.TAGS_TABLE.'
505    INNER JOIN '.IMAGE_TAG_TABLE.' ON id=tag_id
506  GROUP BY id';
507  $result = pwg_query($query);
508  while ($tag = pwg_db_fetch_assoc($result))
509  {
510    $transliterated_tag = transliterate($tag['name']);
511
512    // find how this tag matches query tokens
513    for ($i=0; $i<count($tokens); $i++)
514    {
515      if ($token_modifiers[$i]&QST_NOT)
516        continue;// ignore this NOT token
517      $transliterated_token = $transliterated_tokens[$i];
518
519      $match = false;
520      $pos = 0;
521      while ( ($pos = strpos($transliterated_tag, $transliterated_token, $pos)) !== false)
522      {
523        if ( ($token_modifiers[$i]&QST_WILDCARD)==QST_WILDCARD )
524        {// wildcard in this token
525          $match = 1;
526          break;
527        }
528        $token_len = strlen($transliterated_token);
529
530        // search begin of word
531        $wbegin_len=0; $wbegin_char=' ';
532        while ($pos-$wbegin_len > 0)
533        {
534          if (! is_word_char($transliterated_tag[$pos-$wbegin_len-1]) )
535          {
536            $wbegin_char = $transliterated_tag[$pos-$wbegin_len-1];
537            break;
538          }
539          $wbegin_len++;
540        }
541
542        // search end of word
543        $wend_len=0; $wend_char=' ';
544        while ($pos+$token_len+$wend_len < strlen($transliterated_tag))
545        {
546          if (! is_word_char($transliterated_tag[$pos+$token_len+$wend_len]) )
547          {
548            $wend_char = $transliterated_tag[$pos+$token_len+$wend_len];
549            break;
550          }
551          $wend_len++;
552        }
553
554        $this_score = 0;
555        if ( ($token_modifiers[$i]&QST_WILDCARD)==0 )
556        {// no wildcard begin or end
557          if ($token_len <= 2)
558          {// search for 1 or 2 characters must match exactly to avoid retrieving too much data
559            if ($wbegin_len==0 && $wend_len==0 && !is_odd_wbreak_begin($wbegin_char) && !is_odd_wbreak_end($wend_char) )
560              $this_score = 1;
561          }
562          elseif ($token_len == 3)
563          {
564            if ($wbegin_len==0)
565              $this_score = $token_len / ($token_len + $wend_len);
566          }
567          else
568          {
569            $this_score = $token_len / ($token_len + 1.1 * $wbegin_len + 0.9 * $wend_len);
570          }
571        }
572
573        if ($this_score>0)
574          $match = max($match, $this_score );
575        $pos++;
576      }
577
578      if ($match)
579      {
580        $tag_id = (int)$tag['id'];
581        $all_tags[$tag_id] = $tag;
582        $token_tags[$i][] = array('tag_id'=>$tag_id, 'score'=>$match);
583      }
584    }
585  }
586  $search_results['qs']['matching_tags']=$all_tags;
587  $debug[] = count($all_tags).' tags';
588
589  // Step 2.2 - reduce matching tags for every token in the query search
590  $score_cmp_fn = create_function('$a,$b', 'return 100*($b["score"]-$a["score"]);');
591  foreach ($token_tags as &$tt)
592  {
593    usort($tt, $score_cmp_fn);
594    $nb_images = 0;
595    $prev_score = 0;
596    for ($j=0; $j<count($tt); $j++)
597    {
598      if ($nb_images > 200 && $prev_score > $tt[$j]['score'] )
599      {// "many" images in previous tags and starting from this tag is less relevent
600        $tt = array_slice( $tt, 0, $j);
601        break;
602      }
603      $nb_images += $all_tags[ $tt[$j]['tag_id'] ]['nb_images'];
604      $prev_score = $tt[$j]['score'];
605    }
606  }
607
608  // Step 2.3 - get the images for tags
609  for ($i=0; $i<count($token_tags); $i++)
610  {
611    $tag_ids = array();
612    foreach($token_tags[$i] as $arr)
613      $tag_ids[] = $arr['tag_id'];
614    $tag_ids = array_unique($tag_ids);
615    $debug[] = count($tag_ids).' unique tags';
616
617    if (!empty($tag_ids))
618    {
619      $tag_photo_count=0;
620      $query = '
621SELECT image_id
622  FROM '.IMAGE_TAG_TABLE.'
623  WHERE tag_id IN ('.implode(',',$tag_ids).')
624  GROUP BY image_id';
625      $result = pwg_query($query);
626      while ($row = pwg_db_fetch_assoc($result))
627      { // weight is important when sorting images by relevance
628        $image_id=(int)$row['image_id'];
629        @$by_weights[$image_id] += 1;
630        $tag_photo_count++;
631      }
632      $debug[] = $tag_photo_count.' photos for tags';
633      $debug[] = count($by_weights).' photos after tags';
634    }
635  }
636
637  // Step 3 - search categories corresponding to the query $q ==================
638  $query = '
639SELECT id, name, permalink, nb_images
640  FROM '.CATEGORIES_TABLE.'
641    INNER JOIN '.USER_CACHE_CATEGORIES_TABLE.' ON id=cat_id
642  WHERE user_id='.$user['id'].'
643    AND MATCH(name, comment) AGAINST( \''.$q.'\' IN BOOLEAN MODE)'.
644  get_sql_condition_FandF (
645      array( 'visible_categories' => 'cat_id' ), "\n    AND"
646    );
647  $result = pwg_query($query);
648  while ($row = pwg_db_fetch_assoc($result))
649  { // weight is important when sorting images by relevance
650    if ($row['nb_images']==0)
651    {
652      $search_results['qs']['matching_cats_no_images'][] = $row;
653    }
654    else
655    {
656      $search_results['qs']['matching_cats'][$row['id']] = $row;
657    }
658  }
659  $debug[] = count(@$search_results['qs']['matching_cats']).' albums with images';
660
661  if ( empty($by_weights) and empty($search_results['qs']['matching_cats']) )
662  {
663    return $search_results;
664  }
665
666  // Step 4 - now we have $by_weights ( array image id => weight ) that need
667  // permission checks and/or matching categories to get images from
668  $where_clauses = array();
669  if ( !empty($by_weights) )
670  {
671    $where_clauses[]='i.id IN ('
672      . implode(',', array_keys($by_weights)) . ')';
673  }
674  if ( !empty($search_results['qs']['matching_cats']) )
675  {
676    $where_clauses[]='category_id IN ('.
677      implode(',',array_keys($search_results['qs']['matching_cats'])).')';
678  }
679  $where_clauses = array( '('.implode("\n    OR ",$where_clauses).')' );
680  if (!empty($images_where))
681  {
682    $where_clauses[]='('.$images_where.')';
683  }
684  $where_clauses[] = get_sql_condition_FandF(
685      array
686        (
687          'forbidden_categories' => 'category_id',
688          'visible_categories' => 'category_id',
689          'visible_images' => 'i.id'
690        ),
691      null,true
692    );
693
694  $query = '
695SELECT DISTINCT(id)
696  FROM '.IMAGES_TABLE.' i
697    INNER JOIN '.IMAGE_CATEGORY_TABLE.' AS ic ON id = ic.image_id
698  WHERE '.implode("\n AND ", $where_clauses)."\n".
699  $conf['order_by'];
700
701  $allowed_images = array_from_query( $query, 'id');
702
703  $debug[] = count($allowed_images).' final photo count -->';
704  global $template;
705  $template->append('footer_elements', implode(', ', $debug) );
706
707  if ( $super_order_by or empty($by_weights) )
708  {
709    $search_results['items'] = $allowed_images;
710    return $search_results;
711  }
712
713  $allowed_images = array_flip( $allowed_images );
714  $divisor = 5.0 * count($allowed_images);
715  foreach ($allowed_images as $id=>$rank )
716  {
717    $weight = isset($by_weights[$id]) ? $by_weights[$id] : 1;
718    $weight -= $rank/$divisor;
719    $allowed_images[$id] = $weight;
720  }
721  arsort($allowed_images, SORT_NUMERIC);
722  $search_results['items'] = array_keys($allowed_images);
723  return $search_results;
724}
725
726/**
727 * returns an array of 'items' corresponding to the search id
728 *
729 * @param int search id
730 * @param string images_where optional aditional restriction on images table
731 * @return array
732 */
733function get_search_results($search_id, $super_order_by, $images_where='')
734{
735  $search = get_search_array($search_id);
736  if ( !isset($search['q']) )
737  {
738    $result['items'] = get_regular_search_results($search, $images_where);
739    return $result;
740  }
741  else
742  {
743    return get_quick_search_results($search['q'], $super_order_by, $images_where);
744  }
745}
746?>
Note: See TracBrowser for help on using the repository browser.