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 lives at https://github.com/mtbarta/Markov_Chain/blob/master/Markov.cs)

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?

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?