# Algorithm for cyclic $n$-string Hamming distance with constant sized language $\Sigma$

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.

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

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.