An 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|.
Looks 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.
Apropos 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.
>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.
Years 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.
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.
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.