Методи пошуку та кодування схожих послідовностей даних в алгоритмах стиснення даних без втрат
DOI:
https://doi.org/10.30837/bi.2021.1(96).07Ключові слова:
СТИСНЕННЯ ДАНИХ БЕЗ ВТРАТ, СХОЖІ ПОСЛІДОВНОСТІ ДАНИХ, ІНДЕКСНІ МЕТОДИ, N-ГРАМИ, ВІДСТАНЬ ЛЕВЕНШТЕЙНА, ВІДСТАНЬ ГЕММІНГА, КОДУВАННЯ ВІДМІННОСТЕЙАнотація
Розглянуто методи пошуку та кодування схожих послідовностей даних, та їх використання для покращення алгоритмів стиснення даних без втрат. Досліджено сучасні підходи до пошуку послідовностей з неточним збігом – тривіальні та евристичні методи, індексні методи та методи, що базуються на N-грамах. Розглянуто підходи кодування відмінностей з використанням відстані Левенштейна та Геммінга. Запропонована розширена структура алгоритму стиснення даних. Комбінації вищезазначених методів у складі запропонованої структури було протестовано на двох датасетах – датасеті англійського тексту «enwik8» та комбінованому датасеті «Silesia Corpus». При тестування оцінювались ступінь стиснення, швидкість кодування та декодування, та загальний баланс. У результаті було розроблено нову структуру алгоритмів стиснення даних та виявлено найбільш ефек- тивні комбінації методів для компресії різних типів даних.
Посилання
Jacob Ziv, Abraham Lempel. (1977) A Universal Algorithm for Sequential Data Compression IEEE Transactions on Information Theory, pp. 337—343.
Van Leeuwen, Jan (1976) On the construction of Huffman trees, pp. 382–410.
Katz, Phillip W. (1991) String searcher, and compresor using same string patterns.
Ranganathan, N, Henriques, S. (1993) High-speed VLSI designs for Lempel-Ziv-based data compression. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, Vol-40, No.2, pp. 96–106.
E.Jebamalar Leavline ,D.Asir Antony Gnana Singh (2013) Hardware Implementation of LZMA Data Compression Algorithm. International Journal of Applied Information Systems (IJAIS).
Apoorv Gupta, Aman Bansal, Vidhi Khanduja, (2017) Modern Lossless Compression Techniques: Review, Comparison and Analysis.
Ilan Sadeh (2009) Universal data compression based on approximate string matching.
Petteri J, Jorma T, Ukkonen E. (1998) A Comparison of Approximate String Matching Algorithms.
Z. Galil, K. Park (1990) An improved algorithm for approximate string matching, SIAM Journal on Computing, 19, pp. 989–999.
R. Grossi, F. Luccio (2018) Simple and efficient string matching with k mismatches, Information Processing, pp. 113–120.
E. Ukkonen (1992) Approximate string matching with qgrams and maximal matches, Theoretical Computer Science, 92, pp. 191–211.
Narendra Kumar, Vimal Bibhu, Mohammad Islam, Shashank Bhardwaj (2017) Approximate string matching using n-grams technique.
Boytsov L. (2011) Indexing Methods for Approximate Dictionary Searching: Comparative Analysis.
A. Yerokhin, A. Nechyporenko, O. Turuta, A. Babii (2016) A new intelligence-based approach for rhinomanometric data processing 2016 IEEE 36th International Conference on Electronics and Nanotechnology (ELNANO), Kiev, 2016, pp. 198-201.
Klovstad J., Mondshein L. (1975) The CASPERS linguistic analysis system. IEEE Transactions on Acoustics, Speech and Signal Processing 23, pp. 118 – 123.
Mihov S., Schulz K. U. (2004) Fast approximate string search in large dictionaries. Computational Linguistics, 30, 4, pp. 451–477.
Cole R., Gottlieb, L. A., AND Lewenstein, M. (2004) Dictionary matching and indexing with errors and don’t cares. In STOC ’04: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing. ACM, pp. 91–100.
Ukkonen, E. (1985) Algorithms for approximate string matching. Information and Control 64, 1-3, pp. 100–118.
Myers, E. (1994) A sublinear algorithm for approximate keyword searching. Algorithmica 12, 4/5, pp. 345–374.
Samir Kumar Bandyopadhyay, Tuhin Utsab Paul, Avishek Raychoudhury (2016) Image Compression using Approximate Matching and Run Length.
Robinson, A. H. Cherry, C. (1967) Results of a prototype television bandwidth compression scheme, Proceedings of the IEEE, pp. 356–364.
