Re:Crit-bit Trees: the best way to store sets
by gorset on Tuesday September 20, 2011 @08:41AM
(#3017296)
Implementing approximate matching has been on my todo list for some time. I'm planning to either implement http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5362... or http://www.sciencedirect.com/science/article/pii/S1570866704...
The data structure for the mealy recognizer described in the paper can very easily be changed to support minimal perfect hash numbers for all elements, without using more space (my implementation uses less space because of it, because the same information can be used to calculate the number of strings with a prefix in O(1) time).
Re:Crit-bit Trees: the best way to store sets
by jakab922 on Tuesday September 20, 2011 @12:03PM
(#3018087)
You might find this interesting as a testbed -> http://www.facebook.com/careers/puzzles.php?puzzle_id=17
I only skimmed the paper, but a simple n*log n approach to produce the same result is to first sort the lexicon, then build the trie while canonicalizing the suffix sets depth first (needing to hash/compare only one level deep, by induction).
This guy wrote an entire thesis comparing various methods for the same task - http://www.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciuk/p...