Изменения

{{В разработке}}'''Алгоритм ФарачаФараха''' — , разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach-Colton) {{---}} алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex>, который длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, при этом причём даже не требуется выполнения выполнение условия конечности алфавита. Такая эффективность достигается за счет счёт того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 {...}\dots , ak\}</tex>, при . При этом накладывается дополнительное условие, что <tex>a \in k = O(N)</tex>. Такие алфавиты часто встречаются на практике. Важно помнить, что алгоритм скорее теоретический, нежели практический, а основная его ценность заключается в том, что размер алфавита может быть произвольным. == Описание алгоритма == Идея алгоритма состоит в том, что мы уменьшаем размер исходной строки, строим суффиксное дерево для неё рекурсивно, а потом получаем из построенного дерево для текущей строки. Для этого мы разбиваем символы исходной строки на пары и нумеруем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче. Алгоритм Фараха будет описан в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>\Sigma = \{1, 2\} </tex> (в этом примере <tex>N = 12</tex>).=== Шаг 1: суффиксное дерево для сжатой строки=== [[Файл:tree101232.png|thumb|300px|Суффиксное дерево для сжатой строки]]* Строка <tex>s</tex> разбивается на пары подряд идущих символов: <tex> \langle 12\rangle \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle \langle 21\rangle </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 \langle 12\rangle \langle 21\rangle \langle 22\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ное дерево]] тем же алгоритмом.* Рекурсия не продолжается, если строка имеет длину, равную единице: суффиксное дерево строится тривиально. === Шаг 2: построение чётного дерева ==={{Определение|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: построение нечетного нечётного по четному чётному ===

|definition= Нечетное Нечётное дерево <tex>T^{odd}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья которого ограничены нечетными нечётными позициями <tex>1,3,5,{...} \dots </tex> строки <tex>s\$</tex>.}} Из чётного дерева, нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях). Для этого можно взять суффиксный массив чётного дерева, отрезать первые символы, и выполнить стабильную сортировку по оставшимся первым символам:

[[Файл:oddOdd.png|300px|thumb|right450px| нечетное Нечётное дерево]]

