4

私は、有効性と効率性が鍵となる古いプロジェクトを取り上げています。数百 GB の XML データを解析しています。XML ツリー (何百万もの) ごとに、いくつかの XML 属性が使用され、そこからパターンが推定されます。ただし、この質問については非常に単純化しますが、大量のデータと高速処理があり、結果を XML にきちんと格納することが重要であることを覚えておくことが重要です。さらに、結果の XML ツリーもトラバースする必要があります。実際、これはBaseXで使用されるカスタム インデックス作成メカニズムとして機能しますが、これについては後で説明します。

すべてのツリー (およびそのサブツリーですが、今は重要ではありません) から、ルート ノードの直接の子に基づくパターンが作成されます。基本的な例として、次の XML ツリーを取り上げます。

<node letter="X">
  <node letter="A"/>
  <node letter="B"/>
  <node letter="C"/>
  <node letter="D"/>
</node>

パターンは、すべての子の文字属性を取得し、それらを並べ替えて結合することによって作成されます。この場合、パターンは になりますABCD。

ツリーごとに、すべての可能なサブツリーも生成されます (順序は重要ではなく、最小の組み合わせ 2)、つまり、子のすべての可能な組み合わせと、それらのパターンが生成されます。組み合わせツリーの XML は含めませんが、考えられるパターンは に加えてABCD次のようになります。

AB
ABC
ABD
AC
ACD
AD
BC
BCD
BD
CD

階層では、これらは次のようになります (ターミナル ノードの重複に注意してください)。

パターンのツリー ビュー

さらに、開始した完全なパターンは、それがツリーの「メイン」パターンであることを示すために、生成された XML でなんらかの形で示される必要があります。最終的には、特定のパターンから派生したすべてのパターンを回復し (後で参照)、それらを「メイン」パターンであるパターンのみにフィルター処理したいと考えています。

クエリの観点からは、argue that I am doing a bottom-up look-up. If I am looking for a generalized pattern, e.g. AB, the more specific patterns should also be found becauseAB is part ofABCD が可能です。したがって、AB上記のデータでパターンを探すとしたら、

ABCD
ABC
ABD

ここに 2 つのステップがあることは明らかです。最初に、1 レベル上に一般化します。AB -> ABC,ABD次にABC->ABCD(そしてABD->ABDC、もちろん、各結果は 1 回だけ検出されます)。最終的な結果だけでなく、中間ステップABCと中間ステップも重要です。ABDABCD

私が直面している懸念は、画像に示されているようなツリーをどのように有効に格納して、1. 説明した方法で簡単にクエリできるようにするかということです。2. ノードを失わずにできるだけまばらにする。3.効率的に構築できます。後者の点は、この質問ではそれほど重要ではありません。ビルド スクリプトを自分で実装するためです。これは Python 3.6 で実行されます。

私が今まで持っていたアイデアは、直接の親ノードを「共索引付け」することによって機能する非常にフラットな構造を持つことです。次のようになります。

<tree>
  <node pattern="AB" index="1">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="8"/> <!-- ABD -->
  </node>
  <node pattern="AC" index="2">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="9"/> <!-- ACD-->
  </node>
  <node pattern="AD" index="3">
    <parentnode coindex="8"/> <!-- ABD -->
    <parentnode coindex="9"/> <!-- ACD -->
  </node>
  <node pattern="BC" index="4">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="BD" index="5">    
      <parentnode coindex="8"/> <!-- ABD -->
      <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="CD" index="6">    
      <parentnode coindex="9"/> <!-- ACD -->
      <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="ABC" index="7">    
    <parentnode coindex="11"/> <!-- ABCD -->
  </node>
  <node pattern="ABD" index="8">    
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="ACD" index="9">   
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="BCD" index="10">    
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="ABCD" index="11" isMain="true"/>
</tree>

こうすることで、リンクされたすべてのパターンを取得できると思います。parentnodeたとえば、ここで AB を探すとしたら、そのノードの子 ( ) に到達し、それらのインデックスを取得して、それらを使用して直接の親を探したいと思います。coindex を持つ要素がなくなるまで、このプロセスを繰り返す必要があります (例:ABCDこの場合)。

このような XML 要素が何千もあり、主要な要素が で示されていると想像してくださいisMain。isMain必ずしも親ノードの子を持たないパターンではないことに注意してください! その結果、すべての元の XML ツリーが蓄積されます。パターンがメインのパターンである場合もあれば、組み合わせの一部である場合もあるということです。このような場合、元の XML には「このパターンを主なパターンとするツリー」があるため、node で示されます。isMain

これはこれまでのところ私の考えですが、より良い方法があるかどうか、またはさらに重要なことに、これが BaseX で簡単にクエリできるかどうかはわかりません。基本的に、特定の入力ABを使用して、インデックスを使用して関連するすべてpatternの s (ABC、ABD、ABCD) を取得し、次にisMain="true". より良いアイデアと、それらを BaseX でクエリする方法を楽しみにしています。私のアイデアが良いものであれば、単一の xquery 式でクエリをキャプチャする良い方法を見たいと思います。

4

1 に答える 1

2

効率的な XML プロセッサである BaseX を引き続き使用するよりも、階層データをフラットな構造にすることで達成しようとしていることがよくわかりません。

私は、データをそれがすでに表している論理構造に入れ、インデックスを使用してデータを効率的にクエリする方が、はるかに自然な (そしてより速い) と思います。

したがって、階層構造をそのまま使用するだけです。たとえば、次のようになります。

<tree>
    <node pattern="ABCD">
      <node pattern="ABC">
        <node pattern="AB"/>
        <node pattern="AC"/>
        <node pattern="BC"/>
      </node>
      <node pattern="ABD">
        <node pattern="AB"/>
        <node pattern="AD"/>
        <node pattern="BD"/>
      </node>
    </node>
</tree>

したがって、パフォーマンス上の理由からその形式を選択したと思います。ただし、データベースを構築するときは、属性インデックスを作成する必要があります。つまり、すべての属性値がインデックス化されます。通常、より一般的なクエリの場合は書き直す必要がありますが、属性インデックスを直接使用できます。たとえば、英語のウィキペディアのダンプを含む 50GB 以上のデータベースがあります。たとえば、ページを検索することを選択しますList of Dragon Ball characters。

db:attribute("wikipedia", "List of Dragon Ball characters")/parent::*

私のマシンでは、これを実行するのに約 20 ミリ秒かかりました。

同様に、単純にパターンを検索してツリーを上っていくことができます:

db:attribute("<YOUR_DB>", "AB")/ancestor::node/@pattern => distinct-values()

最初にインデックスを使用し、次に単純に親に移動することを考えると、これは可能な限り高速になるはずです。

于 2018-06-29T09:15:45.180 に答える