Generate regular expressions that match a set of strings.
Add this line to your application's Gemfile:
And then execute:
$ bundle install
Or install it yourself as:
$ gem install regexgen
require 'regexgen' Regexgen.generate(['foobar', 'foobaz', 'foozap', 'fooza']) #=> /foo(?:zap?|ba[rz])/
regexgen also has a simple CLI to generate regexes using inputs from the
$ regexgen usage: regexgen [-mix] strings... -m Multiline flag -i Case-insensitive flag -x Extended flag
How does it work?
Generate a Trie containing all of the input strings. This is a tree structure where each edge represents a single character. This removes redundancies at the start of the strings, but common branches further down are not merged.
A trie can be seen as a tree-shaped deterministic finite automaton (DFA), so DFA algorithms can be applied. In this case, we apply Hopcroft's DFA minimization algorithm to merge the nondistinguishable states.
Convert the resulting minimized DFA to a regular expression. This is done using Brzozowski's algebraic method, which is quite elegant. It expresses the DFA as a system of equations which can be solved for a resulting regex. Along the way, some additional optimizations are made, such as hoisting common substrings out of an alternation, and using character class ranges. This produces an an Abstract Syntax Tree (AST) for the regex, which is then converted to a string and compiled to a Ruby
After checking out the repo, run
bin/setup to install dependencies. Then, run
rake test to run the tests. You can also run
bin/console for an interactive
prompt that will allow you to experiment.
To install this gem onto your local machine, run
bundle exec rake install. To
release a new version, update the version number in
version.rb, and then run
bundle exec rake release, which will create a git tag for the version, push
git commits and tags, and push the
.gem file to
Bug reports and pull requests are welcome on GitHub at https://github.com/amake/regexgen-ruby.
The gem is available as open source under the terms of the MIT License.