Какой алгоритм лучше подходит для неупорядоченной последовательности задач?

Question

Если у меня есть две последовательности (например, строка)

//   01234567890123456789012  
a = "AAACDDFFFEE1122VV1VAADD"

//   0123456789012345678901
b = "DDFFAA11221DHHVV1VAAFE"

Я хочу знать лучшее совпадение подстрок (неупорядоченных) от b до a, например:

optimal (6 matched parts, 19 characters of a matched)
b         a
DDFF   -> DDFF     (4,7)
AA     -> AA       (0,1)
1122   -> 1122     (11,14)
1     
D      -> D        (21)
HH
VV1VAA -> VV1VAA   (15,20)
FE     -> FE       (8,9)

есть другое решение, но не оптимальное:

not optimal (8 parts matched, 19 characters of a matched)
b        a
DDFF  -> DDFF  (4,7)
AA    -> AA    (0,1)
1122  -> 1122  (11,14)
1     -> 1     (17)
D     -> D     (21)
HH
VV    -> VV    (15,16)
1     
VAA   -> VAA   (18,20)
FE    -> FE    (8,9)

Какой алгоритм лучше для этой проблемы ??? (Мне нужен оптимальный результат и производительность критична).

Спасибо.

Answer 1

Интересная проблема, вы можете решить ее в O (| a |. | B | + | b | ^ 2), используя алгоритмы Бойера-Мура (http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algorithm) или KMP (http://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm) или любой другой линейный алгоритм поиска строки времени.

• Для каждого b [0..i] ty найти его в строке a (в O (| a | + i)), пока вы не сможете его найти больше
• Вы знаете, что можете найти b [0..i], но не b [0..i + 1], поэтому у вас есть совпадение для b [0..i], и вы продолжаете с b [i + 1. .i + 1], B [I + 1..i + 2] ..
• В конце каждая часть b была сопоставлена ​​или нет, и если она соответствовала, была ли она максимально большой.

Суммарная сложность не больше суммы (O (| a | + i), i = 0 .. | b |) = O (| a |. | B | + | b | ^ 2), но может быть много меньше, если в a можно найти только небольшие подстроки из b.

РЕДАКТИРОВАТЬ:

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

---

Мысли об оптимальном решении:

• для каждой | b | ^ 2 подстроки | b | определите, можно ли его найти в | a |, и оставьте только те, для которых это верно
• нам нужно найти среди этих строк их подмножество с:
  • нет совпадений между любыми двумя из них
  • максимальная сумма длины
  • равной длины, количество строк должно быть не менее

Сумму легко вычислить, потому что очень простым решением было бы сопоставить только подстроку размера 1: тогда длина - это число общих букв между a и b.

Таким образом, если мы добавим подстроку размера 1 из b (даже букв, которые не находятся в a) к набору соответствующих строк выше, мы должны найти минимальный набор обложек b без наложения.

Общая обложка набора является NP-полной, но здесь с ограничениями без перекрытия, это помогает?

Я смотрю на это.

Действительно, NP-полный: http://www.springerlink.com/content/n73561q050w54pn6/

Возможно, вы захотите поискать алгоритмы аппроксимации ....

Answer 2

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

Так что в вашем примере AAACDDFFFEE1122VV1VAADD DDFFAA11221DHHVV1VAAFE LCS = VV1VAA

AAACDDFFFEE1122DD DDFFAF121 * 100 *21 * 21 * 211 * 215 * 216 * 211

AAACFEE1122DD AA11221DHHFE

LCS = 1122

AAACFEEDD AADHHFE

и т. Д.

Алгоритм следующий 1) Использовать стандартАлгоритм LCS, основанный на деревьях суффиксов, который равен 1.1, строит деревья суффиксов двух сцепленных строк и с уникальными терминаторами 1.2 помечает каждый узел 1,2 или обоими, в зависимости от того, имеет ли корневое поддерево листья из одной или обеих строк.глубина каждого узла 1.4 найдите строковый самый глубокий узел, который помечен как 1 и 2 2) удалите поддерево, укорененное в этом узле, и обновите метки узлов над ним 3) повторите с 1.4

алгоритм завершаетсякогда в дереве нет узлов, помеченных как 1, так и 2, 1.1 можно сделать в пропорции времениl к сумме длин двух строк 1.2, 1.3 и 1.4 немного больше, чем обходы дерева 2, удаление должно быть постоянным временем, если дерево реализовано правильно, а обновление ограничено длиной LCS 3, сноваобход дерева, но меньшего дерева

Так что это одна оптимизация, чтобы избежать повторных обходов дерева, давайте добавим шаг 1.35: сортировка внутренних узлов, имеющих обе метки, по глубине строки (в отдельной структуре данных дерево все ещетам).Теперь вы можете отсканировать этот отсортированный список узлов, выполнить 2) и повторить.С этой оптимизацией, и если вы можете использовать радикальную сортировку, похоже, что алгоритм представляет собой линейное время, и вы не можете превзойти его в асимптотическом смысле.

Я надеюсь, что это правильно и достаточно ясно, я уверен,вам нужно будет немного ознакомиться с литературой по суффиксам, прежде чем она станет очевидной.Я рекомендую книгу Дэна Гусфилда «Алгоритмы строк, деревьев и последовательностей», в частности, раздел 7.4. Дайте мне знать, если у вас есть вопросы.