approximate matching -- feature request

[mrabarnett]

Original report by Anonymous.

---

I'm currently using the TRE regex engine to match output from OCR, because it supports approximate matching. Very useful. Would be nice to have that capability in Python regex, as well.

[mrabarnett]

Original comment by Anonymous.

---

See http://laurikari.net/tre/

[mrabarnett]

Original comment by Anonymous.

---

I'm not entirely sure how easy this would be, although I have come up with a few ideas.

Could you provide me with some test data, including regex(es)?

[mrabarnett]

Original comment by Anonymous.

---

The code for TRE is under a "two-clause BSD licence", whatever that means. But the approximate matching code is in a single C file there. Could it be lifted?

[mrabarnett]

Original comment by Anonymous.

---

There are a lot of tests as part of TRE; would they be enough? Assuming you use the TRE syntax.

Bill

/*
 * Approximate matching tests.
 *
 * The approximate matcher always searches for the best match, and returns
 * the leftmost and longest one if there are several best matches.
 */

test_comp("(fou){# ~1}", REG_EXTENDED, 0);
test_comp("(fuu){#}", REG_EXTENDED, 0);
test_comp("(fuu){# ~}", REG_EXTENDED, 0);
test_comp("(anaconda){ 1i + 1d < 1, #1}", REG_EXTENDED, 0);
test_comp("(anaconda){ 1i + 1d < 1 #1 ~10 }", REG_EXTENDED, 0);
test_comp("(anaconda){ #1, ~1, 1i + 1d < 1 }", REG_EXTENDED, 0);

test_comp("(znacnda){ #1 ~3 1i + 1d < 1 }", REG_EXTENDED, 0);
test_exec("molasses anaconda foo bar baz smith anderson ",
   0, REG_NOMATCH);

test_comp("(znacnda){ #1 ~3 1i + 1d < 2 }", REG_EXTENDED, 0);
test_exec("molasses anaconda foo bar baz smith anderson ",
   0, REG_OK, 9, 17, 9, 17, END);
test_comp("(ananda){ 1i + 1d < 2 }", REG_EXTENDED, 0);
test_exec("molasses anaconda foo bar baz smith anderson ",
   0, REG_NOMATCH);

test_comp("(fuu){ +3 -3 ~5}", REG_EXTENDED, 0);
test_exec("anaconda foo bar baz smith anderson",
   0, REG_OK, 9, 10, 9, 10, END);
test_comp("(fuu){ +2 -2 ~5}", REG_EXTENDED, 0);
test_exec("anaconda foo bar baz smith anderson",
   0, REG_OK, 9, 10, 9, 10, END);
test_comp("(fuu){ +3 -3 ~}", REG_EXTENDED, 0);
test_exec("anaconda foo bar baz smith anderson",
   0, REG_OK, 9, 10, 9, 10, END);

test_comp("(laurikari){ #3, 1i + 1d < 3 }", REG_EXTENDED, 0);

/* No cost limit. */
test_comp("(foobar){~}", REG_EXTENDED, 0);
test_exec("xirefoabralfobarxie", 0, REG_OK, 11, 16, 11, 16, END);

/* At most two errors. */
test_comp("(foobar){~2}", REG_EXTENDED, 0);
test_exec("xirefoabrzlfd", 0, REG_OK, 4, 9, 4, 9, END);
test_exec("xirefoabzlfd", 0, REG_NOMATCH);

/* At most two inserts or substitutions and max two errors total. */
test_comp("(foobar){+2#2~2}", REG_EXTENDED, 0);
test_exec("oobargoobaploowap", 0, REG_OK, 5, 11, 5, 11, END);

/* Find best whole word match for "foobar". */
test_comp("\\<(foobar){~}\\>", REG_EXTENDED, 0);
test_exec("zfoobarz", 0, REG_OK, 0, 8, 0, 8, END);
test_exec("boing zfoobarz goobar woop", 0, REG_OK, 15, 21, 15, 21, END);

/* Match whole string, allow only 1 error. */
test_comp("^(foobar){~1}$", REG_EXTENDED, 0);
test_exec("foobar", 0, REG_OK, 0, 6, 0, 6, END);
test_exec("xfoobar", 0, REG_OK, 0, 7, 0, 7, END);
/*
  This currently fails.
test_exec("foobarx", 0, REG_OK, 0, 7, 0, 7, END);
*/
test_exec("fooxbar", 0, REG_OK, 0, 7, 0, 7, END);
test_exec("foxbar", 0, REG_OK, 0, 6, 0, 6, END);
test_exec("xoobar", 0, REG_OK, 0, 6, 0, 6, END);
test_exec("foobax", 0, REG_OK, 0, 6, 0, 6, END);
test_exec("oobar", 0, REG_OK, 0, 5, 0, 5, END);
test_exec("fobar", 0, REG_OK, 0, 5, 0, 5, END);
test_exec("fooba", 0, REG_OK, 0, 5, 0, 5, END);
test_exec("xfoobarx", 0, REG_NOMATCH);
test_exec("foobarxx", 0, REG_NOMATCH);
test_exec("xxfoobar", 0, REG_NOMATCH);
test_exec("xfoxbar", 0, REG_NOMATCH);
test_exec("foxbarx", 0, REG_NOMATCH);

/* At most one insert, two deletes, and three substitutions.
   Additionally, deletes cost two and substitutes one, and total
   cost must be less than 4. */
test_comp("(foobar){+1 -2 #3, 2d + 1s < 4}", REG_EXTENDED, 0);
test_exec("3oifaowefbaoraofuiebofasebfaobfaorfeoaro",
   0, REG_OK, 26, 33, 26, 33, END);

