Proteus.. lawnmower-man@mail.ru

Суффиксное дерево

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

Доступные операции

Мы можем наращивать или укорачивать текст по одному символу в начале или в конце, соотвественно, наращивая или укорачивая его суффиксное дерево. Всего можно придумать четыре операции:

Построение суфф дерева

Буду описывать порядку. Начиная от самых простых и известных, кончая сложными. Первые очень коротко и невнятно, последние подробно.

Алгоритм Мак-Крейта

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

Алгоритм Укконена (Эско Укконена)

Здесь дерево просто выращивается с нуля, путём добавления символов в конец текста. Т.е. начинаем с пустого дерева, делаем один проход по тексту и добавляем по одному символу. Наверное, самый быстрый, самый простой, самый экономный по памяти алгоритм. Во всех узлах дерева, есть так называемые суффиксные связи, они указывают на копию этого узла в более коротких ветках. Т.е. в каждой вершине есть указатель, на вершину, чей путь от корня короче ровно на один символ.

Всё что нужно для работы, само дерево, и одна суффиксная связь в каждом узле (никаких глубин, ссылок на родителя и прочее, хранить не нужно). Для каждого нового символа, достаточно выполнить только одну операцию сравнения. В некоторых случаях, добавление новой развилки в сравниваемой позиции. Рост литьев, не обязательно происходит в буквальном смысле. У нас либо есть какое-то условное обозначение конца текста и дерево мы не трогаем, либо все листья сразу кончаются в конце текста. Рост мысленный, главное вовремя добавлять развилки.

По мере прохода по тексту, если сравниваемый символ текста совпадает, то ok - идёт к следующему символу. Если нет, делаем развилку, потом проходим по суффиксной связи узла и копируем эту развилку по другим веткам дерева (число копий не превышает число символов в алфавите). Тут не нужно думать про всякие фазы, случаи и прочие ужасы, очень простой алгоритм. Исходник, который я немного оптимизировал в ущерб наглядности, но обратно переделывать уже неохота:

- ukk2.cpp

Алгоритм Вайнера (Питера Вайнера)

Алгоритм Вайнера, это некое подобие алгоритма Укконена, но задом наперёд. Дерево точно так же выращивается по одному символу, но текст подаётся с конца. Т.е. по мере роста, иногда где-то в дереве возникает новая ветка (одна ветка). Суффиксные связи остались, но теперь они указывают в обратную сторону, кроме того связей стало много, в каждом узле приходится хранить целую таблицу связей (по одной на каждый символ алфавита). Глубина свзянных вершин по прежнему отличается на один символ. Если подробнее, то в каждом узле есть аж целых две таблицы.

Тоже достаточно простой и по своему красивый алгоритм, исходник прилагается:

- vainer.cpp

Кучи больших векторов

По смыслу, алгоритм Вайнера очень похож на Укконена, но две огромные таблицы в каждом узле, это неприятно. От вектора связей избавиться очень просто. Достаточно заметить, что все ссылки таблицы, указывают на узлы с одинаковой глубиной. Достаточно связать эти узлы между собой в список и оставить одну ссылку на начало списка. Т.е. внутри узла Node *L[256]; превращается в Node *L_first, *L_next;. Символ, который используется для указания связи, можно поглядеть в корне, соответствующей ветки дерева. Доступ к символу в корне любой дуги очень прост, если мы знаем глубину узла: text[edge->begin-edge->depth]. То что вместо таблицы мы проверяем список, отнимает какое-то время, но его можно свести к нулю, если в начало списка выносить, ту часть, которой нет в списках дочерних узлов, тогда целиков списки проверять не понадобиться.

