powered by simpleCommunicator - 2.0.36     © 2025 Programmizd 02
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Поиск уникальных png иконок
25 сообщений из 57, страница 1 из 3
Поиск уникальных png иконок
    #40111067
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Есть набор png иконок. Размером до 32х32. Нужно из этого набора найти только уникальные иконки. По прогнозам всего будет 2-3 различных размера, в каждом размере до 10 уникальных иконок. Всего иконок порядка 10000-20000.

Идея решения
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
TIconList = class
strict private
  type
    TIconSize = record
      Width: Word;
      Height: Word;
    end;
    THash = type Integer;
    TIconBucket = TDictionary<THash, Integer>;
  class var
    FCurIdx: Integer;
strict private
  FIcons: TObjectDictionary<TIconSize, TIconBucket>;
strict private
  class function CalcHash(AData: Pointer; ADataSize: Integer): THash; static;
public
  constructor Create;
  destructor Destroy; override;
  function TryAddIcon(AData: Pointer; ADataSize, AWidth, AHeight: Integer): Integer;
end;

{ TIconList }

constructor TIconList.Create;
begin
  inherited Create;
  FIcons := TObjectDictionary<TIconSize, TIconBucket>.Create([doOwnsValues]);
end;

destructor TIconList.Destroy;
begin
  FIcons.Free;
  inherited Destroy;
end;

class function TIconList.CalcHash(AData: Pointer; ADataSize: Integer): THash;
begin
  // Result := 0;
end;

function TIconList.TryAddIcon(AData: Pointer; ADataSize, AWidth,
  AHeight: Integer): Integer;
var
  LSize: TIconSize;
  LBucket: TIconBucket;
  LHash: THash;
begin
  LSize.Width := AWidth;
  LSize.Height := AHeight;
  if not FIcons.TryGetValue(LSize, LBucket) then begin
    LBucket := TIconBucket.Create;
    FIcons.Add(LSize, LBucket);
  end;
  LHash := CalcHash(AData, ADataSize);
  if not LBucket.TryGetValue(LHash, Result) then begin
    Result := FCurIdx;
    Inc(FCurIdx);
    LBucket.Add(LHash, Result);
  end;
end;

и использование
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
var
  LMemStrm: TMemoryStream;
  LIStrm: IStream;
begin
  LMemStrm := TMemoryStream.Create;
  try
    LIStrm := TStreamAdapter.Create(LMemStrm, soReference);
    GPCheck(GdipSaveImageToStream(Handle, LIStrm, @TGDIPlusManager.PngEncoder, nil));
    Idx := IconList.TryAddIcon(LMemStrm.Memory, LMemStrm.Size, FIconWidth, FIconHight);
  finally
    LMemStrm.Free;
  end;
end;


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

Вопросы: на сколько адекватный алгоритм? Какой хеш использовать (скорость в приоритете)? Есть ли в Delphi Rio готовые реализации хеш-функций?

С уважением, Vasilisk
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111069
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Первая ссылка в гугле:
https://docwiki.embarcadero.com/Libraries/Sydney/en/System.Hash

PS: Алгоритм неадекватный вообще. В том числе из-за "коллизию хэшей считаем невозможной".
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111076
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
В том числе
А еще?
Dimitry Sibiryakov
коллизию хэшей считаем невозможной
Ну не хочется на каждый чих еще и CompareMem дергать. Он тогда будет вызываться в 99%. Тогда и хеши со словарями не нужны.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111078
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_
Он тогда будет вызываться в 99%.
99% хешей совпадает? :)
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111079
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_А еще?

1. Не озвучен критерий уникальности.
2. Не озвучена допустимость ложноположительных срабатываний.
3. Не озвучена допустимость ложноотрицательных срабатываний.

Из этих трёх условий может вытекать всё, что угодно, вплоть до тривиального
CRC32 непосредственно файлов.

_Vasilisk_
не хочется на каждый чих еще и CompareMem дергать

