Определение.

Функция f называется функцией отказов и задается следующим образом:

.

Т.е. f( j ) равна максимальному s, такому, для которого x₁…x_s – суффикс цепочки x₁…x_j,

Пример.

Пусть y = aabbaab. Функция f принимает значения :

Например, f(6) = 2, так как aa  самый длинный собственный префикс цепочки aabbaa, который является ее суффиксом.

Алгоритм 6.1a.

Вход. Слово x длины n, цепочка str длины m.

Выход. Значение переменной FOUND = True, если слово x содержится в строке str,

FOUND = False в противном случае.

Для вычисления функции отказов используется алгоритм 6.1б.

FOUND = False;

r = 1;

k = 0;

while (!Found && r  m - n)

begin

while (x [ k+1] == str [ k + r ] && k < n) k++;

if ( k == n ) FOUND = True;

else

if ( k == 0) r++;

else

begin

r += k ;

k = f (k - 1);

end;

end;

Сложность алгоритма O(m+n). Так как движение по строке только вперед.

Алгоритм 6.1б. Вычисление функции отказов.

Вход. Цепочка-образ x = x₁ … x_n, n  1.

Выход. Функция отказов f для x.

begin

f(1) = 0;

for j = 2 to n

begin

i = f(j – 1);

while (x[ i ]  x[ i+1] && i > 0) do i = f (i);

if (x[i]  x[i+1] && i==0) then f(j) = 0;

else f(j) = i+1;

end;

end

Теорема 6.2.

1. Алгоритм 6.1.Б вычисляет f за o(n) шагов.

2. Алгоритм 6.1.а работает за O(n + m) шагов.



1. Строки алгоритма “i = f(j–1);” и “ if (x[i]x[i+1]&& i==0) then f(j) = 0;” имеют фиксированную сложность. Сложность while-оператора пропорциональна числу уменьшений значения i оператором i = f (i). Единственный способ увеличить i  это присвоить f(j) = i+1, затем увеличить j на единицу в цикле и положить i = f(j – 1). Так как вначале i = 0, а строка ” else f(j) = i+1; ” выполняется не более n-1 раз, то while-оператор не может выполняться более n раз. Поэтому строка “ while (x[ i ]  x[ i+1] && i > 0) do i = f (i);” требует O(n) времени. Остальная часть алгоритма имеет сложность O(n), и поэтому весь алгоритм тратит O(n) времени.

2. С помощью аналогичных рассуждений можно доказать, что при обработке входной цепочки str срока “ while (x [k+1] == str [k+r]&& k < n) k++;” алгоритма 6.1.а выполнится не более 2m раз. Поэтому можно узнать, является ли x подцепочкой str, проследив изменение переменной k. Для этого надо лишь знать значения функции отказов на x. По пункту 1 значения функции f можно найти за время O(n). Следовательно, узнать, является ли x подцепочкой цепочки str, можно за время O(n + m), не зависящее от размера алфавита.



Теорема 6.3.

Пусть необходимо распознать вхождение сразу k цепочек x₁,…,x_k.

Алгоритмом 6.1. вычисляет f за O( (n_k+m))   + km.

k

6.1. Текстовая компрессия.

Алгоритмы:

1. RLE.

2. Huffman.

3. Арифметический.

4. Дельта-кодирование (DPCM/ADRM).

5. LZ.

6. LZW.

7. (LZ/LZW+2) / 3.

Алгоритм LZ и LZW

Алгоритм данного класса заменяет последовательность символов из кодируемого потока данных на адрес соответствующей строки в словаре.

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

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

Схема LZW

а) Кодирование

Инициализация словаря

Установка текущей позиции в начале текста.

Пока весь текст не записан, выделить наиболее длинную, начинающуюся с

текущей позиции, подстроку S, для которой есть соответствие в словаре.

Записать в архив номер позиции P найденной в словаре подстроки.

Посмотреть следующий за подстрокой в тексте символ k, занести в словарь

подстроку sk . Продвинуть текущую позицию, чтобы она указывала на символ k.