[algorithm] ツリー構造をハッシュする



4 Answers

ツリーのレイアウトごとにハッシュ結果が異なる必要があるという要件を導入した編集後、ツリー全体をトラバースし、その構造を単一の配列に書き込むオプションが残っています。

これは次のように行われます。ツリーをたどり、自分が行った操作をダンプします。 元のツリーの場合(左の子右の兄弟構造の場合):

[1, child, 2, child, 3, sibling, 4, sibling, 5, parent, parent, //we're at root again
 sibling, 6, child, 7, child, 8, sibling, 9, parent, parent]

その後、好きなようにリスト(つまり、効果的には文字列)をハッシュすることができます。 別のオプションとして、ハッシュ関数の結果としてこのリストを返すこともできるので、衝突のないツリー表現になります。

しかし、構造体全体に関する正確な情報を追加することは、通常、ハッシュ関数が行うことではありません。 提案された方法は、すべてのノードのハッシュ関数を計算し、ツリー全体を走査する必要があります。 したがって、以下で説明する、他のハッシュ方法を検討することもできます。

ツリー全体をトラバースしたくない場合は、次のようにします。

すぐに私の心に来た1つのアルゴリズムはこれのようなものです。 大きな素数H (これは子供の最大数よりも大きい)を選びます。 ツリーをハッシュし、そのルートをハッシュし、 H mod nnはルートの子の数)を選択し、この子のサブツリーを再帰的にハッシュする。

樹木が葉の近くで深くしか異なっていない場合、これは悪い選択肢のようです。 しかし、少なくともそれは非常に背の高い木では速く走るべきです。

より少ない要素をハッシュするがツリー全体を通過させたい場合は

サブツリーをハッシュする代わりに、レイヤーごとにハッシュすることができます。 つまり、最初にハッシュルートを子ノードであるノードのハッシュよりも子孫の子ノードの1つにするなど、特定のパスの代わりにツリー全体をカバーします。 これはもちろん、ハッシュ処理を遅くします。

    --- O  ------- layer 0, n=1
       / \
      /   \
 --- O --- O ----- layer 1, n=2
    /|\    |
   / | \   |
  /  |  \  |
 O - O - O O------ layer 2, n=4
          / \
         /   \
 ------ O --- O -- layer 3, n=2

レイヤからのノードは、 H mod nルールで選択されます。

このバージョンと以前のバージョンとの違いは、ハッシュ関数を保持するためにはツリーがかなり非論理的な変換を受けなければならないということです。

Question

私はちょうど既に知られているインスタンスと平等のために異なるツリーオブジェクトを比較する必要があり、任意のツリー上で動作する何らかの種類のハッシングアルゴリズムが非常に有用であると考えたプロジェクトでシナリオを見つけました。

たとえば、次のツリーを参照してください。

        O
       / \
      /   \
     O     O
    /|\    |
   / | \   |
  O  O  O  O
          / \
         /   \
        O     O

Oはツリーのノードを表し、任意のオブジェクトであり、関連するハッシュ関数を有する。 したがって、問題は次のようになります。ツリー構造のノードのハッシュコードと既知の構造が与えられた場合、ツリー全体の衝突のないハッシュコードを計算するための適切なアルゴリズムは何ですか?

ハッシュ関数のプロパティに関するいくつかの注意:

  • ハッシュ関数は、ツリー内のすべてのノードのハッシュコードとその位置に依存する必要があります。
  • ノードの子を並べ替えると、生成されるハッシュコードはっきりと変更されるはずです。
  • ツリーのどの部分を反映させても、結果として得られるハッシュコード

それが役に立ったら、私はここで私のプロジェクトでC#4.0を使用していますが、主に理論的な解決策を探しています。したがって、擬似コード、説明、または別の命令型言語のコードがうまくいくでしょう。

更新

さて、私自身の提案された解決法があります。 これはいくつかの答えによって多くの助けを得ました。

