Самая длинная повторяемая (k раз) подстрока

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

Это для проблема проекта Rosalind LREP. Я пытаюсь найти самую длинную подстроку k-peated в строке, и я был предоставлен деревом суффиксов, что приятно. Я знаю, что мне нужно аннотировать таблицу суффиксов количеством оставшихся листьев от каждого node, а затем найти узлы с потомками >=k и, наконец, найти самый глубокий из этих узлов. Понятно, что я настроен.

Я получил большую помощь из следующих ресурсов (oops, я могу только отправить 2):

Я могу получить пути от корня до каждого листа, но я не могу понять, как предварительно обработать дерево таким образом, чтобы я мог получить количество потомков из каждого node. У меня есть отдельный алгоритм, который работает на небольших последовательностях, но в экспоненциальной сложности, поэтому для больших вещей он занимает слишком много времени. Я знаю, что с DFS я должен выполнять всю задачу в линейной сложности. Чтобы этот алгоритм работал, мне нужно иметь возможность получить самый длинный k-торф длиной более 40 000 строк менее чем за 5 минут.

Здесь приведены некоторые примеры данных (первая строка: sequence, вторая строка: k, формат таблицы суффиксов: parent child location length):

CATACATAC$
2
1 2 1 1
1 7 2 1
1 14 3 3
1 17 10 1
2 3 2 4
2 6 10 1
3 4 6 5
3 5 10 1
7 8 3 3
7 11 5 1
8 9 6 5
8 10 10 1
11 12 6 5
11 13 10 1
14 15 6 5
14 16 10 1

Выход из этого должен быть CATAC.

Со следующим кодом (измененным из LiteratePrograms) Я смог получить пути, но он все еще занимает много времени время для более длинных последовательностей для анализа пути для каждого node.

#authors listed at
#http://en.literateprograms.org/Depth-first_search_(Python)?action=history&offset=20081013235803
class Vertex:
    def __init__(self, data):
        self.data = data
        self.successors = []

def depthFirstSearch(start, isGoal, result):
    if start in result:
        return False

    result.append(start)

    if isGoal(start):
        return True
    for v in start.successors:
        if depthFirstSearch(v, isGoal, result):
            return True

    # No path was found
    result.pop()
    return False

def lrep(seq,reps,tree):
    n = 2 * len(seq) - 1
    v = [Vertex(i) for i in xrange(n)]
    edges = [(int(x[0]),int(x[1])) for x in tree]
    for a, b in edges:
        v[a].successors.append(v[b])

    paths = {}
    for x in v:
        result = []
        paths[x.data] = []
        if depthFirstSearch(v[1], (lambda v: v.data == x.data), result):
            path = [u.data for u in result]
            paths[x.data] = path

Что бы я хотел сделать, это предварительно обработать дерево, чтобы найти узлы, которые удовлетворяют требованию descendants >= k, прежде чем находить глубину. Я даже не добрался до того, как еще собираюсь рассчитать глубину. Хотя я предполагаю, что у меня будет некоторый словарь для отслеживания глубин каждого node в пути, а затем суммы.

Итак, мой первый самый важный вопрос: "Как препроцессить дерево с листьями потомков?"

Мой второй-менее важный вопрос: "После этого, как я могу быстро вычислить глубину?"

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

Ответы

Ответ 1

Хороший вопрос для упражнений в основных строковых операциях. Я больше не помню суффикс-дерево;) Но, как вы заявили: теория-мудрый, вы настроены.

Как предварительно обработать дерево листьями потомков?

wikipedia-stub на эту тему немного запутан. Вам нужно только знать, если вы являетесь самым внешним не-leaf- node с детьми n >= k. Если вы нашли подстроку от root-node к этому во всей строке, суффикс-дерево сообщает вам, что существуют n возможные продолжения. Таким образом, должно существовать n места, где происходит эта строка.

После этого, как быстро вычислить глубину?

Простая ключевая концепция этой и многих подобных проблем заключается в том, чтобы выполнить поиск по глубине: в каждом Node задайте дочерние элементы для их значения и верните максимальное значение родительскому элементу. Окончательный результат получит root-node.

Как рассчитываются значения, различаются проблемы. Здесь у вас есть три возможности для каждого node:

  • node не имеют дочерних элементов. Его лист - node, результат недействителен.
  • Каждый ребенок возвращает неверный результат. Его последний не-лист- node, результат равен нулю (после символа node больше символов). Если этот node имеет дочерние элементы n, то конкретизированная строка каждого ребра из корня в этот node появляется n раз во всей строке. Если нам нужны не менее k узлы и k > n, результат также недействителен.
  • Один или несколько листов возвращают что-то действительное. Результатом является максимальное значение возвращаемого значения плюс, длина строки привязала к нему ребро.

Конечно, вам также нужно вернуть корреспондирующий node. В противном случае вы узнаете, как долго длится повторяющаяся подстрока, но не там, где она есть.

код

Сначала вы должны попытаться закодировать это самостоятельно. Построение дерева прост, но не тривиально, если вы хотите собрать всю необходимую информацию. Тем не менее, вот простой пример. Обратите внимание: каждая проверка работоспособности выбывает из строя, и все будет терпеть неудачу, если вход каким-то образом недействителен. Например. не пытайтесь использовать какой-либо другой корневой индекс, чем один, не ссылайтесь на узлы как на родителя, на которые раньше не указывались дочерние элементы и т.д. Много места для улучшения * hint;) *.

class Node(object):
    def __init__(self, idx):
        self.idx = idx     # not needed but nice for prints 
        self.parent = None # edge to parent or None
        self.childs = []   # list of edges

    def get_deepest(self, k = 2):
        max_value = -1
        max_node = None
        for edge in self.childs:
            r = edge.n2.get_deepest()
            if r is None: continue # leaf
            value, node = r
            value += len(edge.s)
            if value > max_value: # new best result
                max_value = value
                max_node = node
        if max_node is None:
            # we are either a leaf (no edge connected) or 
            # the last non-leaf.
            # The number of childs have to be k to be valid.
            return (0, self) if len(self.childs) == k else None
        else:
            return (max_value, max_node)

    def get_string_to_root(self):
        if self.parent is None: return "" 
        return self.parent.n1.get_string_to_root() + self.parent.s

class Edge(object):
    # creating the edge also sets the correspondending
    # values in the nodes
    def __init__(self, n1, n2, s):
        #print "Edge %d -> %d [ %s]" % (n1.idx, n2.idx, s)
        self.n1, self.n2, self.s = n1, n2, s
        n1.childs.append(self)
        n2.parent = self

nodes = {1 : Node(1)} # root-node
string = sys.stdin.readline()
k = int(sys.stdin.readline())
for line in sys.stdin:
    parent_idx, child_idx, start, length = [int(x) for x in line.split()]
    s = string[start-1:start-1+length]
    # every edge constructs a Node
    nodes[child_idx] = Node(child_idx)
    Edge(nodes[parent_idx], nodes[child_idx], s)

(depth, node) = nodes[1].get_deepest(k)
print node.get_string_to_root()