Jump to content
Sign in to follow this  

Radix Patricia Tree

Recommended Posts

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.

Share this post

Link to post
Share on other sites

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.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

  • Create New...