Раздел «Алгоритмы».SuffixArray:

Суффиксный массив

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

-ЭПИКТЕТ (EPICTETUS), Беседы IV.i

Содержание

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

Немного теории

Пусть даны T[1 .. m] – исходный «текст» длины m и строка P[1 .. n] – та самая подстрока, которую мы ищем. Мы будем говорить, что ω – префикс, или начало строки x, если существует такая строка y, что x = ωy (конкатенация). Будем говорить, что ω – суффикс строки x, если существует такая строка y, что x = yω. Заметим, что как ω, так и y могут быть пустыми строками. Например, для строки «abcdeab» префиксами будут: «», «a», «ab», «abc», … , «abcdeab». А суффиксами будут: «», «b», «ab», «eab», … , «abcdeab». Каждый суффикс однозначно задаётся числом – позицией, с которой он начинается в строке. В строке «abcdeab» суффикс «deab» начинается с 4-й позиции, а суффикс «bcdeab» со 2-й. Для удобства суффикс текста T, начинающийся с s-й позиции бдем обозначать T[s .. m]. Так вот. Запишем все суффиксы исходного текста, начиная с 1-й позиции, заканчивая m-й. Пусть T = “suffix”. Затем отсортируем суффиксы в таблице в лексикографическом порядке. Тогда таблицы должны выглядеть следующим образом: 

  Было:            
N   s   Суффикс
1   1   suffix
2   2   uffix
3   3   ffix
4   4   fix
5   5   ix
6   6   x


Стало:

N   s   Суффикс
1   3   ffix
2   4   fix
3   5   ix
4   1   suffix
5   2   uffix
6   6   x

Вот теперь можно записать полученные значения s в массив. И получится у нас массив Pos[1 .. m]. В данном примере массив Pos будет выглядеть так:

Pos = [3, 4, 5, 1, 2, 6].

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

Бинарный поиск

Суть бинарного поиска проста. Пусть нам дан отсортированный по возрастанию массив, например, чисел. И мы ищем число x. А возьмём-ка мы число из серединки массива. Это будет y. Очевидно, что если x < y, то поиск следует продолжить в левой части массива, а если x > y, то — в правой части массива. И, наконец, если x == y, то поиск закончен. На каждом шаге область поиска уменьшается в два раза. Если изначально мы имеем массив из N = 2^20 элементов, то за 20 шагов мы точно найдем искомый элемент или два числа, между которыми он должен стоять.

Итак…

Двоичный поиск можно применить к лексикографически-отсортированным строкам: 

