   Data structure for storing massive amounts of word association data
  Hi,I'm currently playing around with the dissociated press algorithm for generating semi random text. The algorithm is basically as follows:Choose a (long) source text.Let key = Choose a sequence s of n words.Let sentence := the empty listUntil we have enough words, do:  Find a place in the source text where the sequence s appears.  Append the next word in the source text to key  Append the first word of key to sentence  Discard the first word of keyOutput sentenceIn order to do this, I have to keep track of what words might follow every sequence of n words (currently using n = 3 as the max key length) and my current implementation uses a self balancing binary tree (Haskell's Data.Map) to store this information. To store information about what word may follow the words "hey guys," I use a list ["hey", "guys"] as the key into the tree.Since I want to be able to choose a word and generate text both forward and backward from it, to have the word in the middle of a sentence, I'm storing this table twice over, once forward and once reversed.For moderately sized inputs this works great, but as I try to use larger and larger source texts, creating the initial dictionary becomes prohibitively slow (about one minute for both forward and backward trees with ~140k words on my Atom N280 netbook.) Generating text is plenty fast though. After profiling, it turns out that the vast majority of the time is spent simply inserting word associations into the tree. Since the max key length is three, about 420 000 items end up stored in each tree.Since the keys are structured in a nicely hierarchical way, I thought that using a trie to store the associations instead might help, but that ended up being about 50% slower, and a splay tree solution was even worse.Are these results normal for self balancing binary trees with string keys or am I doing something stupid somewhere else? Does anyone have a suggestion for a better way to structure this data? Since I'm using Haskell and want to keep the code pure, a hash table is unfortunately out of the question.   
  The formal term is n-gram.The problem can be non-trivial, so reading up on existing literature would be a good start. Most applications settle for n=2 or n=3. Using sparse tables can help for small n.As far as performance goes, Haskell tends to be a hit or miss. Slowness might be more a consequence of particular a compiler/interpreter than the algorithm itself.A trivial algorithm for off-line table generation is this:- Open input- Read one word X-- Read word Y-- Write to file A words X and Y-- Write to file B words Y and X-- Assign Y to X-- Repeat- Sort files A and B on first word- Build forward and backward tablesWhile this can be done fully in memory, off-line version can be reduced, and isn't limited in size.The process can be extended to n words. Sorting must be performed multiple times - first sort each file completely by first word, then by second, ..., finally by (n-1)th word.Sorting helps since final table can then be built sequentially, since all n-grams are in lexicographic order, so most of lookups will require only a single Map test.   