4 ms·
We wrote a generalization of the Levenshtein distance algorithm for regular expressions in Hyperscan (https://github.com/intel/hyperscan https://github.com/inte
by glangdale 7y ago
We wrote a generalization of the Levenshtein distance algorithm for regular expressions in Hyperscan (https://github.com/intel/hyperscan https://github.com/intel/hyperscan), which allows you to do Levenstein distance matching over regular expressions. It is not necessarily a cheap thing to do, given that incautious use of edit distances and permissive regular expressions can result in automata that match almost anything.
I believe that the first widely available approximate regex matcher was Tre (https://laurikari.net/tre/ https://laurikari.net/tre/). However, while everybody wants to talk about approximate matching like they have something to say, most algorithmists act like they forgot about Tre.
- eesmith 7y agoagrep is from 1988. I heard about it some 10 years later. https://en.wikipedia.org/wiki/Agrep https://en.wikipedia.org/wiki/Agrep says "A more recent agrep is the command-line tool provided with the TRE regular expression library. TRE agrep is more powerful than Wu-Manber agrep since it allows weights and total costs to be assigned separately to individual groups in the pattern."
- glangdale 7y agoYou're right. I can't believe I forgot agrep (so addled was I with my "forgot about tre" pun). Our departmental Unixen machines had agrep in '91, I think.
- deleted 7y ago[deleted]