Context Modeling

Just as a word in a sentence occurs in a context, a character in a string can be considered to occur in a context. For example, in the string `` object'' the character `` t'' is said to occur within the context `` objec''. However, we can also say that `` t'' occurs within the context `` c'', `` ec'', `` jec'', and `` bjec''. The length of a context is termed its order. In the example string, `` jec'' would be considered a third order context for `` t''. In text compression these contexts are used to model which characters are likely to be seen next. For example, given that we have seen the context `` object'' it may be likely that the next character be a space, or possibly an `` i'', but it is unlikely that the next character is an `` h''. On the other hand, if we only consider the first order context, `` t'', then `` h'' is not so unlikely. Techniques that track multiple contexts of varying orders are termed Multi-Order Context Models [2]. To prevent the model from quickly growing beyond available resources, most implementations of a multi order context model limit the highest order tracked to some finite number (m), hence the term Finite Multi-Order Context Model.

At every point in the string, the next character can be modeled by the last seen contexts (a set of order 0 through m). For example, take the input string `` objec'' and limit our model to a third order (m=3). The next character can now be described by four contexts { ø, `` c,'' `` ec,'' `` jec'' }. This set of contexts can be thought of as the current state of whatever we are modeling, be it a character input stream or a sequence of file system events. With each new event, the set of new contexts is generated by appending the newly seen event to the end of the contexts that previously modeled our state. If the above set was our current state at time t, and at time t+1 we see the character `` t'', our new state is described by the set { ø, `` t,'' `` ct,'' `` ect'' }. The nature of a context model, where one set of contexts is built from the previous set, makes it well suited for a trie [9], where the children of each node indicate the events that have followed the sequence represented by that node. A resulting property of this trie is that the frequency count for each current context is equal to the sum of its children's counts plus one. It is from this property that we derive our probability estimate in §2.3