Implementing php prefix tree versus array

Question

UPD: I translated the original question to https://codereview.stackexchange.com/questions/127055/building-tree-graph-from-dictionary-performance-issues

Here is the short version, no codes.

I am trying to build a prefix tree from a dictionary. So, using the following dictionary 'and','anna','ape','apple' , the graph should look like this: I tried 2 approaches: using an associative array and using tree / node self-signed classes.

Note: the original dictionary is approximately 8 MB and contains> 600,000 words.

Question: is there a good (fast / efficient) way to do this?

I have tried so far:

• php associative arrays (they are not very flexible for future work with this chart).

• self-registering Tree / node classes (performance problems - runtime increases to 7x, memory usage increases by 2x even without implementing anything other than the inserting function).

Sample codes are available at codereview (the very first link in question)

Answer 1

While I switched to C ++ and got a good answer on codereview , I will simply answer my question here.

There is another way to make it more time-efficient by increasing memory usage (this is not a very big increase compared to array array of array s ... approach). This approach is called "double array trie" and you can read the information on this topic here and read the above answer on codereview to see an example implementation.

This is a more economical time, but it provides less flexibility / usability for future trie use (compared to the OOP approach).

So, the final answer to this question is for me: "php is not the best tool to work with really big attempts with."