Изменения

{{В разработке}}'''Алгоритм Фарача Фараха''', разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach,(1997)-Colton)''' {{---}} алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполнятеся выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнения выполнение условия конечности алфавита. Такая эффективность достигается за счет счёт того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике. Важно помнить, что алгоритм скорее теоретический, чем нежели практический, а основная его ценность его заключается в том, что размер алфавита может быть произвольным.

== Описание алгоритма ==

Основная идея Идея алгоритма заключается состоит в том, что мы уменьшаем размер исходной строки, строим суффиксное дерево для неё рекурсивно, а потом получаем из того дерева нашепостроенного дерево для текущей строки. Для этого мы разбиваем символы сходной исходной строки на пары и пронумеровываем нумеруем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче.

Алгоритм Фарача Фараха будет описан в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>\Sigma = \{1, 2\} </tex> (в этом примере <tex>N = 12</tex>).

*: (если символов нечетное нечётное число {{---}} последняя пара дополняется специальным символом <tex>\$</tex>).* Пары сортируются устойчивой сотрировкой сортировкой (удобно сортировать [[Цифровая_сортировка | поразрядной]], так как число разрядов мало, размер алфавита — <tex>O(n)</tex>, поэтому то время работы сортировки — линейное): <tex> \langle 11 \rangle \langle 12\rangle \langle 12\rangle \langle 21\rangle \langle 21\rangle \langle22\rangle </tex>.

* Парам даются номера (условно, в массиве они и так есть): <tex>\langle 11\rangle -(0), \langle 12\rangle -(1), \langle 21\rangle -(2), \langle 22\rangle-(3)</tex>.* В исходной строке пары заменяются на номера: <tex>1 0 1 2 3 2</tex>.* Из полученной строки вдвое меньшего размера рекурсивно создаётся [[Сжатое суффиксное дерево | суффикcное дерево]] тем же алгоритмом:[[Файл:tree101232.png|300px|суффиксное дерево для сжатой строки]]* рекурсия Рекурсия не продолжается, если строка имеет длину <tex>1</tex>, равную единице: возвращается суффиксное дерево из одной вершиныстроится тривиально.

|definition= Четное Чётное дерево <tex>T^{even}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья которого ограничены четными чётными позициями <tex>0,2,4,6, \dots </tex> строки <tex>s\$</tex>.}} [[Файл:Tree101232even-pre.png|thumb|300px|Раскрываем все пары в суффиксы]][[Файл:Tree101232even.png|thumb|300px|Корректируем все развилки дерева]]

Номер каждой пары превращается в номер четного чётного суффикса исходной строки. Раскрываем все пары в суффиксы, а из-за чего номера в листьях от этого умножатся на <tex>2</tex> очевидным образом. Корректируем все развилки дерева (так как они могут совпадать в первых символах):для всех внутренних вершин <tex>u</tex>, ребра всех детей которых начинаются с одинаковых символов, мы создадим новую вершину между <tex>u</tex> и ее детьми. Это можно сделать быстро, так как все ребра, исходящие из любой вершины, лексикографически отсортированы по своим первым двум символам (так как мы сортировали номера пар на прошлом шаге). Для каждого ребра нам достаточно проверить, что его первый символ соответствует первому символу соседнего ребра, и, если так, сделать необходимые исправления. Может случиться, что ребра ко всем детям <tex>u</tex> начинаются с одинакового символа, и в этом случае у вершины <tex>u</tex> будет только один ребенок. Тогда удалим <tex>u</tex>.Эта процедура требует константное время на каждое ребро и константное время на каждую вершину, а значит, на нее требуется линейное время. Итак, если <tex>T(n)</tex> {{---}} это время, которое потребуется нашему алгоритму, чтобы построить суффиксное дерево для строки <tex>S</tex>, то <tex>T_{even}</tex> может быть построено за время <tex>T(n/2) + O(n)</tex>         

=== Шаг 3: построение нечетного нечётного по четному чётному ===

которого ограничены нечетными нечётными позициями <tex>1,3,5, \dots </tex> строки <tex>s\$</tex>.}} Из чётного дерева нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях). Мы хотим получить лексикографически отсортированные нечетные суффиксы строки, по которым восстановим нечетное дерево. Заметим, что все нечетные суффиксы представляют собой один символ, за которым дальше следует четный суффикс, которые у нас уже отсортированы. Тогда поразрядно отсортируем их за линейное время. Таким образом <tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.

Выяснение общего префикса строк можно находить общего предка вершин в [[Сжатое суффиксное Из чётного дерева нужно получить нечётное дерево|суффиксном дереве]]. Такого предка можно найти за [http://e-maxx.ru/algo/lca_linear константное время, потратив <tex>O(nдерево из суффиксов в нечётных позициях)</tex> на препроцессинг]. Для примера в этом дереве, общее начало строк '''5''' и '''9''' (<tex>11011111000</tex> и <tex>1111011111000</tex>) записано в пути от корня до общего предка этих вершин: (рисунок 3-1)

* [[Файл:treestep3_blueСжатое_суффиксное_дерево#.jpgD0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 |400pxСтроим по чётному дереву суффиксный массив]] — это можно сделать за <tex>О(n)</tex>. * Дописываем ко всем суффиксам (кроме того, что на нулевой позиции) символ, предшествующий ему в строке. * Заметим, что все нечётные суффиксы представляют собой один символ, за которым дальше следует чётный суффикс. А чётные суффиксы у нас уже были отсортированы в суффиксном массиве. Тогда отсортируем их по первому символу за линейное время.* [[Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 |рисунок 3-1Построим из нового суффиксного массива дерево]], которое будет уже нечётным, что тоже делается за линейное время.

Поскольку структуры нечётного дерева у нас заранее нет и мы её только строимТаким образом, то подходящих предков мы можем найти в исходном чётном дереве, для этого достаточно проверить вершины с номерами на единицу меньше и отрезать первый символ : (рисунок 3-2)<tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.

[[Файл=== Шаг 4:treestep3_red.jpg|400px|рисунок 3-2]]слияние чётного и нечётного дерева ===

=== Шаг 4[[Файл: слияние четного и нечетного дерева ===Tree101232merged-pre.png|thumb|450px|Слитое дерево (условно)]][[Файл:Tree101232merged-next.png|thumb|450px|Слитое дерево (в упрощённом виде)]]

Далее необходимо найти эффективный способ слияния нечетного нечётного и четного чётного деревьев в одно дерево <tex>T_s</tex>. Слияние будем производить, начиная с корней деревьев. Предположим, что для каждого узла деревьев <tex>T_s^{odd}</tex> и <tex>T_s^{even}</tex> выходящие из них ребра занесены в специальные списки, где они '''упорядочены''' в возрастающем лексикографическом порядке подстрок, которые представляют эти ребра. Пусть каждое ребро будет дополнительно "помечено" своим первым символом. Возьмем по одному ребру из этих списков с одинаковыми метками (в одном списке не может быть ребер с одинаковыми метками, так как это сжатые суффиксные деревья), обработаем их, и рекурсивно спустимся в их поддеревья. Если для ребра из одного списка не оказалось ребра с такой же меткой из другого, то в поддеревья, очевидно, не спускаемся, так как там нечего сливать.

* если <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex> и длины подстрок, представленных соответствующими ребрами, равны, в дерево слияния к текущему узлу добавляются два сына: один {{---}} из четного чётного дерева, другой {{---}} из нечетногонечётного;

Если начать эту процедуру для корней нечётного и чётного деревьев, она рекурсивно выполнится для корней всех поддеревьев, которые, возможно, уже содержат узлы из нечетного нечётного и четного чётного деревьев, поскольку ранее мог быть реализован случай <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex>. Так как время манипулирования любым ребром этих деревьев фиксировано, то общее время слияния деревьев составит <tex>O(N)</tex>. [[Файл:Tree101232merged-pre.png|450px|Слитое дерево (условно)]]  [[Файл:Tree101232merged-next.png|450px|Слитое дерево (в упрощённом виде)]]

Разбираемся с двойными дугами (на этом примере их три). Для этого мы должны выяснить, сколько начальных символов таких у них совпадает. Совпадать может любое число символов, даже все. Проверять их все по очереди нельзя (это даст квадратичное время)[[Файл:Tree101232merged. png|thumb|500px|Откорректированное дерево строки <tex>121112212221</tex>]]Если дуги совпадают полностью, тогда ничего не делаем, удаляем одну из копий и всё. Если начало для двух дуг совпадает только частично, тогда нужно делать для них общее начало, а ветки, которые на концах, снова развести по разным деревьям (для этого можно во время слияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки)[[Файл:Treestep5_1. jpg|thumb|550px|Пример]]

[[Файл:Tree101232mergedРазбираемся с двойными дугами (в примере их три). Для этого мы должны выяснить, сколько начальных символов у них совпадает. Совпадать может любое число символов, даже все. Проверять их все по очереди нельзя, так как это даст квадратичное время. Если дуги совпадают полностью, тогда просто удаляем одну из копий. Если начало для двух дуг совпадает только частично, тогда нужно сделать для них общее начало, а ветки, которые на концах, снова развести по разным деревьям (для этого можно во время слияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки).png|500px]]

 Для примера Рассмотрим то, как это сделать возьмём строку , на примере строки <tex>10010010101000</tex>: [[Файл:Treestep5_1.jpg|550px]]

# расслоение Расслоение находится на расстоянии <tex>2</tex> от корня, то есть дуга не расслаивается.# конец Конец является родителем вершин <tex>2</tex>, <tex>7</tex>. Родитель <tex>3</tex>, <tex>8</tex> после слияния дуги <tex>(1)</tex>, находится на глубине <tex>2</tex> символа. Значит, дуга <tex>(2)</tex> расслаивается на глубине <tex>3</tex> символа, то есть так же также не расслаивается. Дугу <tex>(2)</tex> нужно вычислять после обработки дуги <tex>(1)</tex>, потому что конец дуги <tex>(1)</tex> после обработки может оказаться на разной высоте, в зависимости от того на каком символе она расслоилась.# конец Конец является родителем <tex>2</tex>, <tex>9</tex>. Родитель <tex>3</tex>, <tex>10</tex> находится на расстоянии <tex>3</tex>, а наше расслоение на расстоянии <tex>4</tex>, то есть сливается первый символ двойной дуги. Дугу <tex>(3)</tex> надо вычислять после дуги <tex>(2)</tex>. Потому что если на дуге <tex>(2)</tex> появится разветвление, то компоненты дуги <tex>(3)</tex> придётся растащить по разным веткам дерева и сравнивать их будет не нужно.# конец Конец является родителем <tex>1</tex>, <tex>4</tex>. Расслаивается на втором символе.# конец Конец является родителем <tex>0</tex>, <tex>3</tex>. Дугу <tex>(5)</tex> можно обрабатывать только после дуги <tex>(4)</tex>, так как от неё будет зависеть глубина расслоения.

Дерево после обработки: [[Файл:Treestep5_2.jpg|thumb|center|650px|Итоговое дерево строки <tex>10010010101000</tex>]]

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

==Сравнение с другими алгоритмами== ===Достоинства===*Алгоритм Фараха является первым, имеющим асимптотически оптимальное время построения <tex>O(N)</tex> для строк длины <tex>N</tex> над полиномиальным алфавитом, то есть алфавитом мощности порядка <tex>O(N)</tex>. ===Недостатки=== *Данный алгоритм является больше теоретическим, нежели практическим. Как можно было заметить, основная идея алгоритма довольно проста и понятна. И хоть он и является асимптотически оптимальным, на практике его используют довольно редко. Это связано с тем, что алгоритм весьма сложен для реализации по сравнению с другими алгоритмами построения суффиксных деревьев, а также требует достаточно большой объем памяти.*Является offline-алгоритмом, то есть требует для начала работы всю строку целиком. ==См. также==

= Ссылки = Источники информации ==

*[http://www.proteus2001.narod.ru/gen/txt/11/farach.html Суффиксное дерево {{- --}} Алгоритм фарачаФараха]