Лекция 6. Анализ и синтез информационных систем. 8 страница

Стандарт ASCII предусматривает создание различных таблиц для разных национальных языков. Каждая из них делится на основную и вспомогательную таблицы. Основная таблица содержит коды от 0 до 127, которые соответствуют стандартным управляющим символам, арабским цифрам, латинским буквам и некоторым друтим общепринятым символам. Вспомогательные таблицы содержат коды от 128 до 255 с символами национальных языков и псевдографики. Вывод таблиц ASCII с помощью программы на языке Бейсик описан в разделе 9.7.4.

В новых операционных системах для компьютеров, например Windows 98/2000/NT/XP, применяются и двухбайтные коды (Unicode), позволяющие довести число кодируемых знаков до 2" = 65536 символов. Этого достаточно для кодирования самых сложных языков.

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

Преобразуя символы в коды, нетрудно автоматизировать операции с текстами. Например, несложно подсчитать число символов в строке, выделить первый, последний или вообще любой символ, выполнить сортировку слов, осуществить замену одного символа или подстроки на друтой (другую) и даже осуществить автоматическую проверку орфографии и грамматики, используя для этого определенные наборы правил того языка, на котором создается и обрабатывается текст. Все это и делают текстовые редакторы и более мощные текстовые процессоры, такие, как всемирно известный редактор текстов Microsoft Word.HeMHoro сложнее кодирование черно-белой графики. Любую точку можно представить набором чисел-кодов: координат по осям X и Y. Имея эти коды, можно построить точку в нужном месте экрана. А из множества точек составить любой рисунок. Однако он будет выглядеть как точечный черно-белый рисунок из старых газет.

Чтобы получить более качественные полутоновые (grayscale) и особенно цветные (color) рисунки, к' численным координатам каждой точки придется добавить некоторые коды цвета и иных свойств точек графики (например признака мигания точки или ее прозрачности). Их принято именовать графическими атрибутами точки.

С позиций математики набор координат точек представляет собой матрицу — прямоугольную таблицу с числами в ее ячейках. Если составить изображение из точек трех основных цветов, например красного (Red), зеленого-(Green) и голубого (Blue), то нам придется хранить матрицы трех цветов и помещать в ячейки матрицы числа, определяющие 'интенсивность каждого цвета (например, от 0 до 1). Это соответствует одной из ряда схем цифрового кодирования изображений, называемой RGB-мет одом кодирования изображений. Рассмотренное выше кодирование информации является самым простым. Существует множество и других систем кодирования:

• кодирование с целью сокращения объема информации путем удаления из нее избыт очной информации;

• кодирование для оперативной шифровки информации;

• помехоустойчивое кодирование для устранения влияния помех и случайных сбоев в каналах связи;

• кодирование для устранения несанкционированного доступа к информации или к информационным устройствам.

Более актуальным является кодирование для запрета несанкционированного доступа к данным или просто к информационным устройствам — программам, компьютерам, сотовым телефонам, средствам Интернета и так далее. Разработкой методов такого кодирования занимается специальная наука — крипт ография.

Имеется много вполне очевидных способов кодирования сообщений. В детстве все мы кодировали слова, произнося их задом наперед. Например, слово «привет» при этом звучало как «тевирп». Юлий Цезарь еще до нашей эры немного превзошел детей. В его письмах каждая буква с начала алфавита заменялась такой же по порядку, но с конца алфавита.

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

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

2. Помехоустойчивое кодирование.

Целью помехоустойчивого кодирования является повышение достоверности доставки сообщений, передаваемых по каналам связи с помехами. В этой лекции рассматриваются методы помехоустойчивого кодирования, ориентированные на доставку сообщений без использования обратного канала сообщений в пакетных сетях. Примерами таких сетей являются любая компьютерная сеть и сеть Интернет. Тема использования FEC в таких сетях не нова. Однако за последние 5-6 лет в этой области кодирования родилось много новых идей. В результате был создан новый класс потоковых кодов, ориентированный на решения большого числа сетевых приложений, для которых в интерактивности нет необходимости. Применение кодирования в таких приложениях позволяет резко уменьшить объём трафика в сети. Эти идеи уже нашли практическое воплощение в таких сетевых приложениях как IP вещание, IP Multicast-сервис, одновременная передача данных с нескольких сайтов в Интернет и т.д.

Лекция 12. Методы сжатия информации с потерями, методы сжатия

информации без потерь.

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

