]> git.openstreetmap.org Git - nominatim.git/blob - lib-php/SimpleWordList.php
Merge remote-tracking branch 'upstream/master'
[nominatim.git] / lib-php / SimpleWordList.php
1 <?php
2
3 namespace Nominatim;
4
5 /**
6  * A word list creator based on simple splitting by space.
7  *
8  * Creates possible permutations of split phrases by finding all combination
9  * of splitting the phrase on space boundaries.
10  */
11 class SimpleWordList
12 {
13     const MAX_WORDSET_LEN = 20;
14     const MAX_WORDSETS = 100;
15
16     // The phrase as a list of simple terms (without spaces).
17     private $aWords;
18
19     /**
20      * Create a new word list
21      *
22      * @param string sPhrase  Phrase to create the word list from. The phrase is
23      *                        expected to be normalised, so that there are no
24      *                        subsequent spaces.
25      */
26     public function __construct($sPhrase)
27     {
28         if (strlen($sPhrase) > 0) {
29             $this->aWords = explode(' ', $sPhrase);
30         } else {
31             $this->aWords = array();
32         }
33     }
34
35     /**
36      * Get all possible tokens that are present in this word list.
37      *
38      * @return array The list of string tokens in the word list.
39      */
40     public function getTokens()
41     {
42         $aTokens = array();
43         $iNumWords = count($this->aWords);
44
45         for ($i = 0; $i < $iNumWords; $i++) {
46             $sPhrase = $this->aWords[$i];
47             $aTokens[$sPhrase] = $sPhrase;
48
49             for ($j = $i + 1; $j < $iNumWords; $j++) {
50                 $sPhrase .= ' '.$this->aWords[$j];
51                 $aTokens[$sPhrase] = $sPhrase;
52             }
53         }
54
55         return $aTokens;
56     }
57
58     /**
59      * Compute all possible permutations of phrase splits that result in
60      * words which are in the token list.
61      */
62     public function getWordSets($oTokens)
63     {
64         $iNumWords = count($this->aWords);
65
66         if ($iNumWords == 0) {
67             return null;
68         }
69
70         // Caches the word set for the partial phrase up to word i.
71         $aSetCache = array_fill(0, $iNumWords, array());
72
73         // Initialise first element of cache. There can only be the word.
74         if ($oTokens->containsAny($this->aWords[0])) {
75             $aSetCache[0][] = array($this->aWords[0]);
76         }
77
78         // Now do the next elements using what we already have.
79         for ($i = 1; $i < $iNumWords; $i++) {
80             for ($j = $i; $j > 0; $j--) {
81                 $sPartial = $j == $i ? $this->aWords[$j] : $this->aWords[$j].' '.$sPartial;
82                 if (!empty($aSetCache[$j - 1]) && $oTokens->containsAny($sPartial)) {
83                     $aPartial = array($sPartial);
84                     foreach ($aSetCache[$j - 1] as $aSet) {
85                         if (count($aSet) < SimpleWordList::MAX_WORDSET_LEN) {
86                             $aSetCache[$i][] = array_merge($aSet, $aPartial);
87                         }
88                     }
89                     if (count($aSetCache[$i]) > 2 * SimpleWordList::MAX_WORDSETS) {
90                         usort(
91                             $aSetCache[$i],
92                             array('\Nominatim\SimpleWordList', 'cmpByArraylen')
93                         );
94                         $aSetCache[$i] = array_slice(
95                             $aSetCache[$i],
96                             0,
97                             SimpleWordList::MAX_WORDSETS
98                         );
99                     }
100                 }
101             }
102
103             // finally the current full phrase
104             $sPartial = $this->aWords[0].' '.$sPartial;
105             if ($oTokens->containsAny($sPartial)) {
106                 $aSetCache[$i][] = array($sPartial);
107             }
108         }
109
110         $aWordSets = $aSetCache[$iNumWords - 1];
111         usort($aWordSets, array('\Nominatim\SimpleWordList', 'cmpByArraylen'));
112         return array_slice($aWordSets, 0, SimpleWordList::MAX_WORDSETS);
113     }
114
115     public static function cmpByArraylen($aA, $aB)
116     {
117         $iALen = count($aA);
118         $iBLen = count($aB);
119
120         if ($iALen == $iBLen) {
121             return 0;
122         }
123
124         return ($iALen < $iBLen) ? -1 : 1;
125     }
126
127     public function debugInfo()
128     {
129         return $this->aWords;
130     }
131 }