Вы делаете хорошо. Я не знаком с алгоритмом, но сегодня прочитал статью. Все, что вы написали, верно, насколько это возможно. Вы правы в том, что некоторые части объяснения предполагают многое.
Ваши вопросы
1. К чему относится размер вывода с точки зрения дерева суффиксов или входных строк? Финальная фаза вывода перечисляет все вхождения Key(r) в T для всех состояний r, помеченных для вывода.
Выходные данные состоят из совпадений максимального k-расстояния P в T. В частности, вы получите окончательный индекс и длину для каждого. Так что ясно, что это тоже O(n) (помните, что big-O — это верхняя граница), но может быть меньше. Это намек на то, что невозможно сгенерировать p совпадений менее чем за время O(p). Остальная часть ограниченного времени относится только к длине шаблона и количеству жизнеспособных префиксов, оба из которых могут быть сколь угодно малы, поэтому размер вывода может доминировать. Предположим, что k=0, а входные данные представляют собой 'a', повторяющееся n раз с шаблоном 'a'.
2. Глядя на алгоритм C, функция dp определена (страница четыре); Я не понимаю, какой индекс я представляю. Он не инициализирован и не увеличивается.
Ты прав. Это ошибка. Индекс цикла должен быть i. А как насчет j? Это индекс столбца, соответствующего входному символу, обрабатываемому в динамической программе. Это действительно должен быть входной параметр.
Давайте сделаем шаг назад. Таблица Пример на странице 6 вычисляется слева направо, столбец за столбцом, с использованием уравнений (1–4), приведенных ранее. Они показывают, что для получения следующего необходимы только предыдущие столбцы D и L. Функция dp — это всего лишь реализация этой идеи вычисления столбца j из j-1. Столбец j D и L называются d и l соответственно. Столбец j-1 D и L — это d' и l', входные параметры функции.
Я рекомендую вам работать с динамической программой, пока вы не поймете ее хорошо. Алгоритм заключается в том, чтобы избежать дублирования вычислений столбцов. Здесь «дублировать» означает «иметь одинаковые значения в основной части», потому что это все, что имеет значение. Несущественные части не могут повлиять на ответ.
Несжатое дерево — это просто сжатое, расширенное очевидным образом, чтобы иметь одно ребро на символ. За исключением идеи «глубины», это неважно. В сжатом дереве глубина (глубина) — это просто длина строки, которую он называет ключом (ключами), необходимой для получения из корневого узла 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, в узел дерева для суффикса ввода с префиксом Q_h. Функция f(s) = r является функцией перехода суффикса.
Как бы то ни было, изображение суффиксного дерева в Википедии показывает это неплохо. Например, если от узла для «NA» пройти по суффиксному ребру, мы попадем в узел для «A», а оттуда — к «». Мы всегда вырезаем главного героя. Итак, если мы пометим состояние s с помощью Key(s), мы получим f("NA") = "A" и f("A") = "". (Я не знаю, почему он не помечает такие состояния в статье. Это упростило бы многие объяснения.)
Теперь это очень круто, потому что мы вычисляем только один столбец для каждого жизнеспособного префикса. Но это все еще дорого, потому что мы проверяем каждый символ и, возможно, пересекаем ребра суффикса для каждого из них.
Алгоритм Б
Намерение алгоритма B состоит в том, чтобы работать быстрее, пропуская ввод, касаясь только тех символов, которые могут создать новый столбец, то есть тех, которые являются концами ввода, которые соответствуют ранее невиданному жизнеспособному префиксу шаблона.
Как вы уже догадались, ключом к алгоритму является функция loc. Грубо говоря, это скажет, где находится следующий «вероятный» входной символ. Алгоритм немного похож на поиск A*. Мы поддерживаем минимальную кучу (которая должна иметь операцию удаления), соответствующую набору S_i в статье. (Он называет это словарем, но это не совсем общепринятое использование этого термина.) Минимальная куча содержит потенциальные «следующие состояния», заданные на позиции следующего «вероятного символа», как описано выше. Обработка одного символа создает новые записи. Продолжаем, пока куча не опустеет.
Вы абсолютно правы, что здесь он становится схематичным. Теоремы и леммы не связаны вместе, чтобы аргументировать правильность. Он предполагает, что вы переделаете его работу. Меня не совсем убеждает это размахивание руками. Но кажется, что там достаточно, чтобы «расшифровать» алгоритм, который он имеет в виду.
Другой ключевой концепцией является множество S_i и, в частности, подмножество, которое остается не устраненным. Мы будем хранить эти неустраненные состояния в минимальной куче H.
Вы правы, говоря, что обозначение скрывает смысл S_i. Когда мы обрабатываем входные данные слева направо и достигаем позиции i, мы накопили набор жизнеспособных префиксов, которые мы видели до сих пор. Каждый раз, когда обнаруживается новый, вычисляется новый столбец dp. В обозначениях автора эти префиксы будут Q_h для всех h‹=i или более формально { Q_h | ч ‹= я}. Каждый из них имеет путь от корня к уникальному узлу. Набор S_i состоит из всех состояний, которые мы получаем, делая еще один шаг от всех этих узлов вдоль переходных ребер в дереве. Это дает тот же результат, что и просмотр всего текста в поисках каждого вхождения Q_h и следующего символа a, а затем добавление состояния, соответствующего Q_h a, в S_i, но это быстрее. Ключи для состояний S_i являются правильными кандидатами для следующего жизнеспособного префикса Q_{i+1}.
Как мы выбираем подходящего кандидата? Выберите тот, который будет следующим после позиции i во входных данных. Здесь на помощь приходит loc(s). Значение 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 (s) изменяется по мере обработки ввода.
Оказывается, та часть определения, которая применяется к исключенным состояниям, «просто происходит», потому что состояния помечаются как исключенные при удалении из формы H. Так что в этом случае нам нужно только проверить наличие отметки.
Другой случай — неисключенные состояния — требует, чтобы мы искали во входных данных следующее вхождение в тексте, которое не покрыто какой-либо другой строкой. Это понятие покрытия должно гарантировать, что мы всегда имеем дело только с «самыми длинными» жизнеспособными префиксами. Более короткие должны быть проигнорированы, чтобы избежать вывода отличных от максимальных совпадений. Теперь поиск вперед звучит дорого, но, к счастью, у нас уже есть суффиксное дерево, которое позволяет нам сделать это за время O(|Key(s)|). Trie должен быть тщательно аннотирован, чтобы вернуть соответствующую позицию ввода и избежать скрытых вхождений ключа (ов), но это не будет слишком сложно. Он никогда не упоминает, что делать, если поиск не удался. Здесь loc(s) = \infty, т.е. он исключен и должен быть удален из H.
Возможно, самая трудоемкая часть алгоритма — это обновление H, чтобы иметь дело со случаями, когда мы добавляем новое состояние s для жизнеспособного префикса, который покрывает Key(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 только для узлов, которые еще не были «посещены», но я не понимаю, что означает «посещение» в этом контексте. Я думаю, что посещенные состояния по определению алгоритма А не возникнут, потому что они были удалены из H. Это загадка...
Операция increase_key в лемме 9 описана наспех без доказательства. Его заявление о том, что операция min возможна за время O(log |alphabet|), оставляет много места для воображения.
Количество причуд заставляет меня задаться вопросом, не является ли это окончательным проектом документа. Это также публикация Springer, и эта копия в Интернете, вероятно, нарушила бы ограничения авторского права, если бы она была точно такой же. Возможно, стоит поискать в библиотеке или заплатить за окончательную версию, чтобы увидеть, не были ли устранены некоторые шероховатости во время окончательного просмотра.
Это все, что я могу получить. Если есть конкретные вопросы, постараюсь уточнить.
person
Community
schedule
27.10.2013
