Нахождение самой длинной общей подпоследовательности в переменном количестве наборов без повторяющихся символов?

Question

Я пытаюсь найти эффективный алгоритм, который работал бы в JavaScript для самой длинной общей проблемы подпоследовательности .Однако между моей проблемой и проблемой, описанной в статье в Википедии, есть два основных различия.Во-первых, у меня будет более двух наборов символов.Во-вторых, символы никогда не будут повторяться в наборе.Это означает, что длина каждого набора будет не более 50 символов (то есть печатаемых символов ASCII).

Например, наборы могут содержать:

A = ZBANICOT
B = ACNTBZIO
C = ANICOTZB
D = ZIANCOTB

... ион должен вывести ACO, ACT, ANO и ANT, так как это самые длинные подпоследовательности во всех 4 наборах (насколько я могу судить по ручной проверке этих наборов).

Поскольку ни одна из букв не повторяется, есть ли более эффективный алгоритм, который я должен рассмотреть, а не тот, который описан в статье Википедии?Если нет, есть ли где-нибудь описание того, как преобразовать алгоритм в N наборов вместо 2?

Answer 1

Не уверен, насколько эффективной была бы адаптация обычного алгоритма LCS, поэтому это может быть неэффективно, но, поскольку подходящих букв не так много, это не так уж и ужасно.

Создайте матрицу-преемник. Для каждой строки s, для каждой пары букв (s[i],s[j]) с i < j, приращение matrix[s[i]][s[j]]. Пара букв может быть частью самой длинной общей подпоследовательности, если matrix[a][b] = n = number of strings. Постройте ориентированный граф из букв, участвующих в такой паре, с ребром от a до b тогда и только тогда matrix[a][b] = n. Найдите самый длинный путь в этом графе.

Answer 2

То, что вы пытаетесь сделать, называется выравнивание нескольких последовательностей .Алгоритм «можно» переписать так, чтобы он был n-мерным, но это увеличило бы сложность пространства до Length ^ Dimensions.

Поскольку ни одна из букв не повторяется, есть ли более эффективный алгоритм, который я должен рассмотретьа не тот, который описан в статье Википедии?

Возможно.Сначала создайте отображение (a, b) так, чтобы a --- Mapping for character[0] Z - B A - C A - N Z - I A N I A N I C N I B O C C Z T O O I Z T T O B B --- Mapping for character[1] B - A C - N N - I I - A N I C N I B O C C Z T O O I Z T T O B B --- Mapping for character[2] A - N N - I N - C I - N I B O C C Z T O O I Z T T O B B Затем сохраняются только сопоставления, общие для всех наборов.Вот пример следования этому процессу, обход набора [A] (ZBANICOT), который даст нам набор отношений, общих для всех наборов.

Итак, с буквой Z вы увидитечто в Set [C] единственным символом, который следует за Z, является B, так что вы можете исключить практически все сопоставления из Z, которые не относятся к B. Но вкратце, каждое сопоставление для Z удаляется.Обратите внимание, что удаляются только сопоставления из Z, а не сопоставления с Z.

Также обратите внимание, что поскольку Set [D] заканчивается на B, мы можем безопасно удалить все сопоставления из B.Следуя этому процессу, можно наблюдать, что A отображается на N, C, O и T.Далее идет N, которое отображается на T и O.

I отображается на O (честно, "I / O"), в то время как C отображается на O и T (Какой милый).И как ни странно, O ничего не отображает !!!Как следует.

Наконец, есть еще один символ, и T тоже ничего не отображает (так как ZBANICOT заканчивается T).

В конце концов, вы остаетесь сследующие сопоставления:

A - C    C - O    I - O    N - O
    N        T                 T
    O
    T

Теперь все, что вам нужно сделать, это начать с каждого из ключей (A, C, I и N) и искать самую длинную последовательность без каких-либоповторяющиеся узлы (в данном случае символы).

Вот все общие подпоследовательности (все с использованием простого алгоритма):

ACO
ACT
ANO
ANT
AO
AT
CO
CT
IO
NT
NO

Answer 3

Что если бы я сохранил сопоставление символов для каждого набора символов и затем увеличивал это число каждый раз ...

Для 1-го набора (ZBANICOT) это создаст следующие пары символов (28 изих):

ZB, ZA, ZN, ZI, ZC, ZO, ZT
    BA, BN, BI, BC, BO, BT
        AN, AI, AC, AO, AT
            NI, NC, NO, NT
                IC, IO, IT
                    CO, CT
                        OT

Для 2-го сета (ACNTBZIO) у меня снова будет 28 пар:

AC, AN, AT, AB, AZ, AI, AO
    CN, CT, CB, CZ, CI, CO
        NT, NB, NZ, NI, NO
            TB, TZ, TI, TO
                BZ, BI, BO
                    ZI, ZO
                        IO

Для 2 последних сессий у меня будет:

AN, AI, AC, AO, AT, AZ, AB
    NI, NC, NO, NT, NZ, NB
        IC, IO, IT, IZ, IB
            CO, CT, CZ, CB
                OT, OZ, OB
                    TZ, TB
                        ZB

ZI, ZA, ZN, ZC, ZO, ZT, ZB
    IA, IN, IC, IO, IT, IB
        AN, AC, AO, AT, AB
            NC, NO, NT, NB
                CO, CT, CB
                    OT, OB
                        TB

(Итак, чтобы подсчитать количество итераций, пусть N будет равно числу наборов, а M будет количеством символов в каждом наборе, у нас будет N*(M)((M-1)/2) или 4*28=112в этом примере)

Далее я бы посчитал, сколько раз существует каждая пара.Например,

PairCounts["ZB"] == 3
PairCounts["ZA"] == 2
// ...
PairCounts["AO"] == 4
PairCounts["AT"] == 4
// ...
PairCounts["AN"] == 4
PairCounts["AC"] == 4
PairCounts["CT"] == 4
PairCounts["NO"] == 4
PairCounts["NT"] == 4

Тогда, так как у нас есть 4 пары, я бы отбросил все пары, у которых нет счетчика 4. И затем я бы попытался объединить каждую пару, чтобы сформировать самую длинную строку.возможно.