Вводная часть
Проблема скорости поиска
Прежде чем перейти к основной теме имеет смысл взглянуть на проблему со стороны.
-
Сколько кадров содержит среднестатистический видео фильм?
-
Сколько фильмов должно быть в базе данных, чтобы пользователи начали пользоваться данным сервисом?
Попробуем ответить на эти вопросы.
-
150 000 кадров — содержит среднестатистический фильм.
-
1 000 000 видео — столько должна содержать современная база данных, чтобы быть востребованной.
В нашей базе данных должно быть порядка 150 миллиардов кадров. Это очень много! Как осуществить поиск за доли секунды по такой огромной таблице?
Поисковый алгоритм «VideoColor»
Технология поиска «VideoColor» заключается в том, что каждый кадр в видео рассматривается как отдельное изображение по которому может вестись поиск. Индексируемое, а затем и искомое изображение, делится на табличные области и в каждой из её ячеек находятся усреднённые значения компонент красного, зелёного и синего цветов. По ним, в дальнейшем, можно производить сравнение для нахождения искомого кадра.
Решение проблемы
Использование хэшей для ускорения поиска
Для решения вышеописанной проблемы есть решение и оно заключается в использовании хэшей. Хэш — это некоторое число, которое получается путём применения хэш-функции к исходным данным. Использование хэшей даст нам возможность ускорить поиск нашего кадра в огромном массиве информации.
В качестве исходных данных можно использовать усреднённые значения RGB определённых областей заданного изображения. А сам хэш можно сделать 32-битовым беззнаковым целым числом.
Проблема неоднозначности хэшей
Позиции значений
При вычислении хэшей нам необходимо привести усреднённое значение к целому числу, а вот здесь возможны неприятности.
Поскольку при перекодировании видео под разное разрешение или битрейт получаемые при просмотре кадры немного отличаются от оригинала, то может случиться следующее. Хэш от исходного изображения, возможно, будет отличаться от хэша перекодированного изображения. Это связано с тем, что усреднённые значения в пограничных областях могут изменяться в большую или меньшую стороны (пусть даже на небольшую величину) и мы можем получить вместо a значение a+1.
Кроме того, при захвате или экспорте кадра из видео в формат JPEG или другой формат (с потерями) происходит дополнительное изменение исходного кадра.
В результате мы получаем неоднозначность хэшей от различных версий кадров одного и того же видео. Это серьёзная проблема!
Использование массива хэшей
Удваивание хэшей
Для решения проблемы неоднозначности хэшей можно применить следующий подход. Если проанализировать входные значения, то можно увидеть, что они занимают либо центральные (близкие к центру) позиции или граничные позиции. В этом случае можно сделать предположение, что мы получили вилку значений и от одного значения хэша мы переходим к двум значениям и т. д. На каждом таком пограничном случае мы удваиваем количество хэшей, причём каждому присваиваем определённое значение вероятности.
Да, мы усложняем алгоритм поиска и многократно увеличиваем время поиска. Скользкий путь, но, попробуем пойти по нему дальше.
Вероятности хэшей
Если бы у всех значений из массива хэшей были бы равные вероятности, то нам пришлось бы в процессе поиска осуществлять поиск по всем хэшам. Если хэши имеют разную вероятность, то мы можем в первую очередь осуществлять поиск по более вероятным. И в случае нахождения кадра с минимальными отклонениями в узловых точках имеем право считать, что поиск успешен, а оставшиеся хэши просто игнорировать. Тем самым существенно ускоряем процесс поиска.
Проблема неравномерного распределения хэшей по адресному пространству
Как устроен индексный хэш?
Если каждой записи в таблице присвоить добавить новое поле - хэш, то можно его использовать как индекс для поиска. К сожалению, это потребует дополнительных затрат на индексацию и мы поступим по-другому. Создадим индексный файл, каждая ячейка которого будет содержать ссылку на запись в таблице с данными. А сами данные упорядочим таким образом чтобы внутри одной группы были записи с одинаковым индексным хэшем, причём эти группы упорядочены по значению хэша.
В этом случае, когда нам понадобится найти данные с заданным значением хэша (индекса), мы просто читаем поле с этим индексом из индексного файла (а также последующее поле, чтобы узнать количество записей с этим значением индекса). А затем, имея номер нулевой записи группы в таблице с записями читаем необходимые записи из таблицы записей.
Распределение по частоте индексного хэша
В идеале, если распределение записей более менее равномерное, мы получим, что для 150 миллиардов записей в каждой индексной ячейке будет приблизительно
150 000 000 000 / 4 000 000 000 = 38 записей.
Однако, в реальности дела обстоят не так радужно. Если построить гистограмму распределения, то она будет выглядеть приблизительно так.
Пики соответствуют наиболее частым значениям. Это, например, может быть значение (R=0, G=0, B=0) и оно по частоте может достигать 3-5% от общего количества кадров. В этом случае необходимо использовать другие механизмы ускорения поиска внутри группы, например, перцептивные хэши.
Выводы
Для ускорения поиска кадров в базе данных отлично подходят индексные хэши. С их помощью можно многократно ускорить процесс поиска. Хотя проблема неоднозначности хэшей вынуждает нас осуществлять поиск не по одному, а по целой группе хэшей, тем не менее «игра стоит свеч».
Ссылки по теме
Автор: Александр Алексеев
