1

各キーワードにIDが割り当てられ、一意であるキーワードテーブルがあります。親キーワードのIDを子キーワードのIDにリンクする2番目のテーブルがあります。1つのキーワードには、最大で約800人の子を含めることも、まったく子を持たないこともできます。子供はさらに多くのキーワードの親になることができます（そして...）

私が遭遇している問題は、子供（または孫または曽孫）が最初のキーワードの親であり、循環構造を引き起こす可能性があることです。再帰関数を使用して最初のキーワードのツリーデータ構造を構築しようとしていますが、関数が終了しないか、Pythonの1000レベルの再帰制限を超えています。

これを防ぐために（または挿入中に事前チェックを行うために）親/子テーブルを設計するためのより良い方法はありますか、またはこの状態が発生するのを防ぐために再帰関数を書くためのより良い方法はありますか？再帰関数の深さを制限しようとしましたが、単一レベルの問題が発生しました（つまり、子が親の親になります）。繰り返しますが、私の目標は、最初のキーワードのツリー構造を作成することです。

Table Keyword:
    id int(11) not null primary key auto_increment (id of keyword)
    text varchar(255) unique (keyword text e.g. "computer help desk")

Table Keyword_Relation:
    id int(11) not null primary key auto_increment (id for parent/child combo, not keyword id)
    parent int(11) (id of parent keyword)
    child int(11) (id of child keyword)
4

2 に答える 2

2

あなたがやろうとしているのは、トポロジカルソートを作成することです。これを最適に行うために公開されているメソッドは多数あり、スキーマと推奨されるメソッドによって異なります。

あなたの場合、あなたは複数の親を持っていないように聞こえます。しかし、私がプログラムでそれを処理した方法は、リーフノード（つまり、子のないノード）から始めて、ツリーを上ることです。昇順の間、遭遇したノードのコレクションを保持します。遭遇を繰り返すと、サイクルが存在し、トポロジカルソートは不可能になります。

無限ループは発生しませんが、トポロジに1000を超えるノードが含まれる可能性は確かにあります。そのため、再帰が不可能な場合があります。

編集：「より良い設計」についてのあなたの質問に答えるために....可能であれば、ルートノード識別子を保存することが有利かもしれません。つまり、親、子、孫、曽孫、曽孫を与えられた....孫

各行には、直接の親のIDだけでなく、ルートノードの親ID...または「既知の正常な」ルートノードも含まれます。

これを行うと、ルートノードまで昇順で、同じルートノードを持つセットのみを含めることでトポロジカルソートメソッドを高速化できます。

于 2011-08-23T18:16:07.857 に答える
1

ツリーの一番上から始めて、すでに見つけたノードを追跡し、それらを無視することができます。

def getchildren(node, ignore_nodes=[]):
    child_nodes = []
    for child in node.children():
        if child in ignore_nodes:
            continue
        child_nodes.append(child)
        ignore_nodes.append(child)
        nodes, ignore_nodes = getchildren(child, ignore_nodes)
        child_nodes.extend(nodes)
    return child_nodes, ignore_nodes
于 2011-08-23T21:52:35.120 に答える