Определить наибольший суффикс некоторого файла, который является префиксом другого файла - PullRequest
Новая
       5

Определить наибольший суффикс некоторого файла, который является префиксом другого файла

4 голосов
/ 31 марта 2011

У меня есть два файла - давайте назовем их file0 и file1.

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

Определить самый большой суффикс file0, который является префиксом file1, что означает блок памяти B (или, точнее: число байтов такого блока памяти) максимальной длины, так что

  • file0 состоит из некоторого блока памяти A, за которым следует B
  • file1 состоит из блока памяти B, за которым следует блок памяти C

Обратите внимание, что блоки A, B и C также могут иметь длину нулевых байтов.

Редактировать (чтобы ответить на замечание Драйсдама): очевидный довольно медленный алгоритм, о котором я думаю (псевдокод): пусть длина файлов ограничена m, n с wlog m <= n. </p> 

for each length from m to 0
    compare the m last bytes of file0 with the first m bytes of file1
    if they are equal
        return length

Это, очевидно, алгоритм O (m * min (m, n)). Если файлы примерно одинакового размера, это O (n ^ 2).

Файлы, которые я должен обработать в настоящее время, имеют размер от 10 до нескольких сотен мегабайт. Но в крайних случаях они также могут иметь размер в несколько гигабайт - достаточно большой, чтобы больше не помещаться в 32-разрядное адресное пространство x86.

Ответы [ 3 ]

3 голосов
/ 31 марта 2011

Рассмотрим обработку ваших байтов как чисел 0..255, хранящихся как целые числа mod p, где p - простое число, необязательно намного больше, чем 255. Вот два способа вычисления b0 * x ^ 2 + b1 * x + b2:

(b0 * x + b1) * x + b2

b0 * x ^ 2 + (b1 * x + b2).

Поэтому я могу эффективно вычислить эту величину либоработая слева направо - умножьте на x и добавив b2, или работая справа налево - добавив b0 * x ^ 2.

Выберите случайный x и вычислите эту работу справа налево в AB и изслева направо в до н.Если вычисленные значения совпадают, запишите местоположение.Позже сделайте медленную проверку всех совпадений, начиная с самого длинного, чтобы увидеть, действительно ли B в обоих случаях одинаковы.

Какова вероятность совпадения случайным образом?Если у вас ложное совпадение, то (a0 - c0) * x ^ 2 + (a1 - c1) * x + (a2 - c2) = 0. Многочлен степени d имеет не более d корней, поэтому, если x случайный,вероятность ложного совпадения составляет самое большее d / p, и вы можете сделать это маленьким, работая мод p для достаточно большого p.(Если я правильно помню, существует схема аутентификации сообщений, в основе которой лежит эта идея).

1 голос
/ 01 апреля 2011

Если это не академическое задание, то, возможно, имеет смысл реализовать простейшее решение и посмотреть, как оно ведет себя с вашими данными.

Например, теоретически более эффективное решение на основе алгоритма Кнута-Морриса-Пратта может работать хуже, чем решение на основе IndexOf (см. Обнаружение перекрытия ).

Для больших файлов ваша программа может тратить все время на ожидание ввода / вывода.

1 голос
/ 31 марта 2011

В зависимости от того, сколько памяти у вас есть, вы можете рассмотреть возможность создания дерева суффиксов для первого файла.Получив это, вы можете запросить префикс второго файла, который максимально перекрывается с суффиксом второго файла, просто переместив дерево суффиксов вниз от корня по краям, соответствующим буквам префикса второго файла.Поскольку деревья суффиксов могут быть построены за линейное время, время выполнения для этого алгоритма составляет O (| A | + | B |), используя вашу терминологию, поскольку для построения дерева суффиксов требуется O (| A | + | B |).O (| B |) время пройти по дереву суффиксов, чтобы найти блок B.

...