С индикатороным вектором немного сложнее. Можно заметить, что алфавит ограничен, а дерево имеет очень много одинаковых индикаторных векторов. Вместо индикаторных векторов, можно хранить ссылки на индикаторные вектора, и не хранить в памяти одинаковые вектора. Понятно что каждый индикаторный вектор изменяется не спеша, меняется каждый раз только один символ, можно хранить в памяти все варианты этих векторов и переходить между ними во время каждого одиночного изменения. На практике это оказалось неудобно и не быстро, поэтому лучше просто завести одну хеш таблицу для всех векторов и пытаться брать копии оттуда, так проще всего, так быстрее всего. Опыты показывают, что достаточно таблицы которая в полтора раза больше предполагаемое количество дублей, это почти полностью убирает все повторы. Принципиально не важно какого размера будет таблица, большая маленькая, это погоды не портит. Исходник прилагается.

- vainer-set.cpp

Можно попробовать сделать с индикаторным вектором, тоже самое что с вектором связей. Хранить списки для индикаторного вектора негде, он никуда не указывает. Он говорит о наличии в дереве некоего пути. Мы можем создавать вершину в конце каждого такого пути. Каждый раз, создавая одну развилку, вместо пометки в индикаторе, можно создавать дополнительную одиночную вершину и ссылку на неё (место для вершины можно найти быстро и оценка времени для алгоритма не портится). Всё было бы очень красиво, если бы не надо было заодно менять процедуру поиска вершины с индикаторной меткой (FindI), которая тоже ставит отметки в индикаторном векторе и следовательно тоже должна создавать подобные вершины. И так, индикаторный вектор можно убрать из алгоритма полностью, вся информация легко перемещается в вектор связей. Но, количество узлов на дереве, сильно возрастает (в среднем где-то в два раза).

Даже если мы не создаём дополнительные вершины для ссылок или не создаём их внутри FindI. Поскольку для тех символов где в узлах стоит ссылка и векторе связей, автоматически есть метка и в индикаторном векторе, то можно не использовать индикаторный вектор, там где он совпадает с вектором связи. По моему опыту, на произвольно взятых английских текстах, количество индикаторных векторов сокращается в 3.5 - 7 раз в зависимости от текста.

Сжатие

Одно из самых важных применений суффиксного дерева, это сжатие текста с помощью какого-нибудь LZ алгоритма. Суффиксное дерево позволяет быстро найти самый длинный кусок текста, совпадающий с нашим образцом. К сожалению, на практике, всё не так весело как в теории.

Для создания скользящего окна, проще всего применять тот же алгоритм Укконенна. Казалось бы, проблему поиска ближайшего к концу образца, лучше решает алгоритм Вайнера. Если сделать зеркальный алгоритм Вайнера, то мы получим онлайн алгоритм для построения префиксного дерева, а символы будет подавать от начала к концу.

К сожалению, не всё так хорошо. В префиксном дереве, мы можем найти максимально близкий к концу образец, но он всё равно будет состоять из отрезков, более близких в началу текста (потому как они попали в дерево первыми). Есть два выхода: поправлять эти отрезки, так чтобы они всегда были ближе к концу, линейная оценка, для нашего скользящего по тексту окна, теряется сразу. Второй написать программу так чтобы мы всё таки имели максимально близкие к концу отрезки, но решение будет некрасивое, и оно с одинаковым успехом применимо и к префиксному дереву, к суффиксному Укконена, и поэтому проще применять суффиксное. К тому же, полностью минимизировать смещение от конца текста не имеет смысла. Смещение, в отличии от длины совпадения, как правило практически хаотично, и с дополнительному сжатию (хаффманном или ещё чем-то), не поддаётся. Прилагается исходник для онлайн построения перфиксного дерева, по Вайнеру:

- vainer-prefix.cpp

Алгоритм Фарача (Мартина Фарах Колтона)

Вот тут начинается максимально подробный рассказ. Со всеми, тонкостями и деталями. Как работает алгоритм, я уже расписывал. Для всех исходников требуется свежий компилятор c++11 (писать по другому, было бы слишком неудобно).

Само описание тут: алгоритм Фарача

Коротко обозначим стадии алгоритма:

Структурки

