Initial commit
[moodle.git] / search / 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) 2006 Zend Technologies USA Inc. (http://www.zend.com)
19  * @license    http://framework.zend.com/license/new-bsd     New BSD License
20  */
23 /**
24  * Zend_Search_Lucene_Search_Query
25  */
26 require_once 'Zend/Search/Lucene/Search/Query.php';
28 /**
29  * Zend_Search_Lucene_Search_Weight_MultiTerm
30  */
31 require_once 'Zend/Search/Lucene/Search/Weight/Phrase.php';
34 /**
35  * A Query that matches documents containing a particular sequence of terms.
36  *
37  * @category   Zend
38  * @package    Zend_Search_Lucene
39  * @subpackage Search
40  * @copyright  Copyright (c) 2006 Zend Technologies USA Inc. (http://www.zend.com)
41  * @license    http://framework.zend.com/license/new-bsd     New BSD License
42  */
43 class Zend_Search_Lucene_Search_Query_Phrase extends Zend_Search_Lucene_Search_Query
44 {
45     /**
46      * Terms to find.
47      * Array of Zend_Search_Lucene_Index_Term objects.
48      *
49      * @var array
50      */
51     private $_terms;
53     /**
54      * Term positions (relative positions of terms within the phrase).
55      * Array of integers
56      *
57      * @var array
58      */
59     private $_offsets;
61     /**
62      * Sets the number of other words permitted between words in query phrase.
63      * If zero, then this is an exact phrase search.  For larger values this works
64      * like a WITHIN or NEAR operator.
65      *
66      * The slop is in fact an edit-distance, where the units correspond to
67      * moves of terms in the query phrase out of position.  For example, to switch
68      * the order of two words requires two moves (the first move places the words
69      * atop one another), so to permit re-orderings of phrases, the slop must be
70      * at least two.
71      * More exact matches are scored higher than sloppier matches, thus search
72      * results are sorted by exactness.
73      *
74      * The slop is zero by default, requiring exact matches.
75      *
76      * @var unknown_type
77      */
78     private $_slop;
80     /**
81      * Result vector.
82      * Bitset or array of document IDs
83      * (depending from Bitset extension availability).
84      *
85      * @var mixed
86      */
87     private $_resVector = null;
89     /**
90      * Terms positions vectors.
91      * Array of Arrays:
92      * term1Id => (docId => array( pos1, pos2, ... ), ...)
93      * term2Id => (docId => array( pos1, pos2, ... ), ...)
94      *
95      * @var array
96      */
97     private $_termsPositions = array();
99     /**
100      * Class constructor.  Create a new prase query.
101      *
102      * @param string $field    Field to search.
103      * @param array  $terms    Terms to search Array of strings.
104      * @param array  $offsets  Relative term positions. Array of integers.
105      * @throws Zend_Search_Lucene_Exception
106      */
107     public function __construct($terms = null, $offsets = null, $field = null)
108     {
109         $this->_slop = 0;
111         if (is_array($terms)) {
112             $this->_terms = array();
113             foreach ($terms as $termId => $termText) {
114                 $this->_terms[$termId] = ($field !== null)? new Zend_Search_Lucene_Index_Term($termText, $field):
115                                                             new Zend_Search_Lucene_Index_Term($termText);
116             }
117         } else if ($terms === null) {
118             $this->_terms = array();
119         } else {
120             throw new Zend_Search_Lucene_Exception('terms argument must be array of strings or null');
121         }
123         if (is_array($offsets)) {
124             if (count($this->_terms) != count($offsets)) {
125                 throw new Zend_Search_Lucene_Exception('terms and offsets arguments must have the same size.');
126             }
127             $this->_offsets = $offsets;
128         } else if ($offsets === null) {
129             $this->_offsets = array();
130             foreach ($this->_terms as $termId => $term) {
131                 $position = count($this->_offsets);
132                 $this->_offsets[$termId] = $position;
133             }
134         } else {
135             throw new Zend_Search_Lucene_Exception('offsets argument must be array of strings or null');
136         }
137     }
139     /**
140      * Set slop
141      *
142      * @param integer $slop
143      */
144     public function setSlop($slop)
145     {
146         $this->_slop = $slop;
147     }
150     /**
151      * Get slop
152      *
153      * @return integer
154      */
155     public function getSlop()
156     {
157         return $this->_slop;
158     }
161     /**
162      * Adds a term to the end of the query phrase.
163      * The relative position of the term is specified explicitly or the one immediately
164      * after the last term added.
165      *
166      * @param Zend_Search_Lucene_Index_Term $term
167      * @param integer $position
168      */
169     public function addTerm(Zend_Search_Lucene_Index_Term $term, $position = null) {
170         if ((count($this->_terms) != 0)&&(end($this->_terms)->field != $term->field)) {
171             throw new Zend_Search_Lucene_Exception('All phrase terms must be in the same field: ' .
172                                                    $term->field . ':' . $term->text);
173         }
175         $this->_terms[] = $term;
176         if ($position !== null) {
177             $this->_offsets[] = $position;
178         } else if (count($this->_offsets) != 0) {
179             $this->_offsets[] = end($this->_offsets) + 1;
180         } else {
181             $this->_offsets[] = 0;
182         }
183     }
186     /**
187      * Returns query term
188      *
189      * @return array
190      */
191     public function getTerms()
192     {
193         return $this->_terms;
194     }
197     /**
198      * Set weight for specified term
199      *
200      * @param integer $num
201      * @param Zend_Search_Lucene_Search_Weight_Term $weight
202      */
203     public function setWeight($num, $weight)
204     {
205         $this->_weights[$num] = $weight;
206     }
209     /**
210      * Constructs an appropriate Weight implementation for this query.
211      *
212      * @param Zend_Search_Lucene $reader
213      * @return Zend_Search_Lucene_Search_Weight
214      */
215     protected function _createWeight($reader)
216     {
217         return new Zend_Search_Lucene_Search_Weight_Phrase($this, $reader);
218     }
221     /**
222      * Calculate result vector
223      *
224      * @param Zend_Search_Lucene $reader
225      */
226     private function _calculateResult($reader)
227     {
228         if (extension_loaded('bitset')) {
229             foreach( $this->_terms as $termId=>$term ) {
230                 if($this->_resVector === null) {
231                     $this->_resVector = bitset_from_array($reader->termDocs($term));
232                 } else {
233                     $this->_resVector = bitset_intersection(
234                                 $this->_resVector,
235                                 bitset_from_array($reader->termDocs($term)) );
236                 }
238                 $this->_termsPositions[$termId] = $reader->termPositions($term);
239             }
240         } else {
241             foreach( $this->_terms as $termId=>$term ) {
242                 if($this->_resVector === null) {
243                     $this->_resVector = array_flip($reader->termDocs($term));
244                 } else {
245                     $termDocs = array_flip($reader->termDocs($term));
246                     foreach($this->_resVector as $key=>$value) {
247                         if (!isset( $termDocs[$key] )) {
248                             unset( $this->_resVector[$key] );
249                         }
250                     }
251                 }
253                 $this->_termsPositions[$termId] = $reader->termPositions($term);
254             }
255         }
256     }
259     /**
260      * Score calculator for exact phrase queries (terms sequence is fixed)
261      *
262      * @param integer $docId
263      * @return float
264      */
265     public function _exactPhraseFreq($docId)
266     {
267         $freq = 0;
269         // Term Id with lowest cardinality
270         $lowCardTermId = null;
272         // Calculate $lowCardTermId
273         foreach ($this->_terms as $termId => $term) {
274             if ($lowCardTermId === null ||
275                 count($this->_termsPositions[$termId][$docId]) <
276                 count($this->_termsPositions[$lowCardTermId][$docId]) ) {
277                     $lowCardTermId = $termId;
278                 }
279         }
281         // Walk through positions of the term with lowest cardinality
282         foreach ($this->_termsPositions[$lowCardTermId][$docId] as $lowCardPos) {
283             // We expect phrase to be found
284             $freq++;
286             // Walk through other terms
287             foreach ($this->_terms as $termId => $term) {
288                 if ($termId != $lowCardTermId) {
289                     $expectedPosition = $lowCardPos +
290                                             ($this->_offsets[$termId] -
291                                              $this->_offsets[$lowCardTermId]);
293                     if (!in_array($expectedPosition, $this->_termsPositions[$termId][$docId])) {
294                         $freq--;  // Phrase wasn't found.
295                         break;
296                     }
297                 }
298             }
299         }
301         return $freq;
302     }
304     /**
305      * Score calculator for sloppy phrase queries (terms sequence is fixed)
306      *
307      * @param integer $docId
308      * @param Zend_Search_Lucene $reader
309      * @return float
310      */
311     public function _sloppyPhraseFreq($docId, Zend_Search_Lucene $reader)
312     {
313         $freq = 0;
315         $phraseQueue = array();
316         $phraseQueue[0] = array(); // empty phrase
317         $lastTerm = null;
319         // Walk through the terms to create phrases.
320         foreach ($this->_terms as $termId => $term) {
321             $queueSize = count($phraseQueue);
322             $firstPass = true;
324             // Walk through the term positions.
325             // Each term position produces a set of phrases.
326             foreach ($this->_termsPositions[$termId][$docId] as $termPosition ) {
327                 if ($firstPass) {
328                     for ($count = 0; $count < $queueSize; $count++) {
329                         $phraseQueue[$count][$termId] = $termPosition;
330                     }
331                 } else {
332                     for ($count = 0; $count < $queueSize; $count++) {
333                         if ($lastTerm !== null &&
334                             abs( $termPosition - $phraseQueue[$count][$lastTerm] -
335                                  ($this->_offsets[$termId] - $this->_offsets[$lastTerm])) > $this->_slop) {
336                             continue;
337                         }
339                         $newPhraseId = count($phraseQueue);
340                         $phraseQueue[$newPhraseId]          = $phraseQueue[$count];
341                         $phraseQueue[$newPhraseId][$termId] = $termPosition;
342                     }
344                 }
346                 $firstPass = false;
347             }
348             $lastTerm = $termId;
349         }
352         foreach ($phraseQueue as $phrasePos) {
353             $minDistance = null;
355             for ($shift = -$this->_slop; $shift <= $this->_slop; $shift++) {
356                 $distance = 0;
357                 $start = reset($phrasePos) - reset($this->_offsets) + $shift;
359                 foreach ($this->_terms as $termId => $term) {
360                     $distance += abs($phrasePos[$termId] - $this->_offsets[$termId] - $start);
362                     if($distance > $this->_slop) {
363                         break;
364                     }
365                 }
367                 if ($minDistance === null || $distance < $minDistance) {
368                     $minDistance = $distance;
369                 }
370             }
372             if ($minDistance <= $this->_slop) {
373                 $freq += $reader->getSimilarity()->sloppyFreq($minDistance);
374             }
375         }
377         return $freq;
378     }
381     /**
382      * Score specified document
383      *
384      * @param integer $docId
385      * @param Zend_Search_Lucene $reader
386      * @return float
387      */
388     public function score($docId, $reader)
389     {
390         // optimize zero-term case
391         if (count($this->_terms) == 0) {
392             return 0;
393         }
395         if($this->_resVector === null) {
396             $this->_calculateResult($reader);
397             $this->_initWeight($reader);
398         }
400         if ( (extension_loaded('bitset')) ?
401                 bitset_in($this->_resVector, $docId) :
402                 isset($this->_resVector[$docId])  ) {
403             if ($this->_slop == 0) {
404                 $freq = $this->_exactPhraseFreq($docId);
405             } else {
406                 $freq = $this->_sloppyPhraseFreq($docId, $reader);
407             }
409 /*
410             return $reader->getSimilarity()->tf($freq) *
411                    $this->_weight->getValue() *
412                    $reader->norm($docId, reset($this->_terms)->field);
413 */
414             if ($freq != 0) {
415                 $tf = $reader->getSimilarity()->tf($freq);
416                 $weight = $this->_weight->getValue();
417                 $norm = $reader->norm($docId, reset($this->_terms)->field);
419                 return $tf*$weight*$norm;
420             }
421         } else {
422             return 0;
423         }
424     }