Общие сведения о текстовой информации

Общие сведения о текстовой информации

На текущий момент времени большая часть всей информации, находящейся в сети Интернет, представлена в виде текста на различных национальных языках. Персональные компьютеры еще со времен 60-х годов научились правильно распознавать, обрабатывать, хранить и передавать текстовую информацию. Сложно себе представить современный и актуальный вебсайт, который не содержит ни одного символа. Ежедневно глобальная паутина пополняется десятками миллионов текстовых публикаций различного объема. Все поисковые системы в основном «заточены» на релевантный поиск веб-страниц в соответствии с текстовым запросом пользователей.

Не стоит забывать о том, что процессор любого компьютера, любой марки, любого бренда способен обрабатывать информацию, выраженную комбинацией только из 0 и 1. Следовательно, текстовая информация также должна быть преобразована в двоичный набор кодов. Значит, существует некий алгоритм, позволяющий кодировать текстовую информацию в вид, понятный процессору компьютера.

Кодирование звука

Кодирование звука применяется с целью уменьшения объема файла и осуществляется при помощи специальных алгоритмов сжатия, именуемых кодеками. Наиболее распространённый алгоритм сжатия аудио MP3 (MPEG Layer-3) — создан немецким институтом Фраунгофера (Fraunhofer Institut für Integrierte Schaltungen) в 1989 году.

Данный формат позволяет сохранять в файле не только запись звука, но также метаданные: название альбома, год выпуска, имя исполнителя и многое другое. Данный формат поддерживается большинством музыкальных устройств, что обеспечивает дальнейшую жизнеспособность формата.

Кодирование звука в формате mp3 происходит при частичном отсеивании частот, которые не способно услышать человеческое ухо. Помимо отсеивания частот, сжатый файл адаптируется под более грубую шкалу громкости, где все промежуточные значения округляются до целого числа, за счет чего некоторые частоты могут стать громче, а другие становятся тише.

Подобные искажения менее заметны на средних и низких частотах, имеющих большую амплитуду, но становятся более ощутимы на частотах от 5000 Герц и выше. Пример округления значений показан на рисунке.

Синей линией изображена исходная звуковая волна, красной линией отображена волна, после округления значений громкости. Звуковая волна выделенная красным будет сохранена непосредственно в аудио файл. Если сравнить две волны, мы видим насколько сильны искажения слабых колебаний, при том, что громкий звук записан практически без потерь.

 

Помимо грамотно разрекламированного алгоритма сжатия mp3, существует менее популярный, но более поздний и более качественный алгоритм сжатия, разработанный компанией Майкрософт — WMA (Windows Media Audio). Данный формат позволяет осуществлять сжатие звука до 64 кб/секунду при частоте дискретизации 48 кГц, что существенно снижает объем файла. И это при том, что сохраняется частотный диапазон до 20 000 кГц.

Для сравнения, сжатие звука в формате mp3 до 64 кб/секунду возможно только с частотой дискретизации 22050 Гц, что приводит к сужению диапазона до 7 кГц. Справедливости ради стоит заметить, что сейчас, когда носители информации размером с ноготь — способны хранить от 1 гигабайта информации и больше, нет необходимости в столь сильном сжатии.

Если же возникает необходимость в сохранении качества звука на профессиональном уровне, о любых алгоритмах сжатия следует забыть, но без дискретизации звука обойтись не получится. Впрочем, дискретизация не так страшна, если речь идет о частоте от 48 кило Герц и выше.

Истинные же ценители звука предпочитают слушать виниловые пластинки, считая их звучание непревзойденным. На самом же деле, только новая виниловая пластинка (без пробега) способна хранить частоту до 25 кГц, которую, кстати, не способны воспроизводить даже ультрасовременные музыкальные центры. А непревзойденным следует считать звучание живого музыкального инструмента без студийной обработки. Да и человеческое ухо не способно слышать ультразвук. Качество же винилового носителя, после трех прослушиваний, снижается до 18 кГц, а каждые последующие три прослушивания "съедают" качество записи винила вплоть до 12 кГц.

Алгоритмы сжатия картинок

Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений.
Все существующие алгоритмы можно разделить на два больших класса:

 

· Алгоритмы сжатия без потерь;

· Алгоритмы сжатия с потерями.

Когда мы говорим о сжатии без потерь, мы имеем в виду, что существует алгоритм, обратный алгоритму сжатия, позволяющий точно восстановить исходное изображение. Для алгоритмов сжатия с потерями обратного алгоритма не существует. Существует алгоритм, восстанавливающий изображение не обязательно точно совпадающее с исходным. Алгоритмы сжатия и восстановления подбираются так, чтобы добиться высокой степени сжатия и при этом сохранить визуальное качество изображения.