Для выяснения общего префикса строк* [[Сжатое_суффиксное_дерево#.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 | Строим по чётному дереву суффиксный массив]] — это можно сделать за <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 | Построим из нового суффиксного массива дерево]], которое будет уже нечётным, общее начало строк '''5''' и '''9''' (11011111000 1111011111000) записано в пути от корня до общего предка этих вершин: (рисчто тоже делается за линейное время. 3-1)

[[Файл:treestep3_blueТаким образом, <tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.jpg|400px|рис. 3-1]]

Поскольку структуры === Шаг 4: слияние чётного и нечётного дерева у нас заранее нет и мы её только строим, то подходящих предков мы можем найти в исходном чётном дереве, для этого достаточно проверить вершины с номерами на еденицу меньше и отрезать первый символ : (рис. 3-2).===

[[Файл:treestep3_redTree101232merged-pre.jpgpng|thumb|400px450px|рисСлитое дерево (условно)]][[Файл:Tree101232merged-next. 3-2png|thumb|450px|Слитое дерево (в упрощённом виде)]]

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

Далее необходимо найти эффективный способ слияния нечетного и четного деревьев в одно дерево <tex>Т_s</tex>. Слияние будем производить начиная с корня. Предположим, что для каждого узла деревьев <tex>Т_s^{odd}</tex> и <tex>Т_s^{even}</tex> выходящие из них ребра занесены в специальные списки, где они упорядочены в возрастающем лексикографическом порядке подстрок, которые представляют эти ребра. Алгоритм слияния деревьев просматривает только первые буквы подстрок, представленных ребрами деревьев <tex>Т_sT_s^{odd}</tex> и <tex>Т_sT_s^{even}</tex>, пусть это будут буквы <tex>\lambda^{odd}</tex> и <tex>\lambda^{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>. В результате описанных действий получится дерево <tex>M_x</tex>, в котором будут присутствовать поддеревья, которые прошли процедуру слияния, и которые ее избежали (то есть были перенесены в дерево <tex>M_x</tex> без изменений). === Шаг 5: удаление двойных дуг ===

[[Файл:Tree101232merged-pre.png|450pxthumb|Слитое 500px|Откорректированное дерево (условно)строки <tex>121112212221</tex>]][[Файл:Treestep5_1.jpg|thumb|550px|Пример]]

[[ФайлРассмотрим то, как это сделать, на примере строки <tex>10010010101000</tex>:Tree101232merged-next.png|450px|Слитое дерево (в упрощённом виде)]]

В результате описанных действий получится дерево Для того чтобы узнать общее начало двойной дуги, нужно взять одну чётную и одну нечётную вершину на дереве, для которых родителем является конец нашей двойной дуги. Например, на рисунке выше двойная дуга <tex>(1)</tex> (конец помечен зелёным) является общим родителем для вершин <tex>M_x3</tex>и <tex>6</tex>. Чтобы узнать,в котором будут присутствовать поддеревья, которые прошли процедуру сличнияна каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на единицу и которые ее избежали найти их родителя. Он будет находиться на единицу ближе к корню (ти путь у вершин будет одинаковой строкой, не считая размера).е были перенесены в дерево Родитель вершин <tex>4</tex> и <tex>7</tex> помечен жёлтым, он находится на расстоянии <tex>M_x1</tex> без измененийот корня, следовательно, дуга <tex>(1)</tex> должна расслаиваться в двух символах от корня, то есть обе дуги совпадают и их просто надо слить.

== Шаг 5Разберём дуги по порядку: удаление двойных дуг ==

Разбираемся с двойными дугами (# Расслоение находится на этом примере из три)расстоянии <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>, так как от неё будет зависеть глубина расслоения.

[[Файл:Tree101232mergedTreestep5_2.pngjpg|500pxthumb|center|650px|Итоговое дерево строки <tex>10010010101000</tex>]]

Для того чтобы узнать общее начало двойной дуги, мы должны взять одну чётную и одну нечётную на дереве*Данный алгоритм является больше теоретическим, для которых родителем является конец нашей двойной дугинежели практическим. Например на рисунке выше двойная дуга (1)Как можно было заметить, конец помечен зелёным - является общим родителем для вершин 3 основная идея алгоритма довольно проста и 6понятна. Чтобы узнать на каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на еденицу И хоть он и найти их родителяявляется асимптотически оптимальным, он будет находится на еденицу ближе к корню (и путь у вершин будет одинаковой строкой, не считая размера)практике его используют довольно редко. Родителя вершин 4Это связано с тем, 7 я пометил жёлтымчто алгоритм весьма сложен для реализации по сравнению с другими алгоритмами построения суффиксных деревьев, он находится на расстоянии 1 от корняа также требует достаточно большой объем памяти.*Является offline-алгоритмом, следовательно дуга (1) должна расслаиваться в двух символах от корня, т.е. обе дуги совпадают и их просто надо слитьто есть требует для начала работы всю строку целиком.

* (1) расслоение находится на расстоянии два от корня, т.е. дуга не расслаивается.== Источники информации ==* (2) конец является родителем вершин 2, 7. Родитель 3, 8 после слияния дуги (1), находится на глубине 2 символа. Значит дуга (2) расслаивается на глубине 3 символа, т[http://www.еcs. так же не расслаиваетсяrutgers. Дугу (2) нужно вычислять после обработки дуги (1), потому что конец дуги (1) после обработки может оказаться на разной высоте, в зависимости от того на каком символе она расслоиласьedu/~farach/pubs/Suffix.pdf Optimal suffix tree construction with large alphabets ]* (3) конец является родителем 2, 9[http://www. Родитель 3, 10 находится на расстоянии 3, а наше расслоение на на расстоянии 4, тproteus2001.еnarod. сливается первый символ двойной дуги. Дугу (3) надо вычислять после дуги (2). Потому что если на дуге (2) появится разветвление, то компоненты дуги (3) придётся растащить по разным веткам дерева и сравнивать их будет не нужноru/gen/txt/11/farach.html Суффиксное дерево {{---}} Алгоритм Фараха]* (4) конец является родителем 1, 4[http://books. Расслаивается на втором символеgoogle.ru/books/about/Computing_Patterns_in_Strings.html?id=iKR0EewiCu4C&redir_esc=y Computing Patterns in Strings]* (5) конец является родителем 0, 3. Дугу (5) можно обрабатывать только после дуги (4), так как от неё будет зависеть глубина расслояния[https://github. com/krzysztofp/Text-Algorithms/tree/master/Farach%20suffix%20tree Chris Parjaszewski's implementation]

Дерево после обработки: [[ФайлКатегория:Treestep5_2.jpg|650pxДискретная математика и алгоритмы]]

*[http[Категория://www.proteus2001.narod.ru/gen/txt/11/farach.html - Суффиксное дерево - Алгоритм фарача]*[http://dl.acm.org/citation.cfm?id=796326 - Optimal suffix tree construction with large alphabets ]*[http://books.google.ru/books/about/Computing_Patterns_in_Strings.html?id=iKR0EewiCu4C&redir_esc=y - Computing Patterns in Strings]*[https://github.com/krzysztofp/Text-Algorithms/tree/master/Farach%20suffix%20tree - Chris Parjaszewski's implementation]