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

У меня есть два файла — назовем их файл0 и файл1.

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

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

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

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

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

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.


prefix algorithm
person Nubok    schedule 31.03.2011    source источник
comment
Насколько медленный ваш медленный алгоритм и насколько быстрый он вам нужен? Я могу придумать алгоритм, но, насколько мне известно, он медленнее вашего.   -  person drysdam    schedule 31.03.2011

Ответы (3)


arrow_upward
1
arrow_downward

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

person templatetypedef    schedule 31.03.2011
comment
Это кажется хорошей идеей. Линейный по длине размер файла меньшего размера достаточно быстр. - person Nubok; 31.03.2011
comment
Если вы можете подсказать, как поступить в случае, когда дерево суффиксов просто больше не помещается в память (из-за ограничений 32-битного адресного пространства на X86), я полностью удовлетворен. - person Nubok; 31.03.2011
comment
Если один из файлов, но не другой, может иметь дерево суффиксов, которое помещается в память, вы всегда можете поменять местами два файла, построить дерево суффиксов для второго файла, найти самый длинный суффикс первого файла, который является префиксом первого файла. второй файл. Будет ли это работать? - person templatetypedef; 31.03.2011
comment
Мне ясно, что вы можете ограничить себя размером меньшего файла. Как я сказал в своем замечании: большинство файлов достаточно малы (от 10 до нескольких сотен МБ), но это также должно работать, когда они имеют размер в несколько ГБ. Думаю для обработки этих файлов напишу небольшой менеджер памяти, который подкачивает на диск неиспользуемые части суффиксного дерева - это не самый быстрый способ, но свою работу делает. - person Nubok; 01.04.2011

arrow_upward
3
arrow_downward

Рассмотрите возможность обработки ваших байтов как чисел 0..255, хранящихся как целые числа по модулю 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 и слева направо в BC. Если вычисленные значения совпадают, вы записываете местоположение. Позже выполните медленную проверку всех совпадений, начиная с самого длинного, чтобы убедиться, что B действительно одинакова в обоих случаях.

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

person mcdowella    schedule 31.03.2011

arrow_upward
1
arrow_downward

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

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

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

person jfs    schedule 31.03.2011