ADVANCED LOSSLESS TEXT COMPRESSION ALGORITHM BASED ON SPLAY TREE ADAPTIVE METHODS

Splay Trees are usually considered forms of lexicographically ordered binary search trees [1, 2]. The motivation of this paper comes from the fact that the search trees have multiples drawbacks. These data structures are created to reduce the worst-case time per operation. However, in typical applications of search trees [3] are performed several operations, not a single one, and what matters is the total time necessary for the operations, not the individual times of each of them. In such applications, a better goal is to reduce the amortized time of operations, where amortized time means the average time of an operation in a worst-case sequence of operations [4]. One way to obtain amortized efficiency is to use a self-adjusting data structure. The structure can be in an arbitrary state but, during each operation, a simple restructuring rule is applied to improve the efficiency of the following operations. Self-adjusting data structures have several potential advantages over other balanced structures or with other constraints: • in an amortized case, when the constant factors are ignored, they are never much worse than constrained structures and since they adjust according to use, they can be more efficient if the pattern used is skewed; • requires less space, since no balance or constraint information is stored; • access and update algorithms are easy to implement with a simple concept. Self-adjusting structures also have some drawbacks: • they require more local adjustments, especially during accesses; • individual operations within a sequence can be expensive, which may be a disadvantage especially in real-time applications.