4 ms·

If you don't need the add and remove operations, it's possible to reduce the size significantly by applying automata theory: http://www.n3labs.com/pdf/lexicon-s

by gorset 15y ago

If you don't need the add and remove operations, it's possible to reduce the size significantly by applying automata theory: http://www.n3labs.com/pdf/lexicon-squeeze.pdf http://www.n3labs.com/pdf/lexicon-squeeze.pdf It works extremely well "out of the box" for dictionary words, since the automata enables sharing of both prefixes and suffixes.

jongraehl 15y ago
The minimal-acceptor approach is also best when you're considering dynamic programs that effectively involve some kind of FSA-intersection, including best-first lazy versions like "find the closest spelling correction to a sequence of words in your lexicon of some text", because your state (suffix set) representation is canonical. 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/personal/adfa.html http://www.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciuk/p...
- gorset 15y ago
  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=536247 http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5362... or http://www.sciencedirect.com/science/article/pii/S157086670400053X 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).
  - jakab922 15y ago
    You might find this interesting as a testbed -> http://www.facebook.com/careers/puzzles.php?puzzle_id=17 http://www.facebook.com/careers/puzzles.php?puzzle_id=17

by gorset 15y ago

jongraehl 15y ago

The minimal-acceptor approach is also best when you're considering dynamic programs that effectively involve some kind of FSA-intersection, including best-first lazy versions like "find the closest spelling correction to a sequence of words in your lexicon of some text", because your state (suffix set) representation is canonical. 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/personal/adfa.html http://www.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciuk/p...

gorset 15y ago
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=536247 http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5362... or http://www.sciencedirect.com/science/article/pii/S157086670400053X 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).
- jakab922 15y ago
  You might find this interesting as a testbed -> http://www.facebook.com/careers/puzzles.php?puzzle_id=17 http://www.facebook.com/careers/puzzles.php?puzzle_id=17