posted 2009-10-20T13:25:28Z (apropos 2009-10-19).
this seems like a useful algorithm to know, especially for large datasets. perhaps it could be an efficient first-pass algorithm for finding anomalous densities. paper by Benjamin A. Burton.
Abstract: Given an arbitrary bitstream, we consider the problem of finding the longest substring whose ratio of ones to zeroes equals a given value. The central result of this paper is an algorithm that solves this problem in linear time. The method involves (i) reformulating the problem as a constrained walk through a sparse matrix, and then (ii) developing a data structure for this sparse matrix that allows us to perform each step of the walk in amortised constant time. We also give a linear time algorithm to find the longest substring whose ratio of ones to zeroes is bounded below by a given value. Both problems have practical relevance to cryptography and bioinformatics.
---> back to algomagic.com