Rework word set computation

Switch from an recursive algorithm for computing the word sets
to an iterative one that benefits from caching intermediate
results. This considerably reduces the amount of memory needed,
so that the depth restriction can be dropped. To ensure that
the number of word sets remains manageable, only sets up to
a certain length are accepted and only a certain number of
total word sets. If word sets need to be dropped, we drop
the ones with more words per word set first.

To further reduce the number of potential word sets, the valid
tokens are looked up first and then only word sets containing
valid tokens are computed.

Fixes #1403, #1404 and #654.

diff --git a/lib/Geocode.php b/lib/Geocode.php
index 9e02150c7fca51c30689e5d7b2dd6f62bc19db2c..7a9f5ad4f2799531c726712dd302612c99dc455f 100644 (file)
--- a/lib/Geocode.php
+++ b/lib/Geocode.php
@@ -348,10 +348,7 @@ class Geocode
             $aNewPhraseSearches = array();
             $sPhraseType = $bIsStructured ? $oPhrase->getPhraseType() : '';
 
-            foreach ($oPhrase->getWordSets() as $iWordSet => $aWordset) {
-                // Too many permutations - too expensive
-                if ($iWordSet > 120) break;
-
+            foreach ($oPhrase->getWordSets() as $aWordset) {
                 $aWordsetSearches = $aSearches;
 
                 // Add all words from this wordset
@@ -641,7 +638,6 @@ class Geocode
                 }
             }
 
-            Debug::printDebugTable('Phrases', $aPhrases);
             Debug::printVar('Tokens', $aTokens);
 
             $oValidTokens = new TokenList();
@@ -686,6 +682,11 @@ class Geocode
 
                 Debug::printGroupTable('Valid Tokens', $oValidTokens->debugInfo());
 
+                foreach ($aPhrases as $oPhrase) {
+                    $oPhrase->computeWordSets($oValidTokens);
+                }
+                Debug::printDebugTable('Phrases', $aPhrases);
+
                 Debug::newSection('Search candidates');
 
                 $aGroupedSearches = $this->getGroupedSearches($aSearches, $aPhrases, $oValidTokens, $bStructuredPhrases);