Всё дерево состоит из ребёр. Т.е. у каждого ребра, есть ссылка на список дочерних рёбер, начало и конец отрезка в тексте, глубина в дереве. Двойные дуги описаны, с помощью вспомогательных структур. Для работы с двойными дугами, дополнительная структура это дополнительная сложность, я пытался добавить двойные дуги, как обычные в общий список, но сложностей возникло ещё больше. В рёбрах получается очень много лишних полей, которые после работы не нужны, можно хранить их где-то отдельно, и без труда выкидывать после работы, оставляя только 4 поля (begin, end, child, next). Без некоторых можно обойтись и по время работу, т.к. suff_id=begin-depth , одно из этих полей можно не хранить в памяти. А suff_id можно вообще не хранить, оно требуется только в двойных дугах и листах. А в листах его очень просто узнать, посмотрев на количество символов от конца листа, до корня suff_id = depth+size().

Начало и конец текста в ребёрах обозначены обычными цифрами, это позволяет менять тип данных в исходных данных. Например, был текст из байтов byte, и и вдруг стал dword, само дерево при этом не меняется.

Поскольку дерево у нас явное (это когда на нём явно обозначеные все листья, терминология бывает разная), то в нём приходится обозначать все листья. Я попытался минимизировать расходы, если в какой-то конкретной дуге дерева, может кончаться текст, то конец (end) это дуги всегда ссылается на конец текста, и нам не надо хранить какие-то отдельные отметки.

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

Стадии работы алгоритма

На определённых стадиях алгоритма, мы переводим суффиксное дерево в суффисный массив, потом переводим суффиксный массив в дерево. На выходе всего алгоритма, тоже получается суффиксный массив и его LCP значения. Оба преобразования очень быстрые, линейные по времени. О том, нужно ли делать такое преобразование, в ту или другую сторону, буду упоминать отдельно (есть две главные проблемы).

compress

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

makeEven

Делаем суффиксный массив из наших данных, в новом алфавите. Это делается, через повторный вызов всего этого алгоритма, т.е. рекурсивно.

decompress

Возвращаем данные в исходный алфавит. Для этого достаточно удвоить все расстояния в суффикном дереве (точнее в суфф. массиве). Все свойства суфф. дерева при этом сохраняются, и мы можем по прежнему работать и исходным (несжатым) алфавитом. Надо только поправить, позиции, в развилках дерева, после разжатия могут совпадать первые символы (просто увеличиваем некоторые LCP значения на еденицу).

Получаем - чётный суффиксный массив. Т.е. суфф. дерево которое построено из чётных отрезков исходного дерева.

makeEven

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

В этой, казалось бы самой невинной операции, всего алгоритма, есть три небольших подвоха!

отрезание

Не знаю, кто и где, первым начал писать, что надо отрезать символы. На пальцах, приведу простой пример:

Есть отсортированный массив: 

abb
bab
bba

Мы отрезаем первые символы, то что осталось сортируем по первому символу, не нарушая порядок. И, вуаля! Свойства отсортированного текста нарушены полностью. Все отрезки разлетелись в произвольном порядке. 

ab
bb
ba

Поэтому, на данной стадии, имея отсортированные по алфавиту отрезки, одного и того же текста (суффиксный массив), мы не отрезаем первые символы, а наоборот дописываем. Вместо инкремента позиций в суффиксном массиве, делаем декремент. И получаем правильный, не испорченный суффиксный массив.

массив

Здесь же кроется первая проблема взаимоотношений, массивов и деревьев. На данной стадии мы вроде как, можем применять не массив, а дерево. Всё преобразование будет даже быстрее и легче. Но предполагается, что мы не можем просто так взять и добавить первые символы к деревьям, потом отсортировать ветки корня, по первым символам и получить новое дерево. Преобразования будут достаточно тяжёлые.

lcp

