git.roojs.org Git - web.mtrack/blob - Zend/Search/Lucene/Search/Query/Fuzzy.php

   1 <?php
   2 /**
   3  * Zend Framework
   4  *
   5  * LICENSE
   6  *
   7  * This source file is subject to the new BSD license that is bundled
   8  * with this package in the file LICENSE.txt.
   9  * It is also available through the world-wide-web at this URL:
  10  * http://framework.zend.com/license/new-bsd
  11  * If you did not receive a copy of the license and are unable to
  12  * obtain it through the world-wide-web, please send an email
  13  * to license@zend.com so we can send you a copy immediately.
  14  *
  15  * @category   Zend
  16  * @package    Zend_Search_Lucene
  17  * @subpackage Search
  18  * @copyright  Copyright (c) 2005-2009 Zend Technologies USA Inc. (http://www.zend.com)
  19  * @license    http://framework.zend.com/license/new-bsd     New BSD License
  20  * @version    $Id: Fuzzy.php 16971 2009-07-22 18:05:45Z mikaelkael $
  21  */
  22
  23
  24 /** Zend_Search_Lucene_Search_Query */
  25 require_once 'Zend/Search/Lucene/Search/Query.php';
  26
  27 /** Zend_Search_Lucene_Search_Query_MultiTerm */
  28 require_once 'Zend/Search/Lucene/Search/Query/MultiTerm.php';
  29
  30
  31 /**
  32  * @category   Zend
  33  * @package    Zend_Search_Lucene
  34  * @subpackage Search
  35  * @copyright  Copyright (c) 2005-2009 Zend Technologies USA Inc. (http://www.zend.com)
  36  * @license    http://framework.zend.com/license/new-bsd     New BSD License
  37  */
  38 class Zend_Search_Lucene_Search_Query_Fuzzy extends Zend_Search_Lucene_Search_Query
  39 {
  40     /** Default minimum similarity */
  41     const DEFAULT_MIN_SIMILARITY = 0.5;
  42
  43     /**
  44      * Maximum number of matched terms.
  45      * Apache Lucene defines this limitation as boolean query maximum number of clauses:
  46      * org.apache.lucene.search.BooleanQuery.getMaxClauseCount()
  47      */
  48     const MAX_CLAUSE_COUNT = 1024;
  49
  50     /**
  51      * Array of precalculated max distances
  52      *
  53      * keys are integers representing a word size
  54      */
  55     private $_maxDistances = array();
  56
  57     /**
  58      * Base searching term.
  59      *
  60      * @var Zend_Search_Lucene_Index_Term
  61      */
  62     private $_term;
  63
  64     /**
  65      * A value between 0 and 1 to set the required similarity
  66      *  between the query term and the matching terms. For example, for a
  67      *  _minimumSimilarity of 0.5 a term of the same length
  68      *  as the query term is considered similar to the query term if the edit distance
  69      *  between both terms is less than length(term)*0.5
  70      *
  71      * @var float
  72      */
  73     private $_minimumSimilarity;
  74
  75     /**
  76      * The length of common (non-fuzzy) prefix
  77      *
  78      * @var integer
  79      */
  80     private $_prefixLength;
  81
  82     /**
  83      * Matched terms.
  84      *
  85      * Matched terms list.
  86      * It's filled during the search (rewrite operation) and may be used for search result
  87      * post-processing
  88      *
  89      * Array of Zend_Search_Lucene_Index_Term objects
  90      *
  91      * @var array
  92      */
  93     private $_matches = null;
  94
  95     /**
  96      * Matched terms scores
  97      *
  98      * @var array
  99      */
 100     private $_scores = null;
 101
 102     /**
 103      * Array of the term keys.
 104      * Used to sort terms in alphabetical order if terms have the same socres
 105      *
 106      * @var array
 107      */
 108     private $_termKeys = null;
 109
 110     /**
 111      * Default non-fuzzy prefix length
 112      *
 113      * @var integer
 114      */
 115     private static $_defaultPrefixLength = 3;
 116
 117     /**
 118      * Zend_Search_Lucene_Search_Query_Wildcard constructor.
 119      *
 120      * @param Zend_Search_Lucene_Index_Term $term
 121      * @param float   $minimumSimilarity
 122      * @param integer $prefixLength
 123      * @throws Zend_Search_Lucene_Exception
 124      */
 125     public function __construct(Zend_Search_Lucene_Index_Term $term, $minimumSimilarity = self::DEFAULT_MIN_SIMILARITY, $prefixLength = null)
 126     {
 127         if ($minimumSimilarity < 0) {
 128             require_once 'Zend/Search/Lucene/Exception.php';
 129             throw new Zend_Search_Lucene_Exception('minimumSimilarity cannot be less than 0');
 130         }
 131         if ($minimumSimilarity >= 1) {
 132             require_once 'Zend/Search/Lucene/Exception.php';
 133             throw new Zend_Search_Lucene_Exception('minimumSimilarity cannot be greater than or equal to 1');
 134         }
 135         if ($prefixLength < 0) {
 136             require_once 'Zend/Search/Lucene/Exception.php';
 137             throw new Zend_Search_Lucene_Exception('prefixLength cannot be less than 0');
 138         }
 139
 140         $this->_term              = $term;
 141         $this->_minimumSimilarity = $minimumSimilarity;
 142         $this->_prefixLength      = ($prefixLength !== null)? $prefixLength : self::$_defaultPrefixLength;
 143     }
 144
 145     /**
 146      * Get default non-fuzzy prefix length
 147      *
 148      * @return integer
 149      */
 150     public static function getDefaultPrefixLength()
 151     {
 152         return self::$_defaultPrefixLength;
 153     }
 154
 155     /**
 156      * Set default non-fuzzy prefix length
 157      *
 158      * @param integer $defaultPrefixLength
 159      */
 160     public static function setDefaultPrefixLength($defaultPrefixLength)
 161     {
 162         self::$_defaultPrefixLength = $defaultPrefixLength;
 163     }
 164
 165     /**
 166      * Calculate maximum distance for specified word length
 167      *
 168      * @param integer $prefixLength
 169      * @param integer $termLength
 170      * @param integer $length
 171      * @return integer
 172      */
 173     private function _calculateMaxDistance($prefixLength, $termLength, $length)
 174     {
 175         $this->_maxDistances[$length] = (int) ((1 - $this->_minimumSimilarity)*(min($termLength, $length) + $prefixLength));
 176         return $this->_maxDistances[$length];
 177     }
 178
 179     /**
 180      * Re-write query into primitive queries in the context of specified index
 181      *
 182      * @param Zend_Search_Lucene_Interface $index
 183      * @return Zend_Search_Lucene_Search_Query
 184      * @throws Zend_Search_Lucene_Exception
 185      */
 186     public function rewrite(Zend_Search_Lucene_Interface $index)
 187     {
 188         $this->_matches  = array();
 189         $this->_scores   = array();
 190         $this->_termKeys = array();
 191
 192         if ($this->_term->field === null) {
 193             // Search through all fields
 194             $fields = $index->getFieldNames(true /* indexed fields list */);
 195         } else {
 196             $fields = array($this->_term->field);
 197         }
 198
 199         $prefix           = Zend_Search_Lucene_Index_Term::getPrefix($this->_term->text, $this->_prefixLength);
 200         $prefixByteLength = strlen($prefix);
 201         $prefixUtf8Length = Zend_Search_Lucene_Index_Term::getLength($prefix);
 202
 203         $termLength       = Zend_Search_Lucene_Index_Term::getLength($this->_term->text);
 204
 205         $termRest         = substr($this->_term->text, $prefixByteLength);
 206         // we calculate length of the rest in bytes since levenshtein() is not UTF-8 compatible
 207         $termRestLength   = strlen($termRest);
 208
 209         $scaleFactor = 1/(1 - $this->_minimumSimilarity);
 210
 211         $maxTerms = Zend_Search_Lucene::getTermsPerQueryLimit();
 212         foreach ($fields as $field) {
 213             $index->resetTermsStream();
 214
 215             if ($prefix != '') {
 216                 $index->skipTo(new Zend_Search_Lucene_Index_Term($prefix, $field));
 217
 218                 while ($index->currentTerm() !== null          &&
 219                        $index->currentTerm()->field == $field  &&
 220                        substr($index->currentTerm()->text, 0, $prefixByteLength) == $prefix) {
 221                     // Calculate similarity
 222                     $target = substr($index->currentTerm()->text, $prefixByteLength);
 223
 224                     $maxDistance = isset($this->_maxDistances[strlen($target)])?
 225                                        $this->_maxDistances[strlen($target)] :
 226                                        $this->_calculateMaxDistance($prefixUtf8Length, $termRestLength, strlen($target));
 227
 228                     if ($termRestLength == 0) {
 229                         // we don't have anything to compare.  That means if we just add
 230                         // the letters for current term we get the new word
 231                         $similarity = (($prefixUtf8Length == 0)? 0 : 1 - strlen($target)/$prefixUtf8Length);
 232                     } else if (strlen($target) == 0) {
 233                         $similarity = (($prefixUtf8Length == 0)? 0 : 1 - $termRestLength/$prefixUtf8Length);
 234                     } else if ($maxDistance < abs($termRestLength - strlen($target))){
 235                         //just adding the characters of term to target or vice-versa results in too many edits
 236                         //for example "pre" length is 3 and "prefixes" length is 8.  We can see that
 237                         //given this optimal circumstance, the edit distance cannot be less than 5.
 238                         //which is 8-3 or more precisesly abs(3-8).
 239                         //if our maximum edit distance is 4, then we can discard this word
 240                         //without looking at it.
 241                         $similarity = 0;
 242                     } else {
 243                         $similarity = 1 - levenshtein($termRest, $target)/($prefixUtf8Length + min($termRestLength, strlen($target)));
 244                     }
 245
 246                     if ($similarity > $this->_minimumSimilarity) {
 247                         $this->_matches[]  = $index->currentTerm();
 248                         $this->_termKeys[] = $index->currentTerm()->key();
 249                         $this->_scores[]   = ($similarity - $this->_minimumSimilarity)*$scaleFactor;
 250
 251                         if ($maxTerms != 0  &&  count($this->_matches) > $maxTerms) {
 252                             require_once 'Zend/Search/Lucene/Exception.php';
 253                             throw new Zend_Search_Lucene_Exception('Terms per query limit is reached.');
 254                         }
 255                     }
 256
 257                     $index->nextTerm();
 258                 }
 259             } else {
 260                 $index->skipTo(new Zend_Search_Lucene_Index_Term('', $field));
 261
 262                 while ($index->currentTerm() !== null  &&  $index->currentTerm()->field == $field) {
 263                     // Calculate similarity
 264                     $target = $index->currentTerm()->text;
 265
 266                     $maxDistance = isset($this->_maxDistances[strlen($target)])?
 267                                        $this->_maxDistances[strlen($target)] :
 268                                        $this->_calculateMaxDistance(0, $termRestLength, strlen($target));
 269
 270                     if ($maxDistance < abs($termRestLength - strlen($target))){
 271                         //just adding the characters of term to target or vice-versa results in too many edits
 272                         //for example "pre" length is 3 and "prefixes" length is 8.  We can see that
 273                         //given this optimal circumstance, the edit distance cannot be less than 5.
 274                         //which is 8-3 or more precisesly abs(3-8).
 275                         //if our maximum edit distance is 4, then we can discard this word
 276                         //without looking at it.
 277                         $similarity = 0;
 278                     } else {
 279                         $similarity = 1 - levenshtein($termRest, $target)/min($termRestLength, strlen($target));
 280                     }
 281
 282                     if ($similarity > $this->_minimumSimilarity) {
 283                         $this->_matches[]  = $index->currentTerm();
 284                         $this->_termKeys[] = $index->currentTerm()->key();
 285                         $this->_scores[]   = ($similarity - $this->_minimumSimilarity)*$scaleFactor;
 286
 287                         if ($maxTerms != 0  &&  count($this->_matches) > $maxTerms) {
 288                             require_once 'Zend/Search/Lucene/Exception.php';
 289                             throw new Zend_Search_Lucene_Exception('Terms per query limit is reached.');
 290                         }
 291                     }
 292
 293                     $index->nextTerm();
 294                 }
 295             }
 296
 297             $index->closeTermsStream();
 298         }
 299
 300         if (count($this->_matches) == 0) {
 301             return new Zend_Search_Lucene_Search_Query_Empty();
 302         } else if (count($this->_matches) == 1) {
 303             return new Zend_Search_Lucene_Search_Query_Term(reset($this->_matches));
 304         } else {
 305             $rewrittenQuery = new Zend_Search_Lucene_Search_Query_Boolean();
 306
 307             array_multisort($this->_scores,   SORT_DESC, SORT_NUMERIC,
 308                             $this->_termKeys, SORT_ASC,  SORT_STRING,
 309                             $this->_matches);
 310
 311             $termCount = 0;
 312             foreach ($this->_matches as $id => $matchedTerm) {
 313                 $subquery = new Zend_Search_Lucene_Search_Query_Term($matchedTerm);
 314                 $subquery->setBoost($this->_scores[$id]);
 315
 316                 $rewrittenQuery->addSubquery($subquery);
 317
 318                 $termCount++;
 319                 if ($termCount >= self::MAX_CLAUSE_COUNT) {
 320                     break;
 321                 }
 322             }
 323
 324             return $rewrittenQuery;
 325         }
 326     }
 327
 328     /**
 329      * Optimize query in the context of specified index
 330      *
 331      * @param Zend_Search_Lucene_Interface $index
 332      * @return Zend_Search_Lucene_Search_Query
 333      */
 334     public function optimize(Zend_Search_Lucene_Interface $index)
 335     {
 336         require_once 'Zend/Search/Lucene/Exception.php';
 337         throw new Zend_Search_Lucene_Exception('Fuzzy query should not be directly used for search. Use $query->rewrite($index)');
 338     }
 339
 340     /**
 341      * Return query terms
 342      *
 343      * @return array
 344      * @throws Zend_Search_Lucene_Exception
 345      */
 346     public function getQueryTerms()
 347     {
 348         if ($this->_matches === null) {
 349             require_once 'Zend/Search/Lucene/Exception.php';
 350             throw new Zend_Search_Lucene_Exception('Search or rewrite operations have to be performed before.');
 351         }
 352
 353         return $this->_matches;
 354     }
 355
 356     /**
 357      * Constructs an appropriate Weight implementation for this query.
 358      *
 359      * @param Zend_Search_Lucene_Interface $reader
 360      * @return Zend_Search_Lucene_Search_Weight
 361      * @throws Zend_Search_Lucene_Exception
 362      */
 363     public function createWeight(Zend_Search_Lucene_Interface $reader)
 364     {
 365         require_once 'Zend/Search/Lucene/Exception.php';
 366         throw new Zend_Search_Lucene_Exception('Fuzzy query should not be directly used for search. Use $query->rewrite($index)');
 367     }
 368
 369
 370     /**
 371      * Execute query in context of index reader
 372      * It also initializes necessary internal structures
 373      *
 374      * @param Zend_Search_Lucene_Interface $reader
 375      * @param Zend_Search_Lucene_Index_DocsFilter|null $docsFilter
 376      * @throws Zend_Search_Lucene_Exception
 377      */
 378     public function execute(Zend_Search_Lucene_Interface $reader, $docsFilter = null)
 379     {
 380         require_once 'Zend/Search/Lucene/Exception.php';
 381         throw new Zend_Search_Lucene_Exception('Fuzzy query should not be directly used for search. Use $query->rewrite($index)');
 382     }
 383
 384     /**
 385      * Get document ids likely matching the query
 386      *
 387      * It's an array with document ids as keys (performance considerations)
 388      *
 389      * @return array
 390      * @throws Zend_Search_Lucene_Exception
 391      */
 392     public function matchedDocs()
 393     {
 394         require_once 'Zend/Search/Lucene/Exception.php';
 395         throw new Zend_Search_Lucene_Exception('Fuzzy query should not be directly used for search. Use $query->rewrite($index)');
 396     }
 397
 398     /**
 399      * Score specified document
 400      *
 401      * @param integer $docId
 402      * @param Zend_Search_Lucene_Interface $reader
 403      * @return float
 404      * @throws Zend_Search_Lucene_Exception
 405      */
 406     public function score($docId, Zend_Search_Lucene_Interface $reader)
 407     {
 408         require_once 'Zend/Search/Lucene/Exception.php';
 409         throw new Zend_Search_Lucene_Exception('Fuzzy query should not be directly used for search. Use $query->rewrite($index)');
 410     }
 411
 412     /**
 413      * Query specific matches highlighting
 414      *
 415      * @param Zend_Search_Lucene_Search_Highlighter_Interface $highlighter  Highlighter object (also contains doc for highlighting)
 416      */
 417     protected function _highlightMatches(Zend_Search_Lucene_Search_Highlighter_Interface $highlighter)
 418     {
 419         $words = array();
 420
 421         $prefix           = Zend_Search_Lucene_Index_Term::getPrefix($this->_term->text, $this->_prefixLength);
 422         $prefixByteLength = strlen($prefix);
 423         $prefixUtf8Length = Zend_Search_Lucene_Index_Term::getLength($prefix);
 424
 425         $termLength       = Zend_Search_Lucene_Index_Term::getLength($this->_term->text);
 426
 427         $termRest         = substr($this->_term->text, $prefixByteLength);
 428         // we calculate length of the rest in bytes since levenshtein() is not UTF-8 compatible
 429         $termRestLength   = strlen($termRest);
 430
 431         $scaleFactor = 1/(1 - $this->_minimumSimilarity);
 432
 433
 434         $docBody = $highlighter->getDocument()->getFieldUtf8Value('body');
 435         $tokens = Zend_Search_Lucene_Analysis_Analyzer::getDefault()->tokenize($docBody, 'UTF-8');
 436         foreach ($tokens as $token) {
 437                 $termText = $token->getTermText();
 438
 439                 if (substr($termText, 0, $prefixByteLength) == $prefix) {
 440                 // Calculate similarity
 441                 $target = substr($termText, $prefixByteLength);
 442
 443                 $maxDistance = isset($this->_maxDistances[strlen($target)])?
 444                                    $this->_maxDistances[strlen($target)] :
 445                                    $this->_calculateMaxDistance($prefixUtf8Length, $termRestLength, strlen($target));
 446
 447                 if ($termRestLength == 0) {
 448                     // we don't have anything to compare.  That means if we just add
 449                     // the letters for current term we get the new word
 450                     $similarity = (($prefixUtf8Length == 0)? 0 : 1 - strlen($target)/$prefixUtf8Length);
 451                 } else if (strlen($target) == 0) {
 452                     $similarity = (($prefixUtf8Length == 0)? 0 : 1 - $termRestLength/$prefixUtf8Length);
 453                 } else if ($maxDistance < abs($termRestLength - strlen($target))){
 454                     //just adding the characters of term to target or vice-versa results in too many edits
 455                     //for example "pre" length is 3 and "prefixes" length is 8.  We can see that
 456                     //given this optimal circumstance, the edit distance cannot be less than 5.
 457                     //which is 8-3 or more precisesly abs(3-8).
 458                     //if our maximum edit distance is 4, then we can discard this word
 459                     //without looking at it.
 460                     $similarity = 0;
 461                 } else {
 462                     $similarity = 1 - levenshtein($termRest, $target)/($prefixUtf8Length + min($termRestLength, strlen($target)));
 463                 }
 464
 465                 if ($similarity > $this->_minimumSimilarity) {
 466                     $words[] = $termText;
 467                 }
 468             }
 469         }
 470
 471         $highlighter->highlight($words);
 472     }
 473
 474     /**
 475      * Print a query
 476      *
 477      * @return string
 478      */
 479     public function __toString()
 480     {
 481         // It's used only for query visualisation, so we don't care about characters escaping
 482         return (($this->_term->field === null)? '' : $this->_term->field . ':')
 483              . $this->_term->text . '~'
 484              . (($this->_minimumSimilarity != self::DEFAULT_MIN_SIMILARITY)? round($this->_minimumSimilarity, 4) : '')
 485              . (($this->getBoost() != 1)? '^' . round($this->getBoost(), 4) : '');
 486     }
 487 }
 488