Поліноміальне представлення двійкових дерев ентропійних бінарних кодів

Simple item page
dc.contributor.authorМорозов, Денис
dc.date.accessioned2022-05-27T22:31:00Z
dc.date.available2022-05-27T22:31:00Z
dc.date.issued2021
dc.description.abstractВажливою складовою потокового обміну великими об’ємами інформації є алгоритми стискання інформаційного потоку, які своєю чергою поділяють на алгоритми стискання без втрат (ентропійні) — Шепопа, Хафмана, арифметичне кодування, умовно стискаючі — LZW та інші бієкції інформаційного конусу, алгоритми стискання з втратами, наприклад, mp3, jpeg та низка інших. Під час побудови алгоритму стискання з втратами важливим є дотримуватись певної формальної стратегії. Сформулювати її можна таким чином: після опису множини об’єктів, які є атомарними елементами обміну в інформаційному потоці, необхідно побудувати абстрактну схему цього опису, що дозволить визначити межу для абстрактних зрізів цієї схеми, за якою починаються допустимі втрати. Підходи до виявлення абстрактної схеми, що породжує алгоритми стискання з допустимими втратами, можуть бути отримані з контексту предметної області. Наприклад, алгоритм стискання аудіопотоку може розділяти сигнал на прості гармоніки та залишає серед них ті, що розташовані в певному діапазоні сприйняття. Таким чином, отриманий на виході сигнал є певною абстракцією вхідного, що містить важливу інформацію згідно з контекстом слухового сприйняття аудіопотоку та представлений меншою кількістю інформації. Подібний підхід використовується в форматі mp3, який є стискаючим представленням. На відміну від алгоритмів стискання з втратами, ентропійні алгоритми стискання не вимагають аналізу контексту, а можуть бути побудовані згідно з частотною картиною. Серед відомих алгоритмів побудови таких кодів можна згадати алгоритм Шеннона Фано, алгоритм Хафмана та арифметичне кодування. Знаходження інформаційної ентропії для заданого коду Шеннона є тривіальною задачею. Обернена задача, а саме пошук відповідних кодів Шеннона, що мають наперед задану ентропію та з невизначеними ймовірностями, що є від’ємними цілими степенями двійки, є достатньо складною. Вона може бути вирішена прямим перебором, але суттєвим, недоліком цього підходу є його обчислювана складність. У цій cm am т і запропоновано альтернативний підхід до пошуку таких кодів. Описана техніка поліноміального представлення двійкових дерев бінарних кодів Шеннона з імовірностями, що є від’ємними цілими степенями двійки, дає змогу будувати відповідні коди за відомим значенням інформаційної ентропії.uk_UA
dc.description.abstractAn 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.en_US
dc.identifier.citationМорозов Д. І. Поліноміальне представлення двійкових дерев ентропійних бінарних кодів / Морозов Д. І. // Могилянський математичний журнал. - 2021. - Т. 4. - С. 20-23. - https://doi.org/10.18523/2617-70804202120-23uk_UA
dc.identifier.issn2617-7080
dc.identifier.issn2663-0648
dc.identifier.urihttps://doi.org/10.18523/2617-70804202120-23
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/23005
dc.language.isoukuk_UA
dc.relation.sourceМогилянський математичний журналuk_UA
dc.statusfirst publisheduk_UA
dc.subjectкод Шеннонаuk_UA
dc.subjectінформаційна ентропіяuk_UA
dc.subjectбінарне деревоuk_UA
dc.subjectстаттяuk_UA
dc.subjectShannon codeen_US
dc.subjectinformation entropyen_US
dc.subjectbinary treeen_US
dc.titleПоліноміальне представлення двійкових дерев ентропійних бінарних кодівuk_UA
dc.title.alternativePolynomial representation of binary trees of entropy binary codesen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Morozov_Polinomialne_predstavlennia_dviikovykh_derev_entropiinykh_binarnykh_kodiv.pdf
Size:
114.66 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 4