Radix Patricia Tree

[AGlassman]

Does anyone know of a native AutoIt implementation of Patricia Radix Trees (http://en.wikipedia.org/wiki/Radix_tree)? Or an external implementation that could be interfaced to AutoIt? A search of the forums turns up nothing.

I need an in-memory data structure that can search a large number of long strings that have a (relativly) small number of common prefixes. Insert/Delete times are not that critical for this project, only search speed and memory usage. While there are many versions of associative arrays that might do what I need, none seem to have the combination of speed and compactness that a Patricia Tree might offer. I have started work on my own design, but I certainly don't want to re-invent the wheel.

[jchd]

You may want to consider loading your data as an SQLite in-memory database and then enjoy the power of SQL and built-in functions to query the table(s). A full text search is also available (FTS3) as a standard feature, albeit word-oriented rather than prefix-oriented. In case you need some special search function, writing an ad-hoc extension is fairly easy in most cases.

Comparing the speed of some AutoIt-based Radix-tree implementation with SQLite query using the right index should be favorable to the latter.

You can give it a try in surprisingly few lines of standard AutoIt code, just to keep sure you don't miss an opportunity to keep things simple.