TRE: A Regex Engine with Approximate Matching
ducktape.blot.im
TRE: A Regex Engine with Approximate Matching
1–10 of 12 posts
Re: TRE: A Regex Engine with Approximate Matching
#2Looks pretty handy, but wish it could capture the actual edit distance somewhere. You can set a max, but many use cases call for knowing how close the match was.
Re: TRE: A Regex Engine with Approximate Matching
#3This looks pretty interesting. Anyone know if this library has been ported to any other languages aside Perl?
Re: TRE: A Regex Engine with Approximate Matching
#4This looks pretty interesting. Anyone know if this library has been ported to any other languages aside Perl?
C, Perl, Python, and Haskell: https://laurikari.net/tre/faq/
Re: TRE: A Regex Engine with Approximate Matching
#5Interesting, would help with [1] ReDOS attacks? It would seem that fuzzy matching could put a upper limit on execution time right?
Re: TRE: A Regex Engine with Approximate Matching
#6Years ago in a pinch, I used this library to isolate data in OCR results. Looking for phone numbers or tax IDs, it would return values with a B in it and you could correct to an 8 or other similar transforms. Probably much better tools for this now, but at the time it was extremely useful.
Re: TRE: A Regex Engine with Approximate Matching
#7Interesting, would help with [1] ReDOS attacks? It would seem that fuzzy matching could put a upper limit on execution time right? [1] https://en.m.wikipedia.org/wiki/ReDoS
I believe the correct way to protect against ReDOS is to use one of the many regular expression implementations that do not have exponential worst cases.
Nowadays there are good DFA or Tree based matching algorithms that are O(mn) where m is the length of the regular expression and n is the length of the input.
Re: TRE: A Regex Engine with Approximate Matching
#8Interesting, would help with [1] ReDOS attacks? It would seem that fuzzy matching could put a upper limit on execution time right? [1] https://en.m.wikipedia.org/wiki/ReDoS
No, seems like it would result in a much bigger state machine that includes states and transitions for all those non-exact matches.
https://en.wikipedia.org/wiki/Finite-state_machine#Acceptors...
Re: TRE: A Regex Engine with Approximate Matching
#9Apropos of regex engines: PCRE [1] is an interesting and somewhat widely used [2] C library for Perl-Compatible Regular Expressions.
I was once on a product team where we used PCRE, and one of my tasks was building it from its C source on many Unix variants (such as Linux, Solaris, HP-UX, AIX, Tru64 UNIX, etc.) and Windows (x 32/64-bit OS versions for some of them). I learned something about the differences between the C compiler toolchains on all those OSes in the process. There was quite a bit of variation between them, in the commands and steps needed to compile and link programs.
https://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expres...
https://en.wikipedia.org/wiki/Philip_Hazel (PCRE creator)
[2] From the Wikipedia article about PCRE:
>A number of prominent open-source programs, such as the Apache and Nginx HTTP Servers, and the PHP and R scripting languages, incorporate the PCRE library; proprietary software can do likewise, as the library is BSD licensed. As of Perl 5.10, PCRE is also available as a replacement for Perl's default regular expression engine through the re::engine::PCRE module.
>The library can be built on Unix, Windows, and several other environments. PCRE is distributed with a POSIX C wrapper, a native C++ wrapper,[a] several test programs, and the utility program pcregrep built in tandem with the library.
Re: TRE: A Regex Engine with Approximate Matching
#10An interesting theoretical problem that arises:
Given a regular language L, define LD(L,k) to be the set of strings with Levenshtein distance at most k from some string in L.
1. Is LD(L,k) regular? (yes)
2. How hard is it to construct a regular expression(or DFA, NFA) of LD(L,k) given a regular expression(or DFA, NFA) of L? (probably it is something k times the original size in terms of NFA)
I believe a constant k here does not make much sense. since we might match super long strings, then having more errors seems ok. Maybe we can ask for the following:
LDM(L,ε) is the set of strings, such that if x in LDM(L,ε), then there is a y in L, such that distance between x and y is at most ε|y|.
LDM(L,ε) does not seem to be a regular language.