Иконки 32х32 - маленькие . Для них CompareMem как раз оптимален.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111081
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Для них CompareMem как раз оптимален.

Не когда этих иконок десятки тысяч.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111083
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreatНе когда этих иконок десятки тысяч.

В условии написано, что уникальный - десятки. CompareMem для остальных
остановится уже на первых байтах.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111084
Fr0sT-Brutal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Коллизия хеша среди валидных PNG файлов? На хотя бы 4-байтовом хеше вероятность, кмк, минимальна. Но никто не мешает при коллизии сравнивать непосредственно файлы.
Хотя да, для 10 образцов легче не городить премудростей.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111086
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В любом случае бутылочным горлышком будет диск.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111087
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

Ну так не забывай что расход памяти так в 10000 раз больше.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111091
Fr0sT-Brutal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
rgreat
Dimitry Sibiryakov,

Ну так не забывай что расход памяти так в 10000 раз больше.

Откуда? Хранятся-то только уникальные. А дубли, которые пойдут после 11-ти, сразу же удалять
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111093
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Fr0sT-Brutal,

А, ну да. Забыл что тут частный случай и уникальных мало.

Странная задача.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111095
Fr0sT-Brutal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
rgreat, чего только не приходится делать нашему брату)) может, аватарки какие-то фильтровать надо
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111102
YuRock
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не понимаю, какой смысл считать хэш, чтобы потом его сравнить с существующими, если можно хранить все существующие в памяти, раз их будет несколько десятков всего. Это максимум - 30 килобайт.
Ну и потом.
1. Сравниваем размер. Если такого еще не было - уникальная, добавляем в хранимый список, иначе 2.
2. CompareMem по хранимым иконкам таких размеров. Если не нашли - уникальная, добавляем в хранимый список, иначе - пропуск.
CompareMem на килобайт будет работать так быстро, что тысячи иконок проскочат за такт. Диск будет тормозить, это да.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111106
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
YuRockСравниваем размер. Если такого еще не было - уникальная, добавляем в хранимый
список, иначе 2.

Внезапно здесь размер выступает в роли хэша. Единственное отличие - способ
вычисления и вероятность коллизий.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111110
L_argo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Делайте по файлу MD5. И забыть по коллизии.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111114
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L_argo,

MD5 не гарантия уникальности.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111116
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ни один хэш не гарантия уникальности. По определению.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111124
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreat
99% хешей совпадает? :)
Да. Я же написал, что из 10000 иконок уникальных от силы 30.
Dimitry Sibiryakov
1. Не озвучен критерий уникальности.
Две иконки равны, если они имеют идентичные размеры и они "визуально неотличимы". Вместо "визуально неотличимы" можно использовать "у них совпадает каждый пиксел"
Dimitry Sibiryakov
2. Не озвучена допустимость ложноположительных срабатываний.
3. Не озвучена допустимость ложноотрицательных срабатываний.
Допустимо помещение в список нескольких одинаковых иконок. Недопустимо выбрасывание иконки из-за того, что алгоритм посчитал ее похожей на другую
Dimitry Sibiryakov
Иконки 32х32 - маленькие . Для них CompareMem как раз оптимален.
Но их очень много. И т.к. 99% идентичные, то для них CompareMem будет сравнивать все байты
Dimitry Sibiryakov
В условии написано, что уникальный - десятки. CompareMem для остальных
остановится уже на первых байтах.
Для каждой иконки с большой вероятностью найдется пара. А значит для каждой иконки CompareMem пробежит все байты
Fr0sT-Brutal
Но никто не мешает при коллизии сравнивать непосредственно файлы.
Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше
Dimitry Sibiryakov
В любом случае бутылочным горлышком будет диск.
Они все в памяти. В объектах GDI+
rgreat
Странная задача.
Задача попытка перейти от иконок на ImageList без переписывания API.

Грубо говоря есть такой код
Код: pascal
1.
2.
for i := 0 to 10000 do
  Manager.DrawObject(LBmp.Handle, Point[i]);  // LBmp: TBitmap;

