Representing large sets and maps compactly with finite state transducers http://blog.burntsushi.net/transducers/
-
-
Replying to @aras_p
Interesting and weird: the grep examples flip from having the pattern be an FSM transitioning on the data, to having the data be an FSM transitioning on the pattern input. (PS: It's perfectly possible to write a grep that does edit-distance partial-matching–I've even done it.)
1 reply 0 retweets 0 likes -
Indeed it is. But this is the kind of thing that provides the base regex functionality in projects like Lucene. The name grep it's perhaps misleading.
2 replies 0 retweets 0 likes -
Replying to @burntsushi5 @aras_p
Heh, I realize it's not really grep, but it is still a similar FSM-y operation. In particular that parenthetical just referred to "something that even grep cannot do"--I can't imagine my grep is the only one that does it. But it was a parenthetical because not a big deal.
1 reply 0 retweets 0 likes
Yup. See agrep and TRE for things that do fuzziness. Good stuff!
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.