5

私がクラスを持っていると仮定します

public class Audio
{
    public string artist   { get; set; }
    public string title    { get; set; }
    // etc.
}

ここで、類似性（完全一致ではない）条件によって、そのようなオーディオのリスト内の重複をフィルタリングしたいと思います。基本的には、弦の全長によるしきい値補正を使用したレーベンシュタイン距離です。問題は、IEqualityComparerに関する一般的なヒントは、「常にGetHashCodeとCompareの両方を実装する」ことです。GetHashCodeは比較メソッドではないため、明らかにGetHashCodeで文字列間の距離を計算することはできません。ただし、この場合、同様のオーディオでも異なるハッシュが返され、Distinct（）はそれを異なるオブジェクトとして扱い、compare（）メソッドは起動しません。

GetHashCodeが常に0を返すように強制しようとしたため、コレクション内の各オブジェクトに対してCompareが呼び出されましたが、これは低速です。それで、最後に、質問です。箱から出して.netでできることはありますか、それともフィルタリングのための優れたアルゴリズムを検索する必要がありますか？

4

2 に答える 2

3

(まず第一に) DistinctまたはGetHashCodeを使用しないことをお勧めします。

GetHashCodeはあなたのケースには厳しすぎます (@Gabe が完全に指摘したように)。あなたができることは次のとおりです。

  1. レーベンシュタイン法を使用して、インスタンス ペアの三角形全体 (O(n^2) の複雑さ) を比較する必要があることを認めます。
  2. 本のすべてのトリックを使用してそれを最適化してみてください:空の文字列から現在の 1 つの音までのレーベンシュタイン距離を計算する方法 (つまり、Audio のすべてのインスタンスについて、おそらく両方の文字列プロパティについて別々に) ?

それは、非常に優れたGetHashCodeで終わる可能性があります（言うかもしれません）。ただし、 GetHashCodeのように使用することはできません。次のように使用する必要があります。

bool AreSimilar(Audio me, Audio you) {
  int cheapLevenshtein = Math.Abs(me.AbsoluteQuasiLevenshtein - you.AbsoluteQuasiLevenshtein);

  if (cheapLevenshtein < THRESHOLD) {

    int expensiveLevenshtein = Audio.LevenshteinBetween(me, you);
    var result = (expensiveLevenshtein < LIMIT);
    return result;

  } else
    return false;
}

そして、最終的にアルゴリズムが良くなったり悪くなったりすることになります。これは単なるアイデアであり、もちろん、Distinct() は使用できません。必要に応じて、独自の拡張メソッドを記述して、ユーザー プログラマーの観点から全体を美しく見せることができます。

はい、AbsoluteQuasiLevenshteinは "ab" と "zy" のようなものでは等しくなりますが、"ab" と "blahblahblahblah" では大きく異なり、少なくとも少しは最適化します。( GetHashCode + Distinctアプローチは、追加の問題を引き起こしました - GetHashCodeの厳密さ)。

于 2013-02-24T20:11:17.993 に答える
1

シンプルな「c#相互運用性」レイヤーとc#の例を含むBKTreeのコードは次のとおりです。

https://bitbucket.org/ptasz3k/bktree

VS 2012 ソリューションです。

すべてのオブジェクトからツリーを構築することから始め、セレクター関数 (例では x => x.Key.ToLowerInvariant()) を渡します。次に、指定されたキーとレーベンシュタイン距離を検索すると、ツリーは一致するすべてのオブジェクトを返します。

だから、あなたの問題を正しく理解していれば：

var bk = BKTree.CSharp.CreateBK(x => x.artist, audios);
var allArtists = audios.Select(x => x.artist);
var possibleDuplicates = allArtists.Select(x => new 
    { Key = x, Similiar = BKTree.CSharp.FindInBk(bk, x, treshold).ToList());

お役に立てれば。

于 2013-02-24T22:16:28.163 に答える