Побочный эффект. Несмотря на то что массив, меняется не полностью, мы не можем во время пересортировки сохранить хотя бы часть LCP значений и адаптировать их для нового нечётного массива. Хотя, тут, как всегда, для каждого нельзя, в алгоритмах на суффисных деревьях, у меня есть своё можно :) На самом деле можно частично сохранить и пересчитать после сортировки, имея какой-то массив соразмерный с алфавитом. Но проще всего, просто посчитать его заново: потребуется вспомогательны массив размером с наш массив и линейное время.

treeMerge

Берём наши 'половинчатые' суфф. массивы, и преобразоваывем их в суфф. деревья. После этого сливаем оба дерева рекурсивно, подгоняя длины дуг, под одинаковые размеры. В этоге, получаем уже известное, суфф. дерево с двойными дугами. Поскольку мы не знаем про двойные дуги ничего, т.е. не знаем сколько начальных символов в них совпадает нужна следующая стадия алгоритма.

о массивах

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

edgeMerge

внутри этой стадии, скрывается несколько сложных шагов.

общие предки и поиск вершин

Перебираем все двойные дуги в дереве, и составляем списки дуг, для которых надо найти общего предка. Напомню, что для каждой двойной дуги в дереве, через которую проходят суффиксы id1, id2 - нам надо найти в дереве предка для дуг id1+1, id2+1. Для поиска общих предков я применяю замечательный алгоритм Тарьяна. Который, кажется, с самого начала упоминался в 'оригинале', но я дурак придумал всё сам, заметил и уже потом. Итак, я делаю один обход, составляя списки всех пар вершин, для которых надо найти общих предков. Далее, делаю один обход для поиска, и за линейное время получаю все ответы. Для каждой двойной дуги я ставлю, ссылку на предка id1+1, id2+1, это по сути тоже суффиксные связи, только с не совсем чётким указанием позиций.

Есть две приятные вещи, которые могут сильно упростить жизнь:

слияние дуг и беспорядок

Теперь самая мутная часть алгоритма. Порядок обработки дуг. Есть двойная дуга, через которую проходят суффиксы id1, id2. Чтобы узнать первый отличающийся символ этих дуг, достаточно найти общего предка для суффиксов id1+1, id2+1, и поглядеть на какой глубине у него развилка. Звучит просто, но на самом деле, среди предков id1+1, id2+1, тоже может торчать двойная дуга. Но и это не всё:


Например: обрабатываем двойную дугу, которая торчит из вершины B.
Идём за образцом, из вершины B, в вершину B' чтобы посмотреть где начинается ещё раздвоение. И тут возможны следующие неожиданности:

Когда мы растаскиваем двойную дугу предка B, могут произойти следующие вещи:

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

Единственный способ, распутать клубок из двойных дуг, это обработать все их в правильном порядке. А вот как выбрать это порядок? Отсортировать дуги по какому-то критерию, например чтобы сначала обрабатывались те что ближе к корню, но номеру суффикса или как-то ещё - всё это не поможет. И никакой другой способ выбора порядка, не поможет.

Ответ очень простой - никак! Всё настолько плохо, что даже не важно в каком порядке мы обрабатывать дуги, можно вообще их в случайном порядке дёргать. Временная оценка алгоритма не страдает, потому что лишних попаданий в рекурсию и тому подобных неприятностей у нас нету. Можно произнести умные слова: топологическая сортировка, и, всё таки найти правильный порядок обработки дуг, но все эти проблемы решаются на ходу. Надо заранее впаивать для каждого узла обозначения: есть ли у него предок с двойной дугой (тогда его надо обработать раньше), если в него предок с двойной дугой, которую мы обработали, и сшили дуги на половину (в таком случае тот предок считается общим предком для суффиксов id1+1, id2+1, и нужную глубину расслоения надо подглядывать у его).

В моём исходники для этого есть ссылки Edge::hard_parent, Edge::unmerge_first (в более оптимизированной версии, немного по другому)

готовое дерево

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

renameId

