Comments 4
Мне кажется, у вас плохая хеш-функция. Хорошая хеш-функция на всём массиве данных должна давать более равномерное распределение.
Имея на руках такую базу, можно вполне серьёзно коммитнуться в поиск хорошей хэш-функции для изображения.
Алсо, 32-битное число - плохо. Это всего 4 миллиарда вариантов, а у вас одних кадров 150 миллиардов. Берите u64 или u128 как основу.
Из базовых эвристик: я бы сделал отдельный if если картинка очень чёрная (там вечно титры ползут), т.е. если общая яркость кадра меньше какой-то величины, то используется другая функция (которая, например, пытается найти опорные точки в качестве источника для генерации значения).
Возможно, если видео кропнуть на 20% и пережать в разрешение 8x8, то после сжатия чем-то типа mjpeg, получившееся будет само по себе неплохим хешем.
Спасибо за развёрнутый комментарий!
По-поводу хэш функции: тут, не столько она плоха, сколько сами данные. Здесь я должен извиниться и сказать, что в данной публикации не описал механизм получения исходных данных для вычисления хэша, а они получаются путём загрубления значений R,G,B.
R'=R/8; G'=G/8; B'=B/8;
Иначе флуктуации значений (от пережатых версий видео или JPEG компрессии скриншотов) будут зашкаливать.
Самое большое количество кадров приходится на значения R=G=B=0. Потом R=G=B=255, ну и дальше - градации серого.
Что касается 32 битного целого, то тут ситуация такова. То, что кадров больше, чем значений хэша - в этом нет ничего плохого. Просто когда мы ищем наш кадр, мы анализируем группу с этим значением хэша. Если их там несколько десятков, то мы их быстро проанализируем. Даже если несколько сотен, то на SSD всё летает. Проблема, когда их тысячи и больше. А в выше упомянутых ячейках R'=G'=B'=0 их в той базе может быть несколько миллиардов, что уже очень плохо. Но, плюс U32 в том, что база указателей имеет фиксированный размер в 32 ГБ и она по первому же fseek'у и read'у даёт нам место, где читать данные уже в файле с записями и сколько их читать! Для U64 файл указателей будет нереально большой. Кроме того, это потребует много аппаратных и вычислительных ресурсов при перестроении данных (если мы добавим информацию о новых видео).
Всё же поиск в отдельных случаях требует дополнительного ускорения и я для этого использую перцептивные хэши (об этом в следующей публикации). Как я их использую? Внутри группы с конкретным индексным хэшем данные сортируются по перцептивному хэшу. Получается двойное механизм индексации. Это реально помогает, хотя там есть некоторые нюансы. И, несмотря на это, для некоторых значений R'=G'=B'=0 и некоторых других внутри данной группы могут быть очень длинные подгруппы с одинаковым значением перцептивного хэша. Вот такие цепочки я отбрасываю.
Что касается последнего Вашего замечания, то я его не понял. Хэш я вычисляю для каждого кадра, а mjpeg используется для видео (т.е. множества кадров).
Я понял. У вас проблема не с коллизиями, наоборот, вам важно key space для хеш-таблицы. Кстати, попробуйте положить данные в clickhouse, он ОЧЕНЬ хорошо умеет хера ... обабатывать большие объёмы данных.
насчёт mjpeg: mjpeg это такой 'jpeg для фильмов', т.е. он не учитывает предыдущие/последующие кадры. Грубо говоря, что я предлагал: пережать видео в микроскопический формат, так, чтобы каждый кадр занимал 128 бит, и использовать его как хеш для оригинального кадра.
Впрочем, ваш concern про количество возможных seek'ов понятен.
Мы такое в бытность начала p2p для mp3 пробовали придумать. Когда даже альбом лишний было было вытащить накладно. Тоже - база фреймов. Но закончилось всё на уровне накурились-помечтали мозгового штурма и будучи дилетантами упёрлись, что каждый блок фрейм будет начинать с рандомного места. Сейчас бы наверное можно попробовать привязываться к BPM (для электронной музыки с битом).
Для торрентов кстати тоже актуально, но вроде уже решили в новой версии - отдельным хэшем для каждого файла.
ps извиняюсь, что сумбурно - последствия тех времён)
Использование индексных хэшей для ускорения поиска кадров в базе данных