Найти длинные повторяющиеся подстроки в массивной строке
Я наивно представлял, что мог бы создать три суффиксную запись, в которой я сохраняю счетчик посещений для каждого узла, и тогда самые глубокие узлы с числом больше одного - это набор результатов, который я ищу.
У меня действительно очень длинная строка (сотни мегабайт). У меня около 1 ГБ оперативной памяти.
Вот почему создание суффикса с подсчетом данных слишком неэффективно для меня. Процитируем суффикс-дерево Википедии:
Хранение дерева суффиксов строки обычно требует значительно больше места, чем хранение самой строки.
Большой объем информации в каждом ребре и узле делает дерево суффиксов очень дорогим, потребляя примерно в десять-двадцать раз объем памяти исходного текста в хороших реализациях. Суффиксный массив уменьшает это требование в четыре раза, и исследователи продолжают находить меньшие структуры индексации.
И это были комментарии Википедии о дереве, а не три.
Как я могу найти длинные повторяющиеся последовательности в таком большом количестве данных и за разумное время (например, менее часа на современном настольном компьютере)?
(Некоторые ссылки на Википедию, чтобы люди не публиковали их как "ответ": Алгоритмы на строках и особенно проблема длинных повторяющихся подстрок;-))
9 ответов
Эффективный способ сделать это - создать индекс подстрок и отсортировать их. Это операция O(n lg n).
Сжатие BWT делает этот шаг, поэтому это хорошо понятная проблема, и существуют реализации сортировки по осям и суффиксам (утверждают O(n)) и тому подобное, чтобы сделать ее максимально эффективной. Это все еще занимает много времени, возможно, несколько секунд для больших текстов.
Если вы хотите использовать служебный код, C++ std::stable_sort() работает намного лучше, чем std::sort() для естественного языка (и намного быстрее, чем C qsort(), но по разным причинам).
Затем посещение каждого элемента, чтобы увидеть длину его общей подстроки с соседями, равно O(n).
Вы можете посмотреть на дисковые суффиксные деревья. Я нашел эту библиотеку реализации дерева суффиксов через Google, а также кучу статей, которые могли бы помочь реализовать ее самостоятельно.
Как насчет простой программы, подобной этой:
S = "ABAABBCCAAABBCCM"
def findRepeat(S):
n = len(S)
#find the maxim lenth of repeated string first
msn = int(floor(n/2))
#start with maximum length
for i in range(msn,1,-1):
substr = findFixedRepeat(S, i)
if substr:
return substr
print 'No repeated string'
return 0
def findFixedRepeat(str, n):
l = len(str)
i = 0
while ((i + n -1) < l):
ss = S[i:i+n]
bb = S[i+n:]
try:
ff = bb.index(ss)
except:
ff = -1
if ff >= 0:
return ss;
i = i+1
return 0
print findRepeat(S)
Отвечая на мой собственный вопрос:
Учитывая, что длинное совпадение также является коротким совпадением, вы можете обменять несколько проходов на ОЗУ, сначала найдя более короткие совпадения, а затем посмотрев, можно ли "увеличить" эти совпадения.
Буквальный подход к этому состоит в построении трех (с количеством в каждом узле) всех последовательностей некоторой фиксированной длины в данных. Затем вы отбираете все те узлы, которые не соответствуют вашим критериям (например, самое длинное соответствие). Затем сделайте последующий проход по данным, создавая структуру глубже, но не шире. Повторяйте, пока не найдете самые длинные повторяющиеся последовательности.
Хороший друг предложил использовать хеширование. Хэшируя последовательность символов фиксированной длины, начинающуюся с каждого символа, вы теперь сталкиваетесь с проблемой поиска дублированных хеш-значений (и проверки дублирования, поскольку хеширование с потерями). Если вы выделяете массив длиной данных для хранения значений хеша, вы можете делать интересные вещи, например, чтобы увидеть, больше ли совпадение, чем ваш проход данных фиксированной длины, вы можете просто сравнить последовательности хешей, а не восстановить их. И т.п.
Вы можете решить это, используя разделяй и властвуй. Я думаю, что это должна быть та же алгоритмическая сложность, что и при использовании trie, но, возможно, менее эффективная в плане реализации
void LongSubstrings(string data, string prefix, IEnumerable<int> positions)
{
Dictionary<char, DiskBackedBuffer> buffers = new Dictionary<char, DiskBackedBuffer>();
foreach (int position in positions)
{
char nextChar = data[position];
buffers[nextChar].Add(position+1);
}
foreach (char c in buffers.Keys)
{
if (buffers[c].Count > 1)
LongSubstrings(data, prefix + c, buffers[c]);
else if (buffers[c].Count == 1)
Console.WriteLine("Unique sequence: {0}", prefix + c);
}
}
void LongSubstrings(string data)
{
LongSubstrings(data, "", Enumerable.Range(0, data.Length));
}
После этого вам нужно будет создать класс, который реализует DiskBackedBuffer так, чтобы он представлял собой список чисел, и когда буфер достиг определенного размера, он записывал себя на диск с использованием временного файла и вызывал с диска при чтении от.
Этот текст содержит разрывы слов? Тогда я подозреваю, что вы хотите вариацию ключевого слова в контексте: сделайте копию каждой строки n раз для n слов в строке, разбивая каждую строку в каждом слове; сортировать альфу всего этого; искать повторы.
Если это одна длинная сигнальная строка, как, например, биоинформационные последовательности ДНК, то вы хотите создать что-то вроде вашего файла на диске; построить запись для каждого символа со смещением диска для следующих узлов. Я бы взглянул на том 3 Кнута, раздел 5.4, "внешняя сортировка".
Можете ли вы решить проблему, создав вместо этого массив суффиксов? В противном случае вам, вероятно, понадобится использовать одно из основанных на диске деревьев суффиксов, упомянутых в других ответах.
Просто запоздалая мысль, которая пришла мне в голову...
В зависимости от вашей ОС / среды. (Например, доступны 64-битные указатели & mmap().)
Вы можете создать очень большое суффиксное дерево на диске с помощью mmap(), а затем сохранить в памяти кэшируемое наиболее часто используемое подмножество этого дерева.
Самым простым способом может быть просто потратить $100 для увеличения объема оперативной памяти. В противном случае вам, вероятно, придется взглянуть на структуры на диске для хранения дерева суффиксов.