Re: Algorithm inspiration required.

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]
Re^3: Algorithm inspiration required. by hexcoder (Curate) on Jun 19, 2018 at 18:32 UTC
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]
Re^4: Algorithm inspiration required. by BrowserUk (Patriarch) on Jun 19, 2018 at 19:32 UTC
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]


Your skill will accomplish what the force of many cannot
	PerlMonks