各ノード(サブツリー/リーフノード)には、以下のハッシュ関数があります。

public override int GetHashCode()
{
    int hashCode = unchecked((this.Symbol.GetHashCode() * 31 +
        this.Value.GetHashCode()));
    for (int i = 0; i < this.Children.Count; i++)
        hashCode = unchecked(hashCode * 31 + this.Children[i].GetHashCode());
    return hashCode;
}

このメソッドの素晴らしい点は、ハッシュコードがキャッシュされ、ノードまたはその子孫の1つが変更されたときにのみ再計算されることです。 (これを指摘してくれたvatineとJason Orendorffに感謝します)。

とにかく、人々が私の提案された解決方法についてここでコメントすることができれば、私は感謝しています。




ノードが訪問されたときに依存するハッシュ関数と共に、(決定論的な順序で)単純な列挙が機能するはずです。

int hash(Node root) {
  ArrayList<Node> worklist = new ArrayList<Node>();
  worklist.add(root);
  int h = 0;
  int n = 0;
  while (!worklist.isEmpty()) {
    Node x = worklist.remove(worklist.size() - 1);
    worklist.addAll(x.children());
    h ^= place_hash(x.hash(), n);
    n++;
  }
  return h;
}

int place_hash(int hash, int place) {
  return (Integer.toString(hash) + "_" + Integer.toString(place)).hash();
}



私は、あなたの要件は、ハッシュコードの全体のコンセプトにいくらか反対であると言わざるを得ない。

ハッシュ関数の計算の複雑さは非常に限られているはずです。

計算の複雑さは、コンテナ(ツリー)のサイズに線形に依存すべきではありません。さもなければ、ハッシュコードベースのアルゴリズムを完全に破ります。

ノードのハッシュ関数の主な特性としての位置を考えると、やはりツリーの概念に反しますが、要件を置き換えると、位置に依存する必要があります。

私が提案する全体的な原則は、MUST要件をSHOULD要件に置き換えることです。 そうすれば、適切で効率的なアルゴリズムを思いつくことができます。

たとえば、整数ハッシュコードトークンの限定されたシーケンスを構築し、このシーケンスに必要なものを優先順位で追加することを検討してください。

このシーケンスの要素の順序は重要であり、計算された値に影響します。

たとえば、計算したいノードごとに次のようにします。

  1. 基底オブジェクトのハッシュコードを追加する
  2. 利用可能であれば、最も近い兄弟の基礎となるオブジェクトのハッシュコードを追加します。 私は、左の一兄弟でさえ十分だと思う。
  3. 親の基礎となるオブジェクトのハッシュコードを追加します。ノード自体のような最も近い兄弟は2と同じです。
  4. 限られた深さまで祖父母とこれを繰り返す。

    //--------5------- ancestor depth 2 and it's left sibling;
    //-------/|------- ;
    //------4-3------- ancestor depth 1 and it's left sibling;    
    //-------/|------- ;
    //------2-1------- this;
    

    直接兄弟の基になるオブジェクトのハッシュコードを追加するという事実は、ハッシュ関数に定位置プロパティを与えます。

    これで十分でない場合は、子を追加してください:適切なハッシュコードを与えるために、すべての子を追加する必要があります。

  5. 最初の子を追加し、それは最初の子であり、最初の子です。深さを一定に制限し、再帰的に何も計算しません。基礎となるノードのオブジェクトのハッシュコードだけです。

    //----- this;
    //-----/--;
    //----6---;
    //---/--;
    //--7---;
    

このように、複雑さは、要素の総数ではなく、基礎となるツリーの深さに対して線形です。

ここで、整数の場合はシーケンスがあり、上のElyのように既知のアルゴリズムと組み合わせればよい。

1,2、... 7

この方法では、ツリーの合計サイズに依存せず、ツリーの深さに依存しなくても、ツリー全体のハッシュ関数を再計算する必要がない位置プロパティを持つ軽量ハッシュ関数を使用しますツリー構造。

