Projects

patl

STL-compatible, high-performance template containers and auxiliary classes useful for stringology > Trie containers - trie_set & trie_map. > Online suffix tree containers - suffix_set & suffix_map - O(N) both time & space, 16 bytes per symbol, alphabet-independent. > ... [More] Iterators over each type of containers - standard (const_)(reverse_)iterator, special (post|pre|level)order_iterator for respective tree traversals. > Partial match iterators (const_)partimator (joker pattern filter, Hamming & Levenshtein automata filter). > suffix_cont-special match_iterator & (super_)maxrep_iterator for matching statistics and (super)maximal repeats. > Lowest common ancestor (LCA) O(1) time requests after O(N) postprocessing of the suffix_cont - lca_oracle. > Small & clever demo programs. [Less]

M2Collections

Modula-2 collections library. The library provides an API for collection ADTs, in particular: stacks, queues, double ended queues, priority queues, balanced binary search trees, patricia tries, dynamic arrays and hash tables to store arbitrary data. The hash table ADT allows data to be stored and ... [More] retrieved by reference or by copy, with built-in reference counting. All other ADTs allow data to be stored and retrieved by reference only. The library follows PIM4, it has no dependencies and it is platform independent. The library is tested with GM2 using option 'fpim4'. Under development. BSD style license. [Less]

patricia-trie

PATRICIA Trie Practical Algorithm to Retrieve Information Coded in Alphanumeric "A radix tree, Patricia trie/tree, or crit bit tree is a specialized set data structure based on the trie that is used to store a set of strings. In contrast with a regular trie, the edges of a Patricia trie ... [More] are labelled with sequences of characters rather than with single characters. These can be strings of characters, bit strings such as integers or IP addresses, or generally arbitrary sequences of objects in lexicographical order. Sometimes the names radix tree and crit bit tree are only applied to trees storing integers and Patricia trie is retained for more general inputs, but the structure works the same way in all cases." -- Wikipedia [Less]

radixtree

A radix tree, Patricia trie/tree, or crit bit tree is a specialized set data structure based on the trie that is used to store a set of strings. In contrast with a regular trie, the edges of a Patricia trie are labelled with sequences of characters rather than with single characters. These can be ... [More] strings of characters, bit strings such as integers or IP addresses, or generally arbitrary sequences of objects in lexicographical order. Sometimes the names radix tree and crit bit tree are only applied to trees storing integers and Patricia trie is retained for more general inputs, but the structure works the same way in all cases. For more information see http://en.wikipedia.org/wiki/Radix_tree I have created this Radix tree for a project that required fast searching of user name prefixes for a Google AJAX Search like interface. Radix Tree gives fastest possible ways to search prefixes. For example it can quickly answer queries like "Find all user name starting with 'tahseen'" The database solution for this problem boils down to queries like select * from user where username like 'tahseen%' Database solution does not scale very well if you have a large number of concurrent users searching. A memory based Radix Tree scale very well. Update: (1st Sept 2009) A new method added that would complete a given string to the point where the ambiguity starts. (Contribution by kaljurand (http://code.google.com/u/kaljurand/)) Update: (23rd June 2009) Dennis Heidsiek improvements has been merged with trunk. Update: Javid Jamae (http://www.javidjamae.com/) has provided an excellent implementation of Radix tree in javascript. Go ahead and download it! [Less]

Patricialib

C library for Patricia trie storage. The library provides an API to create and use dynamic compact Patricia tries for arbitrary data. Keys may be of variable length. Data may be stored and retrieved by reference only. Supports in-order retrieval and best-match prefix searches with foreach closure ... [More] semantics. Requires C99, no dependencies, platform independent. Work in progress. BSD style license. [Less]