1
$\begingroup$

Consider an array of bytes.

I want to partition the array, such that the following two conditions hold:

  1. 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.

  2. Given a sub-array (i.e. consecutive bytes) of the main array, partition boundaries within the sub-array can be detected.

Example:

Let the array of bytes be:

array of bytes

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.

partitioned array

To explain requirement 2, assume that the following sub-array is given:

sub-array

An algorithm satisfying requirement 2 should be able to correctly identify partition boundaries:

partitioned sub-array

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$.

$\endgroup$
  • $\begingroup$ If that given subarray is just a random input without any extra information, then it's not possible to provide such an algorithm, but is it a randomized algorithm fine? Then what is the definition of randomized algorithm for this problem? e.g a randomized algorithm that partitions and then finds the corresponding partition in a given subarray with probability $p$ and with shift distance $d$, where $p=f(U,L,n),d=g(U,L,n)$. $\endgroup$ – Saeed Jan 20 '15 at 10:53
  • $\begingroup$ @Saeed: Could you elaborate why "it's not possible to provide such an algorithm"? $\endgroup$ – M.S. Dousti Jan 20 '15 at 10:56
  • $\begingroup$ I mean actually it's somehow not deterministic, e.g attach the subarray that you selected to the end of input, and suppose that the partition in the end is not same as the before, then what shall we guess? the first partition or the second partition? $\endgroup$ – Saeed Jan 20 '15 at 11:05
  • $\begingroup$ @Saeed: The idea of "winnowing windows" (as described at the end of my question) solves the issue you just said. It is deterministic, and it works for all possible sub-arrays. The problem with it, however, is that the partition lengths can be as small as 1. $\endgroup$ – M.S. Dousti Jan 20 '15 at 11:08
  • 1
    $\begingroup$ I have to kindly argue that just because "I think we need some relaxation" is not enough to deduce that "that is not possible to do this". If you can prove it rigorously, then I can look for some relaxation. Anyway, an excellent relaxation in my case is that the partition lengths follow a binomial (or any other bell-shaped) distribution, with a given mean and variance. $\endgroup$ – M.S. Dousti Jan 20 '15 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.