Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


Предисловие автора

В 1829 году Луи Брайль (Louis Braille), молодой органист одного парижского собора, который потерял зрение в раннем детстве в возрасте трех лет, изобрел знаменитый шрифт для слепых. Этот шрифт, названный его именем, широко распространился по всему миру, позволяя слепым людям читать и писать. Брайль слегка усовершенствовал свои коды в 1834 году. Было еще несколько незначительных изменений, однако осталось неизменным основное начертание символов или букв, каждая из которых представлена в виде блока точек 3x2. Эти точки выдавливаются на листе плотной бумаги, причем каждая может быть поднята вверх или опущена, что означает, она присутствует или отсутствует. Таким образом, каждая точка эквивалентна одному биту информации. В результате, шрифт Брайля (см. рис.1) представляет собой шестибитовый код, с помощью которого можно представить ровно 64 символа (блок, в котором все точки опущены, обозначает пустой символ или пробел).

Рис. 1. Алфавит Брайля.

Последователи Брайля расширили возможности его шрифта несколькими путями. Прежде всего они ввели сокращения. Некоторые отдельно стоящие буквы стали обозначать целые слова. Например, отдельно стоящая буква «Ь» (или со знаком препинания) обозначает слово «but» (мы будем вести речь об английском варианте шрифта Брайля). Одиночная буква «е» означает «every», а буква «р» - «people».

Другим полезным правилом стало использование сокращенных форм некоторых часто используемых слов, то есть, комбинации двух и более символов стали обозначать целые слова. Например, «аb» означает «about», «rev» - «receive», а буквосочетание «(the)mvs» - это «themselves». (Символы «the» в круглых скобках тоже имеют свой специальный код, в котором подняты точки 2-3-4-6.) На рис. 2 показаны некоторые специальные коды и соответствующие им слова или части слов.

Рис. 2. Некоторые сокращения и короткие слова.

Немного о Луи Брайле

Луи Брайль родился 4 января 1809 года в городе Купврэ недалеко от Парижа. Несчастный случай лишил его зрения в возрасте 3 лет и сделал слепым на всю жизнь. Когда Луи исполнилось 10 лет, родители послали его в парижскую школу для слепых, где он учился читать с помощью специального рельефно-точечного шрифта. Этот шрифт был изобретен Шарлем Барбье для использования в армии. Он назывался «ночное письмо». С его помощью офицеры и солдаты могли обмениваться сообщениями в темноте. В основе шрифта ночного письма лежали блоки из 12 точек, две точки в длину и шесть точек в высоту. Каждая точка или комбинация выпуклых точек в одном блоке обозначала букву или фонетический звук. В таком представлении, однако, имелось одно существенное неудобство, замедлявшее чтение сообщении: было невозможно прощупать весь блок точек за одно быстрое касание пальцем.

Брайль, потратив 9 лет (а ведь он был слепым!) на развитие и усовершенствование ночного письма, разработал свою систему выпуклых точек, которая теперь носит его имя. Главное усовершенствование кода заключалось в уменьшении блока символа. Вместо матрицы 6х2 он предложил использовать матрицу 3x2 точек. Прежде всего это делалось для того, чтобы читающий мог легко распознать символы за одно легкое касание, быстро перемещая палец по строчке символов.

Шрифт Брайля начал вводиться в Соединенных Штатах Америки в 1860 году. С его помощью стали учить незрячих детей в школе святого Луи для слепых. В 1868 году была основана британская ассоциация слепых. Позже стали образовываться объединения незрячих людей в других странах. Шрифт Брайля стал применяться в Англии и в других странах. Начало развиваться книгопечатание на брайле, стали распространяться книги для слепых.

В США существует Североамериканское Общество Брайля (Braille Authority of North America, BANA) с сайтом http://www.brailleauthority.org. Целью этой организации является продвижение шрифта Брайля, содействие в его использовании при обучении. Общество регулярно публикует стандарты и правила языка брайля и следит за правильностью его употребления.

Сокращения, укороченные слова и некоторые другие приемы использования шрифта Брайля - все это примеры интуитивного сжатия информации. Люди, занимавшиеся развитием шрифта Брайля и приспосабливанием его к другим языкам, осознали, что некоторые часто встречающиеся слова и буквосочетания можно заменить специальными знаками или короткими кодами для ускорения чтения и письма. В основе современных методов сжатия информации лежит та же идея: чем чаще встречаются объекты в массиве сжимаемых данных, тем короче сопоставляемый им код.

