Average case analyses of list update algorithms, with applications to data compression

被引：21

作者：

Albers, S

Mitzenmacher, M

机构：

[1] Max Planck Inst Informat, D-66123 Saarbrucken, Germany

[2] Digital Equipment Corp, Syst Res Ctr, Palo Alto, CA 94301 USA

来源：

ALGORITHMICA | 1998年 / 21卷 / 03期

关键词：

on-line algorithms; competitive analysis; list update problem; probability distribution; data compression; entropy;

D O I：

10.1007/PL00009217

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We study the performance of the Timestamp (0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such sources, and determine performance ratios for TS(0) against the optimal off-line and static adversaries in this situation. Previous work on such sources compared on-line algorithms only with static adversaries. One practical motivation for our work is the use of the Move-to-front heuristic in various compression algorithms. Our theoretical results suggest that in many cases using TS(0) in place of Move-to-front in schemes that use the latter should improve compression. Tests using implementations on a standard corpus of test documents demonstrate that TS(0) leads to improved compression.

引用

页码：312 / 318

页数：7

共 19 条

[1]

Albers S., Improved randomized on-line algorithms for the list update problem, Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 412-419, (1995)

[2]

Bachrach R., El-Yaniv R., Online list accessing algorithms and their applications: Recent empirical evidence, Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 53-62, (1997)

[3]

Bentley J.L., McGeoch C.C., Amortized analyses of self-organizing sequential search heuristics, Communications of the ACM, 28, pp. 404-411, (1985)

[4]

Bentley J.L., Sleator D.S., Tarjan R.E., Wei V.K., A locally adaptive data compression scheme, Communications of the ACM, 29, pp. 320-330, (1986)

[5]

Burrows M., Wheeler D.J., A Block-Sorting Lossless Data Compression Algorithm, (1994)

[6]

Chung F.R.K., Hajela D.J., Seymour P.D., Self-organizing sequential search and Hilbert's inequality, Proceedings of the 17th Annual Symposium on the Theory of Computing, pp. 217-223, (1985)

[7]

Elias P., Universal codeword sets and the representation of the integers, IEEE Transactions on Information Theory, 21, pp. 194-203, (1975)

[8]

Gonnet G.H., Munro J.I., Suwanda H., Exegesis of self-organizing linear search, SIAM Journal on Computing, 10, pp. 613-637, (1981)

[9]

Grinberg D., Rajagopalan S., Venkatesan R., Wei V.K., Splay trees for data compression, Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 522-530, (1995)

[10]

Hardy G.H., Littlewood J.E., Polya G., Inequalities, (1994)

← 1 2 →