git.roojs.org Git - web.mtrack/blob - inc/lib/Zend/Search/Lucene/Search/Query/MultiTerm.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: MultiTerm.php 16541 2009-07-07 06:59:03Z bkarwin $
  21  */
  22
  23
  24 /** Zend_Search_Lucene_Search_Query */
  25 require_once 'Zend/Search/Lucene/Search/Query.php';
  26
  27 /** Zend_Search_Lucene_Search_Weight_MultiTerm */
  28 require_once 'Zend/Search/Lucene/Search/Weight/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_MultiTerm extends Zend_Search_Lucene_Search_Query
  39 {
  40
  41     /**
  42      * Terms to find.
  43      * Array of Zend_Search_Lucene_Index_Term
  44      *
  45      * @var array
  46      */
  47     private $_terms = array();
  48
  49     /**
  50      * Term signs.
  51      * If true then term is required.
  52      * If false then term is prohibited.
  53      * If null then term is neither prohibited, nor required
  54      *
  55      * If array is null then all terms are required
  56      *
  57      * @var array
  58      */
  59     private $_signs;
  60
  61     /**
  62      * Result vector.
  63      *
  64      * @var array
  65      */
  66     private $_resVector = null;
  67
  68     /**
  69      * Terms positions vectors.
  70      * Array of Arrays:
  71      * term1Id => (docId => freq, ...)
  72      * term2Id => (docId => freq, ...)
  73      *
  74      * @var array
  75      */
  76     private $_termsFreqs = array();
  77
  78
  79     /**
  80      * A score factor based on the fraction of all query terms
  81      * that a document contains.
  82      * float for conjunction queries
  83      * array of float for non conjunction queries
  84      *
  85      * @var mixed
  86      */
  87     private $_coord = null;
  88
  89
  90     /**
  91      * Terms weights
  92      * array of Zend_Search_Lucene_Search_Weight
  93      *
  94      * @var array
  95      */
  96     private $_weights = array();
  97
  98
  99     /**
 100      * Class constructor.  Create a new multi-term query object.
 101      *
 102      * if $signs array is omitted then all terms are required
 103      * it differs from addTerm() behavior, but should never be used
 104      *
 105      * @param array $terms    Array of Zend_Search_Lucene_Index_Term objects
 106      * @param array $signs    Array of signs.  Sign is boolean|null.
 107      * @throws Zend_Search_Lucene_Exception
 108      */
 109     public function __construct($terms = null, $signs = null)
 110     {
 111         if (is_array($terms)) {
 112             if (count($terms) > Zend_Search_Lucene::getTermsPerQueryLimit()) {
 113                 throw new Zend_Search_Lucene_Exception('Terms per query limit is reached.');
 114             }
 115
 116             $this->_terms = $terms;
 117
 118             $this->_signs = null;
 119             // Check if all terms are required
 120             if (is_array($signs)) {
 121                 foreach ($signs as $sign ) {
 122                     if ($sign !== true) {
 123                         $this->_signs = $signs;
 124                         break;
 125                     }
 126                 }
 127             }
 128         }
 129     }
 130
 131
 132     /**
 133      * Add a $term (Zend_Search_Lucene_Index_Term) to this query.
 134      *
 135      * The sign is specified as:
 136      *     TRUE  - term is required
 137      *     FALSE - term is prohibited
 138      *     NULL  - term is neither prohibited, nor required
 139      *
 140      * @param  Zend_Search_Lucene_Index_Term $term
 141      * @param  boolean|null $sign
 142      * @return void
 143      */
 144     public function addTerm(Zend_Search_Lucene_Index_Term $term, $sign = null) {
 145         if ($sign !== true || $this->_signs !== null) {       // Skip, if all terms are required
 146             if ($this->_signs === null) {                     // Check, If all previous terms are required
 147                 $this->_signs = array();
 148                 foreach ($this->_terms as $prevTerm) {
 149                     $this->_signs[] = true;
 150                 }
 151             }
 152             $this->_signs[] = $sign;
 153         }
 154
 155         $this->_terms[] = $term;
 156     }
 157
 158
 159     /**
 160      * Re-write query into primitive queries in the context of specified index
 161      *
 162      * @param Zend_Search_Lucene_Interface $index
 163      * @return Zend_Search_Lucene_Search_Query
 164      */
 165     public function rewrite(Zend_Search_Lucene_Interface $index)
 166     {
 167         if (count($this->_terms) == 0) {
 168             return new Zend_Search_Lucene_Search_Query_Empty();
 169         }
 170
 171         // Check, that all fields are qualified
 172         $allQualified = true;
 173         foreach ($this->_terms as $term) {
 174             if ($term->field === null) {
 175                 $allQualified = false;
 176                 break;
 177             }
 178         }
 179
 180         if ($allQualified) {
 181             return $this;
 182         } else {
 183             /** transform multiterm query to boolean and apply rewrite() method to subqueries. */
 184             $query = new Zend_Search_Lucene_Search_Query_Boolean();
 185             $query->setBoost($this->getBoost());
 186
 187             foreach ($this->_terms as $termId => $term) {
 188                 $subquery = new Zend_Search_Lucene_Search_Query_Term($term);
 189
 190                 $query->addSubquery($subquery->rewrite($index),
 191                                     ($this->_signs === null)?  true : $this->_signs[$termId]);
 192             }
 193
 194             return $query;
 195         }
 196     }
 197
 198     /**
 199      * Optimize query in the context of specified index
 200      *
 201      * @param Zend_Search_Lucene_Interface $index
 202      * @return Zend_Search_Lucene_Search_Query
 203      */
 204     public function optimize(Zend_Search_Lucene_Interface $index)
 205     {
 206         $terms = $this->_terms;
 207         $signs = $this->_signs;
 208
 209         foreach ($terms as $id => $term) {
 210             if (!$index->hasTerm($term)) {
 211                 if ($signs === null  ||  $signs[$id] === true) {
 212                     // Term is required
 213                     return new Zend_Search_Lucene_Search_Query_Empty();
 214                 } else {
 215                     // Term is optional or prohibited
 216                     // Remove it from terms and signs list
 217                     unset($terms[$id]);
 218                     unset($signs[$id]);
 219                 }
 220             }
 221         }
 222
 223         // Check if all presented terms are prohibited
 224         $allProhibited = true;
 225         if ($signs === null) {
 226             $allProhibited = false;
 227         } else {
 228             foreach ($signs as $sign) {
 229                 if ($sign !== false) {
 230                     $allProhibited = false;
 231                     break;
 232                 }
 233             }
 234         }
 235         if ($allProhibited) {
 236             return new Zend_Search_Lucene_Search_Query_Empty();
 237         }
 238
 239         /**
 240          * @todo make an optimization for repeated terms
 241          * (they may have different signs)
 242          */
 243
 244         if (count($terms) == 1) {
 245             // It's already checked, that it's not a prohibited term
 246
 247             // It's one term query with one required or optional element
 248             $optimizedQuery = new Zend_Search_Lucene_Search_Query_Term(reset($terms));
 249             $optimizedQuery->setBoost($this->getBoost());
 250
 251             return $optimizedQuery;
 252         }
 253
 254         if (count($terms) == 0) {
 255             return new Zend_Search_Lucene_Search_Query_Empty();
 256         }
 257
 258         $optimizedQuery = new Zend_Search_Lucene_Search_Query_MultiTerm($terms, $signs);
 259         $optimizedQuery->setBoost($this->getBoost());
 260         return $optimizedQuery;
 261     }
 262
 263
 264     /**
 265      * Returns query term
 266      *
 267      * @return array
 268      */
 269     public function getTerms()
 270     {
 271         return $this->_terms;
 272     }
 273
 274
 275     /**
 276      * Return terms signs
 277      *
 278      * @return array
 279      */
 280     public function getSigns()
 281     {
 282         return $this->_signs;
 283     }
 284
 285
 286     /**
 287      * Set weight for specified term
 288      *
 289      * @param integer $num
 290      * @param Zend_Search_Lucene_Search_Weight_Term $weight
 291      */
 292     public function setWeight($num, $weight)
 293     {
 294         $this->_weights[$num] = $weight;
 295     }
 296
 297
 298     /**
 299      * Constructs an appropriate Weight implementation for this query.
 300      *
 301      * @param Zend_Search_Lucene_Interface $reader
 302      * @return Zend_Search_Lucene_Search_Weight
 303      */
 304     public function createWeight(Zend_Search_Lucene_Interface $reader)
 305     {
 306         $this->_weight = new Zend_Search_Lucene_Search_Weight_MultiTerm($this, $reader);
 307         return $this->_weight;
 308     }
 309
 310
 311     /**
 312      * Calculate result vector for Conjunction query
 313      * (like '+something +another')
 314      *
 315      * @param Zend_Search_Lucene_Interface $reader
 316      */
 317     private function _calculateConjunctionResult(Zend_Search_Lucene_Interface $reader)
 318     {
 319         $this->_resVector = null;
 320
 321         if (count($this->_terms) == 0) {
 322             $this->_resVector = array();
 323         }
 324
 325         // Order terms by selectivity
 326         $docFreqs = array();
 327         $ids      = array();
 328         foreach ($this->_terms as $id => $term) {
 329             $docFreqs[] = $reader->docFreq($term);
 330             $ids[]      = $id; // Used to keep original order for terms with the same selectivity and omit terms comparison
 331         }
 332         array_multisort($docFreqs, SORT_ASC, SORT_NUMERIC,
 333                         $ids,      SORT_ASC, SORT_NUMERIC,
 334                         $this->_terms);
 335
 336         $docsFilter = new Zend_Search_Lucene_Index_DocsFilter();
 337         foreach ($this->_terms as $termId => $term) {
 338             $termDocs = $reader->termDocs($term, $docsFilter);
 339         }
 340         // Treat last retrieved docs vector as a result set
 341         // (filter collects data for other terms)
 342         $this->_resVector = array_flip($termDocs);
 343
 344         foreach ($this->_terms as $termId => $term) {
 345             $this->_termsFreqs[$termId] = $reader->termFreqs($term, $docsFilter);
 346         }
 347
 348         // ksort($this->_resVector, SORT_NUMERIC);
 349         // Docs are returned ordered. Used algorithms doesn't change elements order.
 350     }
 351
 352
 353     /**
 354      * Calculate result vector for non Conjunction query
 355      * (like '+something -another')
 356      *
 357      * @param Zend_Search_Lucene_Interface $reader
 358      */
 359     private function _calculateNonConjunctionResult(Zend_Search_Lucene_Interface $reader)
 360     {
 361         $requiredVectors      = array();
 362         $requiredVectorsSizes = array();
 363         $requiredVectorsIds   = array(); // is used to prevent arrays comparison
 364
 365         $optional   = array();
 366         $prohibited = array();
 367
 368         foreach ($this->_terms as $termId => $term) {
 369             $termDocs = array_flip($reader->termDocs($term));
 370
 371             if ($this->_signs[$termId] === true) {
 372                 // required
 373                 $requiredVectors[]      = $termDocs;
 374                 $requiredVectorsSizes[] = count($termDocs);
 375                 $requiredVectorsIds[]   = $termId;
 376             } elseif ($this->_signs[$termId] === false) {
 377                 // prohibited
 378                 // array union
 379                 $prohibited += $termDocs;
 380             } else {
 381                 // neither required, nor prohibited
 382                 // array union
 383                 $optional += $termDocs;
 384             }
 385
 386             $this->_termsFreqs[$termId] = $reader->termFreqs($term);
 387         }
 388
 389         // sort resvectors in order of subquery cardinality increasing
 390         array_multisort($requiredVectorsSizes, SORT_ASC, SORT_NUMERIC,
 391                         $requiredVectorsIds,   SORT_ASC, SORT_NUMERIC,
 392                         $requiredVectors);
 393
 394         $required = null;
 395         foreach ($requiredVectors as $nextResVector) {
 396             if($required === null) {
 397                 $required = $nextResVector;
 398             } else {
 399                 //$required = array_intersect_key($required, $nextResVector);
 400
 401                 /**
 402                  * This code is used as workaround for array_intersect_key() slowness problem.
 403                  */
 404                 $updatedVector = array();
 405                 foreach ($required as $id => $value) {
 406                     if (isset($nextResVector[$id])) {
 407                         $updatedVector[$id] = $value;
 408                     }
 409                 }
 410                 $required = $updatedVector;
 411             }
 412
 413             if (count($required) == 0) {
 414                 // Empty result set, we don't need to check other terms
 415                 break;
 416             }
 417         }
 418
 419         if ($required !== null) {
 420             $this->_resVector = $required;
 421         } else {
 422             $this->_resVector = $optional;
 423         }
 424
 425         if (count($prohibited) != 0) {
 426             // $this->_resVector = array_diff_key($this->_resVector, $prohibited);
 427
 428             /**
 429              * This code is used as workaround for array_diff_key() slowness problem.
 430              */
 431             if (count($this->_resVector) < count($prohibited)) {
 432                 $updatedVector = $this->_resVector;
 433                 foreach ($this->_resVector as $id => $value) {
 434                     if (isset($prohibited[$id])) {
 435                         unset($updatedVector[$id]);
 436                     }
 437                 }
 438                 $this->_resVector = $updatedVector;
 439             } else {
 440                 $updatedVector = $this->_resVector;
 441                 foreach ($prohibited as $id => $value) {
 442                     unset($updatedVector[$id]);
 443                 }
 444                 $this->_resVector = $updatedVector;
 445             }
 446         }
 447
 448         ksort($this->_resVector, SORT_NUMERIC);
 449     }
 450
 451
 452     /**
 453      * Score calculator for conjunction queries (all terms are required)
 454      *
 455      * @param integer $docId
 456      * @param Zend_Search_Lucene_Interface $reader
 457      * @return float
 458      */
 459     public function _conjunctionScore($docId, Zend_Search_Lucene_Interface $reader)
 460     {
 461         if ($this->_coord === null) {
 462             $this->_coord = $reader->getSimilarity()->coord(count($this->_terms),
 463                                                             count($this->_terms) );
 464         }
 465
 466         $score = 0.0;
 467
 468         foreach ($this->_terms as $termId => $term) {
 469             /**
 470              * We don't need to check that term freq is not 0
 471              * Score calculation is performed only for matched docs
 472              */
 473             $score += $reader->getSimilarity()->tf($this->_termsFreqs[$termId][$docId]) *
 474                       $this->_weights[$termId]->getValue() *
 475                       $reader->norm($docId, $term->field);
 476         }
 477
 478         return $score * $this->_coord * $this->getBoost();
 479     }
 480
 481
 482     /**
 483      * Score calculator for non conjunction queries (not all terms are required)
 484      *
 485      * @param integer $docId
 486      * @param Zend_Search_Lucene_Interface $reader
 487      * @return float
 488      */
 489     public function _nonConjunctionScore($docId, $reader)
 490     {
 491         if ($this->_coord === null) {
 492             $this->_coord = array();
 493
 494             $maxCoord = 0;
 495             foreach ($this->_signs as $sign) {
 496                 if ($sign !== false /* not prohibited */) {
 497                     $maxCoord++;
 498                 }
 499             }
 500
 501             for ($count = 0; $count <= $maxCoord; $count++) {
 502                 $this->_coord[$count] = $reader->getSimilarity()->coord($count, $maxCoord);
 503             }
 504         }
 505
 506         $score = 0.0;
 507         $matchedTerms = 0;
 508         foreach ($this->_terms as $termId=>$term) {
 509             // Check if term is
 510             if ($this->_signs[$termId] !== false &&        // not prohibited
 511                 isset($this->_termsFreqs[$termId][$docId]) // matched
 512                ) {
 513                 $matchedTerms++;
 514
 515                 /**
 516                  * We don't need to check that term freq is not 0
 517                  * Score calculation is performed only for matched docs
 518                  */
 519                 $score +=
 520                       $reader->getSimilarity()->tf($this->_termsFreqs[$termId][$docId]) *
 521                       $this->_weights[$termId]->getValue() *
 522                       $reader->norm($docId, $term->field);
 523             }
 524         }
 525
 526         return $score * $this->_coord[$matchedTerms] * $this->getBoost();
 527     }
 528
 529     /**
 530      * Execute query in context of index reader
 531      * It also initializes necessary internal structures
 532      *
 533      * @param Zend_Search_Lucene_Interface $reader
 534      * @param Zend_Search_Lucene_Index_DocsFilter|null $docsFilter
 535      */
 536     public function execute(Zend_Search_Lucene_Interface $reader, $docsFilter = null)
 537     {
 538         if ($this->_signs === null) {
 539             $this->_calculateConjunctionResult($reader);
 540         } else {
 541             $this->_calculateNonConjunctionResult($reader);
 542         }
 543
 544         // Initialize weight if it's not done yet
 545         $this->_initWeight($reader);
 546     }
 547
 548     /**
 549      * Get document ids likely matching the query
 550      *
 551      * It's an array with document ids as keys (performance considerations)
 552      *
 553      * @return array
 554      */
 555     public function matchedDocs()
 556     {
 557         return $this->_resVector;
 558     }
 559
 560     /**
 561      * Score specified document
 562      *
 563      * @param integer $docId
 564      * @param Zend_Search_Lucene_Interface $reader
 565      * @return float
 566      */
 567     public function score($docId, Zend_Search_Lucene_Interface $reader)
 568     {
 569         if (isset($this->_resVector[$docId])) {
 570             if ($this->_signs === null) {
 571                 return $this->_conjunctionScore($docId, $reader);
 572             } else {
 573                 return $this->_nonConjunctionScore($docId, $reader);
 574             }
 575         } else {
 576             return 0;
 577         }
 578     }
 579
 580     /**
 581      * Return query terms
 582      *
 583      * @return array
 584      */
 585     public function getQueryTerms()
 586     {
 587         if ($this->_signs === null) {
 588             return $this->_terms;
 589         }
 590
 591         $terms = array();
 592
 593         foreach ($this->_signs as $id => $sign) {
 594             if ($sign !== false) {
 595                 $terms[] = $this->_terms[$id];
 596             }
 597         }
 598
 599         return $terms;
 600     }
 601
 602     /**
 603      * Query specific matches highlighting
 604      *
 605      * @param Zend_Search_Lucene_Search_Highlighter_Interface $highlighter  Highlighter object (also contains doc for highlighting)
 606      */
 607     protected function _highlightMatches(Zend_Search_Lucene_Search_Highlighter_Interface $highlighter)
 608     {
 609         $words = array();
 610
 611         if ($this->_signs === null) {
 612             foreach ($this->_terms as $term) {
 613                 $words[] = $term->text;
 614             }
 615         } else {
 616             foreach ($this->_signs as $id => $sign) {
 617                 if ($sign !== false) {
 618                     $words[] = $this->_terms[$id]->text;
 619                 }
 620             }
 621         }
 622
 623         $highlighter->highlight($words);
 624     }
 625
 626     /**
 627      * Print a query
 628      *
 629      * @return string
 630      */
 631     public function __toString()
 632     {
 633         // It's used only for query visualisation, so we don't care about characters escaping
 634
 635         $query = '';
 636
 637         foreach ($this->_terms as $id => $term) {
 638             if ($id != 0) {
 639                 $query .= ' ';
 640             }
 641
 642             if ($this->_signs === null || $this->_signs[$id] === true) {
 643                 $query .= '+';
 644             } else if ($this->_signs[$id] === false) {
 645                 $query .= '-';
 646             }
 647
 648             if ($term->field !== null) {
 649                 $query .= $term->field . ':';
 650             }
 651             $query .= $term->text;
 652         }
 653
 654         if ($this->getBoost() != 1) {
 655             $query = '(' . $query . ')^' . round($this->getBoost(), 4);
 656         }
 657
 658         return $query;
 659     }
 660 }
 661