Чтобы найти вершину образец, из которой надо тянуть информацию. нужно правильно поставить номера суффиксов для двойных дуг. Через одну вершину дерева может проходить любое количество суффиксов, при этом, не все суффиксы подходят нам для работы. Не всякие числа однозначно определяют вершину id1, id2 в дереве, и соответствующую ему вершину id1+1, id2+1. Перед тем как искать общих предков, придётся подкорректировать номера дуг.

Допустим, у нас есть двойная дуга в вершине А, чтобы найти номера которые однозначно определяют вершину, надо заглянуть в C и D - и достать номер любого чётного суффикса из ветки C, и номер любого нечётного суффикса из D. Или наоборот, нечётного из C, чётного из D (один из вариантов может отсутствовать в дереве). Таким образом, будет обозначена точная позиция вершины и суффиксы id1+1, id2+1 дадут точную информацию.

Оставлять номера в исходном виде, как они легли при построении, нельзя. Простой проход по дереву, со слепым выдёргиванием всех чётных и нечётных номеров (как пишут в книгах), не даст абсолютно ничего. Алгоритм слияния двойных дуг, либо выдаст неверные дистанции, либо уйдёт в вечный цикл, пытаясь выбрать порядок обработки дуг.

Для начала, это всё что нужно знать. Прилагается соотв. исходник, настолько упрощённый, что даже для сортировки используется - обычная нелинейная сортировка.

- fara-draft.cpp

Написано на C++11. Для проверки работает в три этапа, сначала, немного рабочих тестов, потом обработка тестового файла. Потом случайно выдуманные строки. Название файла для тестов, можно задать в начале исходника. Предпочтительно файл размером в 1-15 мегабайт. В принципе можно даже не текстовой файл, а бинарный, но для этого придётся немного доработать обвязку, которая занимается вводом и выводом. Так же в начале файла есть настройки, для реальной работы, рекомендую выключить всё.

Неявное дерево

Можно строить неявное суф. дерево, в конце и в промежуточных стадиях алгоритма. Это сильно экономит память и время, но до конца эту мысль я довести не пробовал. Для этого придётся немного усложнить все процедуры, для работы с суфф. массивами (которые я надеюсь всё таки выкину, вместе с массивами). И немного переделать процедуру слияния. Допустим мы хотим слить дуги id1, id2, мы идём смотреть на дуги id1+1, id2+1, а одна из них в дереве попросту отсутствует. Эта неприятность решается просто, идём смотрим на дуги id1+2, id2+2, если их тоже нет, то пытаемся найти id1+3, id2+3 и т.д. Для правильного вычисления дистанции, нужно запомнить сколько таких попыток мы сделали. Так же, лучше заранее узнать максимальный номер, суффикса, который есть в дереве. Если понятно что нужной пары найти нельзя, то можно просто пройтись по дугам id1, id2 и сравнить в их вручную, такая ситуация возникнет всего один раз на всё дерево. Алгоритм Фарача отлично работает для неявных суффиксных деревьев.

О сортировке

Для сортировки предлагается использовать, всеми любимую, радиальную сортировку, которая абсолютно линейна по скорости, и очень хорошо распихивается по нескольким ядрам процессора. Но можно не усложнять себе жизнь и использовать частный случай такой сортировки, а именно сортировку с подсчётом. Это очень удобно, потому что мы делаем либо стабильную сортировку очень небольшого алфавита (char). Либо сортировку большого алфавита, который всё равно не разспхуает до бесконечности (он стабильно меньше чем массив с данными), а после первого же сжатия все символы в этого алфавита идут по порядку (без дыр в нумерации).

