Перевод текста в килобайты
Как передаются тексты с одного компьютера на другой? Например, мы хотим переслать текст «Мама мыла раму» или «Над всей Испанией безоблачное небо». Как это сделать? Разумеется, по проводам нельзя передать напечатанные слова «мама», «небо» и другие. Можно передать только сигналы. Значит, каждой букве или слову нужно подобрать свой сигнал.
Как перевести слова в сигналы? Если подумать, то на ум приходит нечто вроде азбуки Морзе, когда все буквы и слова передаются в виде точек и тире. Совершенно аналогично компьютеры пользуются всего двумя сигналами. Поэтому вся информация в компьютере записывается посредством двух символов: 0 и 1.
Понятно, что мы только для примера написали фразы по-русски. А вдруг завтра нам понадобится передать сообщение на английском или французском, где совсем другие (латинские) буквы, не говоря уже о разных «акцентах», характерных для французского языка? А еще есть арабские буквы, несколько витиеватых алфавитов Индии и тысячи, если не десятки тысяч, китайских и японских иероглифов! Обучить компьютер отличать один язык от другого – не проблема, такие программы уже есть. Но для хранения и передачи информации это совершенно бесперспективно. Гораздо проще для каждого символа, будь то буквы, иероглифы или знаки препинания, составить свою, уникальную, последовательность из нулей и единиц. К этому можно добавить отдельные последовательности для часто употребляемых слов, особенно если их не слишком много.
Конечно, можно построить компьютеры, которые будут различать три разных сигнала или больше. Но двоичная система (два сигнала, два символа) гораздо удобнее. Ток либо есть (1), либо нет (0) здесь машина не может ошибиться. Поэтому устройства с двоичной системой проще в изготовлении и надежнее.
Все наши компьютеры устроены именно так. Мы печатаем тексты на всех языках мира, рисуем таблички и сохраняем фотографии, а в памяти компьютера нет ничего, кроме нулей и единиц. На самом деле это поразительно!
Соответственно, объем информации в компьютере определяется тем, сколько нулей и единиц нам понадобилось. Каждый ноль или единица представляют собой минимальный объем информации, так называемый один бит. Восемь битов, то есть последовательность из восьми нулей и единиц, называется один байт. Всем известный килобайт (Кбайт), та самая единица измерения объема наших имейлов и документов, равен 1024 байта, или 8192 нуля и единицы. Аналогично мегабайт – это 1024 килобайта.
Почему 1024, а не просто 1000? Потому что в двоичной системе, где всего две цифры, проще всего пользоваться степенями двойки: 2, 4, 8, 16, 32 и так далее. Вполне логично, что в привычной нам десятичной системе, где у нас 10 цифр от 0 до 9, удобно пользоваться степенями десятки: 10, 100, 1000 и так далее. Число 1024 – это два в десятой степени:
1024=2 10 =2×2×2×2×2×2×2×2×2×2
Многие считают, что килобайт – это тысяча байтов. Строго говоря, это не так, но приблизительно верно и больше соответствует нашей привычке считать десятками, сотнями и тысячами.
Сколько килобайтов в вашем сообщении, зависит не только от самого текста, но и от того, каким образом ваши слова были переведены в нули и единицы.
Как сделать сообщение компактным? Где гарантия, что замена нескольких нулей на единицы из-за помех в каналах связи не изменит смысл на полностью противоположный? Проблемы передачи информации послужили толчком для развития целой области современной математики – теории кодирования.
Что такое кодирование
Итак, наша цель – закодировать каждый символ или каждое слово текста с помощью нулей и единиц. Фактически код – это словарь, состоящий из кодовых слов. Каждое кодовое слово представляет собой последовательность нулей и единиц (желательно небольшой длины), которая что-то означает (буква, цифра, знак препинания или целое слово). Построить код можно множеством разных способов, а значит, эта задача очень интересная.
Давайте, к примеру, закодируем отдельно каждую букву русского алфавита. Забавно, кстати, что, когда ставишь эту задачу студентам, почти всегда кто-нибудь спрашивает, сколько букв надо учитывать: 32 или 33. По-видимому, они считают букву «ё» не вполне самостоятельной, потому что в текстах ее обычно меняют на «е». Будем все-таки считать, что букв у нас 33. Сколько байтов (нулей и единиц) нам понадобится, чтобы закодировать 33 буквы?
Совершенно ясно, что тридцати трех байтов вполне достаточно, потому что мы можем каждую букву обозначить кодом из 32 нулей и одной единицы – на той позиции, которую занимает эта буква в алфавите. Такой наивный код будет выглядеть так:
а: 100000000000000000000000000000000
б: 010000000000000000000000000000000
в: 001000000000000000000000000000000
г: 000100000000000000000000000000000
и так далее
я: 000000000000000000000000000000001
Сразу видно, что подобное кодирование неприменимо на практике. Слишком много драгоценных байтов уходит на нули, которые несут очень мало информации.
Какая минимальная длина кода нам понадобится, чтобы закодировать русский алфавит? Скажем, хватит ли нам кодов длины 5? Это зависит от того, сколько разных последовательностей из нулей и единиц длины 5 мы можем составить: 00000, 00001, 00010, 00011 и далее до 11111. Всего 32 такие последовательности. Получить данный ответ довольно просто: это 2 в степени 5, то есть 2 × 2 × 2 × 2 × 2.
Оказывается, последовательностей длины 5 не хватает, так что вопрос студентов попал в самую точку! Всего из-за одной «лишней» буквы нам понадобится как минимум 6 нулей и единиц в каждом «кодовом слове».
Интересно, что добавление всего одной позиции кода очень сильно меняет дело. Для русского алфавита нам нужны последовательности длины 6, а их уже 64. Значит, нам их хватит не только на русский алфавит, но и, например, на латинский из 26 букв, и в запасе еще останется пять свободных последовательностей для знаков препинания.
Ключевой вывод: добавление всего одной позиции кода увеличивает количество разных последовательностей вдвое. Потому что лишнюю позицию можно заполнить двумя способами – либо нулем, либо единицей. В результате количество букв, слов или сообщений, которые мы можем закодировать, возрастает с длиной кода по так называемому экспоненциальному закону, как степень двойки.
«Растет по экспоненциальному закону» на общедоступном языке означает «растет очень быстро»! Помните легенду о том, как король хотел наградить изобретателя шахмат? Умный изобретатель попросил короля положить на первую клетку доски одно зернышко, на вторую – два, на третью – четыре и далее в том же порядке: в два раза больше на каждую следующую клетку. Король согласился и был потрясен, когда зерна в его амбарах не хватило и на половину доски. Точно так же и количество возможных последовательностей из нулей и единиц возрастает очень быстро с их длиной: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024…
Экспоненциальная зависимость между количеством разных кодовых слов и их длиной – абсолютно фундаментальная концепция в информатике и вопросах передачи информации.
Заметим, что количество информации зависит не только от длины кода в килобайтах, но и от того, насколько информативны кодируемые слова. Естественная иллюстрация – это отправка сообщения по телеграфу. Там каждое слово стоит денег, и люди стараются не использовать лишних слов, избегая союзов и предлогов, потому что они менее информативны, чем глаголы и существительные.
Основные концепции о том, как измерить количество информации, изложены в фундаментальной работе Клода Шэннона, опубликованной в 1949 году. Эти концепции во многих отношениях положили начало развитию информатики и строятся все на той же основополагающей экспоненциальной зависимости. Однако мы не будем углубляться в теорию информации, а вернемся к вопросу о том, как составить надежные и эффективные коды.
Коды, исправляющие ошибки
Как вы уже поняли, код – это просто любой набор последовательностей из нулей и единиц. Но не все коды одинаково хороши. Разумеется, неплохо, если каждое кодовое слово достаточно короткое. Об этом мы как раз говорили в прошлом разделе. Однако есть куда более интересные характеристики кода, нежели длина кодовых слов.
Представим, что мы начали передавать кодовые слова по каналу связи, но в нем иногда возникают помехи. Из-за каждой такой помехи передаваемый символ меняется на противоположный: ноль – на единицу, единица – на ноль. Можно ли подобрать кодовые слова так, чтобы все передаваемые символы, несмотря на ошибки, удалось однозначно восстановить? Звучит как научная фантастика! Но оказывается, можно! Достаточно лишь правильно сформулировать соответствующую математическую задачу.
Допустим, наши кодовые слова длины 6 и на каждое кодовое слово приходится не более одной ошибки. Поскольку это простой пример, представим, что наш словарный запас беднее, чем у Эллочки-людоедки из «Двенадцати стульев», и состоит всего из трех слов, которые мы закодировали тремя кодовыми словами:
111000, 001110, 100011.
Конечно, много таким кодом не передашь, но для примера вполне достаточно. Еще важно, что получатель знает наш «словарь», то есть ожидает от нас либо 111000, либо 001110, либо 100011 и ничего другого.
Предположим, мы сначала передаем слово 111000. В результате не более чем одной ошибки (ошибки мы выделили жирным шрифтом) оно может превратиться в одно из слов:
111000, 011000, 101000, 110000, 111100, 111010, 111001, (3.1)
включая, как видите, само себя. Аналогично при передаче слова 001110 может получиться любое из слов:
001110, 101110, 011110, 000110, 001010, 001100, 001111. (3.2)
Наконец, для 100011 у нас выйдет:
100011, 000011, 110011, 101011, 100111, 100001, 100010. (3.3)
Замечательно то, что списки (3.1) (3.3) попарно не пересекаются. Иными словами, если на другом конце канала связи появляется любое слово из списка (3.1), получатель точно знает, что ему передавали именно слово 111000, а если появляется любое слово из списка (3.2) слово 001110; то же самое касается и списка (3.3). В этом случае говорят, что наш код исправил одну ошибку.
За счет чего произошло исправление? За счет двух факторов. Во-первых, получатель знал весь «словарь». Когда код передавался всего с одной ошибкой, выходило слово, которого в словаре не было.
Во-вторых, слова в словаре были подобраны особенным образом. Даже при возникновении ошибки получатель не мог перепутать одно слово с другим. Например, если словарь состоит из слов «дочка», «точка», «кочка» и при передаче получалось «вочка», то получатель, зная, что такого слова не бывает, исправить ошибку не смог бы – любое из трех слов может оказаться правильным. Если же в словарь входят «точка», «галка», «ветка» и нам известно, что допускается не больше одной ошибки, то «вочка» это заведомо «точка», а не «галка». В кодах, исправляющих ошибки, слова выбираются именно так, чтобы они были «узнаваемы» даже после ошибки. Разница лишь в том, что в кодовом «алфавите» всего две буквы – ноль и единица.
Совершенно ясно, что наугад такие коды составить невозможно. За этим стоит целый математический аппарат. Нам нужно научиться измерять расстояния между словами и даже работать с шарами из слов. Что это такое и как это делается, может понять практически любой человек. Ниже мы попробуем объяснить, как создаются коды, исправляющие ошибки, и какие при этом возникают проблемы.
Шары Хэмминга
Математики уже давно договорились, что такое шар. Шар состоит из всех точек, которые удалены от центра не больше чем на какое-то заданное расстояние, обозначаемое буквой r, – радиус. В нашем привычном трехмерном пространстве, где расстояния измеряются в метрах, это обычный шар, как на рис. 3.1.
Рис. 3.1. Шар радиуса r в трехмерном пространстве. Все точки удалены от центра не больше чем на расстояние r
Зато понятия точка и расстояние в математике абсолютно абстрактные. Есть несколько простых правил, которых следует строго придерживаться, но в рамках этих правил – полная свобода. Точками могут быть сигналы, а могут – кривые и даже результаты случайных экспериментов. И расстояния между ними можно определить самыми разными способами. В итоге получаются «шары», не поддающиеся воображению. Тем не менее эти абстрактные шары играют в математике очень большую роль.
В теории кодирования точка – это кодовое слово, то есть последовательность нулей и единиц заданной длины. А расстоянием принято считать так называемое расстояние Хэмминга.
Расстояние Хэмминга между двумя кодовыми словами – это всего-навсего число позиций, на которых у этих слов стоят разные символы: у одного 0, а у другого 1. Например, на рис. 3.2 расстояние Хэмминга между двумя кодовыми словами равно трем. Мы заключили в рамки те позиции, где эти два кодовых слова отличаются друг от друга.
Рис. 3.2. Расстояние Хэмминга между двумя кодовыми словами – число позиций, на которых у этих слов стоят разные символы. На рисунке это расстояние равно трем. Позиции, где два кодовых слова отличаются друг от друга, заключены в рамки
Что происходит, если при передаче, скажем, слова 111000 произошла одна ошибка?
Получится другое слово, которое будет отличаться от 111000 всего на одной позиции. Иначе говоря, если у нас при передаче происходит не больше одной ошибки, расстояние Хэмминга между отправленным и полученным кодовым словом будет не больше единицы. Давайте снова посмотрим на перечень (3.1) предыдущего раздела:
111000, 011000, 101000, 110000, 111100, 111010, 111001.
Расстояние Хэмминга между словом 111000 и любым другим словом из перечня не превосходит 1. Значит, этот список – не что иное, как шар радиуса 1 с центром 111000!
Кстати, подобное определение можно ввести и для обычных слов русского языка одинаковой длины. Например, расстояние Хэмминга между словами «дочка» и «точка» равно единице, а между словами «точка» и «галка» – трем. Если слово «точка» – это центр шара Хэмминга радиуса 1, то слово «дочка» входит в этот шар, а слово «галка» – нет.
Шары Хэмминга очень трудно себе представить даже для маленьких кодов. На рис. 3.3 мы изобразили расстояния Хэмминга между кодовыми словами длины 3. Расстояния Хэмминга могут быть 0, 1, 2 или 3. На рисунке чем темнее цвет, тем больше расстояние. Если взять, например, колонку 000, то шар Хэмминга радиуса 1 – это все белые и светло-серые квадратики в этой колонке: 000, 001, 010, 100. Сразу видно, что расположение белых и, скажем, самых темных квадратиков в колонках неодинаковое, хотя, конечно, в рисунке много закономерностей. Например, рисунок из самых светлых тонов (белый и светло-серый) абсолютно симметричен рисунку из двух оставшихся более темных тонов.
Рис. 3.3. Расстояние Хэмминга между кодовыми словами длины 3. Справа изображен цветовой код. Расстояния: 0, 1, 2, 3. Чем темнее цвет, тем больше расстояние
Кодовые слова длины 3 – очень простой пример, их всего восемь. Стоит чуть увеличить длину кодового слова, и из-за уже знакомого нам экспоненциального закона слов станет так много, что картинка нам не поможет. Профессор Джон Слэни из Австралийского национального университета сделал замечательный рисунок, на котором изображены расстояния Хэмминга между кодовыми словами длины 8, а это всего один байт. Таких слов 256. Советуем заглянуть на веб-страницу Слэни и посмотреть на этот рисунок. Вам сразу станет понятно, что он никак не поможет найти хороший код. Картинка скорее напоминает красивый коврик. Нам нужен другой математический аппарат, и, к счастью, такой аппарат есть. Теория кодирования тесно связана с комбинаторикой – наукой о комбинациях тех или иных объектов.
Возможно, вы уже заметили связь между шарами Хэмминга и кодами, исправляющими ошибки. Допустим, мы передаем кодовые слова длины 10 и хотим, чтобы код исправлял две ошибки. Тогда надо построить код, в котором шары с центрами в кодовых словах и радиусами 2 попарно не пересекались бы. Все последовательности нулей и единиц в таком шаре будут означать одно и то же кодовое слово. Иначе говоря, кодовые слова должны отличаться друг от друга настолько, чтобы при наличии двух ошибок их невозможно было перепутать. На языке математики это значит, что расстояния Хэмминга между кодовыми словами должны быть как минимум равны 5.
При создании кодов возникает немало интересных вопросов. Например, очень важно, чтобы количество кодовых слов было как можно большим, так как это позволит передать по каналу связи больше информации, исправляя при этом заданное наперед количество ошибок (характерное для данного канала связи). Отыскание максимальных кодов при заданной длине кодового слова и количестве ошибок – крайне трудная и не до конца решенная математическая задача. По сути, это задача комбинаторики, хотя и мотивированная совершенно практическими вопросами кодирования информации.
История кодов, исправляющих ошибки
Ричард Хэмминг, именем которого названы расстояния между кодовыми словами, – один из основателей современной теории кодирования. Эта теория начала развиваться в конце 40-х годов XX века, когда Хэмминг работал в Bell Labs и занимался проблемами передачи информации.
Хэмминг заметил, что в коде, исправляющем ошибки, количество возможных кодовых слов неизбежно должно быть ограничено. Например, мы хотим построить код из слов длины 10, который исправляет две ошибки. Сколько разных кодовых слов мы можем использовать? Допустим, мы выбрали кодовое слово 0000011111, чтобы закодировать букву «а». Теперь все последовательности на расстоянии Хэмминга один или два от 0000011111, то есть в шаре радиуса 2 с центром 0000011111, нельзя использовать для кодирования никакой другой информации. Они нам нужны для исправления ошибок при передаче буквы «а». Такой шар содержит 56 последовательностей. Получается, что на каждое кодовое слово, которое что-то означает, приходится 56 слов на исправление ошибок. Поэтому мы можем закодировать не 1024, а всего лишь 1024/56, то есть 18 разных символов или сообщений. Если этого мало – например, мы хотим закодировать русский алфавит, – то длину кодовых слов придется увеличить. Это увеличит и количество килобайтов, но такова цена за исправление ошибок.
Рассуждая примерно так, как мы описывали в предыдущем параграфе, Хэмминг получил максимальное число слов любой длины с исправлением любого заданного количества ошибок. Эта формула называется границей Хэмминга.
Заметим, что граница Хэмминга – это максимально возможное число слов в коде, исправляющем ошибки. Но это еще не означает, что такой максимальный код можно найти. Представьте, что мы имеем дело с обычными шарами. Нельзя уложить круглые апельсины в ведро или коробку так, чтобы между соседними апельсинами не было пустот! Где же гарантия, что все последовательности из нулей и единиц можно разбить на шары Хэмминга так, чтобы они не пересекались и между ними не было свободного места? Оказывается, такое разбиение во многих случаях возможно. Мы не станем здесь описывать конструкцию, ее можно найти в специальной литературе (см.).
Впрочем, сделано в этом направлении далеко не все. Конструкции есть, но только асимптотические, то есть такие, в которых длина кодового слова очень большая и увеличивается до бесконечности, а количество ошибок при этом маленькое и фиксированное. Однако во многих практических задачах чем длиннее кодовое слово, тем больше ошибок. В такой ситуации проблема отыскания правильных верхних границ и построения максимальных кодов по-прежнему открыта! Более того, в этой ситуации известно, что граница Хэмминга, как правило, не точна, и есть еще масса более аккуратных оценок, среди которых и оценка Владимира Иосифовича Левенштейна, замечательного российского математика, и границы линейного программирования. Эти конструкции очень сложны и выходят далеко за рамки нашей книги.
Особый интерес вызывают так называемые равновесные коды. В них все кодовые слова содержат одинаковое количество единиц. Для таких кодов можно найти границу, аналогичную границе Хэмминга. И снова возникает вопрос о существовании равновесного кода, достигающего полученной границы. В начале 80-х годов XX века Войцех Рёдль придумал очень хитрую вероятностную технику, позволившую доказать наличие равновесных кодов, в которых число кодовых слов асимптотически равно верхней границе.
Буквально пару лет назад Питер Киваш из Оксфордского университета объявил о построении равновесных кодов, в которых количество слов достигает теоретической верхней границы. Это очень объемная и трудная математическая работа; она до сих пор тщательно проверяется и потому опубликована только в интернете.
Что же касается случаев, когда число ошибок и число единиц в равновесном коде пропорциональны длине кодового слова, то здесь пока все безнадежно. А именно эти случаи особенно важны! Вот такая она, математика. На первый взгляд кажется, что все давно известно. А на самом деле вопросов, на которые по-прежнему нет ответов, несмотря на всю естественность их возникновения и важность для практики, гораздо больше, чем тех, ответы на которые уже получены.
Можем ли мы закодировать все подряд
Все описанное в этой главе в основном применимо к кодированию текстов. Другим видам информации присущи свои особенности.
Как, например, закодировать цвет? Наверное, вы не раз отправляли, получали или по крайней мере видели в интернете цветные фотографии. Значит, закодировать цвет можно, и люди уже этому научились. На самом деле это вовсе не тривиальная задача, и решить ее удалось только потому, что, оказывается, любой цвет можно разбить на три компонента: красный, зеленый и синий. Иными словами, любой оттенок определяется лишь интенсивностью этих трех основных цветов. Так устроен наш цветной мир, такой вот подарок для кодирования. Если бы природа цвета была иной, то никаких цветных фотографий мы не могли бы пересылать.
Если вам когда-нибудь приходилось использовать нестандартные цвета в обычных программах типа Word или PowerPoint, вы, возможно, заметили опцию, где интенсивность красного, зеленого и синего можно задать вручную. Обычно интенсивность определяется числом от 0 до 255. Всего 256 вариантов – ровно по количеству разных последовательностей нулей и единиц длины 8, то есть один байт. В результате нам нужно всего три байта, чтобы закодировать 256 × 256 × 256 = 16777216 – более шестнадцати с половиной миллионов оттенков компьютерной палитры.
Если обозначать интенсивность цветов цифрами в стандартном порядке красный-зеленый-синий, то 0–0–0 – это черный цвет, а 255–255–255 – белый. Если интенсивность красного, зеленого и синего одинаковая, то между черным и белым получится целых 254 оттенка серого. А желтый можно получить, если использовать красный и зеленый с одинаковой интенсивностью. В табл. 3.1 приводится пример красно-зелено-синего кода для цветов радуги.
Таблица 3.1. Пример цветового кода для цветов радуги. Интенсивность основных цветов (красного, зеленого и синего) определяется числом от 0 до 255
Дополнительные серьезные проблемы возникают при необходимости передать фильм. Если кодировать каждую точку каждого кадра, понадобится такое количество гигабайтов, что они не уместятся в памяти ни одного компьютера. Поэтому цифровое видео появилось относительно недавно.
Здесь требовалось решить задачу иного рода – задачу сжатия данных: как сделать код как можно короче и при этом не потерять информацию. Такие задачи часто возникают, когда нужно сохранить и использовать большое количество информации. Именно эту задачу решают программы для архивирования типа Zip.
Стандартный способ сжатия данных для фильма – полностью кодировать первый кадр, а затем кодировать не каждый кадр отдельно, а только изменения. Но при необходимости сохранить информацию иного рода, например кто с кем дружит в «Фейсбуке», понадобятся совершенно другие способы сжатия данных. И они, кстати, уже разработаны.
А вот со звуком все намного сложнее. Мы до сих пор не умеем кодировать звучание симфонического оркестра так, чтобы оно воспроизводилось как в концертном зале.
Эта задача выходит за рамки не только нашей книги, но и математики. Математика – великая наука, но ее возможности распространяются только на объекты, которые поддаются формальному описанию, буквами и числами. Математики научились кодировать текст потому, что когда-то люди изобрели слова и алфавит. Математики умеют кодировать цвет потому, что физики обнаружили, что любой оттенок определяется интенсивностью красного, синего и зеленого. Несомненно, математики придумали бы эффективные коды для живого звука, если бы хоть кто-нибудь сумел описать, из каких сигналов и интенсивностей он состоит. Но, к сожалению, сделать это исчерпывающим образом пока никому не удалось.