Эффективные методы кодирования низкоэнтропийных источников

Актуальность темы

.

Задача эффективного кодирования источников является одной из центральных в теории информации, что объясняется ее теоретической важностью и многочисленными практическими приложениями к сжатию данных самой различной природы. Изучению этой задачи посвящены многочисленные работы В. Ф. Бабкина, Р. Е. Кричевского, Б. Я. Рябко, В. К. Трофимова, Ю. М. Штарь-кова, Р. Галлагера, Я. Зива, А. Лемпела, И. Риссанена, П. Элай-еса и других исследователей.

Задача кодирования обычно ставится следующим образом. Источник информации порождает сообщение X — х. .XI, вероятности появления отдельных символов которого могут быть известны или неизвестны. Необходимо поставить в соответствие каждому сообщению X кодовое слово С (Х) = ссч. сцх) так? чтобы по С (Х) можно было однозначно восстановить (декодировать) X и средняя длина Ь (Х) кодового слова по множеству всех сообщений была минимальной. Известно [32], что Ь (Х) ограничена снизу шенноновской энтропией источника. Разность между средней длиной кодового слова и энтропией называется избыточностью кода. Кроме избыточности, эффективность кода оценивается объемом памяти V кодера и декодера (в битах), который требуется при реализации метода на компьютере со свободным доступом к памяти (это модель «обычного» компьютера [1]), и средним временем Т кодирования и декодирования одного символа источника информации, измеряемым числом бинарных операций над однобитовыми словами.

Рассматриваются задачи кодирования источников с известной з и неизвестной статистикой. Методы, предназначенные для кодирования источников с известной статистической структурой, называют статическими (неадаптивными) методами. Адаптивные методы кодирования позволяют эффективно сжимать данные с заранее неизвестной статистикой. В настоящее время известно большое число адаптивных кодов. К ним относятся такие известные коды как арифметический [22, 35, 37], код «стопка книг» [12], адаптивный код Хаффмана [27, 31], частотный код [13], коды Зива-Лемпела [43, 44] и «быстрый» код [14, 40].

Во многих практических приложениях часто возникает задача кодирования источников с малой энтропией. Начиная с работы К. Шеннона [19], предложившего первый специальный код для таких источников, эта задача представляла и представляет интерес для исследователей, так как известно, что для низкоэнтропийных источников существуют значительно более простые методы кодирования, чем для произвольных источников. Для источников с малой энтропией «общие» методы кодирования (то есть методы, предназначенные для кодирования любых источников, а не только низкоэнтропийных) оказываются неэффективными. Различные методы кодирования низкоэнтропийных источников разрабатывались и изучались в работах П. Элайеса [25, 26], Э. Л. Блоха [3], С. Голомба [29], Р. Галлагера и Д. Вурхиса [28], В. Ф. Бабкина и Ю. М. Штарькова [20], X. Танака и А. Леон-Гарсиа [41] и других исследователей.

Однако известные методы кодирования низкоэнтропийных источников не позволяют строить коды с наперед заданной избыточностью. Поэтому важной является задача построения методов, позволяющих достигать сколь угодно малой, наперед заданной избыточности и сложность которых, измеряемая объемом памяти кодера и декодера и средним временем кодирования и декодирования, существенно меньше, чем у «общих» методов.

Целью данной диссертационной работы является:

1. Разработка эффективных методов кодирования низкоэнтропийных источников информации с известной статистикой, которые позволяют строить коды с любой наперед заданной избыточностью и сложность которых, как функция от избыточности, существенно меньше, чем у «общих» методов.

2. Построение адаптивных методов кодирования низкоэнтропийных источников, обеспечивающих достижение наперед заданной избыточности и обладающих более низкой сложностью, чем ранее известные методы.

Методы исследования. В работе были использованы основные положения теории кодирования дискретных источников, теории вероятностей и теории сложности алгоритмов.

Научная новизна результатов работы. В диссертации получены следующие новые результаты:

1. Предложен метод кодирования низкоэнтропийных бернулли-евских источников с известной статистикой, позволяющий строить коды с любой наперед заданной избыточностью г > 0. Для предложенного метода при г —> 0 память кодера и декодера равна по порядку памяти «общих» методов, а его скорость кодирования и декодирования существенно выше.

2. На основе предложенной конструкции кода построены адаптивные методы кодирования низкоэнтропийных бернуллиевских источников и оценена сложность построенных методов.

3. Предложены алгоритмы кодирования низкоэнтропийных марковских источников для случаев известной и неизвестной статистики, позволяющие строить коды с любой наперед заданной избыточностью и обладающие при той же (по порядку) памяти кодера и декодера, что и у «общих» методов, более высокой скоростью кодирования и декодирования.

