4
$\begingroup$

I am interested in proposed base R/Python solutions (i.e. without relying on external packages/libraries) to the following problem:

You have a large dictionary containing millions of valid English words. You are given an input “word”, which may or may not be an anagram of one or more words in the dictionary. Find all possible valid words in the dictionary of which the input may be an anagram. Note, the input “word” may be meaningless. For example,

input: lloeh output: hello

input: cksli output: slick, licks

Rather than use a brute force technique that computes all possible character combinations for each input target and compares them to a dictionary, you want to use a more efficient technique.

The approach I was considering was to pre-compute impossible string onsets in the target language. For example, in English, the onset sequences ^ck and ^ng are not permissable because they violate the orthographic and phonotactic constraints of the language. Given an off-line list of impossible_sequences at run time you would incrementally build possible "words" from the target. During each iteration the possible word is checked against the impossible_sequences list and if it matches the search down that search branch is terminated. The following pseudo-code in R uses for loops to illustrate my idea.

target <- "cksli"
impossible_list <- c("ck", "ng", "rt", "zz") # pre-computed not-possible English onsets

for (i in 1:nchar(target)) {
  word <- substr(target, i, i)
  if (word %in% impossible_list) break
  for (j in 2:nchar(target)) {
    word <- paste0(word, substr(target, j, j))
    if (word %in% impossible_list) break
    for (k in 3:nchar(target)) {
      ### same logic
      ### goes deeper and deeper
    }
  }
}

(1) Are there any issues with the underlying logic of my proposal? (2) Obviously nested for loops are inelegant - Could one do this recursively and if so, how? (3) What other approaches should be considered?

$\endgroup$
2
$\begingroup$

A simple solution is store the words in a dictionary (since you have to store them in some data structure) whose key is the character distribution; e.g., Counter("hello") = {h: 1, e: 1, l: 2, o: 1}. Querying the dictionary would give you the anagrams.

For storing the immutable key (character distribution) can either use a tuple list, incurring a sort, or you can use a vector the length of your alphabet (26). So you can make a speed-space trade-off in the preparation stage; the look-ups are constant time, not counting the time it takes to calculate the character distribution of the query word. If you go the latter, fixed-width route, you can make another trade-off by hashing the key, since you know the cardinality of the input (number of unique words).

$\endgroup$
3
  • $\begingroup$ The issue is that character distribution is a bad key for anagrams: dict key should be unique, so all anagrams, except the last one will be flushed. $\endgroup$
    – sobach
    Jul 27 '16 at 7:19
  • 1
    $\begingroup$ No, it won't; the value is a list of all the anagrams with the same key (distribution). Isn't identity of the character distribution precisely what constitutes an anagram? $\endgroup$
    – Emre
    Jul 27 '16 at 7:29
  • $\begingroup$ You are right, in "dict of lists" case it will work, indeed. Didn't think about such implementation. $\endgroup$
    – sobach
    Jul 27 '16 at 10:47
2
$\begingroup$

This is fun! Here is an implementation of Emre's idea in Python. I tried to avoid loops wherever possible to make the code fast.

First, some imports and constants.

from collections import Counter
import urllib.request

ALPHABET = 'abcdefghijklmnopqrstuvwxyz'
LEN_ALPHABET = len(ALPHABET)

1. Download a comprehensive list of English words. (I avoid calling it a 'dictionary' to avoid mix ups with the Python type of the same name). I found one here. Remove all words that contain non-alphabetic characters (including hyphenated words ... maybe not optimal).

response = urllib.request.urlopen('http://www-personal.umich.edu/~jlawler/wordlist')
words = str(response.read()).replace('\\r', '').split('\\n')
words = {w for w in words if set(w).issubset(set(ALPHABET))}

2. Create the hash function. Map a given word to a tuple of length LEN_ALPHABET. The first entry is the character count for a, the second is the character count for b, etc. For instance, the word 'agaze' is hashed to the tuple (2, 0, 0, 0, 1, 0, 1, 0, ...0, 0, 1).

char_to_int = {c: i for i, c in enumerate(ALPHABET)}

def hasher(w):
    w = [char_to_int[c] for c in w]
    count = Counter(w)
    return tuple(count[i] for i in range(LEN_ALPHABET))

