Как ускорить вычисление длины самой длинной общей подстроки?

У меня есть две очень большие строки, и я пытаюсь выяснить их Самая длинная общая подстрока.

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

Использование динамического программирования alt text

Проблема в том, что метод динамического программирования имеет огромное время работы (сложность равна O(n*m), где n и m — длины двух строк).

Что я хочу знать (прежде чем переходить к реализации суффиксных деревьев): Можно ли ускорить алгоритм, если я хочу знать только длину общей подстроки (а не самой общей подстроки)?


c++ algorithm dynamic-programming lcs suffix-tree
person Lazer    schedule 25.04.2010    source источник

Ответы (4)


arrow_upward
2
arrow_downward

Будет ли это быстрее на практике? да. Будет ли это быстрее относительно Big-Oh? Нет. Решение динамического программирования всегда равно O(n*m).

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

Удачи :)

person Billy ONeal    schedule 25.04.2010
comment
@Billy ONeal: вы сравниваете дерево суффиксов и динамическое программирование? Я не прошу об этом. What I what to know is that is there a way to make the dynamic programming algorithm faster if I only want to know the length of the common substring? - person Lazer; 26.04.2010
comment
@eSKay: я считаю, что первая часть моего ответа отвечает на этот вопрос. - person Billy ONeal; 26.04.2010
comment
@eSKay: алгоритм нахождения длины и фактической строки одинаковый. Единственное отличие состоит в том, что алгоритм, находящий фактическую строку, сохраняет фактическую строку вместе с этой длиной в таблице. Не сохраняя строку, вы можете работать быстрее, поскольку тратите меньше времени на выделение строк. Поэтому быстрее, но не в плане Big-Oh. - person Billy ONeal; 26.04.2010

arrow_upward
3
arrow_downward

Это ускорит его работу, но все равно будет O(nm).

Одна оптимизация находится в пространстве (что может сэкономить вам немного времени на выделение), замечая, что LCSuff зависит только от предыдущей строки, поэтому, если вас интересует только длина, вы можете оптимизировать пространство O(nm) до O(min(n,m)).

Идея состоит в том, чтобы сохранить только две строки — текущую строку, которую вы обрабатываете, и предыдущую строку, которую вы только что обработали, а остальные выбросить.

person Larry    schedule 25.04.2010
comment
@Ларри: спасибо! Я уже реализовал это, хотя. Любые другие, которые приходят вам в голову? - person Lazer; 26.04.2010
comment
Другой заключается в реализации как сверху вниз, так и снизу вверх. Вы можете применить некоторые методы ветвей и границ сверху вниз, чтобы ускорить работу и, возможно, пропустить состояния, которые никогда не понадобятся. - person Larry; 26.04.2010

arrow_upward
0
arrow_downward

Вот простой алгоритм, который может завершиться за O((m+n)*log(m+n)), и его гораздо проще реализовать по сравнению с алгоритмом дерева суффиксов, который выполняется за O(m+n).

пусть он начинается с минимальной общей длины (minL) = 0 и максимальной общей длины (maxL) = min(m+n)+1.

1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.

Остается проблема, как хэшировать всю подстроку длины L за время O(n). Вы можете использовать формулу полинома следующим образом:

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];
person DU Jiaen    schedule 16.11.2015

arrow_upward
-1
arrow_downward

Вам может помочь бит-векторный алгоритм Майера. Он работает с использованием битовых манипуляций и является гораздо более быстрым подходом.

person Suraj Kumar Ghosh    schedule 16.11.2015
comment
@Lance: Использование X названного канонического алгоритма определенно является ответом, хотя и несколько разреженным. - person Nathan Tuggy; 16.11.2015
comment
Эм, я не помню, чтобы делал этот комментарий. Извиняюсь. Во всяком случае, я бы назвал это ответом только для ссылки. - person Lance; 16.11.2015