Чтобы небыло обидно (в основном мне), я положу исходник радиальной сортирвки массива, и его многоядерную версию (без openMP она не запустится). Многоядерная версия, работает заметно быстрее однопоточной. Ускорение, не ровно в количество ядер, но очень впечатляющее. Единственная беда, что на некоторых машинах, очень сильно проседает скорость записи в память, с непоследовательными адресами, тогда почти весь выигрыш теряется (тут уже надо можно многоядерную сортировку слиянием, не такая быстрая, но быстрая в любом случае). К сожалению не всегда работает правильно с openmp, потому что omp_get_thread_num() выдаёт неверные значения (можно переписать под winapi, posix, c++11, но в общем без разницы, это всё уже не так актуально).

- radix-threads.cpp

Рабочий вариант для построения суф. дерева Фарача: (оптимизировать его я могу до бесконечности):

- fara.cpp !!

Многоядерность

Любую, простую или сложную стадию алгоритма Фарача можно распаралеллить на несколько ядер процессора:

Вообще, никакого радикального выигрыша, от полного распаралелнивания алгоритма, получить не получится. Там нет никаких тяжёлых вычислений, весь алгоритм просто жонглирует ссылками в памяти. Параллельную обработку дерева можно получить простой параллельной обработкой корневых веток дерева. Даже есть на первой стадии алгоритма, веток будет недостаточно (что очень навряд ли), после первого рекурсивного вызова, веток будет достаточно в любом случае (см. процедуру Edge::WalkParallel).

Две самых не очевидных в стадии я всё таки опишу:

Поиск общих предков - многоядерный Алгоритм Тарьяна

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

Единственная сложность, которая остаётся, это необходимость, как-то отличать узлы дерева для одного потока и другово. Проблема в том, что у нас есть запросы для пар вершин, и вершины для этих запросов могут находиться в разных ветках дерева, которые обрабатываются разными потоками. Момент, когда нужно выдавать ответ на запрос какой-то отдельной пары, выбирается с помощью разметки уже посещённых вершин. В случае с параллельным алгоритмом, одна вершина помечается обходом в одном потоке, другая вершина помечаться проходом в другом потоке, и происходит это вовсе не в тот момент, когда надо выдать родителя для этих двух вершин. Ответ будет выдавать тот поток, который первым отметил вторую вершину, и ответ будем неправильным. Тут можно много решений придумать, например грубо, вместе с разметкой, ставить в узлы номер потока.

Многоядерная обработка двойных дуг

Слияние двойных дуг, можно делать параллельно, если построить очень хитрый lock-free алгоритм. Здесь очень удобно, то что порядок обработки дуг практически не определён, что можно два раза натравить одну процедуру на одну и туже вершину, что двойная дуга всегда превращается в обычную, а не наоборот. А жёстко заданный предок уже ни во что не превращается.

Можно поступить ещё проще, влепить в каждый узел дерева что-то вроде spin-lock блокировки, но даже тут возникает много проблем. В обоих случаях возникает проблемы с тем что время обработки отдельных вершин, неравномерное. Иногда одна вершина ждёт другую, иногда нужная какая-то дополнительная разметка веток (которые можно повесить на другие потоки, в моменты их простоя). Это всё довольно неудобно.

Есть максимально красивое решение, без spin-lock и даже без lock-free. В процессе работы с двойной дугой мы заглядываем в id1+1, id2+1, перед этим изучаем двойные дуги его предка и своего предка. Можно сделать один очень простой проход, по дереву и выделить все множества взаимосвязанных подобным образом вершин. Линейное время прохода, линейное время для всего алгоритма.

В результате, мы получим огромное количество связанных друг с другом вершин, которые никак не влияют друг на друга во время обработки. И можно без всяких блокировок и каких-то бы то нибыло хитростей, запускать в дерево любое количество потоков, они смогут работать свободно и ничем не будут мешать друг другу. Даже если у нас бинарный алфавит, и на первой стадии из корня торчат две ветки - количество таких обособленных зон, будет огромным, его хватит на любое количество процессоров.

