Optimisation de l'implémentation de Trie

Question

Pour la seule raison que ce soit amusant, j'ai implémenté un Trie aujourd'hui. Pour le moment, il supporte add() et search(), remove() devrait aussi être implémenté mais je pense que c'est assez simple.

Il est entièrement fonctionnel, mais remplir le Trie avec des données prend un peu trop à mon goût. J'utilise cette liste comme source de données: http://www.isc.ro/lists/twl06.zip (trouvé ailleurs sur SO). Cela prend ~ 11s à charger. Ma mise en œuvre initiale a pris ~ 15s donc je lui ai déjà donné une belle amélioration de la performance, mais je ne suis toujours pas satisfait :)

Ma question est: quoi d'autre pourrait me donner un coup de pouce (substantiel) de performance? Je ne suis pas lié par cette conception, une révision complète est acceptable.

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

Je ne sais pas php mais,

dans les méthodes suivantes:

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; 
    } 

Pourquoi avez-vous besoin même le $str .= $char (que je suppose est append)? Cela modifie lui-même votre addition/recherche de temps O (n) en Omega (n^2) (n est la longueur de $value) au lieu de O (n). Dans une étape, vous marchez généralement pendant que vous marchez sur la chaîne, c'est-à-dire que vous trouvez le nœud suivant basé sur le caractère actuel, plutôt que sur le préfixe courant.

Answer 2

Je suppose que cette implémentation est pour un type d'insertion et de recherche Key | value? En voici un qui traite les mots [anglais].

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(); 

    } 
} 

Exemple d'utilisation

$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/>"; 
     } 
    }