/* Partially approximate matches. */
test_comp("foo(bar){~1}zap", REG_EXTENDED, 0);
test_exec("foobarzap", 0, REG_OK, 0, 9, 3, 6, END);
test_exec("fobarzap", 0, REG_NOMATCH);
test_exec("foobrzap", 0, REG_OK, 0, 8, 3, 5, END);
test_comp("^.*(dot.org){~}.*$", REG_EXTENDED, 0);
test_exec("www.cnn.com 64.236.16.20\n"
   "www.slashdot.org 66.35.250.150\n"
   "For useful information, use www.slashdot.org\n"
   "this is demo data!\n",
   0, REG_OK, 0, 120, 93, 100, END);

/* Approximate matching and back referencing cannot be used together. */
test_comp("(foo{~})\\1", REG_EXTENDED, REG_BADPAT);

[mrabarnett]

Original comment by Anonymous.

---

I took the tre test code and turned it into Python. You can adapt it a bit to regex.

Bill

[mrabarnett]

Original comment by Anonymous.

---

I've now re-cast the tests as a function you could drop into test_regex.py. If the "tre" module is installed, it will use that; if not, it will try to use regex instead to run the tests.

[mrabarnett]

Original comment by Anonymous.

---

Whoops -- found a bug (by inspection) in the regex-test code branch. Updated.

[mrabarnett]

Original comment by Anonymous.

---

What do you think about the notation in the {...}? Is it clear?

One idiosyncrasy I don't like is that in this:

1i + 1d < 1

the maximum cost is 1, but it uses "<", not "<=".

On another issue, it looks like a pattern which is going to be used for approximate matching would need to be specially marked (a flag and/or presence of {...} notation) because certain tricks to improve the speed of exact matching aren't possible for approximate matching, and I don't think the user would want to lose those speedups when most matching is exact. Another possibility is for an unmarked pattern to be recompiled automatically for approximate matching on demand.

[mrabarnett]

Original comment by Anonymous.

---

One idiosyncrasy I don't like is that in this:

1i + 1d < 1

the maximum cost is 1, but it uses "<", not "<=".

Good point. Since it was developed as a C library, I suspect there wasn't a lot of Pythonic thinking involved.

What do you think about the notation in the {...}? Is it clear?

I guess the question is, can we improve on it? I've been using TRE for a bit, so it's clear to me, but perhaps there is a better way of saying these things.

On another issue, it looks like a pattern which is going to be used for approximate matching
would need to be specially marked (a flag and/or presence of {...} notation) because certain
tricks to improve the speed of exact matching aren't possible for approximate matching,
and I don't think the user would want to lose those speedups when most matching is exact.

Yep. That seems appropriate to me. Presence of {...} notation would seem to be
the preferable way of doing it.

Bill

[mrabarnett]

Original comment by Anonymous.

---

I discovered that it is using "<" correctly.

I've decided to allow both "<" and "<=", with their usual meanings.

This is TRE: "(foobar){+1 -2 #3, 2d + 1s < 4}"
This will be regex: "(foobar){i <= 1, d <= 2, s <= 3, 2d + 1s < 4}"

My latest build passes the tests, although it isn't as fast at approximate matching, and it's too prone to catastrophic backtracking. I'm going to see whether I can adapt the existing safeguards used with repeats.

[mrabarnett]

Original comment by Anonymous.

---

The regex version certainly seems easier to read... a good Pythonic quality :-).

[mrabarnett]

Original comment by Anonymous.

---

After making some modifications and adding a simple heuristic, I've got fuzzy matching to work acceptably, but I'd be interested in any further test cases I can try which are closer to real-world use-cases before the next release.

Restriction: fuzzy matching doesn't work on group references or named lists (but that's not to say that they never will).

[mrabarnett]

Original comment by Anonymous.

---

I downloaded the latest version from PyPI (regex-0.1.20110623a), but I get an error when I try to use it:

p = regex.compile('(foobar){i <= 1, d <= 2, s <= 3, 2d + 1s < 4}')
p = regex.compile('(foobar){i <= 1, d <= 2, s <= 3, 2d + 1s < 4}')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Library/Python/2.5/site-packages/regex.py", line 266, in compile
    return _compile(pattern, flags, kwargs)
  File "/Library/Python/2.5/site-packages/regex.py", line 373, in _compile
    parsed = parse_pattern(source, info)
  File "/Library/Python/2.5/site-packages/_regex_core.py", line 300, in parse_pattern
    branches = [parse_sequence(source, info)]
  File "/Library/Python/2.5/site-packages/_regex_core.py", line 319, in parse_sequence
    item = parse_item(source, info)
  File "/Library/Python/2.5/site-packages/_regex_core.py", line 354, in parse_item
    if not subpattern or min_count == max_count == 1:
NameError: global name 'subpattern' is not defined
>>>

[mrabarnett]

Original comment by Anonymous.

---

Fuzzy matching wasn't in that release. You're the only person to have reported a problem with it! (Definitely a bug, though...)

New release (regex-0.1.20110627), with fuzzy matching, now on PyPI.

If all goes well, I'll be adding fuzzy named lists and group references in the next release.

[mrabarnett]

Original comment by Anonymous.

---

Excellent. OK, let me try it out, and I'll see if I can come up with more test cases.

This kind of thing is heavily used in text mining applications over OCR'd document sets. Mainly legal and medical, as far as I know. The legal use case is scanning a huge discovery collection for specific terms of art, and for specific named parties (which is where fuzzy named lists would come in). Unfortunately, it's hard to get real-world data to try things on, because legal and medical documents are typically privileged info.