Предшественницей этой книги послужила монография «Сжатие данных: полное руководство» («Data Compression: The Complete Reference»), опубликованная в 1977 году и переизданная в конце 2000 года. Быстрые и весьма благожелательные читательские отклики на это издание побудили меня к написанию этой небольшой книги. В первой книге я стремился самым подробным образом осветить как основные принципы сжатия данных, так и все детали множества специфических методов. Поэтому она вышла такой объемной. При написании новой книги я был менее амбициозен. В ней я задался целью провести неискушенного читателя по полям сжатия, чтобы он ощутил чудесный аромат этих полей. Это будет сделано с помощью представления основных приемов сжатия информации, а также с помощью описания ключевых алгоритмов. В книге совсем немного математики, нет упражнений, но зато имеется множество примеров, которые помогут проиллюстрировать основные методы.

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

В главе 1 обсуждаются статистические методы сжатия (компрессии) информации. В основе этих методов лежит оценка вероятностей появления элементарных символов в сжимаемом массиве информации, которая определяет коды переменной длины сопоставляемые этим символам. Элементарными символами могут быть биты, ASCII-коды, байты, пикселы, аудио-фрагменты или другие компоненты. Главной идеей этой главы является использование кодов переменной длины, так называемых, префикс-кодов. Среди описываемых методов: кодирование Хаффмана, факсимильное сжатие и арифметическое кодирование.

Популярная техника словарного сжатия является предметом главы 2. Метод словарного сжатия основан на сохранении байтов и фрагментов сжимаемого файла в виде специальной структуры, называемой словарем. Для каждого нового фрагмента данных делается поиск в словаре. Если этот фрагмент находится в словаре, то в сжатый файл записывается ссылка на этот фрагмент. В этой главе описываются следующие известные алгоритмы компрессии этого типа: LZ77, LZSS, LZ78 и LZW.

Чрезвычайно важными объектами сжатия в компьютерных приложениях являются всевозможные оцифрованные изображения (графики, рисунки, картинки или фотографии), которые обычно имеют большой объем. Глава 3 посвящена сжатию изображений. В основном в этой главе обсуждаются различные подходы к решению этой проблемы, такие как кодирование длинных серий, вероятность контекста, предсказание пикселов и преобразование изображений. Из конкретных алгоритмов обсуждаются JPEG и JPEG-LS.

В главе 4 рассматривается преобразование вейвлетов. Этот метод становится все более важным в сжатии изображений и в компрессии аудио-видео информации. Для чтения этой главы необходимы некоторые математические сведения, которые для удобства читателя здесь же и излагаются. Глава начинается описанием интуитивной техники, основанной на вычислении среднего и разностей, которая имеет прямое отношение к вейвлетному преобразованию Хаара. Затем вводится понятие банка фильтров, которое рассматривается после дискретного преобразования вейвлетов. В конце главы излагается алгоритм компрессии SPIHT, основанный на преобразовании вейвлетов.

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

В последней главе, главе 6, рассматривается аудиокомпрессия. Звук является одним из «медиа» в компьютерных мультимедиа приложениях. Он очень популярен среди компьютерных пользователей. Перед сохранением и использованием на компьютере звук необходимо оцифровать. В результате получается исходный аудиофайл очень большого объема. В этой главе описаны основные операции, используемые в знаменитом методе аудиосжатия МРЗ, который, на самом деле, является звуковой частью алгоритма MPEG-1. В главе имеется короткое введение в теорию звука и его восприятия человеком, а также в аудиосэмплирование.

Эта книга прежде всего предназначена тем читателям, которые хотят узнать и освоить основные методы сжатия информации, но у которых нет времени вдаваться во все обширные технические детали множества алгоритмов компрессии и декомпрессии. Я также надеюсь, что использование математики позволит полнее раскрыть «тайны» сжатия информации читателю, который не является экспертом в этой важной области компьютерной науки.

Northridge, California                                                                                                            
David Salomon
Математика это трудно.
- Барби
Non mi legga chi поп e matematico.
(Пусть не читает меня не математик.)
- Леонардо да Винчи

 



<< ПредыдущаяОглавлениеСледующая >>