セットトライを圧縮するアルゴリズム

Question

私はtrieに配置したいセットのコレクションを持っています。

通常の試行は要素の文字列で行われます。つまり、要素の順序が重要です。セットには定義された順序がないため、より大きな圧縮の可能性があります。例えば

、文字列​​を与え、"bc"、および"c"、私がトライを作成したい：

(*,3) -> ('a',1) -> ('b',1) -> ('c',1) 
     -> ('b',1) -> ('c',1) 
     -> ('c',1) 

しかしセット{ 'a', 'b', 'c' }、{ 'b', 'c' }、{ 'c' }与えられ、私は上記のトライを作成したり、任意の可能性これらの11の：

(*,3) -> ('a',1) -> ('b',1) -> ('c',1) 
     -> ('c',2) -> ('a',1) 

(*,3) -> ('a',1) -> ('c',1) -> ('b',1) 
     -> ('b',1) -> ('c',1) 
     -> ('c',1) 

(*,3) -> ('a',1) -> ('c',1) -> ('b',1) 
     -> ('c',2) -> ('a',1) 

(*,3) -> ('b',2) -> ('a',1) -> ('c',1) 
       -> ('c',1) 
     -> ('c',1) 

(*,3) -> ('b',1) -> ('a',1) -> ('c',1) 
     -> ('c',2) -> ('b',1) 

(*,3) -> ('b',2) -> ('c',2) -> ('a',1) 
     -> ('c',1) 

(*,3) -> ('b',1) -> ('c',1) -> ('a',1) 
     -> ('c',2) -> ('b',1) 

(*,3) -> ('c',2) -> ('a',1) -> ('b',1) 
     -> ('b',1) -> ('c',1) 

(*,3) -> ('c',2) -> ('a',1) -> ('b',1) 
       -> ('b',1) 

(*,3) -> ('c',2) -> ('b',1) -> ('a',1) 
     -> ('b',1) -> ('c',1) 

(*,3) -> ('c',3) -> ('b',2) -> ('a',1) 

したがって、圧縮のためのスペース（7つのノードから4）があります。

I 容疑者子どもの相対頻度に応じて各ノードでローカル注文を定義するとしますが、それはあまりにも高価かもしれません。

ホワイトボードにヒットする前に、自分の圧縮アルゴリズムでクラックを開始する前に、既存の圧縮アルゴリズムがありますか？それはどれくらい費用がかかりますか？それはバルクプロセスか、または挿入/削除ごとに行うことができますか？

Answer 1

基本的に依存グラフを作成する必要があります。要素yがxが発生した場合にのみ発生する場合は、xからyへの辺を描画します（等号の場合は辞書順に並べ替えます）。結果のグラフはDAGです。今、このグラフをトポロジカルにソートして、要素の順序を捻って取得します。 2つ（またはそれ以上の要素）のいずれかを選択できるときは、出現回数の多いものを選択します。

Answer 2

あなたはアイテムの頻度に従ってセットをソートしなければならないと思います。これは、あなたが疑うように良いヒューリスティックを取得します。コンパクトな方法で表すためにFP-growth（頻繁なパターンマイニング）で使用するのと同じアプローチ。

Answer 3

私の懸念は、最大の圧縮が最も一般的な要素を（最後の例のように）上に維持するということです。

圧縮アルゴリズムは、結果として得られるツリーは特別なエンドオブを有するであろうセットのコレクション全体と上部ノードで始まり、そして再帰的に最も一般的な要素

Compress(collection, node): 
    while NOT collection.isEmpty? 
     e = collection.find_most_common_element 
     c2 = collection.find_all_containing(e) 
     collection = collection - c2 
     if e==NIL //empty sets only 
     node[END_OF_SET]=node 
     else 
     c2.each{set.remove(e)} 
     node[e]=new Node 
     Compress(c2,node[e]) 
     end 
    end 

を含む各サブセットのノードを作成しそのノードで完全なセットが終了することを示すためにマーカーを設定します。あなた例えば、それはセットを削除

*->(C,3)->(B,2)->(A,1)->EOS 
       ->EOS 
      ->EOS 

だろう簡単で、ちょうどそれがEOSマーカー（および空になる任意の親ノード）のremove。 をオンザフライで挿入する - 各ノードで、一致する要素がなくなるまで大部分の子要素と一致する要素に降りた後、上記アルゴリズムを使用しますが、最大限に圧縮することは難しいでしょう。要素Bが要素Aよりも多くの子を獲得した場合、A & Bを含むすべてのセットをBノードに移動する必要があります。これはAのすべての子を完全に検索することになります。しかし、圧縮しないと、インクルード検索は設定されたサイズで線形ではなくなります。