function BinSearch(left, right)
   middle = (left + right) / 2
   if P есть префикс T[Pos[middle] .. m] then
      запоминаем результат — middle
      BinSearch(left, middle &#8211; 1)
      BinSearch(middle + 1, right)
   end else if P < T[Pos[middle] .. m] then
      BinSearch(left, middle &#8211; 1)
   end Else BinSearch(middle + 1, right)
end

Это несколько упрощённый псевдокод, но он передаёт суть. Давайте его оптимизировать. Во-первых, зачем запоминать каждое найденное место middle? Ясно, что найденные места идут подряд.

Найдем такие imin и imax, что T[Pos[imin] .. m] – самый левый суффикс в отсортированном массиве, префиксом которого является P, а T[Pos[imax] .. m] – самый правый суффикс, префиксом которого является P.

Совершенно очевидно, что, так как массив Pos задаёт лексикографически-отсортированные суффиксы, то для любого imin ≤ i ≤ imax строка P будет префиксом суффикса T[Pos[i] .. m]. Поэтому ответом на вопрос задачи (все вхождения P в T) будет кусок массива Pos[imin .. imax].

Выполняться приведённый код будет за время O(n log m) (напомним, что n — длина P). А именно, число рекурсивных вызовов ограничено log m, и на каждой итерации будет за время O(n) проверятся, является P префиксом T[Pos[middle] .. m] или нет. Время O(n log m) растёт с длиной искомой строки P линейно. Иногда это слишком дорогое удовольствие. Будем оптимизировать дальше.

mlr-оптимизация

Что не совсем хорошо в приведённом коде? То, что P сравнивается каждый раз целиком, в то время как на последних итерациях большой префикс P может быть префиксом T[Pos[middle] .. m]. Для того чтобы узнать P < T[Pos[middle] .. m] или P > T[Pos[middle] .. m] алгоритм будет бежать по первым одинаковым буквам P и T[Pos[middle] .. m] пока не найдёт место, где буквы различаются. По этим одинаковым буквам он будет бегать на каждой следующей итерации.

Введём новую функцию lcp(str1, str2), которая для двух строк выдаст длину их общего префикса. Если в самом начале бинарного поиска сделать следующее: mlr = min(lcp(P, T[Pos[left] .. m]), lcp(P, T[Pos[right] .. m]), то в дальнейшем на первые mlr символов суффиксов в диапазоне от Pos[left] до Pos[right] можно «забить», и проверять только оставшиеся хвостики строк. Это даёт оценку времени работы запроса как O(n + log m), что несколько лучше.

Код на Руби

На языке Руби все эти идеи довольно быстро воплощаются в жизнь. Мы мало того, что напишем класс SuffixArray, так ещё и коснёмся классики – тестировать работу будем на романе Шолохова «Тихий Дон», на благо, оно большое. 

# Создает суффиксный массив для данного текста
# Пусть длина текста равна m. а длина искомой подстроки - n
# Тогда время препроцессинга (initialize) - O(m * m * logm)
# Время поиска (lookup) - O(n * log m), а при 
# использованиии mlr-оптимизации - O(n + logm)

# Подключаем модуль для тестирования прораммы
require 'benchmark'
#
class SuffixArray
protected
# Служебные функции минимума и максимума
 def min(x, y)
   (x < y ? x : y)
 end
 def max(x, y)
   (x > y ? x : y)
 end
  # А это - собственно функция lcp. 
  # Известно, что искать будем в строках 
  # text и term (аналоги T и # P) поэтому есть 
  # смысл задавать только позиции, с которых 
  # начнётся поиск длины общего префикса.
  def lcp(pos_term, pos_text)
    ret = 0
    while pos_term < @term.size && @term[pos_term] == @text[pos_text]
      ret += 1
      pos_term += 1
      pos_text += 1
    end
    # Q: Почему нет проверки pos_text < @text.size? 
    # A: Потому что @text[pos_text] = nil, если pos_text >= @text.size
    ret # Возвращаем lcp в виде счётчика ret
  end

  # Функция сравнения - меньше, больше либо равно для term'а и серединки. 
  # 0   - term является  префиксом, 
  # -1  - меньше, 
  # 1   - больше
  def cmp_prefix(pos_term, pos_text)
    shared = lcp(pos_term, pos_text)
    return 0 if shared + pos_term == @term.size
    return @term[shared + pos_term] <=> @text[shared + pos_text]
  end

  # Процедура бинарного поиска.
  def bin_search_mlr(left, right, mlr)
    return if left > right
    middle = (left + right) / 2
    mlr += min(lcp(mlr, mlr + @pos[left]), lcp(mlr, mlr + @pos[right]))
    res = cmp_prefix(mlr, @pos[middle] + mlr)
    if res == 0
      @min = middle if middle < @min
      @max = middle if middle > @max
      bin_search_mlr(left, middle - 1, mlr)
      bin_search_mlr(middle + 1, right, mlr)
    elsif res < 0
      bin_search_mlr(left, middle - 1, mlr)
    else
      bin_search_mlr(middle + 1, right, mlr)
    end
  end

  public

  # Конструктор суффиксного массива.
  def initialize(text, max_search_size=50)
    @text = text
    # То есть на деле мы сортируем массив чисел от 0 до m - 1.
    # Только в качестве сравнения - слова
    # Кстати - сравнивать можно только первые wordsize символов -
    # Это несколько ускоряет процесс сортировки. 
    # Взамен &#8211; невозможность искать термы большей длины.
    @pos = (0 ... text.size).sort_by {|i| 
      text[i ... min(i + max_search_size, text.size)] 
    }
  end

  # Lookup возвращает результат поиска - 
  def lookup(term)
   @term = term
   # Изначально заведомо "нехорошие" значения.
   @min = @text.size
   @max = -1
   bin_search_mlr(0, @text.size - 1, 0)
   # Возвращаем кусок массива Pos от @min до @max.
   @pos[@min .. @max]
 end
end


text = ""
out = []
object = nil

# Собственно, процесс тестирования
Benchmark.bm(4) do |b|
  # Отдельная графа для считывания текста
  b.report("read...") do
    text = File.open("c:/don.txt").read
    # Как вариант -
    # text = Net::HTTP.get(URI.parse('http://www.lib.ru/PROZA/SHOLOHOW/tihijdon12.txt'))
  end
  # Собственно, препроцессинг. Самая долгая часть.
  b.report("init...") do
    object = SuffixArray.new(text, 8)
  end
  # Ищем слово "баркас" и печатаем &#8211; 
  # сколько раз оно встречается - это 
  # размер возвращаемого массива.
  b.report("lookup баркас ") do
    out = object.lookup("баркас")
    puts out.size
  end

  # Аналогичные манипуляции со словом "война"
  b.report("lookup война ") do
    out = object.lookup("война")
    puts out.size
  end

  # ... имя главного героя
  b.report("lookup Гриша ") do
    out = object.lookup("Гриша")
    puts out.size
  end
  
  # и немного от себя
  b.report("lookup руби ") do
    out = object.lookup("руби")
    puts out.size
  end
end

Всё. Можно идти пить кофе. Результатом вывода программы будет: 

          user     system      total        real
read...  0.000000   0.031000   0.031000 (  0.032000)
init... 84.454000   0.594000  85.048000 ( 85.109000)
lookup баркас 51
  0.000000   0.000000   0.000000 (  0.000000)
lookup война 63
  0.000000   0.000000   0.000000 (  0.000000)
lookup Гриша 164
  0.016000   0.000000   0.016000 (  0.016000)
lookup руби 120
  0.015000   0.000000   0.015000 (  0.016000)

Так мы опытным путём доказали, что Руби – очень древний язык — ещё Шолохов упоминал о нём по меньшей мере 120 раз. Первое число в приведённом отчёте – время работы функции в user-space. Второе – сколько работало ядро системы. Третье – арифметическая сумма первых двух. Последнее – сколько оттикало на настенных часах, то есть можно установить, как сильно отвлекался процессор от задачи выполнения нашей программы на другие задачи. Как видим - весьма быстро выполняются запросы, но зато весьма долго – препроцессинг (тест выполнялся на Celeron 2.40 GHz, 480 Мб ОЗУ). Полторы минуты для такой машины – это неэффективно. Надо улучшить результат.

Действительно, сортировка с помощью встроенного метода sort_by это, конечно хорошо, но только если нам мало, что известно о сортируемых элементах. А это не так. Мы сортируем суффиксы, все их длины различны и меняются от 1 до max_search_size. Суть оптимизированной сортировки такова:

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

Ссылки

AlgorithmClasifyForm
Type:  
Scope:  
Strategy:  
Language:  
Complexity: Low

Attachment sort Action Size Date Who Comment
SuffixArrays-ruby.doc manage 88.5 K 24 Jun 2008 - 09:03 ArtemVoroztsov  
icalp03.pdf manage 188.2 K 30 Aug 2008 - 18:53 ArtemVoroztsov Линейный алгоритм построения суффиксного массива
don-koi8r.zip manage 627.7 K 30 Aug 2008 - 19:17 ArtemVoroztsov "Тихий дон", Михаил Шлохов. Кодировка koi8r.
don-win.zip manage 628.0 K 30 Aug 2008 - 19:17 ArtemVoroztsov "Тихий дон", Михаил Шлохов. Кодировка windows.