Optimizing variable order Markov Chain Implementation

Question

I've created a variable order Markov chain built on top of a tree, but I can't train on datasets >1MB worth of text without running out of memory. I'm sure the tree can be replaced by something else more efficient, but I'm struggling with figuring that out. I've heard a linked list might work, but I'm not sure how.

Below is the AddString method for variable order chains (of characters).

public void AddString(string s)
{
    // Construct the string that will be added.
    StringBuilder sb = new StringBuilder(s.Length + 2 * (MarkovOrder));

    sb.Append(StartChar, MarkovOrder);
    sb.Append(s);
    sb.Append(StopChar, MarkovOrder);

    for (int i = 0; i < sb.Length; ++i)
    {
        // Get the order 0 node
        Node parent = root.AddChild(sb[i]);

        //add N-grams
        for (int j = 1; j <= MarkovOrder && j + i < sb.Length; j++)
        {
            Node child = parent.AddChild(sb[j + i]);
            parent = child;
        }
    }
}

(code base found here)

This code bloats my memory with every order up to the defined order, and I'm not sure how I'd alter it to only store one order without it completely breaking down. I'd like to do something like

markov = new markovChain(order = 3);.

I've been playing around with algorithms that can store a chain of order (i.e.) 4 without going through the other orders. These implementations aren't performing as well, and I keep resorting to several lists that make node creation complex for me. (https://gist.github.com/mtbarta/8127895)

I'm not sure what structure to use so that I can generate a chain at a given order without bloating memory use. Can I implement a linked list that stores a list of following nodes? Does that ruin the point of a linked list while bloating my memory anyway?

Answer 1

I'm sure the tree can be replaced by something else more efficient, but I'm struggling with figuring that out. I've heard a linked list might work, but I'm not sure how.

Perhaps use the SortedList class instead of the Dictionary class.

For example, this blog entry says,

Best memory footprint we see in the SortedList, followed by Hashtable, SortedDictionary and the Dictionary has highest memory usage. Despite all that, we have to note, that the differences are not significant and unless your solution requires extreme sensitivity about the memory usage you should consider the other two parameters: time taken for the insert operations and time taken for searching a key as more important.

Other optimizations might include:

• Don't allocate Node.Children until/unless the AddChild method is called.
• Use the Dictionary constructor which lets you specify the initial capacity (and specify a very low initial capacity)
• Add a KeyValuePair<char,Node> OnlyChild member to Node, and use it (instead of creating Dictionary) when the first child is added (delete it and create a dictionary when the second child is added) to optimize the case where a Node has only exactly one child

Beware that the above are 'micro-optimizations' which don't change the algorithm; changing the algorithm (I don't understand Artur Mustafin's comment) might result in bigger savings.