Тема: Исследование асимметричных систем счисления как нового метода энтропийного кодирования информации

В течение последних пятидесяти лет наблюдается стремительное развитие вычислительной техники. Одновременное увеличение количества используемых компьютеров, рост пропускной способности и общего количества линий связи, появление и развитие глобальных компьютерных сетей, в настоящее время используемых сотнями миллионов пользователей, вызвали быстрое увеличение объемов передаваемой и хранимой информации. Растет частота и производительность процессоров, увеличиваются объемы памяти и ускоряется доступ к ней, однако скорость работы каналов связи, по которым необходимо быстро и надежно передавать большое количество информации, растет значительно меньшими темпами.
Одновременно с этим успешно выполняются проекты по переводу в цифровой вид содержимого огромных хранилищ информации, таких как библиотеки, галереи, музеи. Компании активно переходят к электронному документообороту и способу хранения и мониторинга данных. Алгоритмы компрессии должны выполняться на любых платформах от серверов до цифровых фотоаппаратов. Вычислительная техника непрерывно совершенствуется, поэтому алгоритмы и методы сжатия данных должны также постоянно развиваться и адаптироваться.
Таким образом, задача хранения и передачи текстовой, мультимедийной и другой информации в наиболее компактном виде очень актуальна. Последние десятилетия в этой области ведутся активные разработки. Одной из новых технологий сжатия данных без потерь являются асимметричные системы счисления, относящиеся к семейству методов энтропийного кодирования .
Целью данной работы является исследование асимметричных систем счисления и сравнение их с другими эффективными методами энтропийного кодирования информации по времени работы и коэффициенту сжатия данных.
Для достижения поставленной цели необходимо решить следующие задачи:
• выполнить анализ предметной области;
• разработать математические модели эффективных методов энтропийного кодирования, таких как алгоритм Шеннона Фано, Хаффмана и арифметическое кодирование;
• разработать математические модели асимметричных систем;
• реализовать методы на языке С++;
• реализовать пользовательский интерфейс для демонстрации результатов работы методов;
• протестировать методы на различных экспериментальных данных;
• проанализировать полученные результаты.
Купить

Данная работа посвящена исследованию асимметричных систем счисления как нового метода энтропийного кодирования информации.
В результате выполнения работы был проведен сравнительный анализ ANS с алгоритмами Хаффмана и Шеннона Фано по времени работы и с арифметическим кодированием по коэффициенту сжатия информации.
Для проведения сравнительного анализа эффективные методы энтропийного кодирования были реализованы на языке С++ в среде разработки Microsoft Visual Studio 2012. Для того чтобы измерить время работы методов, было сгенерировано по 10 тестов для каждого из четырех различных размеров алфавита: 161, 97, 27 и 11 символов. Данные размеры алфавитов выбраны не случайно. Таблица ASCII кодов состоит из 256 символов, из них 161 - используемые при написании текстов символы (латинские и русские буквы, знаки препинания и перевод строки), 97 - латинские буквы, знаки препинания и перевод строки, 27 - маленькие латинские буквы и перевод строки и 11 - цифры и перевод строки. Тестами являются файлы различного размера, наибольший размер - 10000000 символов. Для тестирования были выбраны текстовые файлы как наиболее простой и компактный вид входных данных, которые необходимо сжать без потерь. Для проведения сравнительного анализа по коэффициенту сжатия также были сгенерированы тесты различного размера и на различных алфавитах, однако размер файлов был существенно меньше из-за трудоемкости выполнения арифметического кодирования. Для демонстрации результатов работы методов был реализован пользовательский интерфейс.
В ходе сравнительного анализа был сделан вывод, что ANS комбинируют в себе скорость сжатия информации алгоритмом Хаффмана и коэффициент сжатия арифметического кодирования. Данный вывод подтверждает теоретические оценки. Эти свойства асимметричных систем делают их одним из наиболее эффективных методов сжатия информации без потерь на текущий момент.
Такие компании как Apple, Google, Facebook на данный момент успешно внедряют эту технологию в свои архиваторы и компрессоры, однако большинство из них защищены патентами. В будущем ANS получат широкое распространение и среди общедоступных методов сжатия данных.
В дальнейшем планируется рассмотреть приложения ANS в криптографии.
Купить