Нахождение самой длинной общей подстроки в большом наборе данных

Question

За последние несколько дней я тщательно исследовал это, я прочитал так много вещей, что теперь я запутался больше, чем когда-либо. Как найти самую длинную общую подстроку в большом наборе данных? Идея состоит в том, чтобы удалить дублированный контент из этого набора данных (различной длины, поэтому алгоритм должен будет работать непрерывно). Под большим набором данных я имею в виду примерно 100 МБ текста.

Суффикс дерево? Суффиксный массив? Рабина-Карпа? Какой лучший способ? И есть ли библиотека, которая может мне помочь?

Очень надеясь на хороший ответ, у меня сильно болит голова. Спасибо! : -)

Answer 1

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

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

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

LE: Кстати, вам не нужно удалять какие-либо данные, чтобы найти самую длинную общую подстроку.

Из самой длинной общей проблемы с подстроки :

function LCSubstr(S[1..m], T[1..n])
    L := array(1..m, 1..n)
    z := 0
    ret := {}
    for i := 1..m
        for j := 1..n
            if S[i] = T[j]
                if i = 1 or j = 1
                    L[i,j] := 1
                else
                    L[i,j] := L[i-1,j-1] + 1
                if L[i,j] > z
                    z := L[i,j]
                    ret := {}
                if L[i,j] = z
                    ret := ret ∪ {S[i-z+1..i]}
    return ret

Вам не нужно ничего сортировать, вам нужно только один раз проанализировать ваши 100-мегабайтные данные и создать массив символов n * m для хранения ваших вычислений.Также проверьте эту страницу

LE: Рабин-Карп - это алгоритм сопоставления с образцом, он вам здесь не нужен.