fast n-gram access data structure

Question

TL;DR

Is there a data structure that'd quickly let me match words at any point (e.g., 'foo' matches 'foobar' and 'zoofoo'), and, ideally, returns a list of "characters that show up after the needle" (e.g., 'foo' should return ['b', $]).

---

I'm implementing an algorithm that generates random words from a training set of other words.

In simple terms, it's basically like this:

1. Choose an arbitrary starting point.
2. Choose the longest suffix of the current word that is contained in at least 2 other words
3. Choose one of those words at random, and append the next character to the current wor.
4. GOTO 2 until "next character" is EOW

e.g., if the current word is 'tat', some valid options would be 'potato' and 'tattoo'; if the current word is "ophtalmi", the only option is "ophtalmic", so we search if any words contain "phtalmi", "htalmi", "talmi", and so on.

I've tried a couple of implementations: in one, I've used a trie populated with every suffix of every word. This is very fast at generating words, but populating the trie is VERY slow (~4 million words have not finished in over 10 hours).

In another, I've generated a hash of:

for word in words:
    for suffix in tails(words):
        for prefix, suffix in prefixes(words): # prefixes("foo") = [("f","oo"),("fo","o"),("foo","")]
            ngrams[prefix].add(suffix) # this is a set

and it's much faster at reading the training set, and very fast at generating, but it takes a lot of RAM.

And, finally, the dumb option, of simply searching

candidates = [word for word in words if string in words]

which takes very little memory, but is much slower.

Is there a data structure with the behaviour I need?

Answer 1

The classic answer would be a trie which stores all rotations of words (in scrabble there is a very similar need and a very similar datastructure called a gaddag). It turns out you can do much better (B-tree of words where the lowest level is delta encoded), but the simplest thing you can do is store a sorted list of all rotations of all words in your dictionary and binary search for things. Example:

Our dictionary contains the word w = 'zoofoo', so we store:

sorted(w[i:] + '^' + w[:i] for i in range(len(w)))
['foo^zoo', 'o^zoofo', 'ofoo^zo', 'oo^zoof', 'oofoo^z', 'zoofoo^']

Hey look, one of those entries starts with 'foo'! We can find it via binary search, and reconstruct the original word from 'foo^zoo' by flipping around the ^.

If you can sort your input as well you can do a linear intersection of the input list and the rotation dictionary.

Answer 2

I'm thinking some variation of a trie.

A common application of a trie is storing a predictive text or autocomplete dictionary, such as found on a mobile telephone. Such applications take advantage of a trie's ability to quickly search for, insert, and delete entries.

Answer 3

You might want to look into Lucene (through Elasticsearch or Solr) or another search-based solution for your problem. Lucene uses an inverted index data structure for efficiently doing lookups on strings. It was at one point exactly a trie, but I'm not entirely sure that the current implementaton can be still considered a trie as its been worked on and optimized so much.

One nice thing about a search engine like Lucene is its built in text analysis features. These analyzers can be chained together to control what strings are placed in the index and also what strings are used to query that index.

Lucene has built in ngram analysis, but you can also easily write your own that takes input text and chops them up in a custom way to satisfy your search requirements.

For a pure Python search solution, you can also check out Whoosh.

Answer 4

Either ternary search trees or marisa-tries seem data structures that perform well for common prefix search, which is what you are trying to do.

Since you seem to be using Python, here you have a package for the fomer, while the latter seems to have two Python bindings: the official one based on SWIG, but also an unofficial one based on Cython.