2
$\begingroup$

Suppose we are given a language $\Sigma$ where, suppose, $|\Sigma| = O(1)$. Consider two fixed strings $A, B \in \Sigma^n$. Define the Hamming metric between these strings as $$d_{H}(A,B) = \sum_{i=1}^n \boldsymbol{1}\lbrace A(i) \neq B(i)\rbrace$$ If we define $B^{(k)}$ as the $k$-shift (to the right) cyclic permutation of $B$, then what I am looking to compute is $$d_{\text{cyc},H}(A,B) = \min_{k \in \lbrace 0, \cdots, n-1 \rbrace} d_H\left(A, B^{(k)}\right)$$ So it is easy to see that we can compute $d_H(A,B)$ for some length $n$ strings $A$ and $B$ in time $O(n)$, implying a trivial $O(n^2)$ algorithm for $d_{\text{cyc},H}(A,B)$. So my goal is to see if we can do something better. If someone knows of an algorithm that generalizes to any constant value for $|\Sigma|$, I would be happy to know. For now, I will lay out some of my thoughts.


Suppose that $|\Sigma| = 2$, namely that $\Sigma = \lbrace \alpha, \beta \rbrace$. Let us define a map $h: \Sigma \rightarrow \lbrace -1, 1 \rbrace$ where, say, $h(\alpha) = -1$ and $h(\beta) = 1$. If we transform the strings $A$ and $B$ element-wise to strings $A'$ and $B'$ in $\lbrace -1, 1\rbrace^n$, we can then compute all of the $d_H\left(A, B^{(k)}\right)$ values via a FFT of the concatenated string $B'B'$ and $A'$. We can see this by first considering the computation of $d_H(A,B)$. Suppose $I_{=} \subseteq [n]$ is the set of indices for characters where $A$ and $B$ are the same and make $I_{\neq} = [n] \setminus I_{=}$ the set of indices where $A$ and $B$ differ. Clearly $I_{=}$ and $I_{\neq}$ are disjoint, so $|I_{=}| + |I_{\neq}| = n$. Now let us compute the inner product of $A'$ and $B'$. Any element where $A$ and $B$ have the same character, $A'$ and $B'$ will have the same sign at that element. Any element where $A$ and $B$ differ, the signs will differ as well. Thus we find that $$(A' \cdot B') = \sum_{i=1}^n A'(i) B'(i) = \sum_{i \in I_=} A'(i) B'(i) + \sum_{i \in I_{\neq}} A'(i) B'(i) = |I_=| - |I_{\neq}|$$ As $d_H(A,B) = |I_{\neq}|$ and $(A'\cdot B') = |I_{=}| - |I_{\neq}| = n - 2 |I_{\neq}|$, this implies that we can find $d_H(A,B)$ to be equal to $$d_H(A,B) = |I_{\neq}| = \frac{1}{2}\left(n - (A' \cdot B')\right)$$ Now if $\text{rev}(S)$ reverses a string $S$ of size $n$, implying that $S(i) = \text{rev}(S)(n-i)$, we can observe that if we define the string $C' = \text{rev}(B'B')$, we can find for any $k \in [n]$ that \begin{align} v_k &:= \sum_{i=1}^n C'((n-k+1)-i)A'(i)\\ &= \sum_{i=1}^n (B'B')((k-1) + i)A'(i) \\ &= \sum_{i=1}^n (B')^{(k-1)}(i) A'(i) \\ &= \left((B')^{(k-1)} \cdot A'\right) \\ &= n - 2 d_H\left( A, B^{(k-1)} \right) \end{align}

This implies doing the convolution of the strings $C'$ and $A'$ give us a mechanism to compute all values for $d_H\left(A, B^{(k)}\right)$, which can be done in $O(n \log(n))$ time using the Fast Fourier Transform (FFT). This sounds great for the special case that $|\Sigma| = 2$, but I am unsure about an efficient, exact way that generalizes to larger constant values for the size of $\Sigma$.

My initial thought as an approximation is to create, say, an $r$-wise independently family of hash functions $\mathcal{H} := \left\lbrace h: \Sigma \rightarrow \lbrace -1, 1 \rbrace \,|\, \forall c \in \Sigma, h(c) = 1 \text{ with prob } 1/2\right\rbrace$ for $r$ at least 2, uniformly sample some $h \in \mathcal{H}$, and then for a string $A \in \Sigma^n$ set $A'(i) = h(A(i))$. If we define the random variable $Y(A,B) = A' \cdot B'$ under this type of transformation, we can find that \begin{align} \mathbb{E}\left(Y(A,B)\right) &= \sum_{i=1}^n \mathbb{E}\left(A'(i)B'(i)\right) \\ &= \sum_{i \in I_{=}} \mathbb{E}\left( A'(i)B'(i)\right) + \sum_{i \in I_{\neq}} \mathbb{E}\left(A'(i)B'(i)\right) \end{align} Consider two characters $a, c \in \Sigma$. If $a = c$, then $\mathbb{E}(h(a) h(c)) = \mathbb{E}(h(a)^2) = \mathbb{E}(1) = 1$ since $h(a) = h(c)$. If $a \neq c$, then $\mathbb{E}(h(a) h(c)) = \mathbb{E}(h(a)) \mathbb{E}(h(c)) = 0$. This result implies that \begin{align} \mathbb{E}\left(Y(A,B)\right) &= \sum_{i \in I_{=}} \mathbb{E}\left( A'(i)B'(i)\right) + \sum_{i \in I_{\neq}} \mathbb{E}\left(A'(i)B'(i)\right) \\ &= |I_{=}| \\ &= n - |I_{\neq}| \end{align} Which means that technically we could use the estimator $\hat{d}_H(A,B) = n - Y(A,B)$. Obviously we could then average across $k$ estimates to minimize variance, but at least initial calculations of the variance of this estimator seem to show that the variance satisfies $\text{Var}(\hat{d}_H(A,B)) = \Theta(n^2)$, which kind of makes sense because there are hash functions that could completely get things wrong. Like if we happen to choose a hash function such that $h(c) = 1$ for all $c \in \Sigma$, then we will get an estimate that the strings are identical even if the strings have no overlap, e.g. $A = aaa$ and $B = bbb$. Thus, this randomized approach does not seem sound. If anyone has ideas of how things could be modified to improve the concentration properties, I would be happy to hear them!


