МЕТОДЫ СЖАТИЯ ТЕКСТОВЫХ ДАННЫХ НА ОСНОВЕ ВЗАИМНОГО ОБЪЕМА ИНФОРМАЦИИ
|
Введение 3
1. Постановка задачи 6
2. Обзор методов сжатия информации без потерь 7
2.1. Код Хаффмана 7
2.2. Арифметическое кодирование 12
2.3. Алгоритм LZ77 16
2.4. Алгоритм LZ78 19
2.5. Алгоритм RLE 21
3. Оценка использования взаимной информации текстов методами сжатия 23
3.1. Код Хаффмана 26
3.2. Арифметическое кодирование 28
3.3. Алгоритм LZ77 29
3.4. Алгоритм LZ78 31
4. Модификации алгоритма словарного сжатия 33
4.1. Использование языковых словарей 34
4.2. Построение стилистических словарей 37
4.2.1. Алгоритм поиска часто встречаемых буквосочетаний в тексте 37
4.2.2. Определение размера словарей 39
4.2.3. Формирование словарей 44
4.3. Использование стилистических словарей 47
4.4 Стилистические словари как классификаторы текстов 49
Заключение 51
Список литературы 52
Приложение
1. Постановка задачи 6
2. Обзор методов сжатия информации без потерь 7
2.1. Код Хаффмана 7
2.2. Арифметическое кодирование 12
2.3. Алгоритм LZ77 16
2.4. Алгоритм LZ78 19
2.5. Алгоритм RLE 21
3. Оценка использования взаимной информации текстов методами сжатия 23
3.1. Код Хаффмана 26
3.2. Арифметическое кодирование 28
3.3. Алгоритм LZ77 29
3.4. Алгоритм LZ78 31
4. Модификации алгоритма словарного сжатия 33
4.1. Использование языковых словарей 34
4.2. Построение стилистических словарей 37
4.2.1. Алгоритм поиска часто встречаемых буквосочетаний в тексте 37
4.2.2. Определение размера словарей 39
4.2.3. Формирование словарей 44
4.3. Использование стилистических словарей 47
4.4 Стилистические словари как классификаторы текстов 49
Заключение 51
Список литературы 52
Приложение
С самого начала развития компьютерных технологий возникала потребность в достаточном количестве памяти на физических носителях. Несколько десятков лет назад существовала проблема малого объема памяти на носителях и в то же время их дороговизны. И пусть сейчас эта проблема отошла немного на второй план, в связи с тем, что жесткие диски компьютеров способны хранить терабайты информации, а также развитие получили технологии облачного хранения данных. Но процесс сжатия данных по- прежнему актуален.
Действительность такова, что помимо оптимального использования дискового пространства, архиваторы позволяют нам экономить в том числе и интернет-трафик, что ведет к экономии времени и средств. Преимущества особенно очевидны при передаче большого объема информации, что не является редкостью.
За счет чего же удается уменьшить объем данных? В первую очередь за счет того, что переданная информация, как правило, обладает избыточностью. Простейшим примером подобной избыточности является повторение некоторых фраз. Поэтому вместо того, чтобы еще раз повторять этот же фрагмент, можно использовать ссылку на предыдущее его использование. Есть множество способов устранения избыточности и все они так или иначе используются в современных архиваторах для сжатия данных.
Сжатию могут быть подвержены совершенно различные виды данных. Это и всем привычные тексты, и изображения, и аудио- и видеофайлы. Сжаты могут быть даже и иные файлы. Но здесь стоит сказать о том, что помимо того, что данные теряют в объеме при сжатии, через некоторое время они должны быть успешно восстановлены. И это гораздо более важный фактор. Здесь мы приходим к понятиям кодера и декодера.
Кодер, как нетрудно догадаться по названию, кодирует данные. Если точнее описывать этот процесс, то кодер получает файлы с исходными данными, преобразует данные в этих файлах, в ходе чего они заметно уменьшаются в объеме, а затем на выходе мы и получаем сжатые файлы. Это и является целью кодера. С помощью декодера сжатые файлы восстанавливаются к первоначальному виду.
Вообще говоря, данные полученные после работы декодера, должны быть эквивалентны исходным. В таком случае говорят о сжатии без потерь данных. Но имеет место и сжатие с потерями, когда не вся первоначальная информация была успешна восстановлена. При использовании сжатия с потерями данные, полученные подобным путем, будут воспроизводить нечто похожее на исходные данные, но не абсолютно точное. Зачем это нужно?
Во-первых, это позволяет еще лучше сжать данные. Во-вторых, сжатие, как и процесс разжатия (декодирования), как правило, происходят быстрее. Конечно мы теряем часть информации, но в некоторых случаях это позволительно.
Например, мы не можем использовать подобный вид сжатия для информации, точность которой нам очень важна. Подобный вид сжатия не употребим в случае, когда мы захотим сжать, например, данные различных счетов банка. В данном примере нам важна каждая цифра или буква и потеря их приведет к колоссальным проблемам.
Несмотря на это, методы сжатия с потерями данных имеют свое применение. Чаще всего их используют для обработки различных изображений, звуковых файлов, видео. Это вполне допустимо, потому что человек воспринимает подобную информацию в целом, а не с побитовой точностью. Например, мы можем преобразовать изображение. В ходе обратного преобразования мы получим то же самое изображение, но в чуть худшем качестве (вполне возможно, что мы даже этого и не заметим). Но если предполагается компьютерная обработка звуков, изображений, то требования к потерям будут гораздо более жесткие.
Существует большое разнообразие методов сжатия данных и для того, чтобы понимать, насколько эффективен тот или иной метод, должна быть какая-то мера оценки. И подобные меры действительно есть. Назовем основные:
1. Степень сжатия - отношение длины исходных данных к длине сжатых данных. Часто вместо степени сжатия используют коэффициент сжатия, определяемый как отношение длины сжатых данных к длине соответствующих исходных данных.
2. Скорость сжатия - время, затраченное на работу алгоритма сжатия.
3. Скорость разжатия (декодирования) - время, затраченное на работу декодера.
4. Объемы памяти, необходимые для сжатия и для разжатия.
Подводя итог написанному выше, уверенно можно сказать, что сжатие данных (текстов, видео, изображений и т.д.) по-прежнему является достаточно актуальной и интересной областью для изучения. И в данной работе мы ознакомимся с данной областью науки, а также опробуем некоторые идеи на примере локальных задач сжатия.
Действительность такова, что помимо оптимального использования дискового пространства, архиваторы позволяют нам экономить в том числе и интернет-трафик, что ведет к экономии времени и средств. Преимущества особенно очевидны при передаче большого объема информации, что не является редкостью.
За счет чего же удается уменьшить объем данных? В первую очередь за счет того, что переданная информация, как правило, обладает избыточностью. Простейшим примером подобной избыточности является повторение некоторых фраз. Поэтому вместо того, чтобы еще раз повторять этот же фрагмент, можно использовать ссылку на предыдущее его использование. Есть множество способов устранения избыточности и все они так или иначе используются в современных архиваторах для сжатия данных.
Сжатию могут быть подвержены совершенно различные виды данных. Это и всем привычные тексты, и изображения, и аудио- и видеофайлы. Сжаты могут быть даже и иные файлы. Но здесь стоит сказать о том, что помимо того, что данные теряют в объеме при сжатии, через некоторое время они должны быть успешно восстановлены. И это гораздо более важный фактор. Здесь мы приходим к понятиям кодера и декодера.
Кодер, как нетрудно догадаться по названию, кодирует данные. Если точнее описывать этот процесс, то кодер получает файлы с исходными данными, преобразует данные в этих файлах, в ходе чего они заметно уменьшаются в объеме, а затем на выходе мы и получаем сжатые файлы. Это и является целью кодера. С помощью декодера сжатые файлы восстанавливаются к первоначальному виду.
Вообще говоря, данные полученные после работы декодера, должны быть эквивалентны исходным. В таком случае говорят о сжатии без потерь данных. Но имеет место и сжатие с потерями, когда не вся первоначальная информация была успешна восстановлена. При использовании сжатия с потерями данные, полученные подобным путем, будут воспроизводить нечто похожее на исходные данные, но не абсолютно точное. Зачем это нужно?
Во-первых, это позволяет еще лучше сжать данные. Во-вторых, сжатие, как и процесс разжатия (декодирования), как правило, происходят быстрее. Конечно мы теряем часть информации, но в некоторых случаях это позволительно.
Например, мы не можем использовать подобный вид сжатия для информации, точность которой нам очень важна. Подобный вид сжатия не употребим в случае, когда мы захотим сжать, например, данные различных счетов банка. В данном примере нам важна каждая цифра или буква и потеря их приведет к колоссальным проблемам.
Несмотря на это, методы сжатия с потерями данных имеют свое применение. Чаще всего их используют для обработки различных изображений, звуковых файлов, видео. Это вполне допустимо, потому что человек воспринимает подобную информацию в целом, а не с побитовой точностью. Например, мы можем преобразовать изображение. В ходе обратного преобразования мы получим то же самое изображение, но в чуть худшем качестве (вполне возможно, что мы даже этого и не заметим). Но если предполагается компьютерная обработка звуков, изображений, то требования к потерям будут гораздо более жесткие.
Существует большое разнообразие методов сжатия данных и для того, чтобы понимать, насколько эффективен тот или иной метод, должна быть какая-то мера оценки. И подобные меры действительно есть. Назовем основные:
1. Степень сжатия - отношение длины исходных данных к длине сжатых данных. Часто вместо степени сжатия используют коэффициент сжатия, определяемый как отношение длины сжатых данных к длине соответствующих исходных данных.
2. Скорость сжатия - время, затраченное на работу алгоритма сжатия.
3. Скорость разжатия (декодирования) - время, затраченное на работу декодера.
4. Объемы памяти, необходимые для сжатия и для разжатия.
Подводя итог написанному выше, уверенно можно сказать, что сжатие данных (текстов, видео, изображений и т.д.) по-прежнему является достаточно актуальной и интересной областью для изучения. И в данной работе мы ознакомимся с данной областью науки, а также опробуем некоторые идеи на примере локальных задач сжатия.
Главным результатом данной работы является создание двух модификаций словарного алгоритма сжатия LZ77, которые позволяют нам более качественно сжимать тексты из конкретной предметной области. Подобное улучшение достигается за счет использования взаимных свойств, общих языковых и стилистических структур текстов.
Первая модификация использовала статические словари для английского и русского языков, а вторая - статические словари для каждого из предложенных стилей текстов.
Построенные таким образом словари могут быть использованы в дальнейшем для различных целей. Например, для проведения структурных анализов различных текстов. В частности, как это было показано в работе, может быть решена задача классификации, т.е. соотнесение текста к одному из известных стилей.
Данная работа может быть в дальнейшем развита. Здесь мы проводили анализ, касающийся только языков и стилей. Однако можно такую же работу провести и для отдельных жанров, и для авторов. Словари можно будет расширить, а конструкции словарей увеличить. Тем самым, например, может быть решена задача определения авторства текстов.
Возможны улучшения и в области сжатия. Так, например, перед самим процессом сжатия, можно подготовить входные данные, т.е. каким-то образом их преобразовать. Такой подход называется препроцессингом. Вполне возможно, что это серьёзно увеличит показатели сжатия.
Первая модификация использовала статические словари для английского и русского языков, а вторая - статические словари для каждого из предложенных стилей текстов.
Построенные таким образом словари могут быть использованы в дальнейшем для различных целей. Например, для проведения структурных анализов различных текстов. В частности, как это было показано в работе, может быть решена задача классификации, т.е. соотнесение текста к одному из известных стилей.
Данная работа может быть в дальнейшем развита. Здесь мы проводили анализ, касающийся только языков и стилей. Однако можно такую же работу провести и для отдельных жанров, и для авторов. Словари можно будет расширить, а конструкции словарей увеличить. Тем самым, например, может быть решена задача определения авторства текстов.
Возможны улучшения и в области сжатия. Так, например, перед самим процессом сжатия, можно подготовить входные данные, т.е. каким-то образом их преобразовать. Такой подход называется препроцессингом. Вполне возможно, что это серьёзно увеличит показатели сжатия.