BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:
I'm looking to detect a repeating sequence in a stream of data.
That is, given an essentially endless source of data that is known to eventually repeat; detect the start and length of the repeating sequence.
In simplistic terms, I want to program the equivalent of the algorithm that solve this regex: $str =~ m[(.+).*?(\1)]g;
Except that the values aren't characters or anything easily translated to characters and I cannot see the entire stream at any given time.
And the data stream and the length of the repeated sequence can be big. Very big. Likely bigger than I can hold in memory, so all of those Liv-Zempel windowed and sliding buffer compression algorithms go out of the window; as do any complex tree structures (trees/tries/graphs et. al).
The thought in my mind at the moment is (an adaption of) the rolling checksum algorithm used by rsync; but I'm not seeing how to apply it to my problem.
Any thoughts on that; or any pointers to any other algorithms that might be adaptable to this problem gratefully received.