You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
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?
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.
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.
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.
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.
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).
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
>>>
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.
Sorry for another question regarding fuzzy matching; it seems, I'm still missing something topical regarding this feature.
I tried to make the matches more consistent for the whole text (i.e. in order not to mask suboptimal valid results preceeding a better match - cf. comments 20, 21 here). This can be quite straightforward, simply repeating the search in the substring before the first match of the previous search and collecting the results (the obvious drawbacks is the possibly irregular handling of anchors and lookarounds).
However, I was surprised by another issue - some matches, I'd have expected, are also missing, also after the best match and supposedly complying with the error cost:
>>> import regex
>>> txt = "ab ac ad ae ba bc bd be ca cb cd ce da db dc de ea eb ec ed"
>>> regex.findall(r"\bad{e<=1}\b", txt)
['ad', 'ae']
(with my custom findall function I can also get the "words" preceeding "ad":
['ab', 'ac', 'ad', 'ae']
but there are still others missing; the following pattern only deals with alternation, as insertions and deletions aren't relevant in this sample and given the word boundaries:
\b boundary
a literal "a"
d{e<=1} literal "d" with maximum of 1 error
\b boundary
In the first example, the best match in the text is "ad", and the best match in the remainder is "ae". There are no further matches which meet the constraint.
It always looks for the best match in (the remainder of) the text.
I think I'll have to change the current behaviour (it seems to be too confusing) and add a BEST flag for when you want the best match, unless Bill (the original requester) or anyone else has an objection.
To summarise the differences:
Example 1:
txt = "ab ac ad ae ba bc bd be ca cb cd ce da db dc de ea eb ec ed"
regex.findall(r"\bad{e<=1}\b", txt)
(given the text and the pattern; with the proposed change to also match before the "optimal" match).
My naive approach is something like the following (sorry for the style and coding - there must be some elegant ways to deal with the function arguments duplication etc...)
# # # # # # # # # # # # # # # # # # #
def fuzzy_findall(pattern, string, flags=0, pos=None, endpos=None, overlapped=False, concurrent=None, **kwargs):
tmp_results = []
string = string[0:endpos] # to replace endpos used in another way
tmp_end_pos = len(string)
while tmp_end_pos:
tmp_results.append(regex.findall(pattern=pattern, string=string, flags=flags, pos=pos, endpos=tmp_end_pos, overlapped=overlapped, concurrent=concurrent, **kwargs))
m = regex.search(pattern=pattern, string=string, flags=flags, pos=pos, endpos=tmp_end_pos, overlapped=overlapped, concurrent=concurrent, **kwargs)
if m:
tmp_end_pos = m.start()
else:
break
tmp_results.reverse()
results = [result for sublist in tmp_results for result in sublist]
return results
print fuzzy_findall(r"c{e<=1}", "abcd")
['a', 'b', '', 'c', 'd', '']
with the empty match for the end of the substring in the second trial-match before "c".
I actually had expected empty matches between all the single characters
['', 'a', '', 'b', '', 'c', '', 'd', '']
or is it again some misunderstanding on my part?
Of course, a native behaviour in the regex engine would be much preferred tu such fragile wrapper function (also because of the mentioned anchors, lokkarounds etc.)
>>> txt = "ab ac ad ae ba bc bd be ca cb cd ce da db dc de ea eb ec ed"
>>> regex.findall(r"\b(ad){e<=1}\b", txt)
['ab', 'ac', 'ad', 'ae', 'bd', 'cd', 'ed']
>>> regex.findall(r"c{e<=1}", "abcd")
['a', 'b', 'c', 'd', '']
In the second example:
matches "a" with 1 error
matches "b" with 1 error
matches "c" with 0 errors
matches "d" with 1 error
matches "" at the end with 1 error
Substitution is tried first, then insertion, then deletion.
Thanks, the proposed behaviour looks really promissing and (at least for me) much more consistent.
The deletion being found only at the end, and not during the whole string at character boundaries displays maybe some asymmetry, but it's clear why from your explanation and these empty matches are probably not likely to be useful anyway.
Lately, I have used fuzzy matching for some error checking and it proved to be very helpful;
however, I'd like to better understand the fuzzy matching process and its rules, to be able to reflect it in the patterns.
(Unfortunately, I was not able to learn much from the source, as most of the "magic" apparently happens in the C code (or was it python beyond my competence level? :-)
Comment 28 above clarifies the order of the error types being checked: "Substitution is tried first, then insertion, then deletion."
Now, I would be especially interested, how the segmentation of the matches is designed, if there are large or unlimited number of errors.
It is likely, that the matches without any error are taken as a base, which are then tried for variance defined in the cost-pattern.
Is it the case, that the match-possibilities are determined first and the allowed errors don't change/shift these "boundaries" for possible matches?
It seems, that e.g. the quantifier allowing possibly longer matches somehow "eats up" the possibilities for checking within the error cost:
Does the algorithm work this way or am I misinterpretting these simplified results?
Just another thing I observed - without parentheses (which seem to be preferable in most cases anyway) - the cost pattern between {} seems to apply for the preceding "literal" only, e.g. also excluding quantifiers (?)
>>> regex.findall(r"a{e}","abc")
['a', 'b', 'c', '']
>>> regex.findall(r"a{1}{e}","abc") # the cost is possibly applied for the empty string after the quantifier (?)
[]
>>> regex.findall(r"(a{1}){e}","abc")
['a', 'b', 'c', '']
>>>
as an interesting and probably useless cornercase I found an empty pattern which match the empty string at character boundaries - without the cost pattern and nothing with any errors allowed
>>> regex.findall(r"","abc")
['', '', '', '']
>>> regex.findall(r"{e}","abc")
[]
as there is maybe no useful text for the error checking to begin with?
However, a similar zero width pattern matches identically:
This is meant purely as a question about the matching behaviour; in practice I am very happy with the present functionality; I just feel, that I could use it even better with an appropriate understanding of the "segmentation" for the possible matches tried. I would simply like to understand, how much "erroneous" cases I can match with this feature (not just in the extreme case of {e}, which would conceptually match anything, but obviously doesn't).
As it tries to match, if a part of the pattern fails to match, for example, "a" doesn't match "b", it assumes that there's an error, whether a substitution, insertion or deletion, and then continues. It tries each type of error in turn, checking whether the error constraints allow it.
The error constraint follows the same syntactic rule as the quantifiers, applying to the preceding item. If there's no preceding item, it's treated as a literal, for example, r"{e}" is treated the same as r"\{e}":
>>> regex.findall(r"{e}","abc{e}")
['{e}']
I do note that the quantifiers raise an exception if there's no preceding item, so it could be argued that the error constraint should do the same.
Thanks for the prompt answer;
the fallback to literal makes the relevant pattern clear, as does the analogy to quantifiers in the other cases.
However, how do quantifiers and error costs work together?
It now seems to me, that the two should be combine rather carefully for the same subpattern. (or is it discouraged at all?)
In some elementary patterns (below) it seems that the quantifier somehow hinders matching a (suboptimal) pattern (likely satisfying the general constraint {e}), which is found if equivalent simple literals are used cf. e.g. (Q{1,2}){e} vs (Q){e} , (QQ){e} ...
It optimises repeats of single-character matches (a character, a set, or a property). Unfortunately, that doesn't work as you'd expect when using fuzzy matching. :-(
Thank you very much, in the updated version (regex-0.1.20111004), the fuzzy matching is a bit more predictable for me,
however, I still don't understand e.g.:
I'd think, that all of the "words" would match at most with one error; however the more difficult aspect is the different handling of "abc" vs. "dba", which both need one substitution to match;
even less clear to me is the second example - adding "dba" lets the previous "abc" match, but then, only the second "dba" is matched and not this one in the 2nd word position.
Is it a peculiarity of the fuzzy matching or of the word-beginning/end anchors?
Thanks for the explanation, the recursive readjusting the match for the lowest error cost indeed makes the most cases, which wasn't very clear to me, obvious.
Now I feel, I may even grasp the fuzzy matching rules - sooner or later...
Activity
mrabarnett commentedon Jun 3, 2011
Original comment by Anonymous.
See http://laurikari.net/tre/
mrabarnett commentedon Jun 8, 2011
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 commentedon Jun 8, 2011
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 commentedon Jun 8, 2011
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
mrabarnett commentedon Jun 8, 2011
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 commentedon Jun 11, 2011
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 commentedon Jun 11, 2011
Original comment by Anonymous.
Whoops -- found a bug (by inspection) in the regex-test code branch. Updated.
mrabarnett commentedon Jun 15, 2011
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:
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 commentedon Jun 15, 2011
Original comment by Anonymous.
Good point. Since it was developed as a C library, I suspect there wasn't a lot of Pythonic thinking involved.
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.
Yep. That seems appropriate to me. Presence of {...} notation would seem to be
the preferable way of doing it.
Bill
mrabarnett commentedon Jun 23, 2011
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 commentedon Jun 24, 2011
Original comment by Anonymous.
The regex version certainly seems easier to read... a good Pythonic quality :-).
mrabarnett commentedon Jun 24, 2011
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 commentedon Jun 26, 2011
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:
mrabarnett commentedon Jun 27, 2011
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 commentedon Jun 27, 2011
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.
8 remaining items
mrabarnett commentedon Aug 6, 2011
Original comment by Anonymous.
(No comment was entered for this change.)
mrabarnett commentedon Aug 10, 2011
Original comment by Anonymous.
Sorry for another question regarding fuzzy matching; it seems, I'm still missing something topical regarding this feature.
I tried to make the matches more consistent for the whole text (i.e. in order not to mask suboptimal valid results preceeding a better match - cf. comments 20, 21 here). This can be quite straightforward, simply repeating the search in the substring before the first match of the previous search and collecting the results (the obvious drawbacks is the possibly irregular handling of anchors and lookarounds).
However, I was surprised by another issue - some matches, I'd have expected, are also missing, also after the best match and supposedly complying with the error cost:
(with my custom findall function I can also get the "words" preceeding "ad":
but there are still others missing; the following pattern only deals with alternation, as insertions and deletions aren't relevant in this sample and given the word boundaries:
Is there maybe some left-to-right bias in the algorithm, or am I missing something else?
Possibly related to this, how are the empty strings matched?, e.g.:
why are there no empty matches between each character (all of them cost one deletion), but only the last one?
Thanks in advance,
vbr
mrabarnett commentedon Aug 10, 2011
Original comment by Anonymous.
The regex r"\bad{e<=1}\b" is:
In the first example, the best match in the text is "ad", and the best match in the remainder is "ae". There are no further matches which meet the constraint.
It always looks for the best match in (the remainder of) the text.
I think I'll have to change the current behaviour (it seems to be too confusing) and add a BEST flag for when you want the best match, unless Bill (the original requester) or anyone else has an objection.
To summarise the differences:
Example 1:
Current: ['ad', 'ae']
Proposed: ['ab', 'ac', 'ad', 'ae']
Example 2:
Current: ['b', 'c', 'd', '']
Proposed: ['a', 'b', 'c', 'd', '']
mrabarnett commentedon Aug 10, 2011
Original comment by Anonymous.
Thanks for the detailed answer; now I notice that a part of my surprise was obviously the missing parentheses, i.e. I meant:
to be roughly equivalent to:
(given the text and the pattern; with the proposed change to also match before the "optimal" match).
My naive approach is something like the following (sorry for the style and coding - there must be some elegant ways to deal with the function arguments duplication etc...)
# # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
using this function I get e.g.
but
I actually had expected empty matches between all the single characters
or is it again some misunderstanding on my part?
Of course, a native behaviour in the regex engine would be much preferred tu such fragile wrapper function (also because of the mentioned anchors, lokkarounds etc.)
Many thanks for your efforts,
vbr
mrabarnett commentedon Aug 10, 2011
Original comment by Anonymous.
After the proposed change:
In the second example:
Substitution is tried first, then insertion, then deletion.
mrabarnett commentedon Aug 11, 2011
Original comment by Anonymous.
Thanks, the proposed behaviour looks really promissing and (at least for me) much more consistent.
The deletion being found only at the end, and not during the whole string at character boundaries displays maybe some asymmetry, but it's clear why from your explanation and these empty matches are probably not likely to be useful anyway.
regards,
vbr
mrabarnett commentedon Sep 27, 2011
Original comment by Anonymous.
The regex module now looks for the first match.
Use the BESTMATCH flag to look for the best match.
mrabarnett commentedon Oct 3, 2011
Original comment by Anonymous.
Lately, I have used fuzzy matching for some error checking and it proved to be very helpful;
however, I'd like to better understand the fuzzy matching process and its rules, to be able to reflect it in the patterns.
(Unfortunately, I was not able to learn much from the source, as most of the "magic" apparently happens in the C code (or was it python beyond my competence level? :-)
Comment 28 above clarifies the order of the error types being checked: "Substitution is tried first, then insertion, then deletion."
Now, I would be especially interested, how the segmentation of the matches is designed, if there are large or unlimited number of errors.
It is likely, that the matches without any error are taken as a base, which are then tried for variance defined in the cost-pattern.
Is it the case, that the match-possibilities are determined first and the allowed errors don't change/shift these "boundaries" for possible matches?
It seems, that e.g. the quantifier allowing possibly longer matches somehow "eats up" the possibilities for checking within the error cost:
Does the algorithm work this way or am I misinterpretting these simplified results?
Just another thing I observed - without parentheses (which seem to be preferable in most cases anyway) - the cost pattern between {} seems to apply for the preceding "literal" only, e.g. also excluding quantifiers (?)
as an interesting and probably useless cornercase I found an empty pattern which match the empty string at character boundaries - without the cost pattern and nothing with any errors allowed
However, a similar zero width pattern matches identically:
This is meant purely as a question about the matching behaviour; in practice I am very happy with the present functionality; I just feel, that I could use it even better with an appropriate understanding of the "segmentation" for the possible matches tried. I would simply like to understand, how much "erroneous" cases I can match with this feature (not just in the extreme case of {e}, which would conceptually match anything, but obviously doesn't).
Many thanks in advance.
vbr
mrabarnett commentedon Oct 3, 2011
Original comment by Anonymous.
As it tries to match, if a part of the pattern fails to match, for example, "a" doesn't match "b", it assumes that there's an error, whether a substitution, insertion or deletion, and then continues. It tries each type of error in turn, checking whether the error constraints allow it.
The error constraint follows the same syntactic rule as the quantifiers, applying to the preceding item. If there's no preceding item, it's treated as a literal, for example, r"{e}" is treated the same as r"\{e}":
I do note that the quantifiers raise an exception if there's no preceding item, so it could be argued that the error constraint should do the same.
mrabarnett commentedon Oct 3, 2011
Original comment by Anonymous.
Thanks for the prompt answer;
the fallback to literal makes the relevant pattern clear, as does the analogy to quantifiers in the other cases.
However, how do quantifiers and error costs work together?
It now seems to me, that the two should be combine rather carefully for the same subpattern. (or is it discouraged at all?)
In some elementary patterns (below) it seems that the quantifier somehow hinders matching a (suboptimal) pattern (likely satisfying the general constraint {e}), which is found if equivalent simple literals are used cf. e.g. (Q{1,2}){e} vs (Q){e} , (QQ){e} ...
I see, that such patterns are not very real nor useful, but I just I should understand the matching possibilities better.
Regards,
vbr
mrabarnett commentedon Oct 3, 2011
Original comment by Anonymous.
That's a bug.
It optimises repeats of single-character matches (a character, a set, or a property). Unfortunately, that doesn't work as you'd expect when using fuzzy matching. :-(
Fixed in regex 0.1.20111004.
mrabarnett commentedon Oct 4, 2011
Original comment by Anonymous.
Thank you very much, in the updated version (regex-0.1.20111004), the fuzzy matching is a bit more predictable for me,
however, I still don't understand e.g.:
I'd think, that all of the "words" would match at most with one error; however the more difficult aspect is the different handling of "abc" vs. "dba", which both need one substitution to match;
even less clear to me is the second example - adding "dba" lets the previous "abc" match, but then, only the second "dba" is matched and not this one in the 2nd word position.
Is it a peculiarity of the fuzzy matching or of the word-beginning/end anchors?
vbr
mrabarnett commentedon Oct 4, 2011
Original comment by Anonymous.
When it finds a fuzzy match it tries to see whether it can get a better fit (a match with a lower cost) within that match.
The initial match for:
is actually "abc cde dba" (the cost is 2), but a better fit is "abc cde" (the cost is 1), and an even better fit is "cde" (the cost is 0).
This results in the final output of ['cde', 'dba'].
If it didn't look for a better fit the final output would be ["abc cde dba"].
Let me give you another example:
If I change your example slightly:
And that's my justification. :-)
mrabarnett commentedon Oct 4, 2011
Original comment by Anonymous.
Thanks for the explanation, the recursive readjusting the match for the lowest error cost indeed makes the most cases, which wasn't very clear to me, obvious.
Now I feel, I may even grasp the fuzzy matching rules - sooner or later...
Thanks and regards,
vbr