0

次のように定義されたカスタム equal_to 関数を使用する int への順序付けられていないマップ文字列があります。

bool hashEqual::operator ()(const string &a, const string &b) const
{
    if (a.size() != b.size())
        return false;

    return std::inner_product(
        a.begin(), a.end(), b.begin(),
        0, std::plus<unsigned int>(),
        std::not2(std::equal_to<std::string::value_type>())
        ) <= 8;  
}

基本的には、2 つのキーのハミング距離が 8 以下であれば、同じキーになります。

問題は、ユーザーがコマンドラインから設定できるように、距離のしきい値を動的にすることです。8 の代わりに、可変しきい値またはこのようなものです。

私はグローバル変数のようなハックを探しているのではなく (それがこれを達成する唯一の方法でない限り)、「良い方法」を探しています。

4

2 に答える 2

1

`unordered_map` が確実に機能しない理由

優れた汎用ハッシュ関数は、反復可能ですが、それ以外の場合は一見ランダムな方法でキーをバケットにマップします。つまり、キーが 1 ビットでも変化する場合、バケットは統計的に無関係である必要があります。ランダム。したがって、いくつかの既存の要素を持つハッシュ テーブルがあるとします。

[ bucket 0 - "abcde fghij" ]
[ bucket 1 - <empty> ]
[ bucket 2 - <empty> ]
[ bucket 3 - "01234 56789", "77777 QQQQQ" ]  (2 colliding values for this bucket)
[ bucket 4 - "XXXXX YYYYY" ]
[ bucket 5 - <empty> ]

挿入に来た場合、これらのバケットのいずれかにハッシュできます-他のバケットよりもバケット0である可能性は高くない"Abcde fghij"はずですが、そのバケットがバケット0でない場合は、 「abcde fghij」に対するハミング距離を考慮した等値比較。

`multimap` が確実に機能しない理由

multimapその中にいくつかの既存の文字列 (S1 から S6 までの辞書編集順の昇順 - それぞれが他の要素から 8 を超えるハミング距離を持つ) があると想像してください。

            S4
          /    \
        S2       S6
       /  \     /  \
      S1   S3  S5

ここで、S1 がたまたま で"Abcde fghij"、S4 が である"ZZZZZ ZZZZZ"としましょう"abcde fghij"。

  • ハミング距離の比較でも( ASCII 順であることを"ZZZZZ ZZZZZ" < "abcde fghij"思い出してください) 、ツリーの右側に格納されることが期待されます...'Z' < 'a'multimap"abcde fghij"

  • "abcde fghij"次に S6 と比較され、S5 より小さい場合はそれに応じて挿入されますが、決定的にS1 との比較はありません。

これにより、以前のコメントに戻ります。

総当たり以外に比較を行うための簡単で正しい方法はないと思います（すべての組み合わせを試してください）。また、結果は同じデータでも別の順序で異なります。

于 2014-06-30T08:15:48.767 に答える
0

私はそれを考え出した。

すべてはクラス hashEqual で行われます。定義を次のように変更しました。

class hashEqual {
    private:
        int th;
    public:
       hashEqual();
        hashEqual(int th) { this->th = th; }; // This implemetation on the .cpp
        bool operator ()(const string &a, const string &b) const;
};

operator() の実装:

bool hashEqual::operator ()(const string &a, const string &b) const
{
    if (a.size() != b.size())
        return false;

    return std::inner_product(
        a.begin(), a.end(), b.begin(),
        0, std::plus<unsigned int>(),
        std::not2(std::equal_to<std::string::value_type>())
        ) <= this->th;  
}

そして unordered_map のコンストラクターで:

boost::unordered_map<string, unsigned int, boost::hash<string>, hashEqual> myMap(size, boost::hash<string>(), hashEqual(threshold));
于 2014-06-27T09:34:49.880 に答える