1
$\begingroup$

Suppose there is a very long string $S\in \Sigma^N$ with length $N$, where $\Sigma$ is a relatively small alphabet (for example, $\Sigma=\{'a', 'b', \ldots, 'z'\}$). Now, given a budget $B$, the goal is to find the solution of following problem: $$ \begin{align*} \min_{l\in\mathbb{N}} &\quad l \\ \text{s.t. }& \max_{s\subset S, |s|=l} \ \text{freq}(s) < B \end{align*} $$ i.e., I want to find a length $l_c$, such that for "any" substring $s\subset S$ with length $|s|>l$, it occurs no more than $B$ times.

Assume every character in $S$ obeys the same known distribution $D$: $S[i]\sim D, \forall i\in[N]$. Here we can allow some violations in the constraint, only requiring $$ \Pr[\max_{s\subset S, |s|=l} \ \text{freq}(s) < B] > 1-\delta. $$

Currently I'm using a brute force approach, testing each $l$ from small to large, where for each $l$ I scan through the whole string $S$ to determine if there is one substring occur too often. This is very inefficient since $|S|$ is huge.

So I want to know if there exists some sub-linear (w.r.t. $N$) algorithm that can estimate the maximum frequency of substrings with fixed length.


Maybe I didn’t make it clear. Here is my problem:

  1. Given a constant $B$ and the length of the string $N$, I want to find the minimum length $l$, such that all $l$-long substrings occur no more than $B$ times. Is there a algorithm better than simply testing from small to large?

  2. If it's expensive to determine the exact $l$, an approximated $l$ is also acceptable. Here "approximated" has two meanings: $l$ can be smaller than the true $l_c$ as long as there're not too many violating $l$-long substrings; or it can be larger that $l_c$, but not too far away.

  3. Furthermore, if the distribution of input character is highly skewed (i.e., some characters occur far more often than others), can I find an approximate or exact $l$, such that all $l$-long substrings starting with some fixed character $s$ occur no more than $B$ times?

$\endgroup$
  • $\begingroup$ Welcome to TCS.SE! I don't understand the probabilistic part of your question. What's the random variable? What is the probability taken over? The random choices of the algorithm (which determine $l,B$)? The random choice of the string $S$? Both? If $l,B$ are fixed and $S$ is random, then this is purely a mathematical question, not an algorithmic one. Finally: What is your question? In the last sentence you say you want an algorithm to do something. What are the inputs, and what are the desired outputs? $S,l$ are the inputs, and you want it to output a $B$ such that (..)? $\endgroup$ – D.W. Oct 20 '16 at 20:55
  • $\begingroup$ Also, do you allow linear-time preprocessing that depends only on $S$ but not on $l$? If you do, have you looked at suffix trees? There is a deterministic $O(N)$ time algorithm that will find the exact answer to the problem in your first paragraph, by building a suffix tree and then labelling each node with the number of suffixes that pass through it. $\endgroup$ – D.W. Oct 20 '16 at 20:59
  • $\begingroup$ @D.W. The budget $B$ is a given constant and $S$ is random. I stated the probabilistic part because: firstly, I can get distribution information of $S$ and want to exploit it; secondly, an randomized/approximated solution is acceptable. You can just view the probabilistic part as requiring "for all $l$-long substrings, no more than a small fraction of them have frequency exceeding $B$" $\endgroup$ – xyguo Oct 21 '16 at 14:01
  • $\begingroup$ @D.W. As for the suffix tree you mentioned, actually I was building a suffix tree. But in my case, an $O(N)$ construction time is unacceptable because $N$ is just too large. I can't even afford to put the whole tree in main memory. So I turn to the ERa algorithm which construct a suffix tree with limited memory. The "Virtual Partitioning" procedure of ERa helps, but I wonder whether there exists a better solution. $\endgroup$ – xyguo Oct 21 '16 at 14:08
1
$\begingroup$

If $D$ has high min-entropy, then there's a "sharp cut-off" phenomenom: there's a value $l_0$ depending only on $n,B$ such that the value of $l$ is almost always very close to $l_0$, when $S$ is drawn randomly from $D^n$.

For a simple example, consider the case where $B=2$ and $D$ is the uniform distribution on $\Sigma$. Then

$$l_0 \approx {\lg(n^2/2) \over \lg |\Sigma|},$$

due to the birthday paradox.

Thus, an algorithm can ignore the input string $S$, look only at $B,n$, compute the appropriate $l_0$, and output that. This will be approximately correct, almost all the time.

That's why I say this can be treated as purely a mathematical question, not an algorithmic one.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.