Re:Doug McIlroy's C++ regular expression matching library
by mehrdadn on Tuesday July 31, 2018 @09:18AM
(#17652872)
...yeah, exactly that, thanks for mentioning the character class issues. :-) I think it was partly for this reason (but also others -- like my idea that it would help SAT or SMT solving) I've also had this idea of making a "universal" int_set class that adaptively adjusts its internal data structure (bitvectors, intervals, "shift-intervals", sparse sets, BDDs, etc.) based on its contents' sparsity patterns... which, for n different data structures, would require O(n^2) or O(n^3) methods to handle set and perhaps arithmetic operations between them (n^2 if the output type matches the input type, n^3 if we let the output data structure be different than the inputs'), which is kind of painful but I think doable and likely to be useful. That's yet another ambitious endeavor I may never get around to, or at least not before someone else does...
Re:Doug McIlroy's C++ regular expression matching library
by andreasvc on Wednesday August 01, 2018 @07:27AM
(#17661499)
Regarding that idea for a universal integer set, roaring bitmaps implement that.
Re:Doug McIlroy's C++ regular expression matching library
by HelloNurse on Tuesday July 31, 2018 @11:16AM
(#17653834)
Given a byte based encoding like UTF-8 or extended 8-bit Ascii variants or Shift-JIS, a regular expression over Unicode characters can be translated to a more complicated, but not necessarily slow to match, regular expression over bytes.
Re:Doug McIlroy's C++ regular expression matching library
by burntsushi on Tuesday July 31, 2018 @12:07PM
(#17654395)
Indeed. That's what I meant with: "For most DFA engines I've seen, they take advantage of "strings" themselves and define the alphabet to be the set of bytes. If you're searching UTF-8, then this also implies that your DFA must include UTF-8 decoding (which is generally the right choice for performance reasons anyway)." :-)
Re:Doug McIlroy's C++ regular expression matching library
by HelloNurse on Tuesday July 31, 2018 @05:17PM
(#17657238)
UTF-8 decoding usually means translating UTF-8 text to a more convenient character representation like UTF-32 or if you are naughty UTF-16 before processing, not adapting the application to work with UTF-8 data.
Re:Doug McIlroy's C++ regular expression matching library
by burntsushi on Tuesday July 31, 2018 @07:02PM
(#17658083)
I think the principle of charity applies here. What other possible interpretation of UTF-8 decoding is there for what I wrote? I mean, the automaton literally contains a UTF-8 automaton right in it, and semantically, it is totally matching in terms of codepoints.
For most DFA engines I've seen, they take advantage of "strings" themselves and define the alphabet to be the set of bytes. If you're searching UTF-8, then this also implies that your DFA must include UTF-8 decoding (which is generally the right choice for performance reasons anyway).
Regex engines with modern Unicode support do generally need to support efficient set operations on large sets though, in order to support the various character class syntaxes (which include negation, intersection, symmetric difference and, of course, union). Usually you want some kind of interval set structure, and its implementation complexity, in my experience, generally correlates with the amount of additional memory you're willing to use. :-)