Carleton University
Technical Report TR-53
June 1984
Constrained String Editing
B.J. Oommen
Abstract
Consider a list of elements {R 1 , •, R}N in which the element Ri is accessed with an (unknown) probability Si• If the cost of accessing Ri is proportional to i (as in sequential search) then it is advantageous if each access is accompanied by a simple reordering operation. This operation is chosen so that ultimately the list will be sorted in the descending order of the access probabilities. We present a dynamic list organizing scheme which permits the element Rj to be moved to the front of the list on being accessed. However, as opposed to the schemes discussed in the literature, the move operation is performed with probability Pj• The latter quantity adaptively evolves in such a way that in the limit, no more move operations are performed. When this occurs we say that the scheme has converged. Although the scheme could converge to any one of the N! possible configurations, we shall show that by suitably updating the probabilities {pj} the probability of converging to the right arrangement can be made as close to unity as desired.