5
\$\begingroup\$

I have a list of words in English. My aim is to find all pairs of words that differ by exactly one letter (i.e. edit distance is 1). For instance: PAY-PLAY, WARM-ARM, WORD-WORK.

The naive algorithm is to compare every word with all other words in the list. I've improved it by noticing that if one word is two letters or more longer than the other word, then they can't differ by exactly one letter. So I first sort the word list by length, then compare every word with words of the same length or longer by one letter.

This is my code:

import nltk

words = ['a', 'abide', 'ability', 'able', 'about', 'above', ...]
words.sort(key=len)

pairs = []

for i, w1 in enumerate(words):
  for j, w2 in enumerate(words[i+1:]):
    if len(w2) - len(w1) > 1:
      break
    if nltk.edit_distance(w1, w2) == 1:
      pairs.append((w1, w2))

Can it be improved further? It should scale well with the size of word list (I plan to run it with a list of tens of thousands of words).

\$\endgroup\$

2 Answers 2

7
\$\begingroup\$
  • Sorting seems like a overkill. Assigning words to buckets feels more appropriate:

      buckets = defaultdict(list)
      for word in words:
          buckets[len(word)].append(word)
    

    Now all those not-nicely-looking ifs disappear:

      for length, words in buckets:
          get_pairs_same_length(words)
          get_pairs_different_length(words, buckets[length + 1]
    
  • I don't think that nltk.edit_distance is a right tool here. You spend too much time calculating large distances between unrelated words. Since you are interested only in distance 1 it may make sense to do it manually:

    • For the words are of the same length, compare them letter by letter, allowing only one mismatch.

    • For the length differ by 1, again compare them letter by letter, allowing only one insertion.

\$\endgroup\$
3
\$\begingroup\$

Another quick check to avoid calling edit_distance is that if the first letter of w1 does not appear as either the first or second letter of w2, then the words must also be > 1 distance apart.

You can put w1’s both length and first letter in variables before starting the w2 loop, to avoid re-calculating them for every w2.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ if the first letter of w1 does not appear as either the first or second letter of w2, then the words must also be > 1 distance apart - what about fish - dish or shop - hop? \$\endgroup\$
    – AcK
    Jul 8, 2022 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.