私はこの7つの数字が完璧に近いハッシュ値を与えるだろうと確信しています。




あなたが木を使って作業している時はいつでも、再帰は心に来るべきです:

public override int GetHashCode() {
    int hash = 5381;
    foreach(var node in this.BreadthFirstTraversal()) {
        hash = 33 * hash + node.GetHashCode();
    }
}

ハッシュ関数は、ツリー内のすべてのノードのハッシュコードとその位置に依存する必要があります。

チェック。 明示的にnode.GetHashCode()をツリーのハッシュコードの計算に使用しています。 さらに、アルゴリズムの性質のために、ノードの位置はツリーの最終的なハッシュコードにおいて役割を果たす。

ノードの子を並べ替えると、生成されるハッシュコードがはっきりと変更されるはずです。

チェック。 それらは異なる順序で訪問され、異なる順序でのハッシュコードにつながります。 (同じハッシュコードを持つ2人の子供がいる場合、それらの子供の順番を入れ替えると同じハッシュコードになります)。

ツリーのどの部分を反映させても、結果として得られるハッシュコード

チェック。 再び、ノードは異なる順序で訪問され、異なるハッシュコードにつながる。 (すべてのノードが同じハッシュコードを持つノードに反映されている場合、同じハッシュコードになる可能性があることに注意してください)。




私はあなたが比較する大きな木のセットを持っているなら、潜在的な候補のセットを取得するためにハッシュ関数を使用し、直接比較を行うことができます。

部分文字列を使うと、木の周りに大括弧を入れたり、各ノードの識別子を事前に書き出したりするのにlisp構文を使うだけです。 しかし、これは計算上、ツリーのプリオーダーの比較と同等です。なぜそれだけではありませんか?

2つの解決法を挙げました.1つは、完了したら2つのツリーを比較し(衝突を解決する必要があります)、もう1つはハッシュコードを計算することです。

ツリー比較:

最も効率的な比較方法は、各ステップでノードを比較して、固定順序(プレオーダは他のものと同じくらいシンプルである)で各ツリーを単純に再帰的にトラバースすることです。

  1. したがって、ツリーのプレオーダで次のノードを連続して返すVisitorパターンを作成するだけです。 つまり、コンストラクタはツリーのルートを取ることができます。

  2. 次に、ビジターの2つのインセースを作成します。これは、次のノードのジェネレーターとしてプリオーダーします。 すなわち、Vistor v1 =新しいビジター(root1)、ビジターv2 =新しいビジター(root2)

  3. 別のノードと比較できる比較関数を記述します。

  4. 次に、ツリーの各ノードにアクセスして比較し、比較が失敗した場合はfalseを返します。 すなわち、

モジュール

 Function Compare(Node root1, Node root2)
      Visitor v1 = new Visitor(root1)
      Visitor v2 = new Visitor(root2)

      loop
          Node n1 = v1.next
          Node n2 = v2.next
          if (n1 == null) and (n2 == null) then
                return true
          if (n1 == null) or (n2 == null) then
                return false
          if n1.compare(n2) != 0 then
                return false
      end loop
      // unreachable
 End Function

エンドモジュール

ハッシュコード生成:

ツリーの文字列表現を書き出す場合は、ツリーにlisp構文を使用し、文字列をサンプリングしてより短いハッシュコードを生成することができます。

モジュール

 Function TreeToString(Node n1) : String
        if node == null
            return ""
        String s1 = "(" + n1.toString()
        for each child of n1
            s1 = TreeToString(child)

        return s1 + ")"
 End Function

node.toString()は、そのノードの固有のラベル/ハッシュコード/何でも返すことができます。 次に、TreeToString関数によって返された文字列から部分文字列の比較を行い、ツリーが同等かどうかを判断することができます。 より短いハッシュコードの場合は、TreeToString関数をサンプリングします。つまり、5文字ごとに取得します。

エンドモジュール




Related