Суффиксный массив
- Оригинал: SuffixArrays-ruby.doc статья для школьников из журнала Потенциал
- Автор: Юрий Горшенин, студент ФИВТ, июнь 2007 г.
- Дальнейшее чтение: Линейный алгоритм построения суффиксного массива (локальная версия)
Прошу Вас, ради всего святого, сначала научитесь простому
И только потом переходите к сложному.
Иногда бывает необходимо для данного текста быстро отвечать на многочисленные запросы – есть ли здесь заданная подстрока, или нет, и если есть, то как часто и в каких местах встречается? Когда таких запросов действительно много,
важно, чтобы запросы выполнялись быстро. Для этого обычно осуществляют некоторый перепроцесинг текста для создания некоторой структуры данных, облегчающей поиск в тексте. Суффиксные массивы одна из возможных структур.
-ЭПИКТЕТ (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 – 1) BinSearch(middle + 1, right) end else if P < T[Pos[middle] .. m] then BinSearch(left, middle – 1) end Else BinSearch(middle + 1, right) end
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 символов - # Это несколько ускоряет процесс сортировки. # Взамен – невозможность искать термы большей длины. @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 # Ищем слово "баркас" и печатаем – # сколько раз оно встречается - это # размер возвращаемого массива. 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.
Суть оптимизированной сортировки такова:
- Отсортируем суффиксы по первой букве. Это можно сделать за O(m*Z), где Z число букв в алфавите.
- Суффиксы с одинаковой первой буквой будут лежать в одной корзине. Всего Z корзин. Суффикс T[m .. m] следует сразу поместить в начало своей корзины.
- Пройдёмся по массиву Pos. Для Pos[i] верно, что Pos[i] – 1 – суффикс будет первым в своей корзине. Ставим его на ближайшее к началу корзины место и помечаем это место как занятое. Получаем набор корзин с суффиксами, отсортированными по первым двум буквам.
- Дальше – проходим по Pos[i]. Уже для Pos[i] – 2 – суффикса верно, что он будет на первом месте в своей корзине. Ставим его на ближайшее к началу корзины место, место помечаем как занятое.
- Получаем набор корзин с суффиксами, отсортированными по первым 4-м символам.
- И т.д. Весь процесс сортировки занимает O(m log2 m). А это уже приемлимо.
Ссылки
- Линейный алгоритм построения суффиксного массива (локальная версия)
- http://ru.wikibooks.org/wiki/Ruby - книжка про Руби на русском языке.
- http://acm.mipt.ru/twiki/bin/view/Ruby/WebHome - материалы про Руби на сайте МФТИ.
- http://eigenclass.org/hiki/simple+full+text+search+engine – статья про реализацию суффиксных массивов на Руби.
- http://rain.ifmo.ru/cat/view.php/theory/unsorted/suffix-arrays-2005 - очень просто и понятно.
- Manber, Myers - Suffix arrays - A new method for on-line string searches. Книга про суффиксные массивы.
AlgorithmClasifyForm | |
---|---|
Type: | |
Scope: | |
Strategy: | |
Language: | |
Complexity: | Low |