Прилагается исходник в котором часть алгоритмов работает в многоядерном режиме. Заметного ускорения это не даёт. Я пытался унифицировать каждую попытку обхода дерева, про этому про началу были сплошные лямбды на лямбдах и всё в таком роде, но это как оказалось только замедляет программу. Самое интересное случилось, когда я делал каррирование лямбда функции, то один std::bind умудрился замедлить программу почти в два раза, находясь в не нагруженном участке алгоритма, на низкой частоте вызова во время полной оптимизации. Я не понял что там случилось, может он в куче память аллоцирует или ещё что-то, да и вникать как-то не интересно было.

Поскольку, это тоже черновик, то сравнивать его имеет смысл только с самими собой, на разном количестве потоков:

- fara-thread-draft.cpp

Деревья и массивы

Можно полностью избавить алгоритм от работы с массивами. Разницы между суфф. массивом и суфф. деревом на самом деле на так уж и много, смысл у них одинаковый, конвертируются друг в друга за линейное время. Со временем даже перестаёшь их толком различать. Но тем не менее, массивы из алгоритма можно убрать. Думаю что использовать их стали только для облегчения теории. Что даёт отсутствие массивов:

Подумаем как избавиться от массива. Для начала можно просто уменьшить количество конвертаций:

При этом сильно усложниться процедура слияния, в которую придётся добавить окончательное растаскивание, удаление лишних узлов на ветках и кое что ещё. На выходе из программы будет выдаваться некому непонятное и очень прожорливое дерево.

Что будет, если попробовать преобразовать деревья напрямую, без массивов. Напомню, что суфф. дерево, это просто набор веток, торчащих из корня. Для преобразования чёт.-нечет, достаточно добавить или удалить по символу и начале каждой коревой ветки. Посмотрим поближе:

Преобразование удалением


если мы удаляем символы, то корни становятся короче. Узлы которые расположены у самого корня, рассыпаются. В результате мы получаем ещё больше веток, которые надо как-то отсортировать и слить вместе. Проблема такая же как с массивами. У нас есть две строки X={x1,x2,x3...}, Y={y1,y2,y3..}, допустим первые символы у них разные, x1≠y1, т.е. обе строки были в разных ветках. Отрезали первые символы, строки попали в одну ветку, сколько символов в этих строках теперь совпадает или точный порядок строк выяснить нельзя. Чтобы узнать длину совпадения, придётся сравнить все последующие символы строки, сделать это за линейное время по всему дереву - нельзя.

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

Преобразование добавлением


если, в начале каждой ветки, дописать впереди идущий символ, то ветки тоже же рассыпаются, но тут немного сложнее. Допустим, внутри отдельной ветки у нас лежат строки A, B, C (A={a1,a2..}, B={b1,b2,..}, C={c1,c2..}). Мы приписали впереди идущие символы a0, b0, c0, но символы эти различаются. В этом случае ветка благополучно разделяется на множество метких веток, попросту говоря растаскивается, по первым символам своих строк. Мы опять получаем множество более мелких веток, а сравнивать уже ничего не надо. Всё что нужно, это сшить заново некоторые из них по первым символам. Это очень просто, если две строки изначально совпадали более чем в одном символе, то они изначально были в одной ветке корня. Если символы A={a1,a2..}, B={b1,b2,..}, не совпадали, то строки изначально были в разных ветках. Когда символы a0, b0 совпадут, то очевидно, что строки клеятся только в позиции первого символа a0, b0. Самой неприятной остаётся только процедура расслоения веток, которая, тем не менее, линейна по времени и напоминает усложнённое преобразование массива в дерево. Понадобится либо делать много стеков (что сделать нельзя), либо прошивать родителей для каждой ветки (для этого кстати в узлах есть место, которое до запуска слияния и поиска общих предков не занято).

Я какое-то время думал, как не создавать нечёт дерево вообще. А выращивать его из чётного, проходя по нему в процессе, первого грубого слияния деревьев. Такие мысли напрашиваются сами.

Когда будет время, покажу исходник.

....

Повторно исходники:

Развитие алгоритма