Алгоритмы сжатия без потерь

 

Алгоритм RLE

Все алгоритмы серии RLE основаны на очень простой идее: повторяющиеся группы элементов заменяются на пару (количество повторов, повторяющийся элемент). Рассмотрим этот алгоритм на примере последовательности бит. В этой последовательности будут чередовать группы нулей и единиц. Причём в группах зачастую будет более одного элемента. Тогда последовательности 11111 000000 11111111 00 будет соответствовать следующий набор чисел 5 6 8 2. Эти числа обозначают количество повторений (отсчёт начинается с единиц), но эти числа тоже необходимо кодировать. Будем считать, что число повторений лежит в пределах от 0 до 7 (т.е. нам хватит 3 бит для кодирования числа повторов). Тогда рассмотренная выше последовательность кодируется следующей последовательностью чисел 5 6 7 0 1 2. Легко подсчитать, что для кодирования исходной последовательности требуется 21 бит, а в сжатом по методу RLE виде эта последовательность занимает 18 бит.
Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности. Для примера рассмотрим следующую последовательность 111 0000 11111111 00. Соответствующая ей RL-последовательность выглядит так: 3 4 7 0 1 2. Длина исходной последовательности – 17 бит, длина сжатой последовательности – 18 бит.
Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов.

 

Словарные алгоритмы

Идея, лежащая в основе словарных алгоритмов, заключается в том, что происходит кодирование цепочек элементов исходной последовательности. При этом кодировании используется специальный словарь, который получается на основе исходной последовательности.
Существует целое семейство словарных алгоритмов, но мы рассмотрим наиболее распространённый алгоритм LZW, названный в честь его разработчиков Лепеля, Зива и Уэлча.
Словарь в этом алгоритме представляет собой таблицу, которая заполняется цепочками кодирования по мере работы алгоритма. При декодировании сжатого кода словарь восстанавливается автоматически, поэтому нет необходимости передавать словарь вместе с сжатым кодом.
Словарь инициализируется всеми одноэлементными цепочками, т.е. первые строки словаря представляют собой алфавит, в котором мы производим кодирование. При сжатии происходит поиск наиболее длинной цепочки уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда, при этом выводится сжатый код, соответствующий уже записанной в словаре цепочки. В теории на размер словаря не накладывается никаких ограничений, но на практике есть смысл этот размер ограничивать, так как со временем начинаются встречаться цепочки, которые больше в тексте не встречаются. Кроме того, при увеличении размеры таблицы вдвое мы должны выделять лишний бит для хранения сжатых кодов. Для того чтобы не допускать таких ситуаций, вводится специальный код, символизирующий инициализацию таблицы всеми одноэлементными цепочками.
Рассмотрим пример сжатия алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Предположим, что словарь будет вмещать 32 позиции, а значит, каждый его код будет занимать 5 бит. Изначально словарь заполнен следующим образом:

Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия.

В таблице представлен процесс заполнения словаря. Легко подсчитать, что полученный сжатый код занимает 105 бит, а исходный текст (при условии, что на кодирование одного символа мы тратим 4 бита) занимает 116 бит.
По сути, процесс декодирования сводится к прямой расшифровке кодов, при этом важно, чтобы таблица была инициализирована также, как и при кодировании. Теперь рассмотрим алгоритм декодирования.

Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c — это один символ, а S — строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.

 

Алгоритм Хаффмана

Алгоритм Хаффмана позволяет строить префиксные коды. Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну – 1. Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.
Опишем алгоритм построения дерева Хаффмана и получения кодов Хаффмана.

 

1.Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа

2.Выбираются два свободных узла дерева с наименьшими весами

3.Создается их родитель с весом, равным их суммарному весу

4.Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка

5.Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0

6.Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

С помощью этого алгоритма мы можем получить коды Хаффмана для заданного алфавита с учётом частоты появления символов.

 

Арифметическое кодирование

Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею.
Пусть наш алфавит состоит из N символов a1,…,aN, а частоты их появления p1,…,pN соответственно. Разобьем полуинтервал [0;1) на N непересекающихся полуинтервалов. Каждый полуинтервал соответствует элементам ai, при этом длина полуинтервала пропорциональна частоте pi.
Кодирующая дробь строится следующим образом: строится система вложенных интервалов так, чтобы каждый последующий полуинтервал занимал в предыдущем место, соответствующее положению элемента в исходном разбиении. После того, как все интервалы вложены друг в друга можно взять любое число из получившегося полуинтервала. Запись этого числа в двоичном коде и будет представлять собой сжатый код.
Декодирование – расшифровка дроби по известному распределению вероятностей. Очевидно, что для декодирования необходимо хранить таблицу частот.
Арифметическое кодирование чрезвычайно эффективно. Коды, получаемые с его помощью, приближаются к теоретическому пределу. Это позволяет утверждать, что по мере истечения сроков патентов, арифметическое кодирование будет становиться всё более и более популярным.

 

