Поліноміальне представлення двійкових дерев ентропійних бінарних кодів
Loading...
Date
2021
Authors
Морозов, Денис
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Важливою складовою потокового обміну великими об’ємами інформації є алгоритми стискання інформаційного потоку, які своєю чергою поділяють на алгоритми стискання без втрат (ентропійні) — Шепопа, Хафмана, арифметичне кодування, умовно стискаючі — LZW та інші бієкції інформаційного конусу, алгоритми стискання з втратами, наприклад, mp3, jpeg та низка інших. Під час побудови алгоритму стискання з втратами важливим є дотримуватись певної формальної стратегії. Сформулювати її можна таким чином: після опису множини об’єктів, які є атомарними елементами обміну в інформаційному потоці, необхідно побудувати абстрактну схему цього опису, що дозволить визначити межу для абстрактних зрізів цієї схеми, за якою починаються допустимі втрати.
Підходи до виявлення абстрактної схеми, що породжує алгоритми стискання з допустимими втратами, можуть бути отримані з контексту предметної області. Наприклад, алгоритм стискання аудіопотоку може розділяти сигнал на прості гармоніки та залишає серед них ті, що розташовані в певному діапазоні сприйняття. Таким чином, отриманий на виході сигнал є певною абстракцією вхідного, що містить важливу інформацію згідно з контекстом слухового сприйняття аудіопотоку та представлений меншою кількістю інформації. Подібний підхід використовується в форматі mp3, який є стискаючим представленням. На відміну від алгоритмів стискання з втратами, ентропійні алгоритми стискання не вимагають аналізу контексту, а можуть бути побудовані згідно з частотною картиною. Серед відомих алгоритмів побудови таких кодів можна згадати алгоритм Шеннона Фано, алгоритм Хафмана та арифметичне кодування. Знаходження інформаційної ентропії для заданого коду Шеннона є тривіальною задачею. Обернена задача, а саме пошук відповідних кодів Шеннона, що мають наперед задану ентропію та з невизначеними ймовірностями, що є від’ємними цілими степенями двійки, є достатньо складною. Вона може бути вирішена прямим перебором, але суттєвим, недоліком цього підходу є його обчислювана складність. У цій cm am т і запропоновано альтернативний підхід до пошуку таких кодів. Описана техніка поліноміального представлення двійкових дерев бінарних кодів Шеннона з імовірностями, що є від’ємними цілими степенями двійки, дає змогу будувати відповідні коди за відомим значенням інформаційної ентропії.
An important component of streaming large amounts of information are algorithms for compressing information flow. Which in turn are divided into lossless compression algorithms (entropic) - Shannon, Huffman, arithmetic coding, conditional compression - LZW, and other information cone injections and lossy compression algorithms - such as mp3, jpeg and others. It is important to follow a formal strategy when building a lossy compression algorithm. It can be formulated as follows. After describing the set of objects that are atomic elements of exchange in the information flow, it is necessary to build an abstract scheme of this description, which will determine the boundary for abstract sections of this scheme, which begins the allowable losses. Approaches to the detection of an abstract scheme that generates compression algorithms with allowable losses can be obtained from the context of the subject area. For example, an audio stream compression algorithm can divide a signal into simple harmonics and leave among them those that are within a certain range of perception. Thus, the output signal is a certain abstraction of the input, which contains important information in accordance with the context of auditory perception of the audio stream and is represented by less information. A similar approach is used in the mp3 format, which is a compressed representation. Unlike lossy compression algorithms, entropic compression algorithms do not require context analysis, but can be built according to the frequency picture. Among the known algorithms for constructing such codes are the Shannon-Fano algorithm, the Huffman algorithm and arithmetic coding. Finding the information entropy for a given Shannon code is a trivial task. The inverse problem, namely finding the appropriate Shannon codes that have a predetermined entropy and with probabilities that are negative integer powers of two, is quite complex. It can be solved by direct search, but a significant disadvantage of this approach is its computational complexity. This article offers an alternative technique for finding such codes.
An important component of streaming large amounts of information are algorithms for compressing information flow. Which in turn are divided into lossless compression algorithms (entropic) - Shannon, Huffman, arithmetic coding, conditional compression - LZW, and other information cone injections and lossy compression algorithms - such as mp3, jpeg and others. It is important to follow a formal strategy when building a lossy compression algorithm. It can be formulated as follows. After describing the set of objects that are atomic elements of exchange in the information flow, it is necessary to build an abstract scheme of this description, which will determine the boundary for abstract sections of this scheme, which begins the allowable losses. Approaches to the detection of an abstract scheme that generates compression algorithms with allowable losses can be obtained from the context of the subject area. For example, an audio stream compression algorithm can divide a signal into simple harmonics and leave among them those that are within a certain range of perception. Thus, the output signal is a certain abstraction of the input, which contains important information in accordance with the context of auditory perception of the audio stream and is represented by less information. A similar approach is used in the mp3 format, which is a compressed representation. Unlike lossy compression algorithms, entropic compression algorithms do not require context analysis, but can be built according to the frequency picture. Among the known algorithms for constructing such codes are the Shannon-Fano algorithm, the Huffman algorithm and arithmetic coding. Finding the information entropy for a given Shannon code is a trivial task. The inverse problem, namely finding the appropriate Shannon codes that have a predetermined entropy and with probabilities that are negative integer powers of two, is quite complex. It can be solved by direct search, but a significant disadvantage of this approach is its computational complexity. This article offers an alternative technique for finding such codes.
Description
Keywords
код Шеннона, інформаційна ентропія, бінарне дерево, стаття, Shannon code, information entropy, binary tree
Citation
Морозов Д. І. Поліноміальне представлення двійкових дерев ентропійних бінарних кодів / Морозов Д. І. // Могилянський математичний журнал. - 2021. - Т. 4. - С. 20-23. - https://doi.org/10.18523/2617-70804202120-23