diff --git a/lib/Phrase.php b/lib/Phrase.php
index 7cf3f29736d0f7cee944581b558a8bc2658d02cd..2e90537e10c48c447fe450da388e8fef8adb5d52 100644 (file)
--- a/lib/Phrase.php
+++ b/lib/Phrase.php
@@ -9,7 +9,8 @@ namespace Nominatim;
  */
 class Phrase
 {
-    const MAX_DEPTH = 7;
+    public const MAX_WORDSET_LEN = 20;
+    public const MAX_WORDSETS = 100;
 
     // Complete phrase as a string.
     private $sPhrase;
@@ -20,13 +21,24 @@ class Phrase
     // Possible segmentations of the phrase.
     private $aWordSets;
 
+    public static function cmpByArraylen($aA, $aB)
+    {
+        $iALen = count($aA);
+        $iBLen = count($aB);
+
+        if ($iALen == $iBLen) {
+            return 0;
+        }
+
+        return ($iALen < $iBLen) ? -1 : 1;
+    }
+
 
     public function __construct($sPhrase, $sPhraseType)
     {
         $this->sPhrase = trim($sPhrase);
         $this->sPhraseType = $sPhraseType;
         $this->aWords = explode(' ', $this->sPhrase);
-        $this->aWordSets = $this->createWordSets($this->aWords, 0);
     }
 
     /**
@@ -60,10 +72,17 @@ class Phrase
      */
     public function addTokens(&$aTokens)
     {
-        foreach ($this->aWordSets as $aSet) {
-            foreach ($aSet as $sWord) {
-                $aTokens[' '.$sWord] = ' '.$sWord;
-                $aTokens[$sWord] = $sWord;
+        $iNumWords = count($this->aWords);
+
+        for ($i = 0; $i < $iNumWords; $i++) {
+            $sPhrase = $this->aWords[$i];
+            $aTokens[' '.$sPhrase] = ' '.$sPhrase;
+            $aTokens[$sPhrase] = $sPhrase;
+
+            for ($j = $i + 1; $j < $iNumWords; $j++) {
+                $sPhrase .= ' '.$this->aWords[$j];
+                $aTokens[' '.$sPhrase] = ' '.$sPhrase;
+                $aTokens[$sPhrase] = $sPhrase;
             }
         }
     }
@@ -75,45 +94,60 @@ class Phrase
      */
     public function invertWordSets()
     {
-        $this->aWordSets = $this->createInverseWordSets($this->aWords, 0);
+        foreach ($this->aWordSets as $i => $aSet) {
+            $this->aWordSets[$i] = array_reverse($aSet);
+        }
     }
 
-    private function createWordSets($aWords, $iDepth)
+    public function computeWordSets($oTokens)
     {
-        $aResult = array(array(join(' ', $aWords)));
-        $sFirstToken = '';
-        if ($iDepth < Phrase::MAX_DEPTH) {
-            while (count($aWords) > 1) {
-                $sWord = array_shift($aWords);
-                $sFirstToken .= ($sFirstToken?' ':'').$sWord;
-                $aRest = $this->createWordSets($aWords, $iDepth + 1);
-                foreach ($aRest as $aSet) {
-                    $aResult[] = array_merge(array($sFirstToken), $aSet);
-                }
-            }
-        }
+        $iNumWords = count($this->aWords);
+        // Caches the word set for the partial phrase up to word i.
+        $aSetCache = array_fill(0, $iNumWords, array());
 
-        return $aResult;
-    }
+        // Initialise first element of cache. There can only be the word.
+        if ($oTokens->containsAny($this->aWords[0])) {
+            $aSetCache[0][] = array($this->aWords[0]);
+        }
 
-    private function createInverseWordSets($aWords, $iDepth)
-    {
-        $aResult = array(array(join(' ', $aWords)));
-        $sFirstToken = '';
-        if ($iDepth < Phrase::MAX_DEPTH) {
-            while (count($aWords) > 1) {
-                $sWord = array_pop($aWords);
-                $sFirstToken = $sWord.($sFirstToken?' ':'').$sFirstToken;
-                $aRest = $this->createInverseWordSets($aWords, $iDepth + 1);
-                foreach ($aRest as $aSet) {
-                    $aResult[] = array_merge(array($sFirstToken), $aSet);
+        // Now do the next elements using what we already have.
+        for ($i = 1; $i < $iNumWords; $i++) {
+            for ($j = $i; $j > 0; $j--) {
+                $sPartial = $j == $i ? $this->aWords[$j] : $this->aWords[$j].' '.$sPartial;
+                if (!empty($aSetCache[$j - 1]) && $oTokens->containsAny($sPartial)) {
+                    $aPartial = array($sPartial);
+                    foreach ($aSetCache[$j - 1] as $aSet) {
+                        if (count($aSet) < Phrase::MAX_WORDSET_LEN) {
+                            $aSetCache[$i][] = array_merge($aSet, $aPartial);
+                        }
+                    }
+                    if (count($aSetCache[$i]) > 2 * Phrase::MAX_WORDSETS) {
+                        usort(
+                            $aSetCache[$i],
+                            array('\Nominatim\Phrase', 'cmpByArraylen')
+                        );
+                        $aSetCache[$i] = array_slice(
+                            $aSetCache[$i],
+                            0,
+                            Phrase::MAX_WORDSETS
+                        );
+                    }
                 }
             }
+
+            // finally the current full phrase
+            $sPartial = $this->aWords[0].' '.$sPartial;
+            if ($oTokens->containsAny($sPartial)) {
+                $aSetCache[$i][] = array($sPartial);
+            }
         }
 
-        return $aResult;
+        $this->aWordSets = $aSetCache[$iNumWords - 1];
+        usort($this->aWordSets, array('\Nominatim\Phrase', 'cmpByArraylen'));
+        $this->aWordSets = array_slice($this->aWordSets, 0, Phrase::MAX_WORDSETS);
     }
 
+
     public function debugInfo()
     {
         return array(

diff --git a/lib/TokenList.php b/lib/TokenList.php
index 84dc98d0584fee10558f3271582bcfe4462fd328..fce5f940b84513a6bc1850cbbbdb5e9fa043682c 100644 (file)
--- a/lib/TokenList.php
+++ b/lib/TokenList.php
@@ -55,6 +55,18 @@ class TokenList
         return isset($this->aTokens[$sWord]);
     }
 
+    /**
+     * Check if there are partial or full tokens for the given word.
+     *
+     * @param string $sWord Token word to look for.
+     *
+     * @return bool True if there is one or more token for the token word.
+     */
+    public function containsAny($sWord)
+    {
+        return isset($this->aTokens[$sWord]) || isset($this->aTokens[' '.$sWord]);
+    }
+
     /**
      * Get the list of tokens for the given token word.
      *

diff --git a/test/php/Nominatim/PhraseTest.php b/test/php/Nominatim/PhraseTest.php
index cd74271543c7979300ea6026dd3109bb2c03a944..c23d648338278a270cecf097669f60cf22a08f5e 100644 (file)
--- a/test/php/Nominatim/PhraseTest.php
+++ b/test/php/Nominatim/PhraseTest.php
@@ -4,6 +4,29 @@ namespace Nominatim;
 
 require_once(CONST_BasePath.'/lib/Phrase.php');
 
+class TokensFullSet
+{
+    public function containsAny($sTerm)
+    {
+        return true;
+    }
+}
+
+// phpcs:ignore PSR1.Classes.ClassDeclaration.MultipleClasses
+class TokensPartialSet
+{
+    public function __construct($aTokens)
+    {
+        $this->aTokens = array_flip($aTokens);
+    }
+
+    public function containsAny($sTerm)
+    {
+        return isset($this->aTokens[$sTerm]);
+    }
+}
+
+// phpcs:ignore PSR1.Classes.ClassDeclaration.MultipleClasses
 class PhraseTest extends \PHPUnit\Framework\TestCase
 {
 
@@ -21,6 +44,7 @@ class PhraseTest extends \PHPUnit\Framework\TestCase
     public function testEmptyPhrase()
     {
         $oPhrase = new Phrase('', '');
+        $oPhrase->computeWordSets(new TokensFullSet());
 
         $this->assertEquals(
             array(array('')),
@@ -32,6 +56,7 @@ class PhraseTest extends \PHPUnit\Framework\TestCase
     public function testSingleWordPhrase()
     {
         $oPhrase = new Phrase('a', '');
+        $oPhrase->computeWordSets(new TokensFullSet());
 
         $this->assertEquals(
             '(a)',
@@ -43,20 +68,23 @@ class PhraseTest extends \PHPUnit\Framework\TestCase
     public function testMultiWordPhrase()
     {
         $oPhrase = new Phrase('a b', '');
+        $oPhrase->computeWordSets(new TokensFullSet());
         $this->assertEquals(
             '(a b),(a|b)',
             $this->serializeSets($oPhrase->getWordSets())
         );
 
         $oPhrase = new Phrase('a b c', '');
+        $oPhrase->computeWordSets(new TokensFullSet());
         $this->assertEquals(
-            '(a b c),(a|b c),(a|b|c),(a b|c)',
+            '(a b c),(a|b c),(a b|c),(a|b|c)',
             $this->serializeSets($oPhrase->getWordSets())
         );
 
         $oPhrase = new Phrase('a b c d', '');
+        $oPhrase->computeWordSets(new TokensFullSet());
         $this->assertEquals(
-            '(a b c d),(a|b c d),(a|b|c d),(a|b|c|d),(a|b c|d),(a b|c d),(a b|c|d),(a b c|d)',
+            '(a b c d),(a b c|d),(a b|c d),(a|b c d),(a b|c|d),(a|b c|d),(a|b|c d),(a|b|c|d)',
             $this->serializeSets($oPhrase->getWordSets())
         );
     }
@@ -65,25 +93,47 @@ class PhraseTest extends \PHPUnit\Framework\TestCase
     public function testInverseWordSets()
     {
         $oPhrase = new Phrase('a b c', '');
+        $oPhrase->computeWordSets(new TokensFullSet());
         $oPhrase->invertWordSets();
 
         $this->assertEquals(
-            '(a b c),(c|a b),(c|b|a),(b c|a)',
+            '(a b c),(b c|a),(c|a b),(c|b|a)',
             $this->serializeSets($oPhrase->getWordSets())
         );
     }
 
 
-    public function testMaxDepth()
+    public function testMaxWordSets()
     {
         $oPhrase = new Phrase(join(' ', array_fill(0, 4, 'a')), '');
+        $oPhrase->computeWordSets(new TokensFullSet());
         $this->assertEquals(8, count($oPhrase->getWordSets()));
         $oPhrase->invertWordSets();
         $this->assertEquals(8, count($oPhrase->getWordSets()));
 
         $oPhrase = new Phrase(join(' ', array_fill(0, 18, 'a')), '');
-        $this->assertEquals(41226, count($oPhrase->getWordSets()));
+        $oPhrase->computeWordSets(new TokensFullSet());
+        $this->assertEquals(Phrase::MAX_WORDSETS, count($oPhrase->getWordSets()));
         $oPhrase->invertWordSets();
-        $this->assertEquals(41226, count($oPhrase->getWordSets()));
+        $this->assertEquals(Phrase::MAX_WORDSETS, count($oPhrase->getWordSets()));
+    }
+
+
+    public function testPartialTokensShortTerm()
+    {
+        $oPhrase = new Phrase('a b c d', '');
+        $oPhrase->computeWordSets(new TokensPartialSet(array('a', 'b', 'd', 'b c', 'b c d')));
+        $this->assertEquals(
+            '(a|b c d),(a|b c|d)',
+            $this->serializeSets($oPhrase->getWordSets())
+        );
+    }
+
+
+    public function testPartialTokensLongTerm()
+    {
+        $oPhrase = new Phrase(join(' ', array_fill(0, 18, 'a')), '');
+        $oPhrase->computeWordSets(new TokensPartialSet(array('a', 'a a a a a')));
+        $this->assertEquals(80, count($oPhrase->getWordSets()));
     }
 }