Исходные данные:
  • набор объектов обладающих аттрибутами
  • возможность приблизительно точно идентифицировать объект сопоставив ему контрольную сумму.


Конечная цель:
  • получить списки объектов по которым легко выявить совпадения.

Идея алгоритма заключается в создании суффиксного дерева каждый узел которого хранит в себе один байт контрольной суммы. При получении контрольной суммы очередного объекта мы начинаем движение с корня дерева вглубь, если мы не находим узел для следующего байта в последовательности, то создаем его. Достигнув окончания контрольной суммы и создав конечный узел запишем в него параметры объекта. В итоге мы получим список конечных узлов, если в конечном узле лежит описание более одного объекта мы предполагаем что эти объекты идентичны.

Привожу общий вид исходного текста для лучшего понимания, который можно использовать в качестве шаблона для реальных задач.
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 Гб
Время поиска дубликатов: 117 секунд (2 минуты) + 6 секунд на формирование отчета и копирование файлов дубликатов в папку отчета.
Найдено: 90 дубликатов.
Ссылка на приложение и исходники:
ifolder.ru/19211139

Если кому интересно, проверка файлов на принадлежность к изображениям производится не по расширению, в по сигнатуре, исследуя заголовок файла. Signatures.cs — класс в проекте.

Плюсы:
  • относительно высокая скорость работы
  • простота реализации и хранения данных


Минусы:
  • вся структура данных хранится в оперативной памяти. Если количество картинок будет измеряться сотнями тысяч или миллионами по��ребуется переосмысление способа хранения дерева. Или поиск другого алгоритма.


Буду благодарен тем минусующим пост, которые дадут ссылки на более лучшие известные им алгоритмы или укажут на недостатки описанного.