Лекция 1_12: Наибольшая общая подпоследовательность двух строк

Постановка задачи

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

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

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

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



Что такое строки, и зачем ими заниматься

Психологически удобно иметь в качестве основного примера строку текста, и подготовка к определениям начинается с фразы:

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

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

      аааааааахахахааааа
      пришелувиделпобедил
      эта строка незаконная

 Действительно, последний пример ошибочен. Почему?

Количество букв в строке называется ее длиной. Строка нулевой длины называется пустой строкой.

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

      пришелувиделпобедил

 есть подстрока обед и нет подстроки депо.

Подстроку легко задать, указав ее позицию начальной буквы и длину (для подстроки обед это (14,4), если символы нумеруются от 1, и (13,4) при нумерации от 0).

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

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



Строки в языках программирования

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

В тексте программы переменные строки описываются очень просто:

sName: string;

Строковые константы заключаются в апострофы:

const
    sOrg = 'матмех СПбГУ';

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

В языке Си строки рассматриваются как последовательности байтов, записанных подряд. Строка заканчивается байтом с нулевым значением, поэтому байты с нулевым значением внутри строки не разрешаются. Такой формат принято называть ASCIIZ (ASCII + Zero). Размещение строки в памяти оставляется на усмотрение самого програм­миста. В этом языке вычисление длины строки — это именно вычисление. Впрочем, в системе команд процессоров персональных компьютеров уже давно есть команда просмотра памяти до нахождения байта с нужным значением, так что функция, вычисляющая длину строки работает очень быстро.

В языке С++ тип строка уже есть, размещением строки занимается система.



Операции над строками

Перечислим те операции, которые мы уже рассмотрели, и добавим некоторые новые.

  1. Вычисление длины строки.

  2. Выделение подстроки (префикса, суффикса, произвольного фрагмента).

  3. Ивертирование строки. Эта операция с текстовыми строками используется редко, а в числовых строках встречается.

  4. Конкатенация строк — соединение нескольких подряд расположенных строк в одну. Иногда говорят катенация строк. Слово происходит от латинского catena — цепь. Так что слово сцепление тоже вполне бы подошло.

  5. Сравнение строк. Часто на множестве строк нужно ввести упорядочение. Обычно оно определяется упорядочением букв алфавита и называется лексикографическим. Оно нам уже встречалось, но еще кое-что нам придется обсудить.

  6. Поиск образца. Очень важная операция. Есть две строки: длинная T — текст и короткая P — образец (от Text и Pattern). Нужно найти в строке подстроки, совпадающие с образцом. Это очень важная операция, о ней мы будем говорить отдельно.

  7. Подстановка — фрагмент строки заменяется чем-то другим. Эта операция включает в себя предыдущую.

  8. Поиск максимального совпадения двух строк. Рассмотрим отдельно.

  9. Нахождение редакционного расстояния. Рассмотрим отдельно.
А теперь рассмотрим подробно те операции, о которых мы раньше не говорили или говорили недостаточно.



Сравнение строк

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

В тексте программы переменные строки описываются очень просто:

sName: string;

Строковые константы заключаются в апострофы:

const
    sOrg = 'матмех СПбГУ';

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

В языке Си строки рассматриваются как последовательности байтов, записанных подряд. Строка заканчивается байтом с нулевым значением, поэтому байты с нулевым значением внутри строки не разрешаются. Такой формат принято называть ASCIIZ (ASCII + Zero). Размещение строки в памяти оставляется на усмотрение самого програм­миста. В этом языке вычисление длины строки — это именно вычисление. Впрочем, в системе команд процессоров персональных компьютеров уже давно есть команда просмотра памяти до нахождения байта с нужным значением, так что функция, вычисляющая длину строки работает очень быстро.

В языке С++ тип строка уже есть, размещением строки занимается система.



Монотонность длин кодовых последовательностей


Лемма 1. Пусть алфавит A состоит из n символов с вероятностями p1, p2, ... pn. Пусть длины кодовых последовательностей этих символов в оптимальном коде равны соответственно r1, r2, ... nk.

Тогда ни для какой пары различных индексов k и l не могут одновременно выполняться неравенства

       pk < pl    и    rk < rl .

Доказательство. Действительно, при выполнении этих неравенств верно и неравенство

       (pl − pk) · (rl − rk) > 0.

Это неравенство можно переписать так

       pl · rl + pk · rk > pl · rk + pk · rl.

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

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



Упражнения


  1. Подсчитайте частоты символов во фразе и по этим частотам постройте код Хаффмена
    • на_дворе_трава_на_траве_дрова_не_руби_дрова_на траве_двора
    • aaabbaaabbababababaaaaabbbaaaabbbaaabbbbaaabbbdadadadadadddddaaa
    • мороз_и_солнце_день_чудесный_еще_ты_дремлешь_друг_прелестный (А. Пушкин)
    • майомбе_бомбе_майомбе_майомбе_бомбе_майомбе_майомбе_бомбе_майомбе_ (Н. Гильен)
    Подсчитайте математическое ожидание длины кодовой комбинации.

  2. Закодируйте полученным кодом вторую строку, переведите результат в 16-ричную систему счисления и разбейте на байты.
  3. Постройте код Хаффмена для строки, полученной в результате работы преобразования MTF.
  4. Методом LZ сожмите строку aaaaabbaabaaaabbaabbaaaaabbbbaaaaaa.
  5. Эту же строку сожмите методом LZW, а затем восстановите исходную строку из сжатого текста.
  6. Методом Баррооуза-Уилера сожмите строку 4 из первого упражнения.



Экзаменационные вопросы


  1. Операции над строками.

  2. Лексикографическое сравнение строк.

  3. Нахождение редакционного расстояния.

  4. Поиск образца в строке методом Карпа-Рабина.

  5. Поиск образца в строке с помощью Z-преобразования.