3
$\begingroup$

I want to turn one string into another with only single letter substitions. What is a good way to do this, passing through only valid words in between (this website has some examples)?

Valid here means "a word in English" as this is the domain I consider.

My current idea is that I could use a shortest path algorithm with the Hamming distance for edge weights. The problem is that it will take a long time to build the graph, and even then the weight is not so precise in terms of distance (though it will never underestimate it) unless the weight is one, so I would probably have to find a to build a graph that only had weights of one.

What would be the easiest way to build the graph? Am I taking entirely the wrong approach?

$\endgroup$
6
$\begingroup$

The graph I consider has the valid words for vertices and edges correspond to one-letter substitutions. In this graph the Hamming distance never overestimates the distance but can underestimate it (e.g. between $aa$ and $cc$ in the set of valid words ${aa,ab,bb,bc,cc}$)

You don't need an actual graph, you just need a representation of it. The hard part is computing the neighbors : you may want to store the valid words into a prefix tree. But for the search algorithm you already have a non-overestimating distance so you can use that as a admissible heuristic for the $A^*$ algorithm. You can use an hash table to store the marked vertices.

Building the prefix tree

To list all the neighbors of $w$ first use this function that computes all words $v$ such that $w$ and $v$ differs only on the $i$th letter. It runs in $O(|Σ||w|)$ if you implement it correctly : $w$ must be in the form of a list for the tail() dans head() operation to be in constant time. The operation prefix . c . tail(w) just has to be in linear time.

neighbors(i, prefix, w, trie) =
  if(i == 0) :
    for c in 'a' .. 'z' :
      if(tail(w) is a word of trie) :
        add(prefix . c . tail(w))
  else :
    neighbors(i-1, prefix . w[0], tail(w), trie[head(w)])

Then to list all the neighbors, just run:

for i in 0 .. length(w) - 1 :
  neighbors(i, emptyprefix, w, trie_of_valid_words)

Which runs in $O(|Σ||w|^2)$.

Compared to other methods, where $N_V$ the number of valid words.

  • if you use a hash table and enumerate all the potential neighbors: $O(|Σ||w|^2)$ in the practical case and $O(|Σ||w|^2N_V)$ in the worst case. It might be faster in practice though.
  • if you use a binary search tree: $O(|Σ||w|\log N_V)$ in the worst and average case.

Precomputation

At first the goal was to get all the neighbors in only one look up in time $O(|w|)$ by previously having computed some kind of prefix tree with wildcards. (I don't really know the name of this data structure) Then I realized that it can simply be done with just a reverse search.

I insist that this is only interesting if you only care about the look up time. I would probably be a good idea if you have to find the shortest path between several pairs of words. If it's only one time the method above will be enough.

This is really very simple : for each word $w$, enumerate all the possible neighbors $v$ of $w$ and check if they are valid. This is in $O(N_V\log N_V |w||Σ|)$ or $O(N_V^2)$ if $N_V$ is small enough for this to be interesting. Add them to your automaton / prefix tree / hash table with the key $v$ and the value $w$.

Then getting all the neighbors of $v$ is looking up in this structure and getting back all the $w$'s. So you can make your search algorithm with this.

Implementation details:

  • generic binary tree : look up in $O(\log(N_V|Σ||w|))$ which is $O(|w|+\log|Σ|)$ but you don't care about the $\log|Σ|$.
  • trie : look up in $O(|w|)$
  • hash : look up in $O(|w|)$ (and worst worst case)

Conclusion

If the set of valid words does not change I would suggest precomputing and storing in a hash table and using the A* with the hamming distance admissible heuristic.

$\endgroup$
  • $\begingroup$ What is the cost of creating the tree? Also, how can I run A* on the tree? $\endgroup$ – soandos May 10 '12 at 23:57
  • $\begingroup$ @soandos: the complexity of creating the tree is linear time in the size of your data. You run A* on the graph, not on the tree but you indeed use the tree to compute the list of the neighbors in time $O(|Σ||w|)$. $\endgroup$ – jmad May 11 '12 at 7:40
  • $\begingroup$ How can I use the tree to compute the neighbors $\endgroup$ – soandos May 11 '12 at 7:42
  • $\begingroup$ I updated my answer. It is in fact $O(|Σ||w|^2)$ (which is better than with a hash table) $\endgroup$ – jmad May 11 '12 at 8:24
  • 1
    $\begingroup$ @Syzygy: $O(|w|^2|Σ|)$ for both: in the hash table you have to check in $O(|w|)$ (i.e. hashing time) for all the $|w||Σ|$ combinations. (I emphasized "better" because you have $O(|w||Σ|)$ in your answer - sorry) $\endgroup$ – jmad May 11 '12 at 12:43
5
$\begingroup$

I am not sure if I understood the problem setting correctly, but I think a breadth-first search works?

Problem: Given words $w$ and $w'$ from a dictionary $D$, is it possible to find a sequence of words $w_0,...,w_k$, such that each word is from $D$, $w_0=w$, $w_k=w'$, and $w_i$ and $w_{i+1}$ differ by exactly a single letter substitution.

Algorithm: Start a breadth-first search at $w$, where vertices are words in $D$, and edges connect words which differ by a single letter substitution. Find $w'$ in this way, and you found a shortest path between $w$ and $w'$. How to enumerate the neighbours of some vertex $v$? We can simply go through every position of the word and check for every letter substitution whether the resulting word is in $D$.

Running time: Simple BFS is running time $O(|V|+|E|)$, here $|V|=|D|$. However, enumerating the neighbours takes $|w|*|\Sigma|$ steps, where $|\Sigma|$ is the size of your alphabet. Assuming alphabet size to be constant, and dictionary lookup cost of $O(|w|)$ (e.g. Hashsets), you have a running time of $O(|V||w|^2+|E|)$.

$\endgroup$
  • $\begingroup$ So there is no way to get around enumerating all possible combinations of words of distance 1 from $w$? $\endgroup$ – soandos May 11 '12 at 0:35
  • $\begingroup$ I don't think there is a way around inspecting the neighbourhood of $w$, since you might miss out on a possible sequence then. The question is basically how efficient can we compute the neighbourhood? Again, if $D$ is large, then I think linear in $|w|$ is a fair solution. $\endgroup$ – Syzygy May 11 '12 at 0:46
  • $\begingroup$ Why is it not $(|\Sigma|-1)^{|\omega|}$? $\endgroup$ – soandos May 11 '12 at 1:59

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.