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

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

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

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


string large-files algorithm suffix-tree
person diffuse    schedule 17.11.2010    source источник
comment
Почему он должен работать непрерывно? Данные меняются?   -  person jonderry    schedule 17.11.2010
comment
Почему бы не использовать готовое программное обеспечение для сжатия?   -  person Jason Orendorff    schedule 17.11.2010
comment
jonderry: Я, наверное, не совсем ясно выразился, я имел в виду, что после каждого прохода ему нужно будет найти следующую самую длинную подстроку и так далее.   -  person diffuse    schedule 17.11.2010
comment
jason: какие алгоритмы сжатия достигают этого?   -  person diffuse    schedule 17.11.2010
comment
Дубликат stackoverflow.com/questions/1916218/?   -  person Patrick    schedule 18.11.2010

Ответы (1)


arrow_upward
4
arrow_downward

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

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

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

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

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

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 для хранения ваших вычислений. Также проверьте эту страницу.

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

person sdadffdfd    schedule 17.11.2010
comment
Можете ли вы предоставить мне пример кода или указать ресурсы? Я просто подумал, что сортировка массива из 100 МБ займет очень много времени, может быть, я ошибаюсь. - person diffuse; 17.11.2010
comment
Приведенная выше статья идеальна. Максимальная сложность - O (nm), где n и m - длины сравниваемых строк. Я не думаю, что есть более быстрый способ сделать это. - person sdadffdfd; 18.11.2010
comment
Похоже, вопрос касается удаления повторяющихся битов текста в одном файле (я думаю), и в этом случае вам понадобится for j := i+1..n. Кроме того, обязательно сохраняйте только последнюю и текущую строки, иначе L будет иметь размер около 1e16! - person Jeffrey L Whitledge; 18.11.2010