Move to front alternative

When encoding reference with variable length integers, it's interesting to use small numbers for the most used references. One way to do this is to use the move to front transform.
But when the number of objects is important, it may become costly to maintain a full ordered list of the objects. Here is an algorithm which can be useful for this kind of sparse value set.


T is an array of size n, which will be used to store the nth "most frequent" objects, the index in the array being the reference of the object. This array is split in several range levels: Where f(1)=1 and f(x+1) = f(x) + ceil( f(x)*h ) with h a real in the range ]0 , 1[

When an object of reference r is used two cases can happen:

The idea is that most used objects will gradually move to the lower levels.

Some roughs experiments seems to show that the best results are when:

For objects that are not already in the array, one important point is to chose where to put it in the kth level, so that all objects in the array have the same chance to move off.


Sample program in Python
def mtfa(words, max=1024, delta=.5): toidx = {} fromidx = [] result = [] for w in words: iold = toidx.get(w, None) if iold is None: inew = len(toidx) result.append(inew) toidx[w] = inew if inew=len(fromidx): result.append(iold) pay += iold inew = int(len(fromidx)*delta)+iold%int(len(fromidx)*(1-delta)) permute = fromidx[inew] toidx[w] = inew fromidx[inew]= w toidx[permute] = iold elif iold!=0: result.append(iold) inew = int(iold*delta) permute = fromidx[inew] toidx[w] = inew fromidx[inew]= w toidx[permute] = iold fromidx[iold]=permute return result