Consider an array of bytes.
I want to partition the array, such that the following two conditions hold:
The number of bytes within each partition (except perhaps the last one) is between L and U, inclusive. Here, L is much smaller than U.
Given a sub-array (i.e. consecutive bytes) of the main array, partition boundaries within the sub-array can be detected.
Let the array of bytes be:
Let L = 2 and U = 4.
The following partitioning satisfies requirement 1 (red lines depict partition boundaries). Notice that the size of all partitions is between L and U inclusive.
To explain requirement 2, assume that the following sub-array is given:
An algorithm satisfying requirement 2 should be able to correctly identify partition boundaries:
PS: An idea which only satisfies the second requirement is called winnowing. It uses a sliding window over the bytes, computes some fingerprint in each window, and then uses another sliding window (the "winnowing" window) over fingerprints, and then selects the boundary to be the byte corresponding to the fingerprint which satisfies some property in each winnowing window.
Edit: If no such algorithm exists, we can think of some relaxations. The one that best fits my case changes requirement 1 as follows:
Let p(n) be the fraction of partitions of length n. We want p(n) to follow some bell-shaped distribution with mean $\mu$ and standard deviation $\sigma$. This way, I can reduce $\sigma$ to concentrate the partition lengths around $\mu$.