# Estimate the maximum frequency of substring with given length in a very long character stream

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?

• 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 (..)? – D.W. Oct 20 '16 at 20:55
• 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. – D.W. Oct 20 '16 at 20:59
• @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$" – xyguo Oct 21 '16 at 14:01
• @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. – xyguo Oct 21 '16 at 14:08

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