重複画像の検索の例を使用して、チェックサムによるオブジェクトの一致のクイック検索

ソースデータ：

• 属性を持つオブジェクトのセット
• オブジェクトをチェックサムと比較することにより、オブジェクトをほぼ正確に識別する機能。

最終的な目標：

• 一致を簡単に識別できるオブジェクトのリストを取得します。

アルゴリズムの考え方は、各ノードに1バイトのチェックサムが格納されるサフィックスツリーを作成することです。 次のオブジェクトのチェックサムを受信すると、シーケンスの次のバイトのノードが見つからない場合はツリーのルートからさらに深く移動し、作成します。 チェックサムの最後に到達し、最終ノードを作成したら、オブジェクトパラメーターを書き込みます。 その結果、エンドノードのリストを取得します。エンドノードに複数のオブジェクトの説明が含まれている場合、これらのオブジェクトは同一であると想定します。

理解を深めるために、ソーステキストの一般的なビューを提供します。これは、実際のタスクのテンプレートとして使用できます。

using System;
using System.Collections. Generic ;
/// <summary>
///
/// </summary>
public class HashObject
{
public string attribute1 { get ; set ; }
public string attribute2 { get ; set ; }
}
/// <summary>
/// ,
///
///
/// </summary>
public class HashTreeNode
{
/// <summary>
///
/// </summary>
private byte myPart;
public byte MyPart
{
get { return myPart; }
}
public HashTreeNode( byte part)
{
myPart = part;
}
/// <summary>
/// ,
/// </summary>
public List <HashObject> files = null ;
/// <summary>
///
/// </summary>
private List <HashTreeNode> NextNodes = new List <HashTreeNode>();
/// <summary>
///
/// </summary>
public HashTreeNode FindEndNode( byte [] crc, int position)
{
HashTreeNode endNode = FindSubNodes(crc[position]);
if (position < crc.Length - 1)
return endNode.FindEndNode(crc, position + 1);
else return endNode;
}
/// <summary>
/// /
/// </summary>
private HashTreeNode FindSubNodes( byte part)
{
lock (NextNodes)
{
for ( int i = 0; i < NextNodes.Count; i++)
if (NextNodes[i].MyPart.Equals(part))
return NextNodes[i];
NextNodes.Add( new HashTreeNode(part));
return NextNodes[NextNodes.Count - 1];
}
}
}
/// <summary>
/// ,
/// </summary>
public class HashTree
{
/// <summary>
///
/// </summary>
List <HashTreeNode> Nodes = new List <HashTreeNode>();
/// <summary>
///
/// ,
/// </summary>
/// <param name="crc">Crc32 </param>
/// <returns></returns>
public HashTreeNode CheckOnTree( byte [] crc)
{
HashTreeNode root = FindNode(crc[0]);
return root.FindEndNode(crc, 1);
}
/// <summary>
///
/// </summary>
private HashTreeNode FindNode( byte part)
{
lock (Nodes)
{
for ( int i = 0; i < Nodes.Count; i++)
if (Nodes[i].MyPart.Equals(part))
return Nodes[i];
Nodes.Add( new HashTreeNode(part));
return Nodes[Nodes.Count - 1];
}
}
}

* This source code was highlighted with Source Code Highlighter .

例として、指定されたディレクトリで重複画像を見つけるための最も簡単なアプリケーションが実装されています。 作業の結果、HTMLレポートファイルが取得されます。
プロジェクトはMicrosoft Visual Studio 2008で実行され、Windows x86でコンパイルされました。
プロジェクトは、写真を含む独自のフォルダーでテストされました。テスト結果：
ディレクトリ内のファイル：4326
これらの写真のうち：4131
画像重量：8.33 GB
重複検索時間：117秒（2分）+ 6秒でレポートを生成し、重複ファイルをレポートフォルダーにコピーします。
見つかった：90の重複。
アプリケーションとソースへのリンク：
ifolder.ru/19211139

誰かが興味を持っている場合、画像に属するファイルをチェックするのは拡張子ではなく、署名によってファイルヘッダーを調べることです。 Signatures.csはプロジェクトのクラスです。

長所：

• 比較的高速
• 実装とデータストレージの容易さ

短所：

• データ構造全体がRAMに保存されます。 画像の数を数十万または数百万単位で測定する場合、ツリーの保存方法を再考する必要があります。 または、別のアルゴリズムを検索します。

私は、投稿がマイナスである人々に感謝します。それは、彼らに知られているより良いアルゴリズムへのリンクを提供するか、記載されている欠点を指摘します。