good chemistry is complicated, and a little bit messy -LW |
|
PerlMonks |
Re^2: Algorithm inspiration required. (Further thoughts on rolling checksums)by Eily (Monsignor) |
on Jun 18, 2018 at 13:58 UTC ( [id://1216859]=note: print w/replies, xml ) | Need Help?? |
Your regex: $str =~ m[(.+).*?(\1)]g would accept "abcd" as a repeating pattern in "abcdefabcd", but your example shows no extra data between the repetitions (like in your similar question here). Which interpretation is correct? If your data is only one pattern repeated without intermediate data, any subsequence in that pattern can be interpreted as the start of the pattern (eg, in your example above it would be deab, rather than Abcd). You could keep the checksums for the value, or subpattern with the lower occurence. Eg, 'A' has a ratio of 1/18, so only keeping a checksum for every instance of 'A' would divide the number of checksums to keep in memory by 18. (Ie: that's trying to fit Boyer Moore as much as possible into your problem) Also, if you have a good idea of the ratio for each value beforehand, or can preprocess the input data, n-ary Huffman coding might reduce the size greatly, while choosing n = 16 (with hex representation) or 256 would still keep value aligned on a byte (so convenient for processing). Edited my first link, I wanted to link to the thread, not my post.
In Section
Seekers of Perl Wisdom
|
|