1

Treeのハッシュ値を計算する最良の方法は何ですか?

O(1)のいくつかの木の類似性を比較する必要があります。ここで、ハッシュ値を事前に計算し、必要に応じて比較したいと考えています。しかし、ツリーのハッシュはシーケンスのハッシュとは異なることに気付きました。良いハッシュ関数を思いつくことができませんでした。

ツリーのハッシュ値を計算する最良の方法は何ですか?

注：関数は c/c++ で実装します

4

4 に答える 4

2

ツリーを適切に持つということは、単純な表現または数値を使用して、このツリーと他のツリーを区別できるように、一意の方法でそれを表現することを意味します。通常の多項式ハッシュでは、基数変換を使用します。文字列またはシーケンスを特定の素数基数に変換し、大きな素数でもある mod 値を使用します。これと同じ手法を使用して、ツリーをハッシュできます。

ここで、ツリーのルートを任意の頂点に固定します。root = 1 とし、

B = 変換するベース。

P[i] = B の i 乗 (B^i)。

level[i] = (ルートからの距離) i 番目の頂点の深さ。

child[i] = i を含む i 番目の頂点のサブツリー内の頂点の総数。

degree[i] = 頂点 i の隣接ノードの数。

これで、ハッシュ値の i 番目の頂点の寄与は -

hash[i] = ( (P[level[i]]+degree[i]) * child[i] ) % modVal

そして、ツリー全体のハッシュ値は、すべての頂点のハッシュ値の合計です。

(ハッシュ[1]+ハッシュ[2]+....+ハッシュ[n]) % modVal

于 2019-10-22T10:38:39.037 に答える
0

ツリーを標準シーケンスに変換し、シーケンスをハッシュすることをお勧めします。(変換の詳細は、等価性の定義によって異なります。たとえば、木が二分探索木であり、等価関係が構造的である場合、二分探索木の構造が予約注文の列挙から回復されます。)

トーマスの答えは、一見すると、多変数多項式を各ツリーに関連付け、特定の場所で多項式を評価することに要約されます。現時点で、信仰に関してとらなければならないステップが 2 つあります。1 つ目は、マップが不等なツリーを同じ多項式に送信しないことです。2 つ目は、評価スキームがあまり多くの衝突を導入しないことです。2 変数多項式からの再構成を可能にする等価性の合理的な定義はありますが、現在、最初のステップを評価することはできません。2 つ目は理論的には健全ではありませんが、Schwartz--Zippel を介して実現できます。

于 2013-08-24T14:46:53.080 に答える
0

子ハッシュは、連続して素数を掛けて加算する必要があります。ノード自体のハッシュに別の素数を掛けて加算する必要があります。

ツリー全体のハッシュをキャッシュします。AST を保持するラッパー オブジェクトがある場合は、AST ノードの外部にキャッシュすることを好みます。

public class RequirementsExpr {
    protected RequirementsAST ast;
    protected int hash = -1;

    public int hashCode() {
        if (hash == -1)
            this.hash = ast.hashCode();
        return hash;
    }
}

public class RequirementsAST {
    protected int    nodeType;
    protected Object data;
    // -
    protected RequirementsAST down;
    protected RequirementsAST across;

    public int hashCode() {
        int nodeHash = nodeType;
        nodeHash = (nodeHash * 17) + (data != null ? data.hashCode() : 0);
        nodeHash *= 23;            // prime A.

        int childrenHash = 0;
        for (RequirementsAST child = down; child != null; child = child.getAcross()) {
            childrenHash *= 41;    // prime B.
            childrenHash += child.hashCode();
        }
        int result = nodeHash + childrenHash;
        return result;
    }
}

この結果、異なる位置にある子/子孫ノードは常に異なる係数で乗算されます。ノード自体は、可能な子/子孫ノードとは常に異なる係数で乗算されます。

nodeHashノードデータ自体の構築には、他の素数も使用する必要があることに注意してください。これは、例えばを回避するのに役立ちます。の異なる値とnodeType衝突する の異なる値data。

32 ビット ハッシュの制限内で、このスキームは全体として、ツリー構造 (たとえば、2 つの兄弟の転置) または値の違いに対して非常に高い確率で一意性を提供します。

(AST 全体にわたって) 計算されると、ハッシュは非常に効率的になります。

于 2013-08-24T11:26:00.423 に答える