期刊名称：International Journal of Computer Trends and Technology
电子版ISSN：2231-2803
出版年度：2013
卷号：4
期号：6-2
出版社：Seventh Sense Research Group
摘要：List Accessing Problem is a sound deliberate research problem in the circumstance of linear search. The entire problem of efficiently reorganizing and accessing the elements of the list for obtaining optimal cost is known as list accessing problem. Input to the list accessing problem is an unsorted linear list of distinct elements along with a sequence of requests, where each request is an access operation on an element of the list. The list accessing problem is of significant practical interest in the context of self organizing data structure. Self organizing data structures reorganize their structure while processing a sequence of operations. The purpose of this reorganization is to pledge (guarantee) the competence (efficiency) of prospect operation and improve the performance of this data structure. An algorithm which proficiently reorganizes the list to diminish the access cost is a List Accessing Algorithm. A list accessing algorithm reorganizes the list while processing a request sequence on the list in order to minimize the access cost. List accessing techniques have been comprehensively used in practices when storing and maintaining diminutive dictionaries. One of the significant applications of list accessing problem is data compression. When a sender wants to send a compressed message to a receiver, both the sender and receiver maintains a list containing all the words in the dictionary. Here, initially both lists are in the same order and they both agree upon some list accessing algorithm. When the sender wants to send a word, one sends the current position of the word in the list, which is encoded using some variable length prefix encoding. MovetoFront algorithm has been proved to be the preeminent performing list accessing online algorithm till date in the literature. In this paper, a comprehensive study of list accessing problem and some well known deterministic list accessing algorithms have been studied along with some novel theoretical and analytical results for different permutation of request sequences towards their access cost associated with both MTF and IMTF algorithms.
关键词：List Accessing Problem; List Accessing Cost Models; List Accessing Algorithms; MTF and IMTF Algorithms
