Учитывая две последовательности, найдите максимальное перекрытие между окончанием одного и началом другого

11

Мне нужно найти эффективный (псевдо) код для решения следующей проблемы:

Учитывая две последовательности (не обязательно различных) целых чисел (a[1], a[2], ..., a[n])и (b[1], b[2], ..., b[n]), найти максимальное dтакое , что a[n-d+1] == b[1], a[n-d+2] == b[2]..., и a[n] == b[d].

Это не домашняя работа, я на самом деле придумал это, когда пытался сжать два тензора вдоль как можно большего числа измерений. Я подозреваю, что эффективный алгоритм существует (возможно O(n)?), Но я не могу придумать что-то, чего нет O(n^2). O(n^2)Подход был бы очевидной петля на , dа затем внутренний цикл по пунктам, чтобы проверить требуемое состояние до удара максимума d. Но я подозреваю, что лучше, чем это возможно.

algorithm sequence becko
источник
Если для группы объектов в вашем массиве можно вычислить скользящий хэш, я думаю, что это можно сделать более эффективно. Вычислить хеш для элементов, b[1] to b[d]а затем перейти к массиву aвычислить хеш, a[1] to a[d]если он совпадает, то это ваш ответ, если не вычислить хеш для a[2] to a[d+1]повторного использования хеша, вычисленного для a[1] to a[d]. Но я не знаю, могут ли объекты в массиве быть пригодными для вычисления на них хеш-кода.
SomeDude
2
@becko Извините, я, наконец, понял, чего вы пытаетесь достичь. Который должен найти максимальное перекрытие между концом aи началом b. Как это .
user3386109
1
Мне кажется, что проблема заключается в вариации сопоставления строк, которую можно решить с помощью вариации алгоритма Кнута-Морриса-Пратта . Время выполнения будет O (m + n), где mчисло элементов в a, и nколичество элементов в b. К сожалению, у меня недостаточно опыта работы с KMP, чтобы рассказать, как его адаптировать.
user3386109
1
@ user3386109 Мое решение также является вариантом алгоритма сопоставления строк, который называется Rabin-Karp , с использованием метода Хорнера в качестве хэш-функции.
Даниэль
1
@ Даниэль Ах, я знал, что видел где-то используемый хэш, но не мог вспомнить где :)
user3386109

Ответы:

5

Вы можете использовать алгоритм z, алгоритм линейного времени ( O (n) ), который:

Для строки S длиной n алгоритм Z создает массив Z, где Z [i] - длина самой длинной подстроки, начиная с S [i], которая также является префиксом S

Вам нужно объединить ваши массивы ( b + a ) и запустить алгоритм на полученном построенном массиве до первого i, такого, что Z [i] + i == m + n .

Например, для a = [1, 2, 3, 6, 2, 3] & b = [2, 3, 6, 2, 1, 0] конкатенация будет [2, 3, 6, 2, 1 , 0, 1, 2, 3, 6, 2, 3], что привело бы к Z [10] = 2, при этом Z [i] + i = 12 = m + n .

Amit
источник
Прекрасный! Спасибо.
Беко
3

Для O (n) временной / пространственной сложности задача состоит в том, чтобы оценить хэши для каждой подпоследовательности. Рассмотрим массив b:

[b1 b2 b3 ... bn]

Используя метод Хорнера , вы можете оценить все возможные хеши для каждой подпоследовательности. Выберите базовое значение B(больше, чем любое значение в обоих ваших массивах):

from b1 to b1 = b1 * B^1
from b1 to b2 = b1 * B^1 + b2 * B^2
from b1 to b3 = b1 * B^1 + b2 * B^2 + b3 * B^3
...
from b1 to bn = b1 * B^1 + b2 * B^2 + b3 * B^3 + ... + bn * B^n

Обратите внимание, что вы можете оценить каждую последовательность за O (1) раз, используя результат предыдущей последовательности, следовательно, все затраты на работу O (n).

Теперь у вас есть массив Hb = [h(b1), h(b2), ... , h(bn)], где Hb[i]находится хэш от b1до bi.

Сделайте то же самое для массива a, но с небольшим фокусом:

from an to an   =  (an   * B^1)
from an-1 to an =  (an-1 * B^1) + (an * B^2)
from an-2 to an =  (an-2 * B^1) + (an-1 * B^2) + (an * B^3)
...
from a1 to an   =  (a1   * B^1) + (a2 * B^2)   + (a3 * B^3) + ... + (an * B^n)

Вы должны заметить, что при переходе от одной последовательности к другой вы умножаете всю предыдущую последовательность на B и добавляете новое значение, умноженное на B. Например:

from an to an =    (an   * B^1)

for the next sequence, multiply the previous by B: (an * B^1) * B = (an * B^2)
now sum with the new value multiplied by B: (an-1 * B^1) + (an * B^2) 
hence:

from an-1 to an =  (an-1 * B^1) + (an * B^2)

