Расстояние Хэмминга на двоичных строках в SQL - PullRequest
Новая
       36

Расстояние Хэмминга на двоичных строках в SQL

22 голосов
/ 24 января 2011

У меня есть таблица в моей БД, где я храню хэши SHA256 в столбце BINARY (32). Я ищу способ для вычисления расстояния Хэмминга записей в столбце до предоставленного значения, то есть что-то вроде: 

SELECT * FROM table 
  ORDER BY HAMMINGDISTANCE(hash, UNHEX(<insert supplied sha256 hash here>)) ASC 
  LIMIT 10

(если вам интересно, расстояние Хемминга строк A и B определяется как BIT_COUNT(A^B), где ^ - побитовый оператор XOR, а BIT_COUNT возвращает число 1 в двоичной строке).

Теперь я знаю, что оператор ^ и функция BIT_COUNT работают только с INTEGER, и поэтому я бы сказал, что, вероятно, единственный способ сделать это - разбить двоичные строки в подстроки, привести каждую двоичную подстроку к целому , вычислите подстроку расстояния Хэмминга и затем сложите их. Проблема в том, что это звучит ужасно сложно, не эффективно и определенно не элегантно. Поэтому мой вопрос: не могли бы вы предложить какой-нибудь лучший способ? (обратите внимание, что я на виртуальном хостинге и поэтому не могу изменить сервер БД или загрузить библиотеки)

edit (1): Очевидно, что загрузка всей таблицы в PHP и выполнение вычислений там было бы возможным, но я бы предпочел этого избежать, потому что эта таблица, вероятно, вырастет довольно большой.

edit (2): Сервер БД - MySQL 5.1

edit (3): Мой ответ ниже содержит код, который я только что описал выше.

edit (4): Я только что обнаружил, что использование 4 BIGINT для хранения хеша вместо BINARY (32) дает значительные улучшения скорости (более чем в 100 раз быстрее). Смотрите комментарии к моему ответу ниже.

Ответы [ 2 ]

14 голосов
/ 24 января 2011

Похоже, что хранение данных в столбце BINARY - это подход, который должен быть неэффективным.Единственный быстрый способ получить достойную производительность - это разделить содержимое столбца BINARY на несколько столбцов BIGINT, каждый из которых содержит 8-байтовую подстроку исходных данных.

В моем случае (32 байта)) это будет означать использование 4 BIGINT столбцов и использование этой функции: 

CREATE FUNCTION HAMMINGDISTANCE(
  A0 BIGINT, A1 BIGINT, A2 BIGINT, A3 BIGINT, 
  B0 BIGINT, B1 BIGINT, B2 BIGINT, B3 BIGINT
)
RETURNS INT DETERMINISTIC
RETURN 
  BIT_COUNT(A0 ^ B0) +
  BIT_COUNT(A1 ^ B1) +
  BIT_COUNT(A2 ^ B2) +
  BIT_COUNT(A3 ^ B3);

Использование этого подхода в моем тестировании более чем в 100 раз быстрее, чем использование подхода BINARY.

FWIW, это код, на который я намекал, объясняя проблему.Приветствуются лучшие способы достижения того же самого (особенно мне не нравятся двоичные> шестнадцатеричные> десятичные преобразования): 

CREATE FUNCTION HAMMINGDISTANCE(A BINARY(32), B BINARY(32))
RETURNS INT DETERMINISTIC
RETURN 
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 1,  8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 1,  8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 9,  8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 9,  8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 17, 8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 17, 8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 25, 8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 25, 8)), 16, 10)
  );
1 голос
/ 24 января 2011

Интересный вопрос, я нашел способ сделать это для binary(3), который может также работать для binary(32): 

drop table if exists BinaryTest;
create table  BinaryTest (hash binary(3));
insert BinaryTest values (0xAAAAAA);

set @supplied = cast(0x888888 as binary);

select  length(replace(concat(
            bin(ascii(substr(hash,1,1)) ^ ascii(substr(@supplied,1,1))),
            bin(ascii(substr(hash,2,1)) ^ ascii(substr(@supplied,2,1))),
            bin(ascii(substr(hash,3,1)) ^ ascii(substr(@supplied,3,1)))
        ),'0',''))
from    BinaryTest;

. replace удаляет все нули идлина остатка - это число единиц.(При преобразовании в двоичные числа ведущие нули опускаются, поэтому подсчет нулей не будет работать.)

Это выдает 6, что соответствует числу единиц в 

0xAAAAAA ^ 0x888888 = 0x222222 = 0b1000100010001000100010
...