in reply to Algorithm inspiration required.

Hi,

the best method I know of is using a suffix array (and longest common prefix array) with external memory. Here is a link to a research paper and the website. According to the paper it can handle a text size of 80 GiB using only 4 GiB of RAM. Since endless streams may contain infinite information, this algorithm cannot handle that. It only can work on a snapshot of the stream limited by memory (internal and external).

I would be surprised if that could be beaten by a different algorithm.

hexcoder

Replies are listed 'Best First'.
Re^2: Algorithm inspiration required.
by BrowserUk (Patriarch) on Jun 19, 2018 at 14:50 UTC

    Thank you for this.

    As a first pass (of what is perhaps the most opaque algorithm description I've yet encountered), this does far more work than I see being necessary for my particular problem; as such I think it would be necessary to adapt it quite heavily to only do that which I need.

    My, currently fragile, implementation of the running checksum algorithm works (so far tested on a very limited set of cases):

    [15:15:42.17] C:\test>rollingChksum -MAX=1e6 -BUF=1e3 -WRAP=9.123e5
6891
910000
Found repeat starting at value:912300

[15:15:48.65] C:\test>

[15:16:17.32] C:\test>rollingChksum -MAX=1e7 -BUF=1e3 -WRAP=9.123e6
6891
9120000
Found repeat starting at value:9123000

[15:17:22.49] C:\test>

    [download]

    Needs a lot of work, and a lot more testing, but it is currently processing around 6MB(16bit values, not bytes)/second; and I know that can be sped up by at least 10 times by optimising the Perl; and much further still, once I recode the algorithm into C.

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
    In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit
[reply]
[d/l]
      ok, I see check summing works quite well. I had expected more false positives because different sequences can lead to the same checksum. The suffix array method (from bio informatics) described above OTOH is exact, but admittedly more difficult to implement efficiently. And if you periodically need to throw out old values and feed new values in, that is a requirement for the algorithm that is probably not yet implemented.
[reply]
        I see check summing works quite well. I had expected more false positives because different sequences can lead to the same checksum.

        The algorithm is probably being flattered by my test data -- 16-bit random values. Although I am seeing a few false positives, it doesn't take long to verify them using a value-by-value comparison of a relatively small (currently 100, but that's flexible) number of actual values. With 100 x 16-bit numbers, there are huge number of possibilties (1e65536), so finding a repeat of those 100 is a pretty strong indicator of having found the start of the next repeat.

        I realise with bio data, especially if its just ACGT, you'd need use a much longer tell-tale sequence to avoid many false positives.

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
        In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit
[reply]

In Section Seekers of Perl Wisdom