3 ms·

FWIW, my Dictomaton Java library also has support for Levenshtein automata (besides finite state dictionaries, perfect hash automata, and String mappings based

FWIW, my Dictomaton Java library also has support for Levenshtein automata (besides finite state dictionaries, perfect hash automata, and String mappings based on perfect hash automata): https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton

joe_the_user 11y ago
Care to share any experiences you had implementing them?
burntsushi 11y ago
> besides finite state dictionaries, ..., String mappings based on perfect hash automata I'm implementing a similar library in Rust. One of the key things I've found missing in Daciuk's great work on the topic is the handling of the registry. In your code[1], it looks like you're using a straight a hash table. I thought you'd like to know that I've had great success sacrificing complete DFA minimization in exchange for a small constant memory overhead by using an LRU cache of only some classes of states. My code still needs a good deal of polish, and I intend to write a blog post, but I bet you can make sense of the general strategy from the code and reuse it.[2] N.B. Lucene's implementation permits sacrificing complete minimization, but they don't use an LRU cache and I think still permit the registry to grow without bound. [1] - https://github.com/danieldk/dictomaton/blob/master/src/main/java/eu/danieldk/dictomaton/DictionaryBuilder.java#L292-L296 https://github.com/danieldk/dictomaton/blob/master/src/main/... [2] - https://github.com/BurntSushi/fst/blob/master/src/fst/registry.rs https://github.com/BurntSushi/fst/blob/master/src/fst/regist... (The data type is a map from node hash to LRU cache. That is, there is a small LRU cache for each bin in the map.)
- danieldk 11y ago
  Interesting, thanks for the pointers! I'll look at it when we are done moving :). BTW, for those who are interested, Jan's code is also available online: http://galaxy.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciuk/personal/fsa.html http://galaxy.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciu... http://galaxy.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciuk/personal/fadd.html http://galaxy.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciu... His FSA utilities and the fadd library are used in the Alpino parser: http://www.let.rug.nl/vannoord/alp/Alpino/ http://www.let.rug.nl/vannoord/alp/Alpino/

joe_the_user 11y ago

Care to share any experiences you had implementing them?

burntsushi 11y ago

> besides finite state dictionaries, ..., String mappings based on perfect hash automata I'm implementing a similar library in Rust. One of the key things I've found missing in Daciuk's great work on the topic is the handling of the registry. In your code[1], it looks like you're using a straight a hash table. I thought you'd like to know that I've had great success sacrificing complete DFA minimization in exchange for a small constant memory overhead by using an LRU cache of only some classes of states. My code still needs a good deal of polish, and I intend to write a blog post, but I bet you can make sense of the general strategy from the code and reuse it.[2] N.B. Lucene's implementation permits sacrificing complete minimization, but they don't use an LRU cache and I think still permit the registry to grow without bound. [1] - https://github.com/danieldk/dictomaton/blob/master/src/main/java/eu/danieldk/dictomaton/DictionaryBuilder.java#L292-L296 https://github.com/danieldk/dictomaton/blob/master/src/main/... [2] - https://github.com/BurntSushi/fst/blob/master/src/fst/registry.rs https://github.com/BurntSushi/fst/blob/master/src/fst/regist... (The data type is a map from node hash to LRU cache. That is, there is a small LRU cache for each bin in the map.)

danieldk 11y ago
Interesting, thanks for the pointers! I'll look at it when we are done moving :). BTW, for those who are interested, Jan's code is also available online: http://galaxy.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciuk/personal/fsa.html http://galaxy.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciu... http://galaxy.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciuk/personal/fadd.html http://galaxy.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciu... His FSA utilities and the fadd library are used in the Alpino parser: http://www.let.rug.nl/vannoord/alp/Alpino/ http://www.let.rug.nl/vannoord/alp/Alpino/