I have recently described a move-to-front variant. Here's an improvement that doesn't have dublicated values in its queue:
In normal move-to-front you have a symbol queue where the head is the most recent input symbol and the tail is the oldest.
When an input byte is read, you find it in the queue, move it out and make it the new head. Moving it out creates a gap in the list which you close my moving left and right parts together.
In my variant, the gap is closed by moving the tail into it. This will of course disturb the property of being sorted by local frequency (I do not know how significant the disturbtion is), but here's the scoop: It is possible to execute this move-to-front variant in O(n) time.
Does anybody know if this method exists already and if the resulting output is any good?
Explanation and sample code will follow if it turns out to be unknown