frak: Transform collections of strings into regular expressions | Hacker News Reader

frak: Transform collections of strings into regular expressions

github.com

98 pointsjamesjyu38 comments

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

And my implementation in Java :):

https://github.com/danieldk/dictomaton

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.

It's quite possibly the case that it takes longer to parse the complex trie regex (using character classes, ?, etc.) constructed here than it does for a good regexp library to parse the alternating fixed strings and construct the equivalent automata.

I don’t know how common such “good regexp libraries” are. The README includes a benchmark at the bottom, demonstrating that the complex regex is about ten times faster than the simple version. The benchmark uses Clojure’s built-in regex engine, which is the same as Java’s.

Well, PCRE, the most widely used regex lib in my experience, has a "DFA" mode (scare quotes because it's actually an NFA mode. See [1]). So the option is there, even if most people use PCRE in standard recursive kablooey mode.

I was working on a drop-in managed wrapper around re2[2] so .NET developers would have access to a good regex library, but damned if starting a company hasn't gotten in the way of finishing it. Still, re2 bindings are available for most other common platforms.

(Also I don't believe Java's regex engine is automata-based, which would explain the performance gains.)

1. http://fanf.livejournal.com/37166.html 2. http://code.google.com/p/re2/

grep is one example of a programme with a good regex library.

Compare http://swtch.com/~rsc/regexp/regexp1.html

Especially considering that there are incremental algorithms for constructing the minimized DFA. For instance, I use one such algorithm in my library that (among other things) uses a minimized DFA to store String sets in Java:

https://github.com/danieldk/dictomaton

(It also supports perfect hashing automata and Levenshtein automata.)

Humorous timing for me as I made a (bad) joke the other day about such a piece of software: "I created an algorithm to turn a selection of strings into a regular expression but it just keeps returning (dot asterisk)"

In other news, how do you actually render an asterisk on HN?

* (asterisk followed by whitespace)

To those wondering if this is worth it, the method of using a trie-style regexp to optimize this type of word matching has been used in the Perl community for a while now and it does work well.

Starting with v5.10, if Perl encounters a regexp that is just a list of strings, it will even use trie-based matching automatically.

Prior to that, people have been using modules such as Regexp::Trie to build optimized regexps and noted increases in performance similar to the benchmark shown in the post.

This functionality has been available in Emacs (ELisp) for a long time:

http://www.emacswiki.org/emacs/RegexpOpt

Here goes my frak.el port attempt

Here are some links to papers that show how to generate regular expressions from a set of strings: - http://doi.acm.org/10.1145/1735886.1735890 - http://doi.acm.org/10.1145/1841909.1841911 This is research done in the context of XML schema learning. The first paper restricts to inference of regular expressions in a more limited class: single-occurrence regular expressions. These are expressions in which every alphabet symbol (letter) can occur at most once. When enough strings are present, the algorithms are sound and complete. The second paper drops this requirement but the algorithm are mere heuristics.

Learning regular expressions from strings is a fascinating but non-trivial problem.

If you do not have access to the Digital Library of ACM, scholar.google.com is your friend.

Why not just use, say, an actual (i.e. backtrack-free, DFA-based) regular expression library?

This produces inputs to an arbitrary regex library. You could of course build a regex "(w1|w2|w3|...|wN)" for words w1...wN (assuming an efficient regex library) and save the hassle, but the frak output will hopefully be more compact.

Because that's not why I wrote frak. Originally, I wrote it to help eliminate backtracking and, indirectly, minimize the state table of two enormous regular expressions within Vim's Clojure syntax file (the README has a link in the "Why?" section by the way).

Vim uses an NFA style engine and it was obvious to me that backtracking with these patterns would be an issue. Since we went to such great lengths to provide the most accurate regular expression highlighting possible for Clojure, which is pretty damn accurate, I figured we might as well try to make it performant. It turns out our efforts were not in vain.

Have a look at this pull request: https://github.com/guns/vim-clojure-static/pull/28.

Google Analytics has a filter system that allow one to use regular expressions of length at most 255.

Sometimes, people have long list of strings that have total length more than 255 characters. frak would be a nice tool for compression.

The author found the optimal solution when trying to construct these expressions: store them in a trie. Because the generated regular expressions match only the inputs, this solution may find a more compact way to test if the inputs have lots of overlap.

It would be cool if the inputs weren't matched exactly, and frak could figure out a general pattern for your inputs (decimals, capitalized words, etc). That could help newcomers with a starting expression that matches their inputs.

This was the subject of my honours thesis[1] back in 2000. I was actually inferring DTDs from sample XML documents, but it's the exact problem as DTDs use regular expressions and I only had positive examples to go on.

Based on existing methods my solution started with the same trie and then generalised to a more flexible DFA by merging states. I used information theory (specifically Minimum Message Length) to turn it into an optimisation problem and tried a few different algorithms, in the addition of Ant Colony Optimisation to an existing algorithm produced the best results for my tests. (They were pretty limited, though.)

[1] http://www.cse.unsw.edu.au/~wong/Papers/jason.pdf

> It would be cool if the inputs weren't matched exactly, and frak could figure out a general pattern for your inputs (decimals, capitalized words, etc).

The problem is that there are an huge number of possible solutions for any given input. For example, you could always give a trivial solution: ".*"

For something like that to work, you'd need a large dictionary of common patterns, and then you'd want to compare against the dictionary to see if it matches a sequence of common patterns.

I can't imagine that sort of thing being too useful.

An alternative solution is to provide a list of matches and non-matches, and look for the shortest or simplest regex that separates the two.

(Finding the actual minimal regex, instead of just a reasonable guess, might be a computationally tough problem. I guess it's in coNP and might be in NP, too. An algorithm in P would be nice to find.)

Update: Finding any separating regex would be in P. A separating finite automaton is easy to find, and then you just convert that into a regex. Now, how do you find the minimal regex?

I really want one of these please message me!!! (tom dot larkworthy at gmail)

preferably python but a link to theory is useful too.

I wrote a brute-force minimal-regex finder once; wish I could remember where I put it.

For your entertainment, https://github.com/matthiasgoergens/Div7 has a regex finder for divisibility. E.g. https://raw.github.com/matthiasgoergens/Div7/master/regex7 checks decimal numbers for divisibility by 7.

Very cute. :-)

I found my code and it wasn't exactly it (it just enumerated all regexes in order of size), but here's a crude solution now: https://github.com/darius/sketchbook/blob/master/regex/find_...

(In defense of my memory, I had written superoptimizers for other things.)

It depends on what the grandparent means with 'not exactly'. If it means 'within a certain edit distance', it is very doable. You can store your dictionary in an automaton and construct a Levenshtein[1] automaton in linear time. The intersection of the dictionary and Levenshtein automaton gives all words within the given edit distance. My library (Dictomaton) that I mention in another comment implements this. There is a different implementation in recent Lucene versions, that is used for finding documents with keywords that approximately match the query.

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.6...

The problem is that this is unlikely to give what you want, since, for example, if my inputs are "123", "2315", "12451", ..., then what I'm looking for is probably going to be something along the lines of "\d+", and not the set of words that are within a small edit distance of a subset of integers.

It depends on the application. For instance, in search engines approximate matching is very useful. E.g. if people want to search for Rotterdam, they make typos like Roterdam or are foreigner and don't know that Rotterdam has a double t.

You can rank candidates afterwards. However, it's a good solution for finding words that are closed to a mistyped word.

I have successfully used such techniques in a spellchecker and various search engines.

With a set of true and false inputs you could evolve a regex:

https://www.lri.fr/~hansen/proceedings/2012/GECCO/companion/...

Why evolve, when you can solve exactly?

Actually, frak doesn't generate patterns that require an exact match. I use Clojure's `re-matches` function (for exact matches) in the example and the tests to show and ensure the generated patterns work as expected. Clojure has another function called `re-find` which is a bit more relaxed. An expression like #"bar" will fail with the string "barn" using `re-matches` but succeed with re-find. I plan to include an option for generating regexes that require exact matches.

This may be a naïve question, but what about telling it what words the pattern should not match?

Isn't that more or less the same as what it already does? That is by telling frak which words you want to match you're implying you don't want to match anything else.

Of course, you could generate two patterns; one with the words you do want to match and the other with words you don't. Then simply handle the logic in your program.

frak seems to generate a regex that precisely only matches the input list of strings, no generalizations.

So this seems not to be the tool to auto-create a .gitignore file...

Huh. That's a neat trick.

I certainly wouldn't stop at the output, but this is a very useful tool to speed up regex generation.

This is clever. Using the trie is smart, but does it account for suffixes or infixes?

I misunderstood. Instead of representing the set of sequences, I was assuming it was attempting to extract a general pattern from the inputs, which would be difficult, and non-deterministic.

Reply on news.ycombinator.com