Алгоритмы сжатия с потерями

Не смотря на множество весьма эффективных алгоритмов сжатия без потерь, становится очевидно, что эти алгоритмы не обеспечивают (и не могут обеспечить) достаточной степени сжатия.
Сжатие с потерями (применительно к изображениям) основывается на особенностях человеческого зрения. Мы рассмотрим основные идеи, лежащие в основе алгоритма сжатия изображений JPEG.

 

Алгоритм сжатия JPEG

JPEG на данный момент один из самых распространенных способов сжатия изображений с потерями. Опишем основные шаги, лежащие в основе этого алгоритма. Будем считать, что на вход алгоритма сжатия поступает изображение с глубиной цвета 24 бита на пиксел (изображение представлено в цветовой модели RGB).

 

Квантование

Человек практически не способен замечать изменения в высокочастотных составляющих, поэтому коэффициенты, отвечающие за высокие частоты можно хранить с меньшей точностью. Для этого используется покомпонентное умножение (и округление) матриц, полученных в результате ДКП, на матрицу квантования. На данном этапе тоже можно регулировать степень сжатия (чем ближе к нулю компоненты матрицы квантования, тем меньше будет диапазон итоговой матрицы).

 

Зигзаг-обход матриц

Зигзаг-обход матрицы – это специальное направление обхода, представленное на рисунке:

При этом для большинства реальных изображений в начале будут идти ненулевые коэффициенты, а ближе к концу будут идти нули.

 

RLE- кодировние

Используется особый вид RLE-кодирования: выводятся пары чисел, причём первое число в паре кодирует количество нулей, а второе – значение после последовательности нулей. Т.е. код для последовательности 0 0 15 42 0 0 0 44 будет следующим (2;15)(0;42)(3;44).

 

Фрактальное сжатие

Фрактальное сжатие – это относительно новая область. Фрактал – сложная геометрическая фигура, обладающая свойством самоподобия. Алгоритмы фрактального сжатия сейчас активно развиваются, но идеи, лежащие в их основе можно описать следующей последовательностью действий.
Процесс сжатия:

 

1.Разделение изображения на неперекрывающиеся области (домены). Набор доменов должен покрывать всё изображение полностью.

2.Выбор ранговых областей. Ранговые области могут перекрываться и не покрывать целиком всё изображение.

3.Фрактальное преобразование: для каждого домена подбирается такая ранговая область, которая после аффинного преобразования наиболее точно аппроксимирует домен.

4.Сжатие и сохранение параметров аффинного преобразования. В файл записывается информация о расположении доменов и ранговых областей, а также сжатые коэффициенты аффинных преобразований.

Этапы восстановления изображения:

 

1.Создание двух изображений одинакового размера A и B. Размер и содержание областей не имеют значения.

2.Изображение B делится на домены так же, как и на первой стадии процесса сжатия. Для каждого домена области B проводится соответствующее аффинное преобразование ранговых областей изображения A, описанное коэффициентами из сжатого файла. Результат помещается в область B. После преобразования получается совершенно новое изображение.

3.Преобразование данных из области B в область A. Этот шаг повторяет шаг 3, только изображения A и B поменялись местами.

4.Шаги 3 и 4 повторяются до тех пор, пока изображения A и B не станут неразличимыми.

Точность полученного изображения зависит от точности аффинного преобразования.
Сложность алгоритмов фрактального сжатия в том, что используется целочисленная арифметика и специальные довольно сложные методы, уменьшающие ошибки округления.
Отличительной особенностью фрактального сжатия является его ярко выраженная ассиметрия. Алгоритмы сжатия и восстановления существенно различаются (сжатие требует гораздо большего количества вычислений).

Общие сведения о текстовой информации

На текущий момент времени большая часть всей информации, находящейся в сети Интернет, представлена в виде текста на различных национальных языках. Персональные компьютеры еще со времен 60-х годов научились правильно распознавать, обрабатывать, хранить и передавать текстовую информацию. Сложно себе представить современный и актуальный вебсайт, который не содержит ни одного символа. Ежедневно глобальная паутина пополняется десятками миллионов текстовых публикаций различного объема. Все поисковые системы в основном «заточены» на релевантный поиск веб-страниц в соответствии с текстовым запросом пользователей.

Не стоит забывать о том, что процессор любого компьютера, любой марки, любого бренда способен обрабатывать информацию, выраженную комбинацией только из 0 и 1. Следовательно, текстовая информация также должна быть преобразована в двоичный набор кодов. Значит, существует некий алгоритм, позволяющий кодировать текстовую информацию в вид, понятный процессору компьютера.