Посчитаем, к примеру, сколько займет памяти изображение, по качеству близкое к телевизионному. Пусть его разрешение ~ 800x600 пиксел, а число оттенков цвета около 16 тысяч {High Color), т. е. цвет каждого пиксела представляется двухбайтовым кодом. 800x600=480000 элементов. 480000x2 байт = 960000 байт ~ это чуть меньше 1 мегабайта. Кажется, не так много - на лазерном диске поместится больше 650 таких картинок. Ну, а если речь идет о фильме? Стандартная скорость кинопроекции - 24 кадра в секунду. Значит на компакт-диске можно записать фрагмент длительностью 650:24=27 секунд. Куда это годится?! А ведь это далеко не единственный случай, когда информации "слишком много". Таким образом, одна из причин использования сжатия данных - желание поместить больше информации в память того же объема. Есть и вторая причина. Сжатие информации ускоряет ее передачу.

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

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

Одна из них впервые появилась в методе сжатия текстовой информации, предложенном в 1952 году Хафманом. Вы знаете, что стандартно каждый символ текста кодируется одним байтом. Но дело в том, что одни буквы встречаются чаще, а друтие реже. Например, в тексте, написанном на русском языке, в каждой тысяче символов в среднем будет 90 букв "о", 72 ~ "е" и только 2 ~ "ф". Больше же всего окажется пробелов: сто семьдесят четыре. Если для наиболее распространенных символов использовать более короткие коды (меньше 8 бит), а для менее распространенных ~ длинные {больше 8 бит), текст в целом займет меньше памяти, чем при стандартной кодировке.

Несколько методов сжатия основаны на учете повторяющихся байтов или последовательностей байт. Простейший из них - RLE - широко используется при сжатии изображений. В файле, сжатом таким методом, записывается, сколько раз повторяются одинаковые байты. Например, вместо "RRRRRGGGBBBBBBRRRBBRRRRRRR" будет храниться "5R3G6B3R2B7R"Очевидно, что такой метод лучше всего работает, когда изображение содержит большие участки с однотонной закраской.

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

Методы сжатия без потерь уменьшают размер файлов не очень сильно. Обычно коэффициент сжатия не превосходит 1/3—1/4. Гораздо лучших результатов можно добиться, используя сжатие с потерями. В этом случае на основе специальных исследований определяется, какой информацией можно пожертвовать.

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

Естественно, сжатие с потерями может использоваться только программами, предназначеными для обработки конкретных видов данных (например, графическими редакторами). А вот методы сжатия без потерь применяются и для любых произвольных файлов (широко известны программы-компрессоры ARJ, ZIP, RAR, Stufflt и др).

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

Контрольные вопросы

1. Зачем нужно сжимать информацию?

2. В каких случаях можно использовать сжатие с потерями, в каких ~ без потерь?

3. На чем основаны методы сжатия без потерь? С потерями? Примечания

9. На самом деле, в телевизионном изображении 625 строк.

10. Compressus (лат.) - сжимание.

11. Run-Length Encoding (англ.) - кодирование длины последовательности.

12. На самом деле, конечно, используются коды цветов и коды, указывающие либо сколько раз повторяется следующий байт, либо сколько следующих байтов - неповторяющиеся.

13. На этой идее основан широко использующийся для сжатия различных данных метод LZW, названный так по первым буквам фамилий его разработчиков: Lempel, Ziv и Welch.

14. Joint Photographic Experts Group (англ.) ~ Объединенная группа экспертов по фотографии, разработавшая одноименный метод сжатия изображений.

15. Moving Picture Experts Group (англ.) ~ Группа экспертов по движущимся изображениям

Полагаю, что все читатели знакомы с архиваторами файлов, вероятно, многие из вас неоднократно ими пользовались. Целью архивации файлов является экономия места на жестком или гибком магнитном диске. Кому не приходилось время от времени задумываться над тем, войдет ли данный файл на дискету? Существует большое число программ- архиваторов, имеются и специальные системные программные средства типа Stacker или DoubleSpace и т.д., решающие эту проблему.

