13

これがやや打ちのめされたトピックであることはわかっていますが、すでに回答されているものから得ることができる助けの限界に達しました.

これは、Rosalind プロジェクトの問題 LREP 用です。文字列内で最長の k ピート部分文字列を見つけようとしていますが、サフィックス ツリーが提供されています。各ノードからの子孫の葉の数で接尾辞テーブルに注釈を付け、子孫を持つノードを>=k見つけ、最後にそれらのノードの最も深いところを見つける必要があることはわかっています。理論的には、私は設定されています。

私は次のリソースから多くの助けを得ました (おっと、投稿できるのは 2 つだけです)。

ルートから各リーフへのパスを取得できますが、各ノードから子孫の数を取得できるようにツリーを前処理する方法がわかりません。小さなシーケンスで機能する別のアルゴリズムがありますが、指数関数的に複雑であるため、大きなものでは時間がかかりすぎます。DFS を使用すれば、線形の複雑さでタスク全体を実行できるはずです。このアルゴリズムが機能するには、長さ 40,000 までの文字列の最長の k-peat を 5 分以内に取得できる必要があります。

サンプル データを次に示します (1 行目: sequence、2 行目: 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から変更) を使用すると、パスを取得できましたが、長いシーケンスでは各ノードのパスを解析するのにまだ長い時間がかかります。

#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、深さを見つける前に要件を満たすノードを見つけることです。深さを計算する方法にもまだ到達していません。パス内の各ノードの深さを追跡し、合計するための辞書があると思いますが。

したがって、私の最初の最も重要な質問は、「ツリーを子孫の葉で前処理するにはどうすればよいですか?」ということです。

2 番目に重要でない質問は、「その後、深度をすばやく計算するにはどうすればよいか」です。

PS これは宿題などではありません。私は、計算上の課題で視野を広げようとしている生化学者です。

4

1 に答える 1

5

基本的な文字列操作の演習に最適な質問です。サフィックスツリーをもう覚えていませんでした;）しかし、あなたが述べたように：理論的には、あなたは設定されています。

子孫の葉を持つツリーを前処理するにはどうすればよいですか?

このトピックに関するウィキペディアのスタブは少しわかりにくいです。子を持つ最も外側の非葉ノードである場合にのみ、知る必要がありますn >= k。ルートノードからこの部分文字列までの部分文字列が文字列全体で見つかった場合、接尾辞ツリーはn継続の可能性があることを示します。nしたがって、この文字列が発生する場所が必要です。

その後、どうすれば深度をすばやく計算できますか?

これと多くの同様の問題の単純な重要な概念は、深さ優先検索を行うことです。すべてのノードで、子要素に値を尋ね、その最大値を親に返します。ルートノードが最終結果を取得します。

値の計算方法は問題によって異なります。ここでは、すべてのノードに対して 3 つの可能性があります。

  1. ノードには子がありません。リーフノードです。結果は無効です。
  2. すべての子は無効な結果を返します。最後の非リーフ ノードであり、結果はゼロです (このノードの後に​​文字はありません)。このノードに子がある場合n、ルートからこのノードまでのすべてのエッジの連結された文字列が、n文字列全体で何度も表示されます。少なくともkノード とが必要な場合k > n、結果も無効です。
  3. 1 つまたは複数のリーフが有効なものを返します。結果は、返された値の最大値に、エッジに接続された文字列の長さを加えたものです。

もちろん、対応するノードも返す必要があります。そうしないと、最も長く繰り返される部分文字列の長さはわかりますが、どこにあるかはわかりません。

コード

最初に自分でこれをコーディングしてみてください。ツリーの構築は単純ですが、必要な情報をすべて収集したい場合は簡単ではありません。それにもかかわらず、ここに簡単な例があります。注意: 入力が何らかの理由で無効な場合、すべての健全性チェックが省略され、すべてが恐ろしく失敗します。たとえば、1 つ以外のルート インデックスを使用しようとしない、以前は子として参照されなかったノードを親として参照しないなどです。改善の余地がたくさんあります *ヒント;)*。

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()
于 2012-11-16T17:03:29.590 に答える