sql एसक्यूएल में बाइनरी तारों पर दूरी हैमिंग




mysql hash (2)

मेरे पास मेरे डीबी में एक टेबल है जहां मैं एक BINARY (32) कॉलम में SHA256 हैश स्टोर करता हूं। मैं कॉलम में प्रविष्टियों की एक हैमिंग दूरी की गणना करने के लिए एक तरीका ढूंढ रहा हूं, यानी कुछ ऐसा:

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

(यदि आप सोच रहे हैं, स्ट्रिंग्स ए और बी की हैमिंग दूरी को BIT_COUNT(A^B) रूप में परिभाषित किया गया है, जहां ^ बिटवाई एक्सओआर ऑपरेटर है और BIT_COUNT द्विआधारी स्ट्रिंग में 1s की संख्या देता है)।

अब, मुझे पता है कि ^ ऑपरेटर और BIT_COUNT फ़ंक्शन दोनों केवल INTEGERs पर काम करते हैं और इसलिए मैं कहूंगा कि ऐसा करने का एकमात्र तरीका सबस्ट्रिंग्स में बाइनरी स्ट्रिंग को तोड़ना होगा, प्रत्येक बाइनरी सबस्ट्रिंग को पूर्णांक में डालना होगा, गणना करें हथौड़ा दूरी सबस्ट्रिंग-वार और फिर उन्हें जोड़ें। इसके साथ समस्या यह है कि यह बहुत जटिल, कुशल नहीं है और निश्चित रूप से सुरुचिपूर्ण नहीं लगता है। मेरा सवाल इसलिए है: क्या आप किसी भी बेहतर तरीके से सुझाव दे सकते हैं? (कृपया ध्यान दें कि मैं साझा होस्टिंग पर हूं और इसलिए मैं डीबी सर्वर या लोड पुस्तकालयों को संशोधित नहीं कर सकता)

संपादित करें (1): स्पष्ट रूप से PHP में पूरी तालिका लोड करना और कंप्यूटेशंस करना संभव होगा लेकिन मैं इसके बजाय इसे टालना चाहूंगा क्योंकि यह तालिका शायद काफी बड़ी हो जाएगी।

संपादित करें (2): डीबी सर्वर MySQL 5.1 है

संपादित करें (3): नीचे दिए गए मेरे उत्तर में कोड है जो मैंने अभी ऊपर वर्णित किया है।

संपादित करें (4): मुझे अभी पता चला है कि एक बिएनरी (32) के बजाय हैश को स्टोर करने के लिए 4 बिगिनट्स का उपयोग करके भारी गति सुधार (100 गुना तेजी से) उत्पन्न होता है। नीचे दिए गए मेरे उत्तर में टिप्पणियां देखें।


ऐसा लगता है कि एक BINARY कॉलम में डेटा संग्रह करना एक दृष्टिकोण है जो खराब प्रदर्शन करने के लिए बाध्य है। सभ्य प्रदर्शन प्राप्त करने का एकमात्र तेज़ तरीका कई BIGINT कॉलम में 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);

इस दृष्टिकोण का उपयोग करके, मेरे परीक्षण में, BINARY दृष्टिकोण का उपयोग करने से 100 गुना तेज है।

एफडब्ल्यूआईडब्ल्यू, यह वह कोड है जिसे मैं समस्या बताते समय संकेत दे रहा था। एक ही चीज़ को पूरा करने के बेहतर तरीके स्वागत हैं (मुझे विशेष रूप से बाइनरी> हेक्स> दशमलव रूपांतरण पसंद नहीं है):

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)
  );

दिलचस्प सवाल है, मुझे 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




hamming-distance