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