Универсальные алгоритмы сжатия данных:

Кодирование целых чисел

>> Русские материалы | Английские материалы | Исходные тексты компрессоров

>> Русские материалы | Английские материалы | Исходные тексты компрессоров
Авторы Название Описание Рейтинг
Левенштейн В.И. Об избыточности и замедлении разделимого кодирования натуральных чисел Оригинальное описание кодов, получивших наименование кодов Левенштейна. Коды Левенштейна имеют асимптотически минимальную избыточность среди префиксных кодов с неубывающей функцией длин кодовых слов и полезны в том случае, когда число кодируемых объектов заранее неизвестно.
Англоязычное название: "On the redundancy and delay of separable codes for the natural numbers"
Проблемы кибернетики, N20, 1968, С.173-179.
PDF  307 кбайт
4


>> Русские материалы | Английские материалы | Исходные тексты компрессоров
Fenwick P. Punctured Elias Codes for variable-length coding of the integers Рассматривается целый спектр кодов: Левенштейна, Элиаса, Ивэна-Роде, Голомба, Райса, "старт-шаг-стоп", тернарные коды. Предлагается модификация гамма-кода Элиаса.
Technical Report 137, ISSN 1173-3500, Department of Computer Science, The University of Auckland, December 5, 1996.
PDF.RAR  107 кбайт
5
Golomb S.W. Run-length encodings Коды Голомба предназначены для кодирования бинарных событий, сильно асимметричных по вероятности. Идея заключается в кодировании длины серии высоковероятных событий, разделяющей два маловероятных события. По-видимому, в этой статье впервые введен в обращение термин "run-length encoding". Коды Голомба оптимальны для кодирования неотрицательных чисел с геометрическим распределением.
IEEE Transactions on Information Theory, vol. 12, pp.399-401, July 1966.
PDF  172 кбайт
5
Williams H., Zobel J. Compressing Integers for Fast File Access ...In this paper we show experimentally that, for large or small collections, storing integers in a compressed format reduces the time required for either sequential stream access or random access. We compare different approaches to compressing integers, including the Elias gamma and delta codes, Golomb coding, and a variable-byte integer scheme...
The Computer Journal, Vol.42, No.3, pp.193-201, 1999.
PDF.RAR  132 кбайт
?
Yamamoto H., Ochi H. A New Asymptotically Optimal Code for the Positive Integers A new universal binary code for the positive integers is proposed as a modified version of Wang's flag encoding scheme... The performance of the new scheme is also compared with other universal schemes...
IEEE Transactions on Information Theory, Vol. 37, No. 5, pp.1420-1429, Sep. 1991.
PDF.RAR  662 кбайт
?
Yamamoto H. A New Recursive Universal Code of the Positive Integers A new recursive universal code of the positive integers is proposed, in which any given sequence can be used as a delimiter of codeword while bit “0” is used as a delimiter in known universal codes, e.g., Levenshtein code, Elias code, Even–Rodeh code, Stout code, Bentley–Yao code, etc. The codeword length of the proposed code is shorter than log*_2 n in almost all of sufficiently large positive integers although the known codes are longer than log*_2 n for any positive integer n.
IEEE Transactions on Information Theory, Vol. 46, No. 2, pp.717-723, Mar. 2000.
PDF.RAR  127 кбайт
?
Pigeon S. Start/Stop Codes Start/Stop codes represent a class of codes for the integers not unlike the (start, step, stop) codes, to the difference that actual information on the distribution is used to construct the prefixes and that it never does worse than the natural coding of the integers in a given range. By their structure, Start/Stop codes can be encoded and decoded in a very efficient way...
Universite de Montreal, 2000.
PDF.RAR  119 кбайт
PS.RAR    65 кбайт
?
Seroussi G., Weinberger M. On Adaptive Strategies for an Extended Family of Golomb-type Codes Off-centered, two-sided geometric distributions of the integers are often encountered in lossless image compression applications, as probabilistic models for prediction residuals. Based on a recent characterization of the family of optimal prefix codes for these distributions, which is an extension of the Golomb codes, we investigate adaptive strategies for their symbol-by-symbol prefix coding, as opposed to arithmetic coding...
Designs, Codes and Cryptography, pp. 131-140, 1997.
PDF.RAR  614 кбайт
PS.RAR  296 кбайт
?


>> Русские материалы | Английские материалы | Исходные тексты компрессоров >> C/C++ | Pascal/Delphi

наверх