Performance enhancements to enable large inputs
Hi,
I want to run this on a billion-sized low entropy case-insensitive UTF-8 input with a variable number of characters up to approximately 256 bytes each.
The data comply to an specification format but empirically it is very low entropy, only uses a very narrow subset of the specification and also a very narrow subset of UTF-8 characters.
Think of URI schemes like mailto [1]. The standard yields ample provisions for the format but empirically only a narrow subset is used.
However DFA is very slow even for very small samples. In addition even though I am not very proficient in Rust, I cannot see how to introduce MP or MPI constructs. DFA minimization also returns impractical expressions and I cannot see how to relax, penalize or restrict the size of the expression, coalesce (arbitrary) character ranges or groups, include prior knowledge of the superset expression defined by the specification format, or take advantage of data preorderings.
Finding an expression to match legal and legitimate data based on the empirical set is useful in determining diverging datum.
As an example, if some subexpression is know by the specification to be constrained to \w characters and in the data all lowercase alphabet characters except one were present, it would be fine to merge ranges to [a-z]. The point here would be that even though this subexpression can be all \w characters per specification, only [a-z] would be used in practice - and if some new datum had numbers, even though the specification allows it, it would be kind of weird given a billion samples did not.
The constraints imposed by the DFA solution as implemented are too strict in this regard and I cannot see where to go from here.
To summarize, I would greatly appreciate if you could point me towards scaling this library to work on large inputs.
I hope this tiny discussion interests you to some degree.
Vítor
Source: pemistahl/grex