КОМБІНОВАНИЙ АЛГОРИТМ СТИСНЕННЯ ДАНИХ, ПРЕДСТАВЛЕНИХ В ТЕКСТОВОМУ ФОРМАТІ
COMBINED TEXT DATA COMPRESSION ALGORITHM
Сторінки: 131-133. Номер: №6, 2019 (279)
Автори:
М.М. ЛЕБІГА, О.А. ПАСІЧНИК, Т.К. СКРИПНИК, В.Ю. МЕДВЕДЧУК
Хмельницький національний університет
M.M. LEBIGA, O.A. PASICHNYK, T.K. SKRYPNYK, V.Y. MEDVEDCHUK
Khmelnytskyi National University
DOI: https://www.doi.org/10.31891/2307-5732-2019-279-6-131-133
Рецензія/Peer review : 15.12.2019 р.
Надрукована/Printed : 02.01.2020 р.
Анотація мовою оригіналу
В роботі розроблено комбінований алгоритм стиснення текстових даних задля мінімізації об’єму контенту, який є основою відповідної інформаційної технології. В результаті аналізу отриманих експериментальних даних було обрано оптимальні шляхи мінімізації об’єму текстового контенту на основі алгоритму Хаффмана за допомогою основних і найбільш розповсюджених типів структур текстових даних.
Ключові слова: комбінований алгоритм, алгоритм Хаффмана, мінімізація, оптимізація, граф, дерево, текстові дані, словник.
Розширена анотація англійською мовою
The purpose of the work is to develop a combined algorithm for text data compression. To achieve this goal, the following research objectives have been identified: reviewing existing universal data compression algorithms; analysis of data types and text formats; development of a specialized compression algorithm based on the Huffman algorithm, taking into account the data structure. The two main and most common types of text data structure are graph and tree. To achieve the greatest compression of texts in natural languages, it is decided to use a tree-like structure of the dictionary with a fixed number of branches at each level, as the size of branching decreases with increasing depth, which with a fixed size of branches will lead to a strong redundancy and high memory consumption. To achieve the highest compression of html and xml texts, it is decided to use a dictionary based on a weighted graph with an unspecified number of branches on the node. The graph provides a flexible system by which any structure can be emulated, but constructing such a structure is challenging. An analysis of the amount of savings by optimization is calculated based on the difference between the savings of recording branch information and the number of bits that need to be recorded to inform the decoder of branch usage. If the difference is greater than zero, the information is considered to be advantageous for recording. To record tree-based dictionary optimization information, you must specify all the dictionary branches used. This can be done using a recursive algorithm. The result of the work is the development of a combined algorithm for compressing text data whose structure can be represented as a tree or graph. The developed compression algorithm is based on the Huffman algorithm and is the basis for implementation of the relevant information system.
Keywords: combined algorithm, Huffman algorithm, minimization, optimization, graph, tree, text data, dictionary.
References
- Lempel A., Ziv J. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory. 1978. Т. 24, № 5. Р. 530–536.
- Ziv J. A constrained-dictionary version of LZ78 asymptotically achieves the finite-state compressibility with a distortion measure. IEEE Information Theory Workshop. 2015. Р. 1–4.
- Welch T. A. A technique for high-performance data compression. Computer. 1984. Т. 6, № 17. Р. 8–19.
- Storer J. A. Data Compression: Methods and Theory. New York, USA: Computer Science Press, 1988. 413 р.
- Hucke D., Lohrey M., Reh C. P. The smallest grammar problem revisited. String Processing and Information Retrieval (SPIRE). 2016. Т. 9954. Р. 35–49.
- Graph [Electronic resource]. – Access mode: https://uk.wikipedia.org/wiki/Graph_(mathematics).
- Tree [Electronic resource]. – Access mode: https://uk.wikipedia.org/wiki/Tree_(graph theory).
- Optimization [Electronic resource]. – Access mode: https://uk.wikipedia.org/wiki/ Optimization_(Computer Science).
- Decoder [Electronic resource]. – Access mode: https://uk.wikipedia.org/wiki/ Decoder.
- Recursive algorithm [Electronic resource]. – Access mode: https://uk.wikipedia.org/wiki/ http://mmsa.kpi.ua/sancho/ASD_HTM/Recurs01.html.