Manager понятия не имеет какие битмапы ему подсовывают. Он их преобразовывает в png, сохраняет на диск, а потом у внешней библиотеки вызывает
Код: pascal
1.
LoadIcon(FileName);

В идеале было бы переписать все так
Код: pascal
1.
2.
3.
Idx := Manager.AddIcon(LBmp.Handle);
for i := 0 to 10000 do
  Manager.DrawObjectIdx(Idx, Point[i]);

но это реально очень много переписывать.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111126
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_,

> Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше

Коллизия будет 1 раз из нескольких десятков проверок.
У тебя же несколько десятков уникальных иконок.

Иначе придется каждую с каждой проверять, ну или раньше одинаковые найдешь, если повезет.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111128
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше

Да, именно так, смысла в хэше нет. Каждую иконку тебе надо развернуть до битмапа
чтобы игнорировать разницу метаданных и сжатия, а потом уже голые пиксели можно
тупо сравнивать CompareMem. Хэш, конечно, мог бы дать ускорение, но усложнит
код, который всё равно скорее всего упрётся в диск, а не непосредственно сравнение.

Можно даже не заморачиваться со случаями когда один пиксель отличается младшим
битом в одном цвете.

Но вообще сначала хорошо бы провести эксперимент и посмотреть на результат
md5sum по этим файлам, например. Возможно, даже с разворачиванием в битмап можно
не заморачиваться, а тупо сравнивать файлы побайтово.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111132
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreat
Коллизия будет 1 раз из нескольких десятков проверок.
У тебя же несколько десятков уникальных иконок.
Смотри. Пусть у нас есть три группы иконок. Теперь, что получается:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
procedure TryAddIcon(AIcon);
begin
  LHash := CalcHash(AIcon);
  if IconList.TryGetValue(LHash, LIcon) then begin
    // Иконка, кроме первых трех вызовов, уже есть в списке, поэтому получили равенство хешей
    // Но мы не уверены, что это не коллизия, поэтому должны еще и сравнить побайтово.
    // Т.е. сравнение будет вызываться почти всегда
    if not CompareMem(AIcon, LIcon) then
      AddIcon(AIcon);
  end;
end;

Теперь без хешей
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
procedure TryAddIcon(AIcon);
begin
  for LIcon in IconList then begin
    // CompareMem будет вызываться для каждой иконки из списка,
    // но на других иконках функция вернет False при обнаружении первого же расхождения
    // зато выигрываем на невычислении хеша
    if not CompareMem(AIcon, LIcon) then begin
      AddIcon(AIcon);
      Exit;
    end;
  end;
end;
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111133
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_
Смотри. Пусть у нас есть три группы иконок.
А почему 3 группы а не десятки уникальных иконок?

Ну и ИМХО можно не проверять на полную идентичность, особенно если забацать одновременно 2 принципиально разных хэша.

В то что могут одновременно совпасть 2 разных хеша я не верю.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111135
Fr0sT-Brutal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
_Vasilisk_
Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше

Ты путаешь коллизию и совпадение. Коллизия - это когда два разных набора данных имеют один хеш. Я был неправ насчет CompareMem при совпадении - да, это неприменимо. Но коллизии хеша на валидных PNG... что-то мне мало в это верится. Возьми хеш побольше тогда.

На тупом CompareMem у тебя будет максимум NFiles*NUniques сравнений, в среднем - пополам. Причем эти сравнения наверняка по большей части будут выходить гораздо раньше окончания файлов.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111136
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreat
А почему 3 группы а не десятки уникальных иконок?
Потому что при общем количестве 10000 иконок разницы между 3 и 10 нет
rgreat
если забацать одновременно 2 принципиально разных хэша.
О! Вот это уже ближе к делу.
Fr0sT-Brutal
Ты путаешь коллизию и совпадение.
Не путаю. Но они неотличимы без сравнения данных
...
Рейтинг: 0 / 0
25 сообщений из 57, страница 1 из 3
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Поиск уникальных png иконок
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]