Edit 1 I made a separate realization on how to proceed with the randomized approach. We know by Markov's inequality that for some constant $c > 0$ that $$\text{Pr}\left\lbrace \hat{d}_H(A,B) \geq c d_H(A,B)\right\rbrace \leq \frac{\mathbb{E}\left(\hat{d}_H(A,B)\right)}{c d_H(A,B)} = \frac{1}{c}$$ Now suppose we make $m$ iid estimates for $\hat{d}_H(A,B)$ and choose the minimum one as being correct. The only way our minimum estimate will be larger than $c d_H(A,B)$ is if all estimates are larger than this value. Thus, the probability we error is at most $(1/c)^m$. Setting $c = (1 + \epsilon)$ and $m = 2\epsilon^{-1} \ln(1/\delta)$ gives us that with probability at least $1 - \delta$, the minimum of the $m$ estimators is less than $(1 + \epsilon)d_H(A,B)$. Using this fact, we can generate $m$ iid instances for $A'$ and $B'$ in $O(mn)$ time, use them to compute the necessary FFT data in $O(mn \ln(n))$ time to obtains estimates for the each $d_H(A, B^{(k)})$ term across all samples, then compute the minimum of each estimate across all $m$ samples in $O(nm)$ time, and then compute the minimum across these final estimates in $O(n)$ time to obtain the estimate for $d_{cyc,H}(A,B)$.

Putting this all together, setting $\delta = n^{-3}$, we have with probability at least $1 - \frac{1}{n^3}$ that we compute a $(1+\epsilon)$-approximate cyclic string Hamming distance in time $O(\epsilon^{-1} n \text{polylog}(n))$ time when $|\Sigma| = O(1)$.

Note that this is not necessarily great because if we get a bad hash function, we may incorrectly return a cyclic Hamming distance estimate of $0$ because the hash function may think the strings are equivalent. So it would be nice to figure out a way to get an estimate with high probability that is only a small amount less than the true value.


Edit 2 As the above randomized approach was not too good, I went a different approach by considering things from a streaming model type of approach. Suppose we have a stream $S$ where the $i^{th}$ item from the stream is the tuple $(A[i], B[i])$ from the potentially large strings $A$ and $B$. The idea was to use reservoir sampling to get a $k$-sample of these tokens, form them into strings $A_k$ and $B_k$, and then computing the estimate of the cyclic Hamming distance of strings $A$ and $B$ by doing $$\hat{d}_{\text{cyc},H}\left(A,B\right) = \frac{n}{k} d_{\text{cyc},H}(A_k, B_k)$$

My analysis showed that for $0 < \alpha < 1$ that using this approach, we can get a $O(n^{\alpha})$-approximation with probability at least $1 - 1/n^{O(1)}$where the runtime serially is $O\left((n + n^{1-2\alpha} \ln(n))\ln(n)\right)$ and the space requirements are $O\left(n^{1-2\alpha}\ln(n)\ln|\Sigma|\right)$ bits.

$\endgroup$
2
  • $\begingroup$ Do you care more about the case of large $|\Sigma|$ or small $|\Sigma|$? $\endgroup$
    – D.W.
    Nov 7 '20 at 5:03
  • $\begingroup$ @D.W. I think handling the small $|\Sigma|$ is probably of more practical interest but handling large $|\Sigma|$ would be interesting to achieve efficiently. $\endgroup$
    – spektr
    Nov 7 '20 at 5:39
3
$\begingroup$

Let $\alpha \in \Sigma$ and $d_{\alpha, H}(A,B) = n - \sum1\{A(i)=B(i)=\alpha\}$. Then you can use your FFT technique to compute $d_{\alpha, H}(A, B)$ for each $\alpha \in \Sigma$. It will take $O(n \cdot \log(n) \cdot |\Sigma|)$ time. So you will have an $|\Sigma| \times n$ table, where you should find a column with a minimum sum, which can be done in $O(|\Sigma| \cdot n)$ time.

$\endgroup$
1
  • $\begingroup$ I like this answer! Thank you for your insight! Very elegant! $\endgroup$
    – spektr
    Nov 6 '20 at 20:44

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.