Нахождение длинных повторных подстрок в массивной струне

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

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

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

Ответ 5

как насчет простой программы:

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)

Ответ 6

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

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

Ответ 7

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

Ответ 8

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

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

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

Ответ 9

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