Approximate regular expression library for Java?

Question

I have just written some code for approximate string matching. I would like to benchmark my naive algorithm against a more mature implementation running on the JVM. Any suggestions?

Answer 1

I found these answers elsewhere on this site for similar problems.

Commons Lang has an implementation of Levenshtein distance.
http://commons.apache.org/lang/api-release/org/apache/commons/lang/StringUtils.html

Commons Codec has an implementation of soundex and metaphone.
http://commons.apache.org/codec/api-release/org/apache/commons/codec/language/Soundex.html
http://commons.apache.org/codec/api-release/org/apache/commons/codec/language/Metaphone.html

(source)

Lucene (http://lucene.apache.org/) also implements Levenshtein edit distance.

(source: zarawesome)

Answer 2

It so happens I reinvented this wheel many years ago - in a FORTRAN program on a mainframe :)

When I proudly told other people on the Internet about my algorithm, they laughed and pointed me at the two (four?) big names in this area:

• Needleman-Wunsch and
• Smith-Waterman.

These are algorithms for comparing huge sequences of similar strings. Memory requirement is about m + n, where m and n are the sizes of the strings, and runtime is about m * n.

Gunslinger47 mentions Levenshtein, Soundex and Metaphone. Levenshtein is also a powerful means of computing string distances, but it's better suited for "normal" text. Soundex and Metaphone compute a short string intended to encode the sound of the string when spoken by a human... they become ineffective after about 3 syllables, they're really intended for words in human language rather than strings of genomes or such.

EDIT

Oops, I just found my 4 big names at the bottom of the article you cited. So you're already aware of them. I think that if you search for those names and "Java" should find you implementations. Here's the first one I found.