Теперь у вас есть массив Ha = [h(an), h(an-1), ... , h(a1)], где Ha[i]находится хэш от aiдо an.

Теперь вы можете сравнить Ha[d] == Hb[d]все dзначения от n до 1, если они совпадают, у вас есть свой ответ.

ВНИМАНИЕ : это хеш-метод, значения могут быть большими, и вам, возможно, придется использовать метод быстрого возведения в степень и модульную арифметику , которые могут (вряд ли) привести к коллизиям , что делает этот метод не совсем безопасным. Хорошая практика - выбирать базу Bкак действительно большое простое число (по крайней мере, больше, чем наибольшее значение в ваших массивах). Вы также должны быть осторожны, так как ограничения чисел могут переполняться на каждом шаге, поэтому вам придется использовать (по модулюK ) в каждой операции (где Kпростое число может быть больше, чем B).

Это означает, что две разные последовательности могут иметь одинаковый хеш, но две равные последовательности всегда будут иметь одинаковый хеш.

Даниил
источник
Можете ли вы начать этот ответ с оценки потребностей в ресурсах?
седобородый
2

Это действительно может быть сделано за линейное время, O (n) и O (n) дополнительное пространство. Я предполагаю, что входные массивы являются символьными строками, но это не обязательно.

Наивный метод - после сопоставления k символов, которые равны, - находит символ, который не соответствует, и возвращает k-1 единицы в a , сбрасывает индекс в b , а затем начинает процесс сопоставления оттуда. Это ясно представляет наихудший случай O (n²) .

Чтобы избежать этого процесса обратного отслеживания, мы можем заметить, что возврат назад бесполезен, если мы не встретили символ b [0] при сканировании последних k-1 символов. Если мы действительно обнаружили , что характер, а затем откат к этой позиции будет только полезно, если в том , что к SIZED подстроки мы имели периодическое повторение.

Например, если мы посмотрим на подстроку "abcabc" где-то в a , а b равно «abcabd», и мы обнаружим, что последний символ b не совпадает, мы должны учитывать, что успешное совпадение может начаться со второй «a» в подстроке, и мы должны переместить наш текущий индекс в б соответственно, прежде чем продолжить сравнение.

Идея состоит в том, чтобы сделать некоторую предварительную обработку на основе строки b, чтобы зарегистрировать обратные ссылки в b , которые полезны для проверки в случае несоответствия. Так, например, если b - «acaacaacd», мы могли бы идентифицировать эти обратные ссылки на основе 0 (ставить под каждым символом):

index: 0 1 2 3 4 5 6 7 8
b:     a c a a c a a c d
ref:   0 0 0 1 0 0 1 0 5

Например, если у нас есть равны «acaacaaca» первое несоответствие происходит на последний символ. Приведенная выше информация затем указывает алгоритму вернуться в b к индексу 5, поскольку «acaac» является распространенным. А потом только с изменением текущего индекса в б мы можем продолжить согласование по текущему индексу а . В этом примере совпадение с последним символом завершается успешно.

При этом мы можем оптимизировать поиск и убедитесь , что индекс в всегда может прогрессировать вперед.

Вот реализация этой идеи в JavaScript с использованием только самого основного синтаксиса этого языка:

function overlapCount(a, b) {
    // Deal with cases where the strings differ in length
    let startA = 0;
    if (a.length > b.length) startA = a.length - b.length;
    let endB = b.length;
    if (a.length < b.length) endB = a.length;
    // Create a back-reference for each index
    //   that should be followed in case of a mismatch.
    //   We only need B to make these references:
    let map = Array(endB);
    let k = 0; // Index that lags behind j
    map[0] = 0;
    for (let j = 1; j < endB; j++) {
        if (b[j] == b[k]) {
            map[j] = map[k]; // skip over the same character (optional optimisation)
        } else {
            map[j] = k;
        }
        while (k > 0 && b[j] != b[k]) k = map[k]; 
        if (b[j] == b[k]) k++;
    }
    // Phase 2: use these references while iterating over A
    k = 0;
    for (let i = startA; i < a.length; i++) {
        while (k > 0 && a[i] != b[k]) k = map[k];
        if (a[i] == b[k]) k++;
    }
    return k;
}

console.log(overlapCount("ababaaaabaabab", "abaababaaz")); // 7
Развернуть фрагмент

Хотя есть вложенные whileциклы, они не имеют больше итераций, чем n . Это потому, что значение к строго уменьшается в whileтеле и не может стать отрицательным. Это может произойти только тогда, когда k++было выполнено много раз, чтобы дать достаточно места для такого уменьшения. Таким образом, в целом, не может быть больше казней whileтела, чем естьk++ казней, и последнее явно O (n).

Чтобы завершить, здесь вы можете найти тот же код, что и выше, но в интерактивном фрагменте: вы можете ввести свои собственные строки и увидеть результат в интерактивном режиме:

Показать фрагмент кода

trincot
источник