найти длинные повторяющиеся подстроки в массивной строке

Question

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

У меня действительно очень длинная строка (сотни мегабайт). У меня около 1 ГБ оперативной памяти.

Именно поэтому создание суффикса с подсчетом данных слишком неэффективно для меня. Цитировать Суффиксское дерево Википедии :

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

Большой объем информации в каждом ребре и узле делает дерево суффиксов очень дорогим, потребляя в 10–20 раз больше объема исходного текста в хороших реализациях. Суффиксный массив снижает это требование в четыре раза, и исследователи продолжают находить меньшие структуры индексации.

И это были комментарии Википедии о дереве, а не три.

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

(Некоторые ссылки на Википедию, чтобы люди не публиковали их как «ответ»: Алгоритмы на строках и особенно Проблема самой длинной повторяющейся подстроки ;-))

Answer 1

Эффективный способ сделать это - создать индекс подстрок и отсортировать их. Это операция O (n lg n).

Сжатие

BWT делает этот шаг, так что это хорошо понятная проблема, и существуют реализации сортировки radix и суффикс (утверждают O (n)) и такие, чтобы сделать его настолько эффективным, как возможный. Это все еще занимает много времени, возможно, несколько секунд для больших текстов.

Если вы хотите использовать служебный код, C ++ std::stable_sort() выполняет намного лучше, чем std::sort() для естественного языка (и намного быстрее, чем C qsort(), но по другим причинам).

Тогда посещение каждого элемента, чтобы увидеть длину его общей подстроки с соседями, равно O (n).

Answer 2

Вы можете посмотреть на дисковые суффиксные деревья. Я нашел эту библиотеку реализации дерева суффиксов через Google, а также несколько статей, которые могли бы помочь реализовать ее самостоятельно.

Answer 3

как насчет простой программы, подобной этой:

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)

Answer 4

Отвечая на мой вопрос:

Учитывая, что длинное совпадение также является коротким совпадением, вы можете обменять несколько проходов на ОЗУ, сначала найдя более короткие совпадения, а затем посмотрев, можно ли «увеличить» эти совпадения.

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

Хороший друг предложил использовать хеширование. Хэшируя последовательность символов фиксированной длины, начинающуюся с каждого символа, вы теперь сталкиваетесь с проблемой поиска дублированных хеш-значений (и проверки дублирования, поскольку хеширование с потерями). Если вы выделите массиву длину данных для хранения значений хеша, вы можете делать интересные вещи, например, чтобы увидеть, больше ли совпадение, чем ваш проход данных фиксированной длины, вы можете просто сравнить последовательности хэшей, а не восстанавливать их. И т.д.

Answer 5

Вы можете решить это, используя разделяй и властвуй. Я думаю, что это должна быть та же алгоритмическая сложность, что и при использовании 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 так, чтобы он представлял собой список чисел, и когда буфер достиг определенного размера, он записывал себя на диск с использованием временного файла и вызывал из диск при чтении с.

Answer 6

Этот текст содержит разрывы слов? Тогда я подозреваю, что вы хотите вариацию ключевого слова в контексте: сделайте копию каждой строки n раз для n слов в строке, разбивая каждую строку в каждом слове; сортировать альфу всего этого; искать повторы.

Если это одна длинная гудящая строка, как, например, биоинформационные последовательности ДНК, то вы хотите создать что-то вроде вашего файла на диске; построить запись для каждого символа со смещением диска для следующих узлов. Я бы взглянул на 3 том Кнут , раздел 5.4, "внешняя сортировка".

Answer 7

Просто запоздалая мысль, которая пришла мне в голову ...

В зависимости от вашей ОС / среды. (Например, доступны 64-битные указатели & mmap ().)

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

Answer 8

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

Answer 9

Самый простой способ - просто набрать $ 100 , чтобы получить больше оперативной памяти. В противном случае вам, вероятно, придется взглянуть на структуры на диске для хранения дерева суффиксов.