У вас все хорошо. Я не знаком с алгоритмом, но сегодня прочитал эту статью. Все, что вы написали, правильно, насколько это возможно. Вы правы, что некоторые части объяснения предполагают много.
Ваши вопросы
1.Что делает размер выходного см в терминах дерева суффиксов или входных строк? Конечная фаза вывода отображает все вхождения Key (r) в T для всех состояний r, помеченных для вывода.
Выход состоит из максимальных совпадений k-расстояния P в T. В частности, вы получите окончательный индекс и длину для каждого. Так ясно, что это также O (n) (помните, что big-O является верхней границей), но может быть меньше. Это является признаком того, что невозможно создать p-совпадений менее чем за время O (p). Остальная часть времени связана только с длиной шаблона и числом жизнеспособных префиксов, оба из которых могут быть сколь угодно малыми, поэтому размер вывода может доминировать. Рассмотрим k = 0, а вход «a» повторяется n раз с рисунком «a».
2. При взгляде на алгоритм C определена функция dp (страница 4); Я не понимаю, что представляет собой индекс i. Он не инициализирован и не кажется, что он увеличивается.
Вы правы. Это ошибка. Индекс цикла должен быть i. Как насчет j? Это индекс столбца, соответствующий входному символу, обрабатываемому в динамической программе. Это действительно должен быть входной параметр.
Давайте сделаем шаг назад. Таблица Пример таблица на стр. 6 вычисляется слева направо по столбцу с использованием уравнений (1-4), приведенных ранее. Они показывают, что для получения следующего необходимы только предыдущие столбцы D и L. Функция dp - это всего лишь реализация этой идеи вычисления столбца j от j-1. Столбец j D и L называются d и l соответственно. Столбец j-1 D и L: d' и l' - входные параметры функции.
Я рекомендую вам работать через динамическую программу, пока вы ее не поймете. Алгоритм состоит в том, чтобы избежать дублирования вычислений столбцов. Здесь «дубликат» означает «имеющий те же значения в существенной части», потому что это все, что имеет значение. Несущественные части не могут повлиять на ответ.
Несжатое три просто сжатое, с очевидным расширением, чтобы иметь один ребро на символ. За исключением идеи «глубина», это неважно. В сжатом дереве глубина (глубины) - это просто длина строки, которую он называет Key (s) - необходимо получить из корневого узла s.
Алгоритм
Алгоритм просто умная схема кэширования.
Все его теоремы и леммы показывают, что 1) нам нужно только беспокоиться о существенных частях столбцов и 2) существенная часть столбца j полностью определяется жизнеспособным префиксом Q_j. Это самый длинный суффикс ввода, заканчивающийся на j, который соответствует префиксу шаблона (в пределах расстояния редактирования k).Другими словами, Q_j - это максимальное начало соответствия k-правлению в конце рассмотренного ранее ввода.
С этим, вот псевдо-код алгоритма А.
Let r = root of (uncompressed) suffix trie
Set r's cached d,l with formulas at end page 7 (0'th dp table columns)
// Invariant: r contains cached d,l
for each character t_j from input text T in sequence
Let s = g(r, t_j) // make the go-to transition from r on t_j
if visited(s)
r = s
while no cached d,l on node r
r = f(r) // traverse suffix edge
end while
else
Use cached d',l' on r to find new columns (d,l) = dp(d',l')
Compute |Q_j| = l[h], h = argmax(i).d[i]<=k as in the paper
r = s
while depth(r) != |Q_j|
mark r visited
r = f(r) // traverse suffix edge
end while
mark r visited
set cached d,l on node r
end if
end for
Я ушел из шаг вывода для простоты.
Что такое пересечение границ суффикса? Когда мы делаем это из узла r, где Key (r) = aX (ведущий a, за которым следует некоторая строка X), мы переходим к узлу с ключом X. Следствие: мы сохраняем каждый столбец, соответствующий жизнеспособному префиксу Q_h at trie node для суффикса ввода с префиксом Q_h. Функция f (s) = r является функцией перехода суффикса.
Для чего это стоит, Wikipedia picture of a suffix tree показывает это довольно хорошо. Например, если из узла для «NA» мы следуем за краем суффикса, мы переходим к узлу для «A», а оттуда к «». Мы всегда отключаем лидера. Поэтому, если мы будем обозначать состояние s Key (s), мы имеем f ("NA") = "A" и f ("A") = "". (Я не знаю, почему он не упоминает такие состояния в этой статье. Это упростит многие объяснения.)
Теперь это очень здорово, потому что мы вычисляем только один столбец на жизнеспособный префикс. Но это все еще дорого, потому что мы проверяем каждый символ и потенциально пересекаем края суффикса для каждого из них.
Алгоритм B
Цель алгоритма B является идти быстрее, пропуская через вход, касаясь только те символы, вероятно, создать новый столбец, то есть те, которые являются концами ввода, которые соответствуют ранее невидимое жизнеспособными префикс шаблона.
Как вы подозреваете, ключом к алгоритму является функция loc. Грубо говоря, это скажет, где следующий «вероятный» входной символ. Алгоритм довольно похож на поиск A *. Мы сохраняем минимальную кучу (которая должна иметь операцию удаления), соответствующую набору S_i в документе. (Он называет это словарем, но это не очень традиционное использование этого термина.) В мини-куче содержатся потенциальные «следующие состояния», наложенные на позицию следующего «вероятного символа», как описано выше. Обработка одного символа создает новые записи. Мы продолжаем идти, пока куча не станет пустой.
Вы абсолютно правы, что здесь он становится отрывочным. Теоремы и леммы не связаны друг с другом, чтобы привести аргумент о правильности. Он предполагает, что вы переделаете его работу. Я не совсем уверен в этом размахивании руками. Но, похоже, этого достаточно, чтобы «декодировать» алгоритм, который он имеет в виду.
Другой основной концепцией является набор S_i и, в частности, подмножество, которое остается не устранено. Мы сохраним эти неубранные состояния в мини-куче H.
Вы правы, чтобы сказать, что обозначение затушевывает намерение S_i. Когда мы обрабатываем входные данные слева направо и занимаем позицию i, мы собрали множество реальных префиксов, которые были просмотрены до сих пор. Каждый раз, когда новый найден, вычисляется новый столбец dp. В авторских обозначениях эти префиксы были бы Q_h для всех h < = i или более формально {Q_h | h < = i}. Каждый из них имеет путь от корня до уникального узла. Множество S_i состоит из всех состояний, которые мы получаем, беря еще один шаг из всех этих узлов вдоль по краям в trie. Это дает тот же результат, что и весь текст, который ищет каждое появление Q_h и следующего символа a, а затем добавляет состояние, соответствующее Q_h a, в S_i, но это быстрее. Ключи для состояний S_i являются точными кандидатами на следующий жизнеспособный префикс Q_ {i + 1}.
Как выбрать подходящего кандидата? Выберите тот, который появляется после позиции i на входе. Здесь находится loc (ы). Значение loc для состояния s - это то, что я только что сказал выше: позиция на входе, начинающаяся с i, где следующий жизнеспособный префикс, связанный с этим состоянием.
Важным моментом является то, что мы не хотим просто назначать только что найденное (путем вытягивания значения min loc из H) «следующий» жизнеспособный префикс как Q_ {i + 1} (жизнеспособный префикс для столбца dp i +1) и перейти к следующему символу (i + 2). Здесь мы должны поставить сцену, чтобы как можно дальше проскользнуть до символа символа k (с dp-столбцом k), такого Q_k = Q_ {i + 1}. Мы проскальзываем вперед по краям суффикса, как в алгоритме A. Только на этот раз мы записываем наши шаги для будущего использования, изменяя H: удаление элементов, что является таким же, как удаление элементов из S_i, и изменение значений loc.
Определение функций loc (s) является открытым, и он никогда не говорит, как его вычислить. Также не упоминается, что loc (s) также является функцией i, обрабатываемая текущая позиция ввода (что он перескакивает из j в более ранних частях бумаги в i здесь для текущей позиции ввода бесполезно.) Воздействие заключается в том, что loc (ы) изменений при обработке ввода.
Оказалось, что часть определения, применимая к устраненным состояниям, «просто происходит», потому что состояния отмечены как исключенные после удаления формы H. Поэтому для этого случая нам нужно только проверить отметку.
В другом случае - неиспользуемые состояния - требуется, чтобы мы искали вперед на входе, ища следующее вхождение в тексте, который не покрыт какой-либо другой строкой. Это понятие покрытия - обеспечить, чтобы мы всегда имели дело только с самыми «длинными» возможными префиксами. Более короткие нужно игнорировать, чтобы избежать выдачи матчей, отличных от максимальных. Теперь поиск в прямом эфире звучит дорого, но, к счастью, у нас уже есть уже созданный суффикс, который позволяет нам делать это в O (| Key (s) |). Трой должен быть тщательно аннотирован, чтобы вернуть соответствующую входную позицию и избежать охваченных случаев Key (s), но это было бы не слишком сложно. Он никогда не упоминает, что делать, когда поиск терпит неудачу. Здесь loc (s) = \ infty, то есть он исключен и должен быть удален из H.
Возможно, самая прикольная часть алгоритма обновляет H, чтобы иметь дело с случаями, когда мы добавляем новое состояние s для жизнеспособного префикса, который охватывает Ключ (w) для некоторого w, который уже был в H. Это означает, что мы должны хирургически обновить элемент (loc (w) => w) в H. Оказывается, суффикс trie еще раз поддерживает это эффективно с его суффиксами.
Со всем этим в наших головах давайте попробуем для псевдокода.
H = { (0 => root) } // we use (loc => state) for min heap elements
until H is empty
(j => s_j) = H.delete_min // remove the min loc mapping from
(d, l) = dp(d', l', j) where (d',l') are cached at paraent(s_j)
Compute |Q_j| = l[h], h = argmax(i).d[i]<=k as in the paper
r = s_j
while depth(r) > |Q_j|
mark r eliminated
H.delete (_ => r) // loc value doesn't matter
end while
set cached d,l on node r
// Add all the "next states" reachable from r by go-tos
for all s = g(r, a) for some character a
unless s.eliminated?
H.insert (loc(s) => s) // here is where we use the trie to find loc
// Update H elements that might be newly covered
w = f(s) // suffix transition
while w != null
unless w.eliminated?
H.increase_key(loc(w) => w) // using explanation in Lemma 9.
w = f(w) // suffix transition
end unless
end while
end unless
end for
end until
Снова я пропустил вывод для простоты. Я не скажу, что это правильно, но это в стадионе. Одна вещь состоит в том, что он упоминает, что мы должны обрабатывать Q_j для узлов не до «посещения», но я не понимаю, что означает «посещенный» в этом контексте. Я думаю, что посещаемые состояния по определению алгоритма А не произойдут, потому что они были удалены из Х. Это головоломка ...
Операция increase_key в лемме 9 спешно описана без каких-либо доказательств. Его утверждение о том, что операция min возможно в O (log | alphabet |) время, оставляет много для воображения.
Количество причуд заставляет меня задаться вопросом, не является ли это окончательным проектом статьи. Это также публикация Springer, и эта копия онлайн, вероятно, нарушит ограничения авторского права, если бы она была точно такой же. Возможно, стоит посмотреть в библиотеку или заплатить за финальную версию, чтобы увидеть, были ли некоторые из грубых краев сбиты во время окончательного обзора.
Это насколько я могу получить. Если у вас есть конкретные вопросы, я попытаюсь уточнить.
Я добавил, что я могу понять. У меня нет времени. Удачи вам! – Gene