Первые теоретические разработки в области сжатия информации относятся к концу 40- х годов. В конце семидесятых появились работы Шеннона, Фано и Хафмана. К этому времени относится и создание алгоритма FGK (Faller, Gallager, Knuth), где используется идея "сродства", а получатель и отправитель динамически меняют дерево кодов (смотри, например, http://www.ics.uci.edu/~dan/plus/DC-Sec4.html).

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

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

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

Альтернативой статистическому алгоритму является схема сжатия, основанная на динамически изменяемом словаре (напр., алгоритмы Лембеля-Зива). Данный метод предполагает замену потока символов кодами, записанными в памяти в виде словаря (таблица перекодировки). Соотношение между символами и кодами меняется вместе с изменением данных. Таблицы кодирования периодически меняются, что делает метод более гибким. Размер небольших словарей лежит в пределах 2-32 килобайт, но более высоких коэффициентов сжатия можно достичь при заметно больших словарях до 400 килобайт.

Реализация алгоритма возможна в двух режимах: непрерывном и пакетном. Первый использует для создания и поддержки словаря непрерывный поток символов. При этом возможен многопротокольный режим (например, TCP/IP и DECnet). Словари сжатия и декомпрессии должны изменяться синхронно, а канал должен быть достаточно надежен (напр., Х.25 или РРР), что гарантирует отсутствие искажения словаря при повреждении или потере пакета. При искажении одного из словарей оба ликвидируются и должны быть созданы вновь.

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

При передаче пакетов иногда применяется сжатие заголовков, например, алгоритм Ван Якобсона (RFC-1144). Этот алгоритм используется при скоростях передачи менее 64 Кбит/с. При этом достижимо повышение пропускной способности на 50% для скорости передачи 4800 бит/с. Сжатие заголовков зависит от типа протокола. При передаче больших пакетов на сверх высоких скоростях по региональным сетям используются специальные канальные алгоритмы, независящие от рабочих протоколов. Канальные методы сжатия информации не могут использоваться для сетей, базирующихся на пакетной технологии, SMDS (Switched Multi-megabit Data Service), ATM, Х.25 и Frame Relay. Канальные методы сжатия дают хорошие результаты при соединении по схеме точка-точка, а при использовании маршрутизаторов возникают проблемы - ведь нужно выполнять процедуры сжатия/декомпрессии в каждом маршрутизаторе, что заметно увеличивает суммарное время доставки информации. Возникает и проблема совместимости маршрутизаторов, которая может быть устранена процедурой идентификации при у становлении виртуального канала.

Иногда для сжатия информации используют аппаратные средства. Такие устройства должны располагаться как со стороны передатчика, так и со стороны приемника. Как правило, они дают хорошие коэффициенты сжатия и приемлемые задержки, но они применимы лишь при соединениях точка-точка. Такие устройства могут быть внешними или встроенными, появились и специальные интегральные схемы, решающие задачи сжатия/декомпрессии. На практике задача может решаться как аппаратно, так и программно, возможны и комбинированные решения.

Если при работе с пакетами заголовки оставлять неизмененными, а сжимать только информационные поля, ограничение на использование стандартных маршрутизаторов может быть снято. Пакеты будут доставляться конечному адресату, и только там будет выполняться процедура декомпрессии. Такая схема сжатия данных приемлема для сетей Х.25, SMDS, Frame Relay и ATM. Маршрутизаторы корпорации CISCO поддерживают практически все режимы сжатия/декомпрессии информации, перечисленные выше.

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

12.1 Алгоритм Зива-Лемпеля

Большинство алгоритмов сжатия базируется на последовательной схеме сжатия Лемпеля-Зива {Lempel-Ziv, 1977). Этот алгоритм используется, в частности, стандартной процедурой UNIX Compress. Методики со статистическим моделированием могут обеспечить лучшее сжатие, но они заметно медленнее. Но существует алгоритм, который совмещает в себе лучшие из черт названных выше. Этот алгоритм не предусматривает последовательной обработки входных данных, а обрабатывает текст по-блочно. Здесь используется обратимое преобразование блока данных к виду, который позволяет эффективно сжать данные с помощью простых алгоритмов. Преобразование имеет целью сгруппировать символы так, чтобы вероятность появления последовательностей идентичных символов значительно возросла. Такой текст может быть легко сжат посредством локально- адаптивных алгоритмов в сочетании с кодировкой Хафмана и арифметической кодировкой.

Последовательность S, содержащая N символов ({S(0),... S(N-l)}), подвергается N циклическим сдвигам (вращениям), лексикографической сортировке, а последний символ при каждом вращении извлекается. Из этих символов формируется строка L, где i-ый символ является последним символом i-ro вращения. Кроме строки L создается индекс I исходной строки S в упорядоченном списке вращений. Существует эффективный алгоритм восстановления исходной последовательности символов S на основе строки L и индекса I. Процедура сортировки объединяет результаты вращений с идентичными начальными символами. Предполагается, что символы в S соответствуют алфавиту, содержащему К символов.

Для пояснения работы алгоритма возьмем последовательность S= "abraca" (N=6), алфавит Х= {'a^,,^,b^,,^,c^,,^,r'}.

1. Формируем матрицу из N*N элементов, чьи строки представляют собой результаты циклического сдвига (вращений) исходной последовательности S, отсортированных лексикографически. По крайней мере одна из строк М содержит исходную последовательность S. Пусть I является индексом строки S. В приведенном примере индекс 1=1, а матрица М имеет вид: Номер строки

2. Пусть строка L представляет собой последнюю колонку матрицы М с символами L[0],...,L[N-1] (соответствуют M[0,N-1],...,M[N-1,N-1]). Формируем строку последних символов вращений. Окончательный результат характеризуется (L,I). В данном примере L=^,cai'aab', I =1.

Процедура декомпрессии использует L и I. Целью этой процедуры является получение исходной последовательности из N символов (S).

1. Сначала вычисляем первую колонку матрицы М (F). Это делается путем сортировки символов строки L. Каждая колонка исходной матрицы М представляет собой перестановки исходной последовательности S. Таким образом, первая колонка F и L являются перестановками S. Так как строки в М упорядочены, размещение символов в F также упорядочено. F='aaabcr'.

2. Рассматриваем ряды матрицы М, которые начинаются с заданного символа ch. Строки матрицы М упорядочены лексикографически, поэтому строки, начинающиеся с ch упорядочены аналогичным образом. Определим матрицу М', которая получается из строк матрицы М путем циклического сдвига на один символ вправо. Для каждого i=0,..., N-1 и каждого j=0,...,N-1,

M'[i,j]=m[i,(j-l)modN]

В рассмотренном примере М и М' имеют вид:

Подобно М каждая строка М' является вращением S, и для каждой строки М существует соответствующая строка М\ М' получена из М так, что строки М' упорядочены лексикографически, начиная со второго символа. Таким образом, если мы рассмотрим только те строки М', которые начинаются с заданного символа ch, они должны следовать упорядоченным образом с учетом второго символа. Следовательно, для любого заданного символа ch, строки М, которые начинаются с ch, появляются в том же порядке что и в М', начинающиеся с ch. В нашем примере это видно на примере строк, начинающихся с 'а'. Строки 'aabrac', 'abraca' и 'acaabr' имеют номера 0, 1 и 2 в М и 1, 3, 4 в М'.

Используя F и L, первые колонки МиМ' мы вычислим вектор Т, который указывает на соответствие между строками двух матриц, с учетом того, что для каждого j = О,...,N-1 строки j М' соответствуют строкам T[j] М.

Если L[j] является к-ым появлением ch в L, тогда T[j]=l, где F[i] является к-ым появлением ch в F. Заметьте, что Т представляет соответствие один в один между элементами F и элементами L, a F[T[j]] = L[j]. В нашем примере Т равно: (4 0 5 1 2 3).

3. Теперь для каждого i = 0,..., N-1 символы L[i] и F[i] являются соответственно последними и первыми символами строки i матрицы М. Так как каждая строка является вращением S, символ L[i] является циклическим предшественником символа F[i] в S. Из Т мы имеем F[T[j]] = L[j]. Подставляя i =T[j], мы получаем символ L[T(j)], который циклически предшествует символу L[j] в S.

Индекс I указывает на строку М, где записана строка S. Таким образом, последний символ S равен L[I]. Мы используем вектор Т для получения предшественников каждого символа: для каждого i = 0,...,N-1 S[N-l-i] = L[T[I]], где T°[x] =х, a Tⁱ⁺¹[x] = Т[Т[х]. Эта процедура позволяет восстановить первоначальную последовательность символов S ('abraca').

Последовательность Т'[1] для i =0,...,N-1 не обязательно является перестановкой чисел 0,...,N-1. Если исходная последовательность S является формой Z^p для некоторой подстановки Z и для некоторого р>1, тогда последовательность Т'[1] для i = 0,...,N-1 будет также формой Z^p для некоторой субпоследовательности Z'. Таким образом, если S = 'cancan', Z = 'can' и р=2, последовательность Т'[1] для i = 0,...,N-1 будет [2,4,0,2,4,0].

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

Возьмем в качестве примера букву "t" в слове 'the' и предположим, что исходная последовательность содержит много таких слов. Когда список вращений упорядочен, все вращения, начинающиеся с 'he', будут взаимно упорядочены. Один отрезок строки L будет содержать непропорционально большое число 't', перемешанных с другими символами, которые могут предшествовать 'he', такими как пробел, 's', 'Т' и 'S'.

Аналогичные аргументы могут быть использованы для всех символов всех слов, таким образом, любая область строки L будет содержать большое число некоторых символов. В результате вероятность того, что символ 'eh' встретится в данной точке L, весьма велика, если eh встречается вблизи этой точки L, и мала в противоположном случае. Это свойство способствует эффективной работе локально адаптивных алгоритмов сжатия, где кодируется относительное положение идентичных символов. В случае применения к строке L, такой кодировщик будет выдавать малые числа, которые могут способствовать эффективной работе последующего кодирования, например, посредством алгоритма Хафмана.

12.2 Локально адаптивный алгоритм сжатия

Этот алгоритм используется для кодирования (L,I), где L строка длиной N, а I - индекс. Это кодирование содержит в себе несколько этапов.

1. Сначала кодируется каждый символ L с использованием локально адаптивного алгоритма для каждого из символов индивидуально. Определяется вектор целых чисел R[0],...,R[N-1], который представляет собой коды для символов L[0],...,L[N-1]. Инициализируется список символов Y, который содержит в себе каждый символ из алфавита X только один раз. Для каждого i = 0,...,N-1 устанавливается R[i] равным числу символов, предшествующих символу L[i] из списка Y. Взяв Y = ['a','b','c','r'] в качестве исходного и L = 'caraab', вычисляем вектор R: {2 1 3 1 0 3).

2. Применяем алгоритм Хафмана или друтой аналогичный алгоритм сжатия к элементам R, рассматривая каждый элемент в качестве объекта для сжатия. В результате получается код OUT и индекс I.

Рассмотрим процедуру декодирования полученного сжатого текста (OUT,I).

Здесь на основе (OUT,I) необходимо вычислить (L,I). Предполагается, что список Y известен.

1. Сначала вычисляется вектор R, содержащий N чисел: (213103).

2. Далее вычисляется строка L, содержащая N символов, что дает значения R[0],...,R[N-1]. Если необходимо, инициализируется список Y, содержащий символы алфавита X (как и при процедуре кодирования). Для каждого i = 0,...,N-1 последовательно устанавливается значение L[i], равное символу в положении R[i] из списка Y (нумеруется, начиная с 0), затем символ сдвигается к началу Y. Результирующая строка L представляет собой последнюю колонку матрицы М. Результатом работы алгоритма будет (L,I). Взяв Y = ['a^,,^,b^,,^,c^,,^,r'] вычисляем строку L = 'caraab'.

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

Для того чтобы сжать строку S, сначала сформируем строку S', которая является объединением S с EOF, новым символом, который не встречается в S. После этого используется стандартный алгоритм к строке S'. Так как EOF отличается от прочих символов в S, суффиксы S' сортируются в том же порядке, как и вращения S'. Это может быть сделано путем построения дерева су^гффиксов, которое может быть затем обойдено в лексикографическом порядке для сортировки суффиксов. Для этой цели может быть использован алгоритм формирования дерева суффиксов Мак-Крейгта. Его быстродействие составляет 40% от наиболее быстрой методики в случае работы с текстами. Алгоритм работы с деревом суффиксов требует более четырех слов на каждый исходный символ. Манбер и Майерс предложили простой алгоритм сортировки суффиксов строки. Этот алгоритм требует только двух слов на каждый входной символ. Алгоритм работает сначала с первыми i символами суффикса а за тем, используя положения суффиксов в сортируемом массиве, производит сортировку для первых 2i символов. К сожалению этот алгоритм работает заметно медленнее.

В работе [1] предложен несколько лучший алгоритм сортировки суффиксов. В этом алгоритме сортируются суффиксы строки S, которая содержит N символов S[0,...,N-1].

1. Пусть к число символов, соответствующих машинному слову. Образуем строку S' из S путем добавления к символов EOF в строку S. Предполагается, что EOF не встречается в строке S.

2. Инициализируем массив W из N слов W[0,...,N-1] так, что W[i] содержат символы S'[i,...,i+k-l] упорядоченные таким образом, что целочисленное сравнение слов согласуется с лексикографическим сравнением для к-символьных строк. Упаковка символов в слова имеет два преимущества: это позволяет для двух префиксов сравнить сразу к байт и отбросить многие случаи, описанные ниже.

3. Инициализируется массив Y из N целых чисел. Если элемент V содержит]*, он представляет собой суффикс S', чей первый символ равен S'[j]. Когда выполнение алгоритма завершено, суффикс V[i] будет i-ым суффиксом в лексикографическом порядке.

4. Инициализируем целочисленный массив Y так, что для каждого i = 0,...,N-1:V[i]=i.

5. Сортируем элементы V, используя первые два символа каждого суффикса в качестве ключа сортировки. Далее для каждого символа ch из алфавита выполняем шаги 6 и 7. Когда эти итерации завершены, Y представляет собой отсортированные суффиксы S и работа алгоритма завершается.

Не нашли, что искали? Воспользуйтесь поиском: