Гость
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Поиск уникальных png иконок / 25 сообщений из 57, страница 1 из 3
11.11.2021, 16:30
    #40111067
_Vasilisk_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск уникальных png иконок
Есть набор 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
11.11.2021, 16:35
    #40111069
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск уникальных png иконок
Первая ссылка в гугле:
https://docwiki.embarcadero.com/Libraries/Sydney/en/System.Hash

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

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

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

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

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

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

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

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

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

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

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

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

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

MD5 не гарантия уникальности.
...
Рейтинг: 0 / 0
11.11.2021, 18:05
    #40111116
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск уникальных png иконок
Ни один хэш не гарантия уникальности. По определению.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
11.11.2021, 18:36
    #40111124
_Vasilisk_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск уникальных png иконок
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
11.11.2021, 18:48
    #40111126
rgreat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск уникальных png иконок
_Vasilisk_,

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

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

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

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

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

Но вообще сначала хорошо бы провести эксперимент и посмотреть на результат
md5sum по этим файлам, например. Возможно, даже с разворачиванием в битмап можно
не заморачиваться, а тупо сравнивать файлы побайтово.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
11.11.2021, 19:07
    #40111132
_Vasilisk_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск уникальных png иконок
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
11.11.2021, 19:10
    #40111133
rgreat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск уникальных png иконок
_Vasilisk_
Смотри. Пусть у нас есть три группы иконок.
А почему 3 группы а не десятки уникальных иконок?

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

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

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

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


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