7
$\begingroup$

This question has been prompted by Efficient data structures for building a fast spell checker.

Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, i.e. $\operatorname{LD}(u,v) \geq k$ for a fixed $k \in \mathbb{N}$. Informally, $\operatorname{LD}(u,v)$ is the minimum number of deletion, insertion, substitution and (neighbour) swap operations needed to transform $u$ into $v$. It can be computed in $\Theta(|u|\cdot|v|)$ by dynamic programming. Note that $\operatorname{LD}$ is a metric, that is in particular symmetric.

The question of interest is:

Given a set $S$ of $n$ strings over $\Sigma$ with lengths at most $m$, what is the cardinality of

$\qquad \displaystyle S_k := \{ w \in \Sigma^* \mid \exists v \in S.\ \operatorname{LD}(v,w) \leq k \}$?

As even two strings of the same length have different numbers of $k$-close strings² a general formula/approach may be hard (impossible?) to find. Therefore, we might have to compute the number explicitly for every given $S$, leading us to the main question:

What is the (time) complexity of finding the cardinality of the set $\{w\}_k$ for (arbitrary) $w \in \Sigma^*$?

Note that the desired quantity is exponential in $|w|$, so explicit enumeration is not desirable. An efficient algorithm would be great.

If it helps, it can be assumed that we have indeed a (large) set $S$ of strings, that is we solve the first highlighted question.

  1. Possible variants include using the Levenshtein distance instead.
  2. Consider $aa$ and $ab$. The sets of $1$-close strings over $\{a,b\}$ are $\{ a, aa,ab,ba,aaa,baa,aba,aab \}$ (8 words) and $\{a,b,aa,bb,ab,ba,aab,bab,abb,aba\}$ (10 words), respectively .
Improve this question
$\endgroup$
16
  • $\begingroup$ Isn't the highlighted question basically a k-nearest neighbour search? More specifically I'm thinking about spatial indices. There are data structures that support efficient k-NN queries with arbitrary metric (with some constraints) such as M-tree and its variants. Am I missing something or do you think this would this work? $\endgroup$
    – Juho
    May 9, 2012 at 18:26
  • $\begingroup$ @mrm Sure, that would work -- if I were to write down all exponentially many words up to some length (which I don't want to do), compute all pairwise alignments (which I want to circumvent) and then build the tree. $\endgroup$
    – Raphael ♦
    May 10, 2012 at 0:01
  • 1
    $\begingroup$ @mrm: Now that I think about it, finding the $k$ nearest neighbours does not solve the problem. We want to find all neighbours (up to a fixed distance). $\endgroup$
    – Raphael ♦
    May 10, 2012 at 7:25
  • $\begingroup$ Right, it's a range query search then. I think there's quite a bit of research on the subject, with huge amounts of data and large databases. But regardless, I see your point now. Maybe there's a more clever way :) $\endgroup$
    – Juho
    May 10, 2012 at 9:32
  • $\begingroup$ A couple of rather easy observations: (1) if only deletions are allowed, then the (second) problem is polynomial; (2) a bound for the count is $O\bigl((|w|+k)^k\bigr)$. $\endgroup$
    – rgrig
    May 10, 2012 at 21:56

2 Answers 2

Reset to default
1
$\begingroup$

See Levenshtein's paper. It contains bounds on the number strings obtained from insertion and deletion of a string. If $n$ is the length of the string and the string is binary, then the maximum number of nearest neighbors in the Levenshtein distance is $\Theta(n^2)$. It is comparatively harder to say anything about $k$-nearest neighbours, but one can get bounds. These should give you an estimate on the complexity.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, but this is neither the correct metric, nor won't a binary alphabet be sufficient (though alphabet size has probably not qualitative impact). I don't speak Russian so I can't check how easily the results can be transferred. $\endgroup$
    – Raphael ♦
    May 10, 2012 at 16:26
  • $\begingroup$ Bounds seem easy to find, but the question asks for an exact count. Am I wrong @Raphael? $\endgroup$
    – rgrig
    May 10, 2012 at 17:06
  • $\begingroup$ There is an English version of Levenshtein's paper that you should be able to find; it also contains bounds for general alphabet. $\endgroup$
    – Ankur
    May 10, 2012 at 20:04
  • $\begingroup$ @rgrig: The question asks for the precise number, but (good) bounds would be appreciated. $\endgroup$
    – Raphael ♦
    May 14, 2012 at 16:09
0
$\begingroup$

If your $k$ is fixed and you are allowed to do pre-processing, then this is something you might be able to try

  1. Construct a graph such that the nodes are words and an edge exists between two nodes if the distance between those two words is 1.
  2. Get the adjacency matrix corresponding to that graph (say $M$)
  3. Compute $M^k$

Now, you may be able to use the final matrix to answer all the queries. If you can store $M, M^2, M^4, M^8 \ldots$ etc. You might be able to answer for larger range of $k$ instead of fixed $k$, of course one will pay here with the cost of matrix multiplication.

Improve this answer
$\endgroup$
8
  • $\begingroup$ This is a rather naive procedure, isn't it? Computing all pairwise distances and performing breadth-first search up to depth $k$ is already more efficient. $\endgroup$
    – Raphael ♦
    May 14, 2012 at 16:17
  • $\begingroup$ I am assuming that you mean breadth-first search in the graph constructed above. In which case, you will be doing the search for every query you do. That would be no better than enumeration (which you specified in your question that you didn't want to do). In my reply above, I compute $M^k$ as a pre-processing step, which has to be done just once. After that, for every query one has to just go through a row/column of that matrix, thereby giving a faster response time. $\endgroup$
    – TenaliRaman
    May 14, 2012 at 18:07
  • 1
    $\begingroup$ Well, both ways can hide their "real" effort as preprocessing. Note that $M$ is exponentially big in maximum length $n$, so "just going through a row/column" is not efficient. Computing the distances themselves is not the bottleneck here. (You would need $\sum_{i=1}^k M^i$, by the way.) $\endgroup$
    – Raphael ♦
    May 14, 2012 at 19:38
  • $\begingroup$ Actually $M$ is just num_words x num_words. Also, it is boolean and possibly very sparse. Do you see why? $\endgroup$
    – TenaliRaman
    May 14, 2012 at 19:56
  • $\begingroup$ Yes, and no. $S_k$ contains all close words, and there are exponentially many words, i.e. $\text{num_words } = 2^m$. I edited the question to clarify. $\endgroup$
    – Raphael ♦
    May 14, 2012 at 19:58

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.