Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / хранение и обработка перцептивного хэша в БД / 10 сообщений из 10, страница 1 из 1
12.04.2012, 22:05
    #37751370
XMalon
XMalon
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранение и обработка перцептивного хэша в БД
я близок к нулю в проектировании и работе с БД (нет, конечно как создавать таблицы и писать sql-запросы я выучил, но не более того), а ситуация такая: имеется необходимость хранения 64-битного перцептивного хэша (использую для сравнения изображений); суть перцептивного хэша (и в этом-то для меня вся проблема работы с ним в БД) заключается в том, что по нему можно не только сказать что сравниваемые изображения возможно идентичны или не идентичны (то есть да или нет), а и уточнить с какой степенью вероятности; из выше написанного возникает необходимость запроса который бы выбрал из таблицы все записи у которых 64-битное значение совпадает с искомым не обязательно по всем 64-м разрядам, а может например по 50-ти, 45-ти (некоторое пороговое значение (заранее определенное)). В поисковике ничего не нашел (наверное, просто пока не знаю что ищу). Буду рад если вы мне поможете ссылками на соответствующие ресурсы, форумы, статьи и пр.
Как выгоднее хранить эти 64 бита и как производить поиск по ним как описано выше ? (записей не более 500 000)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.04.2012, 22:15
    #37751376
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранение и обработка перцептивного хэша в БД
XMalonКак выгоднее хранить эти 64 бита и как производить поиск по ним как описано выше ?
(записей не более 500 000)

Разбить биты на отдельные записи. Потом группировка изображений с совпадающими битами и
фильтрация по HAVING COUNT(*)>40.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.04.2012, 23:02
    #37751428
XMalon
XMalon
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранение и обработка перцептивного хэша в БД
Dimitry SibiryakovРазбить биты на отдельные записи. Потом группировка изображений с совпадающими битами и
фильтрация по HAVING COUNT(*)>40.


ну я так понимаю, раз уж мы группируем все таки изображения, значит having count (*)>40 будет проверять количество изображений, а не записей с битами. и что это за условие "с совпадающими битами" (что имелось ввиду ? - полное совпадение чтоли ?). В общем не понятно, уже пол часа пытаюсь понять Вашу мысль, но не доходит, все равно спасибо )
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.04.2012, 23:31
    #37751457
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранение и обработка перцептивного хэша в БД
Ну, например, для некоего образца у вас получилось значение хэша 13. Пусть оно
четырёхбитное. Тогда в таблицу добавляется четыре записи с значениями (1, -2, 3, 4). Здесь
положительные числа - бит установлен, отрицательные - сброшен.

Далее у вас есть для проверки изображение с хэшем 12. Его набор битов, соответственно (-1,
-2, 3, 4).

Делается запрос
Код: sql
1.
2.
3.
SELECT COUNT(*) FROM T
WHERE Value in (-1, -2, 3, 4)
GROUP BY id


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

Это, конечно, только исходя из предположения, что все биты хэша имеют равный вес...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.04.2012, 23:39
    #37751468
sphinx_mv
sphinx_mv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранение и обработка перцептивного хэша в БД
XMalonКак выгоднее хранить эти 64 бита и как производить поиск по ним как описано выше ? (записей не более 500 000)
Мне кажется, самый простой и эффективный способ хранения такого хэша - отдельное поле с типом данных "большое целое" (64 бита).

Исходим из того, что условие фильтра "одинаковости" для выборки - общее количество совпадающих бит между хэшем каждой записи записи и хэшем, который ищем, должно быть больше определенного значения.

Не долго думая (или совсем не думая) алгоритм вычисления значения "в общем виде" примерно такой:
1) битовое исключающее ИЛИ между значением поля таблицы и значением хэша, которое нужно найти - во всех несовпадающих битах будет установлена 1.
2) для полученного результата подсчитывается количество установленных бит (т.е. несовпадений).
3) получить на основе этого значения количество совпадений (64 минус количество несовпадений).

Запрос на SQL может выглядеть примерно так:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
SELECT *
FROM table_with_hash
WHERE (64 -
 /* ...и 64 раза двигаем бит от самого младшего к самому старшему... */
case when (record_hash ^ seacrh_hash) & 0x0000000000000001 = 0 then 0 else 1 end +
case when (record_hash ^ seacrh_hash) & 0x0000000000000002 = 0 then 0 else 1 end +
... +
case when (record_hash ^ seacrh_hash) & 0x4000000000000000 = 0 then 0 else 1 end
) >= criteria


Можно обернуть подсчет количества установленных битов в функцию...
Жесть, конечно, но где-то так...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.04.2012, 23:45
    #37751475
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранение и обработка перцептивного хэша в БД
sphinx_mvЖесть, конечно

Мой вариант хоть и заставит распухнуть базу, но хоть индекс использовать может...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.04.2012, 00:10
    #37751495
XMalon
XMalon
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранение и обработка перцептивного хэша в БД
всем огромное спасибо, особенно Dimitry Sibiryakov, решение супер, с учетом всех требований, я бы сам до него не додумался, простой запрос, а вся необходимая информация как на ладони ))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.04.2012, 00:13
    #37751496
XMalon
XMalon
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранение и обработка перцептивного хэша в БД
Dimitry Sibiryakov,

в моем случае главное скорость. с объемом дискового пространства проблем никаких, да и тем более изображений не так много (не более 500 000), еще раз спс )
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.04.2012, 00:28
    #37751502
sphinx_mv
sphinx_mv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранение и обработка перцептивного хэша в БД
Dimitry Sibiryakovsphinx_mvЖесть, конечно

Мой вариант хоть и заставит распухнуть базу, но хоть индекс использовать может...

...А может и не использовать... Эффективность индексов - величина не абсолютная.
К тому же выполнять многократные запросы к серверу рано или поздно приведет к проблемам с производительностью.

К тому же, я бы сказал, что SQL для непосредственного решения подобной задачи не очень хороший инструмент.
Проще (и, наверное, правильнее) выгрузить на клиента массив из "ID" и "HASH" (для заявленного количества записей получается всего каких-то жалких 8 мегабайт объема данных) и манипулировать ими любым желаемым способом...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.04.2012, 10:33
    #37751855
eny
eny
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
хранение и обработка перцептивного хэша в БД
Есть замечательные инструменты в SQL это внешние функции и внешние агрегирующие функции (программируются на C#) - в них можно реализовать необходимую логику изапросы будут красивыми и структура базы данных.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / хранение и обработка перцептивного хэша в БД / 10 сообщений из 10, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 505ms
Закрыть
start [/forum/topic.php?fid=32&mobile=1&tid=1541739]:
 0ms
get settings:
 9ms
get forum list:
 17ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 178ms
get topic data:
 10ms
get forum data:
 3ms
get page messages:
 45ms
get tp. blocked users:
 1ms
others: 236ms
total:  505ms
x
x
Закрыть


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