Building prefix tree from dictionary, performance issues

Question

I'm trying to build a prfix tree. So, using the following dictionary 'and','anna','ape','apple', graph should look like this: I've tried 2 approaches: using associative array and using self-written tree/node classes.

Note: original dictionary is something about 8 MB and contains >600000 words.

Associative array aproach:

function letter_to_graph ($graph_path,$word,$letter_index) {
    $letter=$word[$letter_index];
    if (!isset($graph_path[$letter])) {
        $graph_path[$letter]=array();
    }
    if ($letter_index == strlen($word)-1) {
        $graph_path[$letter]['.']=array();
    } else {
        letter_to_graph(&$graph_path[$letter],$word,$letter_index+1);
    }
}

function push_word_into_graph ($graph,$word) {
    letter_to_graph(&$graph,$word,0);
}

$words_graph = array();
for ($i=0;$i<count($words);$i++) {
    push_word_into_graph(&$words_graph,strtolower($words[$i]));
    //if ($i % 300 == 0) {echo $i . "_<br/>";} //this is just for testing
}

It takes ~35 seconds to execute, eats up to ~350MB.

Node/tree approach:

class Node
{
    public $_children;

    public function __construct() {
        $this->_children = array();
    }

    public function add_child ($val) {
        if ($this->_children === null)
            $this->_children=array();
        $tmp = new Node();
        $this->_children[$val] = &$tmp;
        return $tmp;
    }
    public function has_child($val) {
        if (isset($this->_children[$val])) {
            return true;
        }
        return false;
    }
    public function get_child($val) {
        //if ($this->has_child($val))
            return $this->_children[$val];
        //else 
            //return false;
    }

}

class Tree
{
    protected $root; 

    public function __construct() {
        $this->root = new Node ();
    }
    public function insert_word ($word) {
        $this->insert_letter_node(&$this->root,$word,0);
    }

    protected function insert_letter_node($node,$word,$letter_index) {
        $letter=$word[$letter_index];
        if (!$node->has_child($letter)) {
            $new_node = $node->add_child ($letter);
        } else {
            $new_node = $node->get_child ($letter);
        }

        if ($letter_index < strlen($word)-1) {
            $this->insert_letter_node(&$new_node,$word,$letter_index+1);
        } else {
            $new_node->add_child('.');
        }
    }
}

$result_tree= new Tree();
for ($i=0;$i<(count($words));$i++) {
    $result_tree->insert_word(strtolower($words[$i]));
    //if ($i % 300 == 0) {echo $i . "_<br/>";}//this is just for testing
}