Практическая ценность. Работа носит теоретический характер, предложенные в ней эффективные алгоритмы кодирования низкоэнтропийных источников могут быть использованы для сжатия данных в системах связи и при передаче и хранении информации в компьютерных сетях.

Апробация работы и публикации.

Основные результаты диссертации опубликованы в работах [45−53] и докладывались на международных конференциях по теории информации ISIT-98 (Cambridge, USA, 1998) и по исследованию операций (Новосибирск, 1998), на международном семинаре по теории информации и статистике IEEE-IMS (Alexandria, USA, 1994), на международном семинаре «Распределенная обработка информации» (Новосибирск, 1998), на первом международном симпозиуме по науке и технологии (University of Ulsan, Korea, 1997), а также на семинарах института математики им. С. JI. Соболева СО РАН и Сибирского государственного университета телекоммуникаций и информатики.

Структура работы.

Диссертация состоит из введения, трех глав, заключения и.

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Бабкин В. Ф., Книжный И. М. Об адаптивном коде Голомба для длин серий // Труды X симпоз. по проблеме избыточности в информационных системах. Тез. докл. Ленинград, 1989. Ч. 2. С. 23−26.

3. Блох Э. Л. О передаче неравномерной бинарной последовательности равномерным кодом // Электросвязь. 1959. № 1. С. 76−77.

4. Боровков А. А. Теория вероятностей. М.: Наука, 1986.

5. Галлагер Р. Теория информации и надежная связь. М.: Наука, 1969.

6. Гильберт Э. Н., Мур Э. Ф. Двоичные кодовые системы переменной длины // Кибернетический сборник. М.: Изд-во иностр. лит-ры, 1961. Вып. 3. С. 103−141.

7. Кнут Д. Е. Искусство программирования для ЭВМ. Т. 2: Получисленные алгоритмы. М.: Мир, 1977.

8. Левенштейн В. И. Об избыточности и замедлении разделимого кодирования натуральных чисел // Проблемы кибернетики. М.: Наука, 1968. Вып. 20. С. 173−179.

9. Мешковский К. А., Кириллов Н. Е. Кодирование в технике связи. М.: Связь, 1966.

10. Новик Д. А. Эффективное кодирование. М.: Энергия, 1965.

11. Романовский В. И. Дискретные цепи Маркова. М.-Л.: Изд-во технико-теоретич. литературы, 1949.

12. Рябко Б. Я. Сжатие данных с помощью стопки книг // Пробл. передачи информации. 1980. Т. 16, № 4. С. 16−21.

13. Рябко Б. Я. Быстрый алгоритм адаптивного кодирования // Пробл. передачи информации. 1990. Т. 26, № 4. С. 24−37.

14. Рябко Б. Я. Эффективный метод кодирования источников информации, использующий алгоритм быстрого умножения // Пробл. передачи информации. 1995. Т. 31, № 1. С. 3−12.

15. Рябко Б. Я. Сжатие данных с помощью «мнимого скользящего окна» // Пробл. передачи информации. 1996. Т. 32, № 2. С. 22−30.

16. Феллер В.

Введение

в теорию вероятностей и ее приложения. М.: Мир, 1963.

17. Ryabko В. Ya., Fionov А. N. Homophonic coding with logarithmic memory size // Algorithms and Computation. Berlin: Springer, 1997. P. 253−262 (Lecture Notes in Comput. Sci., V. 1350).

18. Хаффман Д. А. Метод построения кодов с минимальной избыточностью // Кибернетический сборник. М., 1961. Вып. 3. С. 79−87.

19. Шеннон К. Работы по теории информации и кибернетике. М.: Изд-во иностр. литературы, 1963.

20. Штарьков Ю. М., Бабкин В. Ф. Кодирование длин серий в условиях априорной неизвестности // Аппаратура для космических исследований. М.: Наука, 1973. С. 3−9.

21. Ahlswede R., Han Н. S., Kobayashi К. Universal Coding of Integers and unbounded Search Trees // IEEE Trans. Inform. Theory. 1997. V. 43, N 3. P. 669−683.

22. Bell T. C., Cleary J. H., Witten I. H. Text compression. Englewood Cliffs, NJ: Prentice-Hall, 1990.

23. Bently J. L., Sleator D. D., Tarjan R. E., Wei V. K. A Locally Adaptive Data Compression Sheme // Communication ACM. 1986. V. 29, N 4. P. 320−330.

24. Cleary J. G., Witten I. H. Data compression using adaptive coding and partial string matching // IEEE Trans. Commun. 1984. V. COM-32, N 4. P. 396−402.

25. Elias P. Predictive Coding // IRE Trans. Inform. Theory. 1955. V. IT-1, N 1. P. 16−33.

