В этой статье обсуждаются приближенные методы сопоставления подстрок, в которых используется дерево суффиксов здесь. Однако для некоторых алгоритмов требуется дополнительная предварительная обработка.
Я предлагаю людям добавлять новые алгоритмы (даже если они неполные) и улучшать ответы.
У вас все хорошо. Я не знаком с алгоритмом, но сегодня прочитал эту статью. Все, что вы написали, правильно, насколько это возможно. Вы правы, что некоторые части объяснения предполагают много.
Ваши вопросы
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) - необходимо получить от root node s.
Алгоритм A
Алгоритм A - это просто умная схема кэширования.
Все его теоремы и леммы показывают, что 1) нам нужно только беспокоиться о существенных частях столбцов и 2) существенная часть столбца j полностью определяется жизнеспособным префиксом Q_j. Это самый длинный суффикс ввода, заканчивающийся на j, который соответствует префиксу шаблона (в пределах расстояния редактирования k). Другими словами, Q_j - это максимальное начало соответствия k-правлению в конце рассмотренного ранее ввода.
При этом здесь псевдокод для алгоритма А.
Let r = root of (uncompressed) suffix trie
Set r 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
Я пропустил шаг вывода для простоты.
Что происходит с пересечением границ суффикса? Когда мы делаем это из node r, где Key (r) = aX (ведущий a, за которым следует некоторая строка X), мы переходим к node с ключом X. Следствие: мы сохраняем каждый столбец, соответствующий жизнеспособный префикс Q_h в trie node для суффикса ввода с префиксом Q_h. Функция f (s) = r является функцией перехода суффикса.
Для чего это стоит, Википедия изображение дерева суффиксов показывает это довольно хорошо. Например, если из node для "NA" мы следуем за краем суффикса, мы переходим к node для "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 <= я или более формально {Q_h | h <= i}. Каждый из них имеет путь от корня до уникального node. Множество S_i состоит из всех состояний, которые мы получаем, сделав еще один шаг от всех этих узлов вдоль go-to-edge в trie. Это дает тот же результат, что и весь текст, который ищет каждое появление Q_h и следующего символа a, а затем добавляет состояние, соответствующее Q_h a, в S_i, но это быстрее. Ключи для состояний S_i являются точными кандидатами на следующий жизнеспособный префикс Q_ {i + 1}.
Как выбрать подходящего кандидата? Выберите тот, который появляется после позиции я на входе. Вот где находится loc (s). Значение loc для состояния s - это то, что я только что сказал выше: позиция на входе, начинающаяся с i, где следующий жизненный префикс, связанный с этим состоянием.
Важным моментом является то, что мы не хотим просто назначать вновь найденное (вытягивая значение min loc из H) "next" жизнеспособным префиксом как Q_ {i + 1} (жизнеспособный префикс для столбца dp я + 1) и перейти к следующему символу (i + 2). Здесь мы должны поставить этап, чтобы как можно дальше пропустить последний символ k (с dp-столбцом k), такой Q_k = Q_ {i + 1}. Мы проскальзываем вперед по краям суффикса, как в алгоритме A. Только на этот раз мы записываем наши шаги для будущего использования, изменяя H: удаление элементов, что является таким же, как удаление элементов из S_i, и изменение значений loc.
Определение функции loc (s) является открытым, и он никогда не говорит, как его вычислить. Также не упоминается, что loc (s) также является функцией i, обрабатываемая текущая позиция ввода (что он перескакивает из j в более ранних частях бумаги в я здесь для текущей позиции ввода бесполезно.) Воздействие заключается в том, что loc (s) изменяется по мере поступления входной обработки.
Оказывается, что часть определения, которая применяется к устраненным состояниям, "просто происходит", потому что состояния отмечены исключенными при удалении формы H. Поэтому для этого случая нам нужно только проверить отметку.
Другой случай - un-eliminated states - требует, чтобы мы искали вперед на входе, ища следующее вхождение в тексте, который не покрывается какой-либо другой строкой. Это понятие покрытия - обеспечить, чтобы мы всегда имели дело только с самыми "длинными" возможными префиксами. Более короткие нужно игнорировать, чтобы избежать выдачи матчей, отличных от максимальных. Теперь поиск в прямом эфире звучит дорого, но, к счастью, у нас уже есть уже созданный суффикс, который позволяет нам делать это в O (| Key (s) |). Трой должен быть тщательно аннотирован, чтобы вернуть соответствующую входную позицию и избежать охваченных случаев Key (s), но это было бы не слишком сложно. Он никогда не упоминает, что делать, когда поиск терпит неудачу. Здесь 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 для узлов не до "посещения", но я не понимаю, что означает "посещенный" в этом контексте. Я думаю, что посещенные состояния по алгоритму. Определение не произойдет, потому что они были удалены из Х. Это головоломка...
Операция increase_key в лемме 9 спешно описана без доказательства. Его утверждение о том, что операция min возможно в времени O (log | alphabet |), оставляет много для воображения.
Количество причуд заставляет меня задаться вопросом, не является ли это окончательным проектом статьи. Это также публикация Springer, и эта копия онлайн, вероятно, нарушит ограничения авторского права, если бы она была точно такой же. Возможно, стоит посмотреть в библиотеку или заплатить за окончательную версию, чтобы увидеть, были ли некоторые из грубых краев сбиты во время окончательного обзора.
Это насколько я могу получить. Если у вас есть конкретные вопросы, я попытаюсь уточнить.
Это был исходный вопрос, который начал этот поток.
Профессор Эско Укконен опубликовал статью : Приблизительное сопоставление строк по деревьям суффикса. Он обсуждает 3 разных алгоритма, которые имеют разные совпадения:
O(mq + n)O(mq log(q) + size of the output)O(m^2q + size of the output)Где m - длина подстроки, n - длина строки поиска, а q - расстояние редактирования.
Я пытался понять алгоритм B, но у меня возникли проблемы после выполнения этих шагов. Кто-нибудь имеет опыт работы с этим алгоритмом? Примером может служить пример или псевдо алгоритм.
В частности:
size of the output в терминах дерева суффиксов или входных строк? Конечная фаза вывода перечисляет все вхождения Key(r) в T, для всех состояний r, помеченных для вывода.i. Он не инициализирован и не кажется, что он увеличивается.Вот что я верю (я стою, чтобы исправить):
root обозначает начальное состояние.g(a, c) = b где a и b являются узлами в дереве, а c является символом или подстрокой в дереве. Таким образом, это переход; из a, следуя ребрам, представленным c, переходим к node b. Это называется переход к переходу. Итак, для дерева суффикса ниже, g(root, 'ccb') = red node
Key(a) = edge sequence где a представляет node в дереве. Например, Key(red node) = 'ccb'. Итак g(root, Key(red node)) = red node.Keys(Subset of node S) = { Key(node) | node ∈ S}a и b, f(a) = b: для всех (или, возможно, может существовать) a ≠ root существует символ c, подстрока x и a node b такие, что g(root, cx) = a и g(root, x) = b. Я думаю, что это означает, что для примера дерева суффикса выше, что f(pink node) = green node где c = 'a' и x = 'bccb'.H, содержащее node из дерева суффикса и пару значений. Значение задается loc(w); Я все еще не уверен, как оценить функцию. Этот словарь содержит узлы, которые не были устранены.extract-min(H) относится к достижению записи с наименьшим значением в паре (node, loc(w)) из H.Суть алгоритма, по-видимому, связана с тем, как оценивается loc(w). Я построил свое дерево суффикса, используя комбинированный ответ здесь; однако алгоритмы работают над суффиксом trie (несжатое суффиксное дерево). Поэтому такие концепции, как глубина, необходимо поддерживать и обрабатывать по-разному. В суффиксе trie глубина будет представлять собой длину суффикса; в дереве суффиксов глубина просто представляет глубину node в дереве.