3. Create the dictionary of hashed words. The dictionary maps each tuple to the set of corresponding words.

h_words = {}
for w in words:
    h_words.setdefault(hasher(w), set()).add(w)

4. Look up anagrams. Finally, a wrapper function to make lookups more convenient.

def get_anagrams(w):
    return h_words.setdefault(hasher(w), set())

A small test:

print(get_anagrams('olleh'))

This returns {'hello'} as desired.

Oh, and make sure to execute this:

print('The largest set of anagrams in the English language is:', max(h_words.values(), key=len))
$\endgroup$
2
$\begingroup$

@Emre's response and @elias-strehle's implementation are correct. I have made a similar implementation using an elegant (imho) hashing function I borrowed from this tweet

The class hashes each word to the product of all it's letters, in which each letter is mapped to a prime number. Products of prime numbers only collide when using the exact same numbers.

It is quite fast (as requested), around 200k anagram lookups per second (on my machine)

See here for a full example

class Anagrammer:

    alphabet = {"a":2,"b":3,"c":5,"d":7,"e":11,"f":13,"g":17,"h":19,"i":23,"j":29,"k":31,"l":37,"m":41,"n":43,"o":47,"p":53,"q":59,"r":61,"s":67,"t":71,"u":73,"v":79,"w":83,"x":89,"y":97,"z":101}

    def __init__(self, corpus):
        self.index = {}
        self.createIndex(corpus)

    def createAnagramIndexNumber(self, word):
        index = 1
        for x in list(word):
            index *= self.alphabet[x]
        return index

    def createIndex(self, corpus):
        for word in corpus:
            self.index.setdefault(self.createAnagramIndexNumber(word),set())
            self.index[self.createAnagramIndexNumber(word)].add(word);

    def getAnagrams(self, word):
        return self.index[self.createAnagramIndex(word)]
$\endgroup$
1
$\begingroup$

I think, it would be hard to find a solution without external packages at all. Internally you can create an index, that can be used for efficient search, but I can't remember any "pure-Python/R" data structure with non-unique index search. Dictionary wouldn't fit, because all anagrams will have the same key, that is impossible for dict. And there is no native binary tree search implementation both in Python and R.

Here is a sketch of a possible solution, I would use. Let's create decimal hash to determine letters, a word consists of (Python):

def word2hash(word):
    alphabet = list(map(chr, range(ord('a'), ord('z')+1)))
    hashed_word = {k: 0 for k in alphabet}
    for letter in set(word.lower()):
        hashed_word[letter] = 1
    hashed_word = sorted(hashed_word.items(), key=lambda x: alphabet.index(x[0]))
    hashed_word = ''.join([str(x[1]) for x in hashed_word])
    return int(hashed_word, 2)

This function would produce a decimal hash, based on letters. This hash could be used for efficient binary tree search (BTS). But the collision is that it doesn't take into account double letters. E.g., both for 'hello' and 'ooohell' output would be the same: 2377728. Anyway, it's fast and robust to filter out most part of your dictionary. There are several options of implementing efficient search, based on this index:

  • SQL database: non-unique indexes supported out-of-the-box, but you need an SQL-interface library (python-mysqldb/RMySQL/etc). As for me, this is the best option. Just put your dictionary with precomputed decimal indexes in a database, and query it as much as you want;
  • Any Python/R package with BTS: (e.g., data.tree);
  • Implement BTS on your own without external dependencies.

For the second step let's use more precise tuple-hash. It's not so simple, as previous one, but it's input is much smaller:

def word2letterset(word):
    alphabet = list(map(chr, range(ord('a'), ord('z')+1)))
    letterset = {}
    for letter in list(word):
        try:
            letterset[letter] += 1
        except KeyError:
            letterset[letter] = 1
    return tuple(letterset.items())

This step could be fully implemented in pure Python/R with "brute force": compute tuple-hash for an input "word", and compare it with computed hashes for all the words, found on previous step.

$\endgroup$
1
  • $\begingroup$ Downvoted this because the main assertion is false as demonstrated by the implementations. $\endgroup$ Feb 26 '18 at 17:54

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.