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:
- Choose an arbitrary starting point.
- Choose the longest suffix of the current word that is contained in at least 2 other words
- Choose one of those words at random, and append the next character to the current wor.
- 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?