frak: Transform collections of strings into regular expressions

Re:frak: Transform collections of strings into regular expre... by djvv on Tuesday August 13, 2013 @12:22AM (#6203979)

Here's the paper that shows how to do the direct construction of the minimal DFA in linear time: http://acl.ldc.upenn.edu/J/J00/J00-1002.pdf

[ Parent | on HN ]

Re:frak: Transform collections of strings into regular expre... by danieldk on Tuesday August 13, 2013 @02:25AM (#6204293)

And my implementation in Java :):

https://github.com/danieldk/dictomaton

[ Parent | on HN ]

Re:frak: Transform collections of strings into regular expre... by noprompt on Tuesday August 13, 2013 @02:45PM (#6207479)

This is interesting. Thank you for sharing the link to this paper.

At the moment I believe I have something that looks similar Figure 1, however, the algorithm is nothing to write home about. I wrote the initial version one afternoon and didn't do a tremendous amount of research regarding the problem. In fact, most of the commits I've made to the project have been to the README! I definitely would like to work towards something that more closely resembles Figure 2 and emit the most optimal regular expression possible. Naturally that means I would be rewriting most of it. :)

Again, thanks for sharing this.

[ Parent | on HN ]