|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Есть набор 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.
Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
Т.е. под каждый размер заводим словарь хешей, потом для картинки вычисляем хеш и смотрим его наличие в соответствующем словаре. Коллизию хешей, в виду малого количества иконок считаем невозможной. Вопросы: на сколько адекватный алгоритм? Какой хеш использовать (скорость в приоритете)? Есть ли в Delphi Rio готовые реализации хеш-функций? С уважением, Vasilisk ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 16:30 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Первая ссылка в гугле: https://docwiki.embarcadero.com/Libraries/Sydney/en/System.Hash PS: Алгоритм неадекватный вообще. В том числе из-за "коллизию хэшей считаем невозможной". ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 16:35 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov В том числе Dimitry Sibiryakov коллизию хэшей считаем невозможной ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 16:53 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ Он тогда будет вызываться в 99%. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:02 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_А еще? 1. Не озвучен критерий уникальности. 2. Не озвучена допустимость ложноположительных срабатываний. 3. Не озвучена допустимость ложноотрицательных срабатываний. Из этих трёх условий может вытекать всё, что угодно, вплоть до тривиального CRC32 непосредственно файлов. _Vasilisk_ не хочется на каждый чих еще и CompareMem дергать Иконки 32х32 - маленькие . Для них CompareMem как раз оптимален. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:02 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Для них CompareMem как раз оптимален. Не когда этих иконок десятки тысяч. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:05 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreatНе когда этих иконок десятки тысяч. В условии написано, что уникальный - десятки. CompareMem для остальных остановится уже на первых байтах. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:08 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Коллизия хеша среди валидных PNG файлов? На хотя бы 4-байтовом хеше вероятность, кмк, минимальна. Но никто не мешает при коллизии сравнивать непосредственно файлы. Хотя да, для 10 образцов легче не городить премудростей. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:10 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
В любом случае бутылочным горлышком будет диск. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:12 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, Ну так не забывай что расход памяти так в 10000 раз больше. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:14 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat Dimitry Sibiryakov, Ну так не забывай что расход памяти так в 10000 раз больше. Откуда? Хранятся-то только уникальные. А дубли, которые пойдут после 11-ти, сразу же удалять ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:17 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Fr0sT-Brutal, А, ну да. Забыл что тут частный случай и уникальных мало. Странная задача. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:18 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat, чего только не приходится делать нашему брату)) может, аватарки какие-то фильтровать надо ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:19 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Не понимаю, какой смысл считать хэш, чтобы потом его сравнить с существующими, если можно хранить все существующие в памяти, раз их будет несколько десятков всего. Это максимум - 30 килобайт. Ну и потом. 1. Сравниваем размер. Если такого еще не было - уникальная, добавляем в хранимый список, иначе 2. 2. CompareMem по хранимым иконкам таких размеров. Если не нашли - уникальная, добавляем в хранимый список, иначе - пропуск. CompareMem на килобайт будет работать так быстро, что тысячи иконок проскочат за такт. Диск будет тормозить, это да. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:30 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
YuRockСравниваем размер. Если такого еще не было - уникальная, добавляем в хранимый список, иначе 2. Внезапно здесь размер выступает в роли хэша. Единственное отличие - способ вычисления и вероятность коллизий. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:39 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Делайте по файлу MD5. И забыть по коллизии. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:53 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
L_argo, MD5 не гарантия уникальности. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 18:00 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Ни один хэш не гарантия уникальности. По определению. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 18:05 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat 99% хешей совпадает? :) Dimitry Sibiryakov 1. Не озвучен критерий уникальности. Dimitry Sibiryakov 2. Не озвучена допустимость ложноположительных срабатываний. 3. Не озвучена допустимость ложноотрицательных срабатываний. Dimitry Sibiryakov Иконки 32х32 - маленькие . Для них CompareMem как раз оптимален. Dimitry Sibiryakov В условии написано, что уникальный - десятки. CompareMem для остальных остановится уже на первых байтах. Fr0sT-Brutal Но никто не мешает при коллизии сравнивать непосредственно файлы. Dimitry Sibiryakov В любом случае бутылочным горлышком будет диск. rgreat Странная задача. Грубо говоря есть такой код Код: pascal 1. 2.
Manager понятия не имеет какие битмапы ему подсовывают. Он их преобразовывает в png, сохраняет на диск, а потом у внешней библиотеки вызывает Код: pascal 1.
В идеале было бы переписать все так Код: pascal 1. 2. 3.
но это реально очень много переписывать. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 18:36 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_, > Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше Коллизия будет 1 раз из нескольких десятков проверок. У тебя же несколько десятков уникальных иконок. Иначе придется каждую с каждой проверять, ну или раньше одинаковые найдешь, если повезет. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 18:48 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше Да, именно так, смысла в хэше нет. Каждую иконку тебе надо развернуть до битмапа чтобы игнорировать разницу метаданных и сжатия, а потом уже голые пиксели можно тупо сравнивать CompareMem. Хэш, конечно, мог бы дать ускорение, но усложнит код, который всё равно скорее всего упрётся в диск, а не непосредственно сравнение. Можно даже не заморачиваться со случаями когда один пиксель отличается младшим битом в одном цвете. Но вообще сначала хорошо бы провести эксперимент и посмотреть на результат md5sum по этим файлам, например. Возможно, даже с разворачиванием в битмап можно не заморачиваться, а тупо сравнивать файлы побайтово. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 18:55 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat Коллизия будет 1 раз из нескольких десятков проверок. У тебя же несколько десятков уникальных иконок. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
Теперь без хешей Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 19:07 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ Смотри. Пусть у нас есть три группы иконок. Ну и ИМХО можно не проверять на полную идентичность, особенно если забацать одновременно 2 принципиально разных хэша. В то что могут одновременно совпасть 2 разных хеша я не верю. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 19:10 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше Ты путаешь коллизию и совпадение. Коллизия - это когда два разных набора данных имеют один хеш. Я был неправ насчет CompareMem при совпадении - да, это неприменимо. Но коллизии хеша на валидных PNG... что-то мне мало в это верится. Возьми хеш побольше тогда. На тупом CompareMem у тебя будет максимум NFiles*NUniques сравнений, в среднем - пополам. Причем эти сравнения наверняка по большей части будут выходить гораздо раньше окончания файлов. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 19:10 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat А почему 3 группы а не десятки уникальных иконок? rgreat если забацать одновременно 2 принципиально разных хэша. Fr0sT-Brutal Ты путаешь коллизию и совпадение. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 19:20 |
|
|
start [/forum/topic.php?fid=58&msg=40111135&tid=2036882]: |
0ms |
get settings: |
13ms |
get forum list: |
15ms |
check forum access: |
5ms |
check topic access: |
5ms |
track hit: |
79ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
62ms |
get tp. blocked users: |
2ms |
others: | 259ms |
total: | 452ms |
0 / 0 |