Быстрый поиск совпадений объектов по их контрольным суммам на примере поиска дублирующихся изображений

Исходные данные:

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

Конечная цель:

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

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

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

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 — класс в проекте.

Плюсы:

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

Минусы:

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

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