Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Подсчет расстояния Хэмминга на большом комплекте данных

Anna | 24.06.2014 | нет комментариев
В данной статье речь пойдет об алгорифме HEngine и реализации решения задачи подсчета расстояния Хэмминга на крупных объемах данных.

Вступление

Расстояние Хэмминга — это число различающихся позиций для строк с идентичной длинной. Скажем, HD( 100, 001 ) = 2.

Впервой задача подсчета расстояния Хэмминга была поставлена Minsky и Papert в 1969 году [1], где задача сводилась к поиску всех строк из базы данных, которые находятся в пределах заданного расстояния Хэмминга к запрашиваемой.

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

Расстояние Хэмминга теснее достаточно обширно применяется для разных задач, таких как поиск близких дубликатов, идентификация образов, систематизация документов, исправление ошибок, выявления вирусов и т.д.

Скажем, Manku и сотоварищи предложили решение задачи кластеризации дубликатов при индексации веб документов на основе подсчета расстояния Хэмминга [2].
Также Miller и друзья предложили доктрину поиска песен по заданному аудио фрагменту [3], [4].
Сходственные решения были использованы и для задачи поиска изображений и идентификация сетчатки [5], [6] и т.д.

Изложение задачи

Имеется база данных бинарных строк T, размером n, где длина всякой строки m. Запрашиваемая строка a и требуемое расстояние Хэмминга k.

Задача сводится к поиску всех строк, которые находятся в пределах расстояния k.

В подлинной доктрины алгорифма рассматривается два варианта задачи: статическая и динамическая.

— В статическая задачи расстояние k предопределено предварительно.
— В динамической, напротив, требуемое расстояние предварительно неведомо.

В статье описывается решение только статической задачи.

Изложение алгорифма HEngine для статической задачи

Данная реализация фокусируется на поиске строк в пределах k <= 10.

Существует три решения статической задачи: линейный поиск (linear scan), растяжение запроса (query expansion) и растяжение базы данных (table expansion).

В данном случае под растяжением запроса имеется в виду генерация всех допустимых вариантов строк, которые вписываются в заданное расстояние для изначальной строки.
Растяжение базы данных подразумевает создание множества копий этой базы данных, где либо также генерируются все допустимые варианты, которые отвечают требованиям нужного расстояния, либо данные обрабатываются каким-то иным методом (детально об этом чуть дальше.).

HEngine [8] использует комбинацию этих 3 способов для результативного балансирования между памятью и временем исполнения.

Немножко теории

Алгорифм основывается на маленький теореме, которая гласит следующее:

Если для 2-х строк a и b расстояние HD( ab ) <= k, то если поделить строки a и b на подстроки способомrcut применяя фактор сегментации 
r >= vmk!/i>mark!Для длины строки 64 и предел расстояния 4, фактор сегментации равен 3, соответственно только 3 подстроки на строку.
Где T1, T2 и Т3 — это таблицы сигнатур, содержащие только подстроки B1, B2, B3.

Запрашиваемая строка делится на подстроки. Дальше для соответствующих подстрок генерируются диапазон сигнатур. И вконце производится двоичный поиск.


Рис 1. Упращенная версия обработки запросов к таблицам сигнатур. 

Итоги

Трудность сходственного алгорифма в среднем случае Om( log n 1 ) ), где n — это всеобщее число строк в базе данных, m — число двоичных поисков, а log n 1 двоичный поиск.
В экстремальных случаях может превышать линейную. Скажем, при условии q = 1 и когда все строки из всех таблицы сигнатур, помимо последней, совпадают с запрашиваемой, то получается O( ( r — 1 )mn( log n 1 ) ).

Отмечается, что такой подход использует в 4.65 поменьше памяти и на 16 % стремительней, чем предыдущая работа описанная в [2].

Реализация

Все это безусловно пленительно, но пока не потрогаешь на деле, трудно оценить масштабы.
Был сделан прототип HEngine [9] и протестирован на имеющихся реальных данных.

tests$ ./matches 7 data/db/table.txt data/query/face2.txt
Reading the dataset ........ done. 752420 db hashes and 343 query hashes.
Building with 7 hamming distance bound ....... done.

Building time: 12.964 seconds

Searching HEngine matches .......
found 100 total matches. HEngine query time: 0.228 seconds

Searching linear matches .......
found 100 total matches. Linear query time: 6.828 seconds

Итоги обрадовали, т. к. поиск 343 хеша из базы в 752420 занимает ~0.2 секунды, что в 30 раз стремительней линейного поиска.

Казалось бы здесь дозволено было остановиться. Но уж больно хотелось испробовать это применять как-то в настоящем плане.

В один клик до реального использования

Имеется база данных хешей изображений, и бекенд на PHP.
Задача стояла как-то связать функциональность HEngine и PHP.
Решено было применять FastCGI [10], в этом мне крепко помогли посты habrahabr.ru/post/154187/ иhabrahabr.ru/post/61532/.

Из PHP довольно вызвать:

$list = file_get_contents( 'http://fcgi.local/?' . $hashes );

Что за приблизительно 0.5 секунды возвращает итог. Когда линейным поиском требуется 9 сек, а через запросы к MySQL не поменьше 20 секунд.

Спасибо каждому, кто осилил.

Ссылки

[1] M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, MA, 1969.
[2] G. S. Manku, A. Jain, and A. D. Sarma. Detecting nearduplicates for web crawling. In Proc. 16Th WWW, May 2007.
[3] M. L. Miller, M. A. Rodriguez, and I. J. Cox. Audio fingerprinting: Nearest neighbor search in high-dimensional binary space. In MMSP, 2002.
[4] M. L. Miller, M. A. Rodriguez, and I. J. Cox. Audio fingerprinting: nearest neighbor search in high dimensional binary spaces. Journal of VLSI Signal Processing, Springer, 41(3):285–291, 2005.
[5] J. Landr

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB