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

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

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, и поэтому я бы сказал, что, вероятно, единственный способ сделать это - разбить двоичные строки в подстроках, отбросить каждую двоичную подстроку на integer, вычислите расстояние Хэмминга подстрокой, а затем добавьте их. Проблема в том, что это звучит ужасно сложно, неэффективно и определенно не изящно. Поэтому мой вопрос: можете ли вы предложить лучший способ? (обратите внимание, что я нахожусь на общем хостинге и поэтому не могу изменять сервер БД или загружать библиотеки)

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

редактировать (2): Сервер БД MySQL 5.1

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

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

источник

2011-01-23 CAFxX

Не стесняйтесь также предложить различные способы хранения хэшей, если это может оказаться полезным в поиске лучшее решение. – CAFxX

Если вы сохранили хэш в 8 целых чисел (возможно, в дополнение к двоичному хранилищу), расчет становится намного проще. – Andomar

Мне очень интересно, почему вы хотели бы рассчитать расстояние :) – Nanne

Вероятно, что хранение данных в 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) 
);

источник

2011-01-24 14:55:46 CAFxX

Я только что провел несколько тестов: запуск запроса в исходном вопросе с использованием функция, определенная здесь в таблице со 100000 строк, занимает около 2,5 секунд. Поскольку мне не нужен точный ответ на мой запрос, я могу просто попробовать таблицу, добавив WHERE RAND() <0,05 (чтобы опробовать случайные 5% таблицы), и это сокращает время до 0,2 с , Тем не менее, если какой-либо SQL-гуру там может указать лучший способ сделать это, я бы хотел его услышать. – CAFxX

Другое испытание: Я создал представление, которое преобразует каждый BINARY (32) в четыре BIGINT. Это снижает время от 2,5 до 0,6 с. – CAFxX

ОК, я выяснил, что если я действительно использую таблицу, в которой я храню хэш как 4 BIGINT, тот же запрос завершается в 0.02s. Непосредственное использование BINARY (32) - это плохая идея (TM). – CAFxX

Интересный вопрос, я нашел способ сделать это для 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

источник

2011-01-23 23:49:41 Andomar

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

ответ

Смежные вопросы