This one takes ~240 seconds to execute (estimated; actually it stops at half-path due to timeout limit) and eats up to ~550MB while working (so, if there were no timeout, it could've eaten much more).

They both are building correct graphs (second was tested on a part of dictionary), however 2nd approach is ~7 times slower and "eats" at least twice as much memory. Main question is "why the difference is so big?" - they both seem to have identical complexity. And the second question is "how to make it faster/less memory consuming?". Am I using pointers wrong somewhere?

Some notes on my code :

• I've "commented out" the unnecessary has_child() check, however it doesn't increase speed significantly.

• Currently I'm testing it on php 5.3.2 with Apache 2.2 on win7x32.

• Current numbers are not quite accurate - the time/memory usage currently includes populating $words by reading file line-by-line, however this is not really the issue - it takes ~1 second and uses only a small amount of memory (not more than 7MB).

• Using class approach on php7/win8x64 takes 124s and ~800mb.

UPDATE: I've followed some advices and did following (code in the question is a bit outdated right now):

• Got rid of recursion (no significant improvement).

• Got rid of not really necessary . nodes by replacing them with isEndOfAword flag to a Node (significant improvement, something about 30% both in time and memory usage)

• Modified functions to accept variables by reference instead of using something like letter_to_graph(&$graph,$word,0);. This was done to test code on php7.
• Switched to C++ for current task. Simple trie as from this tutorial http://www.sourcetricks.com/2011/06/c-tries.html takes ~3s and uses ~100 MB at most.

As long as I've switched to C++, I'm leaving this question open, untill someone explains me, why is php operating seven times slower on Node with single Array property and a couple of methods versus just Array of Arrays (of Arrays of Arrays...).

Also I'm starting a bounty, so, probably, you will want to run my code on your machine and check, if the second approach is really 6-7 times slower (3-4 times slower in php7). There is a probability, that something can be wrong with my environment or php configuration. If you are willing to do so, you can take any large english dictionary (500-700 thousands of words) first and put it in $words array;

Answer 1

Time for a little overkill then - PHP can be just as fast, or even faster, than the C++ solution here.

<?php
function add_word(&$index, $word) {
    $length = strlen($word);

    if (!$length) return;

    $index[$word]['.'] = $word;

    $prefix = $word;

    for($i = $length; $i > 0; $i--) {
        $prefix_prev = substr($word, 0, $i - 1);

        if(!isset($index[$prefix_prev][$prefix])) {
            $index[$prefix_prev][$prefix] = &$index[$prefix];
        } else {
            break;
        }

        $prefix = $prefix_prev;
    }
}

function explore_prefix(&$index, $prefix) {
    $result = [];
    array_walk_recursive($index[$prefix], function($word) use (&$result) {
        $result[] = $word;
    });
    return $result;
}

$index = [];
$file = fopen("words.txt", "r");

if($file)  {
    while ($word = fgets($file)) {
        $word = trim($word);
        add_word($index, $word);
    }
    fclose($file);
}

print_r(explore_prefix($index, 'ban'));
print_r(explore_prefix($index, 'tur'));

That algorithm does build the index in less than 2.5 seconds for a list of 663k words. (http://app.aspell.net/create with 95 (insane) 3 (seldom used) Strip)

The catch? Memory consumption is at ~750MB with php 7.0.6 on Arch 64bit.

How does this approach then differ from the original one?

Mostly by storing the tree in a flat hash map, rather than nesting right away. It's also storing the full prefix in the hash map.

The latter one is responsible for the higher memory consumption, but it does also allow to traverse the tree from longest(!) to shortest prefix, and stopping right away when encountering an already known prefix. This little hack makes the effective runtime independent of the length of the words, you are only paying for each unique prefix once.

Just removing the break will already triple the runtime, and writing to the index unconditionally ramps the runtime back to the ~10s, which is almost the same magnitude as the OPs approach with php7.

Actually, in the current implementation, about 50% of the CPU time is spent on substr, but I can't invoke it less often than that. String handling in PHP is pushed to the absolute limits here.

You can do the same in C++, and probably even cut the runtime at least in halt once more. But don't expect the memory usage to go down by much this time. This is a good example of how dynamic programming can trade additional memory consumption for a vastly improved performance.

Why do OOP and the array approach differ so much?

There is a lot of overhead involved when working with objects in PHP, mostly related to possible magic and reflection. The compiler isn't able to just inline functions as it would in other, stricter typed languages but needs a rather long detour to dispatch method calls.

Objects themselves are also nasty little beasts - then compiler can't just deduce from the context as what to interpret the memory block, like any compiler in C++ can, but the Object itself holds a lot of metadata, including the information what datatypes it members currently(!) have and alike.

The compiler will surely try to work around this, but as PHP is weakly typed, only rather simple constructs will be efficient.

There is actually a tiny difference between the implementations:

$graph_path[$letter]=array();

vs

public $_children = array();
...
if ($this->_children === null)
    $this->_children=array();

You did not instantiate a new array in the Node object by default.

There is a catch to that. The compiler can no longer deduce that Node::children is an array in all contexts accessing it. This does increase the effective memory usage.

For a fair comparison, let's just fix that. And while we are at it, also use typehints properly, so we can aid the compiler as much as possible:

class Node
{
    private $_children = [];

    public function __construct()
    {
    }

    public function add_child(string $val)
    {
        $tmp = new Node();
        $this->_children[$val] = $tmp;
        return $tmp;
    }

    public function has_child(string $val)
    {
        if (isset($this->_children[$val])) {
            return true;
        }
        return false;
    }

    public function get_child(string $val)
    {
        //if ($this->has_child($val))
        return $this->_children[$val];
        //else
        //return false;
    }

}

class Tree
{
    protected $root;

    public function __construct()
    {
        $this->root = new Node ();
    }

    public function insert_word(string $word)
    {
        $this->insert_letter_node($this->root, $word, 0);
    }

    protected function insert_letter_node(Node $node, string $word,
                                          int $letter_index)
    {
        $letter = $word[$letter_index];
        if (!$node->has_child($letter)) {
            $new_node = $node->add_child($letter);
        } else {
            $new_node = $node->get_child($letter);
        }

        if ($letter_index < strlen($word) - 1) {
            $this->insert_letter_node($new_node, $word, $letter_index + 1);
        } else {
            $new_node->add_child('.');
        }
    }
}

Benchmark

Now let's compare how the different versions actually fair against each other.

I'm testing this on a 64bit PHP 7.0.4, running on Arch Linux 64bit, 2Ghz Intel Broadwell processor with Turbo disabled. Using the word list mentioned earlier, mixed case. Best out of 3 runs each.

The times measured are only for building the tree. Memory is measured with memory_get_usage(). This is allocated memory, not memory actually assigned by the OS and in use.

• Original array implementation
  • Time: 13.5s
  • Memory: 707.7MB
• Overkill flattened array
  • Time: 2.49s
  • Memory: 763.1MB
• Untyped OOP:
  • Time: 36.7s
  • Memory: 888.7MB
• Typed OOP
  • Time: 33.8s
  • Memory: 800.408MB

Second pass with all strings forced to lower case. The word list still contains special characters:

• Original array implementation
  • Time: 13.4s
  • Memory: 660.0MB
• Overkill flattened array
  • Time: 2.37s
  • Memory: 718.0MB
• Untyped OOP:
  • Time: 36.8s
  • Memory: 832.2MB
• Typed OOP
  • Time: 33.5s
  • Memory: 748.8MB

So yes, the OOP version is still slower and consumes (slightly) more memory. This is expected though.

Typing early and properly did have an measurable impact on both performance and memory consumption of the OOP version. The effective memory overhead for the OP wrapper shrunk to about 50% just by typing early.

Using the data-structure efficiently and minimizing the number of accesses did yield the biggest gains though, and is effectively more than a full magnitude faster than the OOP approach.

When comparing this to the 32bit version, for PHP, you may actually cut all memory requirements roughly in half. PHP wastes most of its memory on pointers, not on actual data.

Answer 2

As for the difference between the between you Class vs. Arrays - it may be something to do with how low-level of a construct the array is (just a guess).

Plus you are also going to be losing quite a bit to the recursion itself (and it's associated stack trace - no matter which route). Recursion can be really handy - but is not always the right tool for the job. Try the following as a recursion free example:

$graph = array();
$words = array('and', 'anna', 'ape', 'apple');

foreach($words as $word){
    $current_graph = &$graph;
    for($i = 0; $i < strlen($word); $i++){
        $letter = $word[$i];
        if(!isset($current_graph[$letter]))
            $current_graph[$letter] = array();
        $current_graph = &$current_graph[$letter];
    }
    $current_graph['.'] = array();
}
unset($current_graph);
echo '<pre>';
print_r($graph);

Answer 3

Syntax and PHP version

First note that the syntax you're using in the recursive approach:

function func($arg) {
  ...
}
func(&$arg);

is obsolete and deprecated as of PHP 5.4, so with recent versions it simply doesn't work and fires a "Call-time pass-by-reference" error!
Instead, this will work with any PHP >= 5.0:

function func(&$arg) {
  ...
}
func($arg);

The same issue exists in your OOP version, when you write:

$this->insert_letter_node(&$this->root,$word,0);

Since as of PHP 4 any object citation is by reference, you have to merely remove "&":

$this->insert_letter_node($this->root,$word,0);

In the other hand, as already pointed by @Pevara, you might notice performance improvement using PHP 7, whatever approach you're using.

Recursive vs non-recursive approach

I tend to agree with @Chris intuition: non-recursvie approach should be faster in this kind of case.

So why is it the contrary with your current case?
It might come from the looping mechanism, which is added when abandoning recursion. So you might have a try with one of these slightly modified versions of his:

foreach ($words as $word) {
    $current_graph = &$graph;
    // below the "strlen($word)" statement gets executed only once per $word
    for ($i = 0, n = strlen($word); $i < $n; $i++) {
        $letter = $word[$i];
        if (!isset($current_graph[$letter]))
            $current_graph[$letter] = array();
        $current_graph = &$current_graph[$letter];
    }
    $current_graph['.'] = array();
}

or even

foreach ($words as $word) {
    $current_graph = &$graph;
    // below the "for()" loop is replaced by "foreach()"
    foreach (str_split($word) as $letter) {
        if (!isset($current_graph[$letter]))
            $current_graph[$letter] = array();
        $current_graph = &$current_graph[$letter];
    }
    $current_graph['.'] = array();
}

Regarding the node/tree approach

For me it seems merely obvious that it takes much more time and eats much more space, because the involved structure is much more complicated.

In the array approach, it's likely that each "node" occupies only 2 bytes (one for the involved character, plus one for either an ending marker or a length container), while handling a node object need surely more than that.
It follows necessarily that it occupies more space and requires more operations to be handled.

So I wouldn't recommend using this approach.