git.roojs.org Git - web.mtrack/blob - Zend/Search/Lucene/Search/Query/Phrase.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: Phrase.php 16541 2009-07-07 06:59:03Z bkarwin $
  21  */
  22
  23
  24 /**
  25  * Zend_Search_Lucene_Search_Query
  26  */
  27 require_once 'Zend/Search/Lucene/Search/Query.php';
  28
  29 /**
  30  * Zend_Search_Lucene_Search_Weight_Phrase
  31  */
  32 require_once 'Zend/Search/Lucene/Search/Weight/Phrase.php';
  33
  34
  35 /**
  36  * A Query that matches documents containing a particular sequence of terms.
  37  *
  38  * @category   Zend
  39  * @package    Zend_Search_Lucene
  40  * @subpackage Search
  41  * @copyright  Copyright (c) 2005-2009 Zend Technologies USA Inc. (http://www.zend.com)
  42  * @license    http://framework.zend.com/license/new-bsd     New BSD License
  43  */
  44 class Zend_Search_Lucene_Search_Query_Phrase extends Zend_Search_Lucene_Search_Query
  45 {
  46     /**
  47      * Terms to find.
  48      * Array of Zend_Search_Lucene_Index_Term objects.
  49      *
  50      * @var array
  51      */
  52     private $_terms;
  53
  54     /**
  55      * Term positions (relative positions of terms within the phrase).
  56      * Array of integers
  57      *
  58      * @var array
  59      */
  60     private $_offsets;
  61
  62     /**
  63      * Sets the number of other words permitted between words in query phrase.
  64      * If zero, then this is an exact phrase search.  For larger values this works
  65      * like a WITHIN or NEAR operator.
  66      *
  67      * The slop is in fact an edit-distance, where the units correspond to
  68      * moves of terms in the query phrase out of position.  For example, to switch
  69      * the order of two words requires two moves (the first move places the words
  70      * atop one another), so to permit re-orderings of phrases, the slop must be
  71      * at least two.
  72      * More exact matches are scored higher than sloppier matches, thus search
  73      * results are sorted by exactness.
  74      *
  75      * The slop is zero by default, requiring exact matches.
  76      *
  77      * @var integer
  78      */
  79     private $_slop;
  80
  81     /**
  82      * Result vector.
  83      *
  84      * @var array
  85      */
  86     private $_resVector = null;
  87
  88     /**
  89      * Terms positions vectors.
  90      * Array of Arrays:
  91      * term1Id => (docId => array( pos1, pos2, ... ), ...)
  92      * term2Id => (docId => array( pos1, pos2, ... ), ...)
  93      *
  94      * @var array
  95      */
  96     private $_termsPositions = array();
  97
  98     /**
  99      * Class constructor.  Create a new prase query.
 100      *
 101      * @param string $field    Field to search.
 102      * @param array  $terms    Terms to search Array of strings.
 103      * @param array  $offsets  Relative term positions. Array of integers.
 104      * @throws Zend_Search_Lucene_Exception
 105      */
 106     public function __construct($terms = null, $offsets = null, $field = null)
 107     {
 108         $this->_slop = 0;
 109
 110         if (is_array($terms)) {
 111             $this->_terms = array();
 112             foreach ($terms as $termId => $termText) {
 113                 $this->_terms[$termId] = ($field !== null)? new Zend_Search_Lucene_Index_Term($termText, $field):
 114                                                             new Zend_Search_Lucene_Index_Term($termText);
 115             }
 116         } else if ($terms === null) {
 117             $this->_terms = array();
 118         } else {
 119             throw new Zend_Search_Lucene_Exception('terms argument must be array of strings or null');
 120         }
 121
 122         if (is_array($offsets)) {
 123             if (count($this->_terms) != count($offsets)) {
 124                 throw new Zend_Search_Lucene_Exception('terms and offsets arguments must have the same size.');
 125             }
 126             $this->_offsets = $offsets;
 127         } else if ($offsets === null) {
 128             $this->_offsets = array();
 129             foreach ($this->_terms as $termId => $term) {
 130                 $position = count($this->_offsets);
 131                 $this->_offsets[$termId] = $position;
 132             }
 133         } else {
 134             throw new Zend_Search_Lucene_Exception('offsets argument must be array of strings or null');
 135         }
 136     }
 137
 138     /**
 139      * Set slop
 140      *
 141      * @param integer $slop
 142      */
 143     public function setSlop($slop)
 144     {
 145         $this->_slop = $slop;
 146     }
 147
 148
 149     /**
 150      * Get slop
 151      *
 152      * @return integer
 153      */
 154     public function getSlop()
 155     {
 156         return $this->_slop;
 157     }
 158
 159
 160     /**
 161      * Adds a term to the end of the query phrase.
 162      * The relative position of the term is specified explicitly or the one immediately
 163      * after the last term added.
 164      *
 165      * @param Zend_Search_Lucene_Index_Term $term
 166      * @param integer $position
 167      */
 168     public function addTerm(Zend_Search_Lucene_Index_Term $term, $position = null) {
 169         if ((count($this->_terms) != 0)&&(end($this->_terms)->field != $term->field)) {
 170             throw new Zend_Search_Lucene_Exception('All phrase terms must be in the same field: ' .
 171                                                    $term->field . ':' . $term->text);
 172         }
 173
 174         $this->_terms[] = $term;
 175         if ($position !== null) {
 176             $this->_offsets[] = $position;
 177         } else if (count($this->_offsets) != 0) {
 178             $this->_offsets[] = end($this->_offsets) + 1;
 179         } else {
 180             $this->_offsets[] = 0;
 181         }
 182     }
 183
 184
 185     /**
 186      * Re-write query into primitive queries in the context of specified index
 187      *
 188      * @param Zend_Search_Lucene_Interface $index
 189      * @return Zend_Search_Lucene_Search_Query
 190      */
 191     public function rewrite(Zend_Search_Lucene_Interface $index)
 192     {
 193         if (count($this->_terms) == 0) {
 194             return new Zend_Search_Lucene_Search_Query_Empty();
 195         } else if ($this->_terms[0]->field !== null) {
 196             return $this;
 197         } else {
 198             $query = new Zend_Search_Lucene_Search_Query_Boolean();
 199             $query->setBoost($this->getBoost());
 200
 201             foreach ($index->getFieldNames(true) as $fieldName) {
 202                 $subquery = new Zend_Search_Lucene_Search_Query_Phrase();
 203                 $subquery->setSlop($this->getSlop());
 204
 205                 foreach ($this->_terms as $termId => $term) {
 206                     $qualifiedTerm = new Zend_Search_Lucene_Index_Term($term->text, $fieldName);
 207
 208                     $subquery->addTerm($qualifiedTerm, $this->_offsets[$termId]);
 209                 }
 210
 211                 $query->addSubquery($subquery);
 212             }
 213
 214             return $query;
 215         }
 216     }
 217
 218     /**
 219      * Optimize query in the context of specified index
 220      *
 221      * @param Zend_Search_Lucene_Interface $index
 222      * @return Zend_Search_Lucene_Search_Query
 223      */
 224     public function optimize(Zend_Search_Lucene_Interface $index)
 225     {
 226         // Check, that index contains all phrase terms
 227         foreach ($this->_terms as $term) {
 228             if (!$index->hasTerm($term)) {
 229                 return new Zend_Search_Lucene_Search_Query_Empty();
 230             }
 231         }
 232
 233         if (count($this->_terms) == 1) {
 234             // It's one term query
 235             $optimizedQuery = new Zend_Search_Lucene_Search_Query_Term(reset($this->_terms));
 236             $optimizedQuery->setBoost($this->getBoost());
 237
 238             return $optimizedQuery;
 239         }
 240
 241         if (count($this->_terms) == 0) {
 242             return new Zend_Search_Lucene_Search_Query_Empty();
 243         }
 244
 245
 246         return $this;
 247     }
 248
 249     /**
 250      * Returns query term
 251      *
 252      * @return array
 253      */
 254     public function getTerms()
 255     {
 256         return $this->_terms;
 257     }
 258
 259
 260     /**
 261      * Set weight for specified term
 262      *
 263      * @param integer $num
 264      * @param Zend_Search_Lucene_Search_Weight_Term $weight
 265      */
 266     public function setWeight($num, $weight)
 267     {
 268         $this->_weights[$num] = $weight;
 269     }
 270
 271
 272     /**
 273      * Constructs an appropriate Weight implementation for this query.
 274      *
 275      * @param Zend_Search_Lucene_Interface $reader
 276      * @return Zend_Search_Lucene_Search_Weight
 277      */
 278     public function createWeight(Zend_Search_Lucene_Interface $reader)
 279     {
 280         $this->_weight = new Zend_Search_Lucene_Search_Weight_Phrase($this, $reader);
 281         return $this->_weight;
 282     }
 283
 284
 285     /**
 286      * Score calculator for exact phrase queries (terms sequence is fixed)
 287      *
 288      * @param integer $docId
 289      * @return float
 290      */
 291     public function _exactPhraseFreq($docId)
 292     {
 293         $freq = 0;
 294
 295         // Term Id with lowest cardinality
 296         $lowCardTermId = null;
 297
 298         // Calculate $lowCardTermId
 299         foreach ($this->_terms as $termId => $term) {
 300             if ($lowCardTermId === null ||
 301                 count($this->_termsPositions[$termId][$docId]) <
 302                 count($this->_termsPositions[$lowCardTermId][$docId]) ) {
 303                     $lowCardTermId = $termId;
 304                 }
 305         }
 306
 307         // Walk through positions of the term with lowest cardinality
 308         foreach ($this->_termsPositions[$lowCardTermId][$docId] as $lowCardPos) {
 309             // We expect phrase to be found
 310             $freq++;
 311
 312             // Walk through other terms
 313             foreach ($this->_terms as $termId => $term) {
 314                 if ($termId != $lowCardTermId) {
 315                     $expectedPosition = $lowCardPos +
 316                                             ($this->_offsets[$termId] -
 317                                              $this->_offsets[$lowCardTermId]);
 318
 319                     if (!in_array($expectedPosition, $this->_termsPositions[$termId][$docId])) {
 320                         $freq--;  // Phrase wasn't found.
 321                         break;
 322                     }
 323                 }
 324             }
 325         }
 326
 327         return $freq;
 328     }
 329
 330     /**
 331      * Score calculator for sloppy phrase queries (terms sequence is fixed)
 332      *
 333      * @param integer $docId
 334      * @param Zend_Search_Lucene_Interface $reader
 335      * @return float
 336      */
 337     public function _sloppyPhraseFreq($docId, Zend_Search_Lucene_Interface $reader)
 338     {
 339         $freq = 0;
 340
 341         $phraseQueue = array();
 342         $phraseQueue[0] = array(); // empty phrase
 343         $lastTerm = null;
 344
 345         // Walk through the terms to create phrases.
 346         foreach ($this->_terms as $termId => $term) {
 347             $queueSize = count($phraseQueue);
 348             $firstPass = true;
 349
 350             // Walk through the term positions.
 351             // Each term position produces a set of phrases.
 352             foreach ($this->_termsPositions[$termId][$docId] as $termPosition ) {
 353                 if ($firstPass) {
 354                     for ($count = 0; $count < $queueSize; $count++) {
 355                         $phraseQueue[$count][$termId] = $termPosition;
 356                     }
 357                 } else {
 358                     for ($count = 0; $count < $queueSize; $count++) {
 359                         if ($lastTerm !== null &&
 360                             abs( $termPosition - $phraseQueue[$count][$lastTerm] -
 361                                  ($this->_offsets[$termId] - $this->_offsets[$lastTerm])) > $this->_slop) {
 362                             continue;
 363                         }
 364
 365                         $newPhraseId = count($phraseQueue);
 366                         $phraseQueue[$newPhraseId]          = $phraseQueue[$count];
 367                         $phraseQueue[$newPhraseId][$termId] = $termPosition;
 368                     }
 369
 370                 }
 371
 372                 $firstPass = false;
 373             }
 374             $lastTerm = $termId;
 375         }
 376
 377
 378         foreach ($phraseQueue as $phrasePos) {
 379             $minDistance = null;
 380
 381             for ($shift = -$this->_slop; $shift <= $this->_slop; $shift++) {
 382                 $distance = 0;
 383                 $start = reset($phrasePos) - reset($this->_offsets) + $shift;
 384
 385                 foreach ($this->_terms as $termId => $term) {
 386                     $distance += abs($phrasePos[$termId] - $this->_offsets[$termId] - $start);
 387
 388                     if($distance > $this->_slop) {
 389                         break;
 390                     }
 391                 }
 392
 393                 if ($minDistance === null || $distance < $minDistance) {
 394                     $minDistance = $distance;
 395                 }
 396             }
 397
 398             if ($minDistance <= $this->_slop) {
 399                 $freq += $reader->getSimilarity()->sloppyFreq($minDistance);
 400             }
 401         }
 402
 403         return $freq;
 404     }
 405
 406     /**
 407      * Execute query in context of index reader
 408      * It also initializes necessary internal structures
 409      *
 410      * @param Zend_Search_Lucene_Interface $reader
 411      * @param Zend_Search_Lucene_Index_DocsFilter|null $docsFilter
 412      */
 413     public function execute(Zend_Search_Lucene_Interface $reader, $docsFilter = null)
 414     {
 415         $this->_resVector = null;
 416
 417         if (count($this->_terms) == 0) {
 418             $this->_resVector = array();
 419         }
 420
 421         $resVectors      = array();
 422         $resVectorsSizes = array();
 423         $resVectorsIds   = array(); // is used to prevent arrays comparison
 424         foreach ($this->_terms as $termId => $term) {
 425             $resVectors[]      = array_flip($reader->termDocs($term));
 426             $resVectorsSizes[] = count(end($resVectors));
 427             $resVectorsIds[]   = $termId;
 428
 429             $this->_termsPositions[$termId] = $reader->termPositions($term);
 430         }
 431         // sort resvectors in order of subquery cardinality increasing
 432         array_multisort($resVectorsSizes, SORT_ASC, SORT_NUMERIC,
 433                         $resVectorsIds,   SORT_ASC, SORT_NUMERIC,
 434                         $resVectors);
 435
 436         foreach ($resVectors as $nextResVector) {
 437             if($this->_resVector === null) {
 438                 $this->_resVector = $nextResVector;
 439             } else {
 440                 //$this->_resVector = array_intersect_key($this->_resVector, $nextResVector);
 441
 442                 /**
 443                  * This code is used as workaround for array_intersect_key() slowness problem.
 444                  */
 445                 $updatedVector = array();
 446                 foreach ($this->_resVector as $id => $value) {
 447                     if (isset($nextResVector[$id])) {
 448                         $updatedVector[$id] = $value;
 449                     }
 450                 }
 451                 $this->_resVector = $updatedVector;
 452             }
 453
 454             if (count($this->_resVector) == 0) {
 455                 // Empty result set, we don't need to check other terms
 456                 break;
 457             }
 458         }
 459
 460         // ksort($this->_resVector, SORT_NUMERIC);
 461         // Docs are returned ordered. Used algorithm doesn't change elements order.
 462
 463         // Initialize weight if it's not done yet
 464         $this->_initWeight($reader);
 465     }
 466
 467     /**
 468      * Get document ids likely matching the query
 469      *
 470      * It's an array with document ids as keys (performance considerations)
 471      *
 472      * @return array
 473      */
 474     public function matchedDocs()
 475     {
 476         return $this->_resVector;
 477     }
 478
 479     /**
 480      * Score specified document
 481      *
 482      * @param integer $docId
 483      * @param Zend_Search_Lucene_Interface $reader
 484      * @return float
 485      */
 486     public function score($docId, Zend_Search_Lucene_Interface $reader)
 487     {
 488         if (isset($this->_resVector[$docId])) {
 489             if ($this->_slop == 0) {
 490                 $freq = $this->_exactPhraseFreq($docId);
 491             } else {
 492                 $freq = $this->_sloppyPhraseFreq($docId, $reader);
 493             }
 494
 495             if ($freq != 0) {
 496                 $tf = $reader->getSimilarity()->tf($freq);
 497                 $weight = $this->_weight->getValue();
 498                 $norm = $reader->norm($docId, reset($this->_terms)->field);
 499
 500                 return $tf * $weight * $norm * $this->getBoost();
 501             }
 502
 503             // Included in result, but culculated freq is zero
 504             return 0;
 505         } else {
 506             return 0;
 507         }
 508     }
 509
 510     /**
 511      * Return query terms
 512      *
 513      * @return array
 514      */
 515     public function getQueryTerms()
 516     {
 517         return $this->_terms;
 518     }
 519
 520     /**
 521      * Query specific matches highlighting
 522      *
 523      * @param Zend_Search_Lucene_Search_Highlighter_Interface $highlighter  Highlighter object (also contains doc for highlighting)
 524      */
 525     protected function _highlightMatches(Zend_Search_Lucene_Search_Highlighter_Interface $highlighter)
 526     {
 527         $words = array();
 528         foreach ($this->_terms as $term) {
 529             $words[] = $term->text;
 530         }
 531
 532         $highlighter->highlight($words);
 533     }
 534
 535     /**
 536      * Print a query
 537      *
 538      * @return string
 539      */
 540     public function __toString()
 541     {
 542         // It's used only for query visualisation, so we don't care about characters escaping
 543         if (isset($this->_terms[0]) && $this->_terms[0]->field !== null) {
 544             $query = $this->_terms[0]->field . ':';
 545         } else {
 546                 $query = '';
 547         }
 548
 549         $query .= '"';
 550
 551         foreach ($this->_terms as $id => $term) {
 552             if ($id != 0) {
 553                 $query .= ' ';
 554             }
 555             $query .= $term->text;
 556         }
 557
 558         $query .= '"';
 559
 560         if ($this->_slop != 0) {
 561             $query .= '~' . $this->_slop;
 562         }
 563
 564         if ($this->getBoost() != 1) {
 565             $query .= '^' . round($this->getBoost(), 4);
 566         }
 567
 568         return $query;
 569     }
 570 }
 571