Оптимизация реализации Trie

Question

Без всяких причин, кроме забавы, я внедрил сегодня Trie. На данный момент он поддерживает add() и search(), remove() также должен быть реализован, но я думаю, что это довольно просто.

Это полностью функциональный, но заполнение Trie данными занимает немного слишком много для моего вкуса. Я использую этот список как источник данных: http://www.isc.ro/lists/twl06.zip (найден где-то еще на SO). Для загрузки требуется ~ 11 секунд. Моя первоначальная реализация заняла ~ 15 секунд, поэтому я уже дал ей хороший прирост производительности, но я все еще не удовлетворен :)

Мой вопрос: что еще может дать мне существенное повышение производительности? Я не связан этим дизайном, полный пересмотр является приемлемым.

class Trie 
{ 
    private $trie; 
    public function __construct(TrieNode $trie = null) 
    { 
     if($trie !== null) $this->trie = $trie; 
     else $this->trie = new TrieNode(); 
     $this->counter = 0; 
    } 
    public function add($value, $val = null) 
    { 
     $str = ''; 
     $trie_ref = $this->trie; 
     foreach(str_split($value) as $char) 
     { 
      $str .= $char; 
      $trie_ref = $trie_ref->addNode($str); 
     } 
     $trie_ref->value = $val; 
     return true; 
    } 
    public function search($value, $only_words = false) 
    { 
     if($value === '') return $this->trie; 
     $trie_ref = $this->trie; 
     $str = ''; 
     foreach(str_split($value) as $char) 
     { 
      $str .= $char; 
      if($trie_ref = $trie_ref->getNode($str)) 
      { 
       if($str === $value) return ($only_words ? $this->extractWords($trie_ref) : new self($trie_ref)); 
       continue; 
      } 
      return false; 
     } 
     return false; 
    } 
    public function extractWords(TrieNode $trie) 
    { 
     $res = array(); 
     foreach($trie->getChildren() as $child) 
     { 
      if($child->value !== null) $res[] = $child->value; 
      if($child->hasChildren()) $res = array_merge($res, $this->extractWords($child)); 
     } 
     return $res; 
    } 
} 
class TrieNode 
{ 
    public $value; 
    protected $children = array(); 
    public function addNode($index) 
    { 
     if(isset($this->children[$index])) return $this->children[$index]; 
     return $this->children[$index] = new self(); 
    } 
    public function getNode($index) 
    { 
     return (isset($this->children[$index]) ? $this->children[$index] : false); 
    } 
    public function getChildren() 
    { 
     return $this->children; 
    } 
    public function hasChildren() 
    { 
     return count($this->children)>0; 
    } 
} 

Answer 1

Не знаю PHP, но

в следующих методов:

public function add($value, $val = null) 
    { 
     $str = ''; 
     $trie_ref = $this->trie; 
     foreach(str_split($value) as $char) 
     { 
      $str .= $char; 
      $trie_ref = $trie_ref->addNode($str); 
     } 
     $trie_ref->value = $val; 
     return true; 
    } 
    public function search($value, $only_words = false) 
    { 
     if($value === '') return $this->trie; 
     $trie_ref = $this->trie; 
     $str = ''; 
     foreach(str_split($value) as $char) 
     { 
      $str .= $char; 
      if($trie_ref = $trie_ref->getNode($str)) 
      { 
       if($str === $value) return ($only_words ? $this->extractWords($trie_ref) : new self($trie_ref)); 
       continue; 
      } 
      return false; 
     } 
     return false; 
    } 

Почему бы вам даже нужен $str .= $char (который я полагаю Append)? Это само по себе меняет ваше добавление/поиск O (n) времени на Omega (n^2) (n - длина $value) вместо O (n).

В trie, вы обычно ходите по trie во время ходьбы по строке. Если вы найдете следующий узел на основе текущего символа, а не текущий префикс.

Answer 2

Я полагаю, что эта реализация предназначена для ключа | значения типа вставки и поиска? Вот один, который обрабатывает [английские] слова.

class Trie { 


static function insert_word(Node $root, $text) 
{ 
    $v = $root; 
    foreach(str_split($text) as $char) { 
    $next = $v->children[$char]; 
     if ($next === null) 
     { 
      $v->children[$char] = $next = new Node(); 
     } 
     $v = $next; 
    } 

    $v->leaf = true; 
} 


static function get_words_sorted(Node $node, $text) 
{ 

    $res = array(); 
    for($ch = 0; $ch < 128; $ch++) { 
    $child = $node->children[chr($ch)]; 

     if ($child !== null) 
     { 
      $res = array_merge($res, Trie::get_words_sorted($child, $text . chr($ch))); 

     } 
    } 
    if ($node->leaf === true) 
    { 
     $res[] = $text; 
    } 
    return $res; 

} 

static function search(Node $root, $text) 
{ 
    $v = $root; 
    while($v !== null) 
    { 
     foreach(str_split($text) as $char) { 
      $next = $v->children[$char]; 
      if ($next === null) 
      { 
       return false; 
      } 
      else 
      { 
       $v = $next; 
      } 
     } 

     if($v->leaf === true) 
     { 
      return true; 
     } 
     else 
     { 
      return false; 
     } 

    } 
    return false; 

} 

} 


class Node { 

    public $children; 
    public $leaf; 


    function __construct() 
    { 
     $children = Array(); 

    } 
} 

Пример использования

$root = new Node(); 
    $words = Array("an", "ant", "all", "allot", "alloy", "aloe", "are", "ate", "be"); 


    for ($i = 0; $i < sizeof($words); $i++) 
    { 

     Trie::insert_word($root, $words[$i]); 
    } 

    $search_words = array("alloy", "ant", "bee", "aren't", "allot"); 

    foreach($search_words as $word) 
    { 
     if(Trie::search($root, $word) === true) 
     { 
      echo $word . " IS in my dictionary<br/>"; 
     } 
     else 
     { 
      echo $word . " is NOT in my dictionary <br/>"; 
     } 
    }