[SQL] SQL 이진 문자열에 거리를 해밍

SQL 이진 문자열에 거리를 해밍

나는 내가 BINARY (32) 열에 SHA256 해시를 저장 내 DB에 테이블이 있습니다. 내가 좋아하는, 즉 뭔가 제공된 값 열에서 항목의 해밍 거리를 계산하는 방법을 찾고 있어요 :

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

(경우에 당신이 궁금, 문자열 A와 B의 해밍 거리가 ^는 비트 XOR 연산자와 BIT_COUNT 바이너리 문자열 1의 개수를 반환 BIT_COUNT (A ^ B)로 정의된다).

지금, 나는 모두 ^ 연산자와 BIT_COUNT의 기능은 정수에 대한 작업과, 정수로 각 이진 문자열을 던져 나는 그것이 문자열에서 이진 문자열을 파괴하는 것입니다 할 것을 아마 유일한 방법을 말하고 싶지만 그래서, 계산 알고 해밍 거리 현명한 하위 문자열 다음에 추가합니다. 이의 문제는 정말 우아하지 확실히 효율적이고하지 복잡 소리이다. 내 질문은 그러므로 : 당신이 어떤 더 좋은 방법을 제안 할 수 있을까? (내가 공유 호스팅에있어주의 때문에 나는 DB 서버 또는로드 라이브러리를 수정할 수 없습니다 바랍니다)

편집 (1) : 분명히 PHP에서 전체 테이블을로드하고 계산이 가능있을 것하고 있지만,이 테이블은 아마 매우 커질 것 때문에 오히려 그것을 피할 것.

편집 (2) : DB 서버는 MySQL은 5.1입니다

편집 (3) : 내 대답은 아래 난 그냥 위에서 설명하는 코드가 포함되어 있습니다.

편집 (4) : 난 그냥 4 BIGINTs를 사용하는 대신 BINARY (32) (100 배 이상 빠른) 엄청난 속도 향상을 얻을 수의 해시를 저장하는 것을 알아 냈다. 내 대답은 아래에 주석을 참조하십시오.

해결법

1. ==============================

   1.바이너리 열에서 데이터를 저장하는 것은 제대로 수행하도록 결합 된 방식임을 보인다. 알맞은 성능을 얻을 수있는 유일한 방법은 빠른 각각 원래의 데이터의 8 바이트의 문자열을 포함하는 여러 BIGINT 컬럼에서 BINARY 항목의 내용을 분리한다.

   바이너리 열에서 데이터를 저장하는 것은 제대로 수행하도록 결합 된 방식임을 보인다. 알맞은 성능을 얻을 수있는 유일한 방법은 빠른 각각 원래의 데이터의 8 바이트의 문자열을 포함하는 여러 BIGINT 컬럼에서 BINARY 항목의 내용을 분리한다.

   내 경우 (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)
     );
   

2. ==============================

   2.흥미로운 질문, 나는 바이너리 (3) 그 힘의 작품뿐만 아니라에 대한 이진 (32)이 작업을 수행 할 수있는 방법을 발견했습니다 :

   흥미로운 질문, 나는 바이너리 (3) 그 힘의 작품뿐만 아니라에 대한 이진 (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;
   

   는 모두 0을 제거 교체하고, 나머지의 길이는 사람의 수입니다. (바이너리를 생략로의 전환은 그렇게하고자하지 작업 제로 계산, 제로를 선도.)

   에 사람의 번호와 일치이 인쇄 6,

   0xAAAAAA ^ 0x888888 = 0x222222 = 0b1000100010001000100010
   

from https://stackoverflow.com/questions/4777070/hamming-distance-on-binary-strings-in-sql by cc-by-sa and MIT license