26. Elias P. Universal Codeword Sets and Representation of the Integers // IEEE Trans. Inform. Theory. 1975. V. 21, N 2. P. 195−203.

27. Gallager R. G. Variations on Theme by Huffman // IEEE Trans. Inform. Theory. 1987. V. 24. P. 668−674.

28. Gallager R. G., Van Voorhis D. C. Optimal Source Codes for Geometrically Distributed Integer Alphabets // IEEE Trans. Inform. Theory. 1975. V. IT-21, N 2. P. 228−230.

29. Golomb S. W. Run Length Encoding // IEEE Trans. Inform. Theory. 1966. V. IT-12, N 4. P. 399−401.

30. Jelinek F. Probabilistic Information Theory. New York: McGraw-Hill, 1968. P. 476−489.

31. Knuth D. E. Dynamic Huffman Coding // J. Algorithms. 1985. V. 6. P. 163−180.

32. Krichevsky R. E. Universal Compression and Retrieval. Kluver Academic Publishers, 1995.

33. Moffat A. M. A note on the PPM data compression algorithm. Res. Rep. 88/7, Dep. Comput. Science. Univ. of Melbourne. Australia, 1988.

34. Pasco R. Source coding algorithm for fast data compression. Ph. D. thesis, Dept. Elect. Eng. Stanford Univ. Stanford, CA, 1976.

35. Rissanen J. J. Arithmetic Coding as Number Representations // Acta Polytecnica. 1979. V. 31. P. 44−51.

36. Rissanen J.J. Genaralized Kraft inequality and arithmetic coding // IBM J. Res. Dev. 1976. V. 20. P. 198−203.

37. Rissanen J., Langdon G. G. Universal Modeling and Coding // IEEE Trans. Inform. Theory. 1981. V. 27, N 1. P. 12−23.

38. Rissanen J., Langdon G. G. Arithmetic coding // IBM J. Res. Dev. 1979. V. 23, N 2. P. 149−162.

39. Rubin F. Arithmetic stream coding using fixed precision registers // IEEE Trans. Inform. Theory. 1979. V. IT-25, N 6. P. 672−675.

40. Ryabko B. Ya. Fast and effective coding of information sources // IEEE Trans. Inform. Theory. 1994. V. 40, N 1. P. 96−99.

41. Tanaka H., Leon-Garsia A. Efficient run-length encodings // IEEE Trans. Inform. Theory. 1982. V. IT-28, N 6. P. 880−890.

42. Wit ten I. H., Neal R., Cleary J. G. Arithmetic coding for data compression // Comm. ACM. 1987. V. 30, N 6. P. 520−540.

43. Ziv J., Lempel A. Compression of Individual Sequences via Variable-Length Coding // IEEE Trans. Inform. Theory. 1978. V. 24. P. 530−536.

44. Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression // IEEE Trans. Inform. Theory. 1977. V. 33, N 3. P. 337−343.СПИСОК РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ.

45. Рябко Б. Л., Шарова М. П. Быстрое кодирование низкоэнтропийных источников //Пробл. передачи информации. 1999. Т. 35, № 1. С. 49−60.

46. Шарова М. П. Быстрое кодирование марковских источников с малой энтропией // Дискретный анализ и исследование операций. 1998. Серия 1. Т. 5, № 4. С. 81−96.

47. Sharova М. P. Coding Low-Entropy Markov Sources with Unknown Statistics // Siberian Adv. Math. 1999. V. 9, JV° 2. P. 72 -82.

48. Шарова M. П. Влияние объема словаря на степень сжатия текста // Дискретный анализ и исследование операций. 1999. Серия 1. Т. 6, № 1. С. 86−96 .

49. Шарова М. П. Алгоритм быстрого кодирования низкоэнтропийных источников // Труды 6-го международного семинара «Распределенная обработка информации». Новосибирск, 1998. С. 421−424.

50. Ryabko В. Ya., Sharova М. P. Fast coding of low-entropy sources // Proceeding of 1998 IEEE Intern. Symposium on Information Theory. MIT, Cambridge. 1998. P. 44.

51. Sharova M. P. Efficient algorithm of low-entropy source coding // Международная Сибирская конф. по исслед. операций. Материалы конференции. Новосибирск, 1998. С. 156.

52. Krichevsky R. Е., Sharova М. P. Shannon-Hartley entropy ratio under Zipf law // Proceeding of the 1994 IEEE-IMS Workshop on Information Theory and Statistics. Virginia, Alexandria. 1994. P. 66.

53. Sharova M. P. Influence of a text dictionary size on the compression ratio // The First Korea-Russia Intern. Symposium on Science and Technology. Ulsan, Korea. 1997. P. 165.