3
$\begingroup$

Let $U$ be a small finite set. Consider the following problem:

Input: two strings $u \in U^k$ and $v\in U^n$ with $k \leq n$.
Output: a (contiguous) substring of $v$ of length $k$ with the minimum Hamming distance from $u$.

In other words I want to compute the following function: $$f(u,v) = \arg\min_{j < n-k} d_H(u, v[j,j+k])$$ where $n = |v|$ and $k = |u|$.

What is the fastest algorithm for this problem?

Can this problem be solved in time $O(n\log n)$?


I think I can solve the problem if I have a data structure as follows: Let $B = \{0, 1 \}$ and $k \le n$ be fixed numbers. We want a data structure $D$ with the following properties:

  • Build: for $v \in B^n$ and $u \in B^k$, $D.Build(v, u)$ builds an instance of $D$ in time $O(n \log n)$.

  • Query: for $1 \le q \le n - k + 1$, $D.Query(q)$ returns $\langle u, v[q, q + k - 1]\rangle$ in time $O(\log n)$.

Is there a data structure with these properties?

$\langle \cdot , \cdot \rangle $ is the dot product and $v[i, j]$ = $(v_i,\ldots, v_{j})$ is the subsequence of $v$ from $i$ to $j$.

$\endgroup$
  • $\begingroup$ I suggest you edit your question to focus more on the actual problem you need to solve than trivialities and formalities (I'm sure everyone here knows how to treat strings as vectors and how dot product is defined). Specifically, it's unclear which of the parameters of your problem are fixed and which are not. I've made a lot of assumption to interpret your question, but in any case, have a look here, I think you will find it interesting. $\endgroup$ – chazisop Nov 15 '15 at 17:55
  • $\begingroup$ @chazisop, I made a few edits. Is it better now? $\endgroup$ – G H Nov 15 '15 at 18:34
  • 2
    $\begingroup$ I did some clean up on the question. ps: If you ask me you should just directly ask for the fastest way to find the subsequence of a given vector from another given vector with min Hamming distance in place of asking for a data structure that you can use to solve the problem in the way you have in mind. $\endgroup$ – Kaveh Nov 15 '15 at 19:53
  • $\begingroup$ Do you mean in time $O(2^n \log(2^n))$? you can't even scan the vector $u$ in time $O(n \log n)$ which you state as your desired complexity. $\endgroup$ – kodlu Nov 15 '15 at 22:39
  • $\begingroup$ @kodlu, why? $v = (v_1, \ldots, v_n)$ we scan in time $O(n)$, $u = (u_1,\ldots,u_n)$ we scan in time $O(k)$ = $O(n)$ because $k \le n$. $\endgroup$ – G H Nov 15 '15 at 22:48
4
+50
$\begingroup$

Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm:

Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$.

Define polynomials $$p(x,y) = \sum_{i \in [n]} x^i y^{v_i} \qquad \text{and} \qquad q(x,y) = \sum_{j \in [k]} x^{k-j} y^{m-u_j}.$$ Compute the polynomial $$r(x,y) = p(x,y) q(x,y).$$ Then $$r(x,y) = \sum_{t,s} x^t y^s \left|\left\{ (i,j) \in [n]\times[k] : i+k-j=t \wedge v_i + m - u_j =s \right\}\right|. $$ In particular, for $k \leq t \leq n$, the coefficient of $x^{t} y^m$ in $r(x,y)$ is $$\left|\left\{ (i,j) \in [n]\times[k] : i=j+t-k \wedge v_i = u_j\right\}\right| = k-d_H(u,v[t-k+1,t]).$$ Thus, the coefficients of $r(x,y)$ provide a lookup table for $d_H(u,v[t-k+1,t])$ for $k \leq t \leq n$. So, given the coefficients of $r(x,y)$, we can easily solve the problem by picking the $t$ such that $x^{t}y^m$ has the largest coefficient:

Output: $f(u,v)+k=\mathrm{arg}\max_{k \leq t \leq n} \mathrm{coefficient}_{r(x,y)}(x^{t}y^m)$

So how fast is this algorithm? I claim it can be implemented in $O(nm \log (nm))$ time (assuming arithmetic operations with $O(\log (nm))$ bits of precision take constant time) using the Fast Fourier Transform.

The core of the problem is computing $r(x,y)=p(x,y)q(x,y)$, where the degree of $p(x,y)$ is at most $n$ in $x$ and $m$ in $y$ and the degree of $q(x,y)$ is at most $k$ in $x$ and $m$ in $y$.

We can first reduce it to univariate polynomial multiplication by defining $$p'(z) = p(z^{m+1},z) \qquad \text{and} \qquad q'(z)=q(z^{m+1},z),$$ computing $r'(z)=p'(z)q'(z)$, and then extracting $r(x,y)$ from the identity $r'(z)=r(z^{m+1},z)$.

I won't go through the FFT algorithm (even though it's one of my favourite algorithms), but the general idea is:

  1. Pick $\ell = O(nm)$ special points $w_1, \cdots, w_\ell \in \mathbb{C}$, namely $w_j=\exp(2\pi\sqrt{-1}j/\ell)$ and $\ell$ is a power of $2$ with $\ell > \mathrm{degree}(r'(z))=O(nm)$.
  2. Evaluate $p'(w_j)$ and $q'(w_j)$ for all $j \in [\ell]$ in $O(\ell \log \ell)$-time using a divide and conquer algorithm.
  3. Compute the values $r'(w_j)=p'(w_j)q'(w_j)$ for all $j$ in $O(\ell)$-time.
  4. Interpolate the coefficients of $r'(z)$ from the values $r'(w_j)$ in $O(\ell \log \ell)$-time using essentially the same divide and conquer algorithm.

The observation that makes the divide and conquer algorithm work is that we can write $p'(z) = p'_\text{even}(z^2) + z \cdot p'_\text{odd}(z^2)$, where $p'_\text{even}$ and $p'_\text{odd}$ have half the degree of $p'$. It then suffices to recursively evaluate $p'_\text{even}(w_{2j})$ and $p'_\text{odd}(w_{2j})$ for $j \in [\ell/2]$.

$\endgroup$
3
$\begingroup$

Hint: Express the binary vectors as a polynomial with coefficients in {-1,0,1} and obtain the hamming distance of u with all length k contiguous subsequences of v through a polynomial multiplication.

Use Fourier transforms to improve the complexity to what you need.

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