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

Только ради развлечения я реализовал сегодня 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;
    }
}

php optimization data-structures trie
person Dennis Haarbrink    schedule 20.07.2010    source источник
comment
Вы уже профилировали код с помощью xhprof или xdebug?   -  person Charles    schedule 20.07.2010
comment
я еще нет, хороший звонок. я буду завтра!   -  person Dennis Haarbrink    schedule 20.07.2010

Ответы (2)


arrow_upward
3
arrow_downward

Не знаю 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 (который, я полагаю, является добавлением)? Это само по себе изменяет ваше добавление/поиск времени O (n) на Omega (n ^ 2) (n - длина $value) вместо O (n).

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

person Community    schedule 20.07.2010
comment
хороший момент, нет абсолютно никакой необходимости. а даст ли это прибавку к скорости? зато памяти будет легче. несмотря ни на что, я реализую это завтра и опубликую результаты здесь. - person Dennis Haarbrink; 20.07.2010
comment
@ Деннис: Да, имхо. На самом деле это одна из основных причин, почему попытки могут быть такими быстрыми. - person ; 21.07.2010
comment
@Dennis: Мне любопытны результаты, которые вы собирались опубликовать :-) - person ; 10.08.2010

arrow_upward
1
arrow_downward

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

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/>";
        }
    }
person Princeton Ebanks    schedule 20.10.2014