在表中查找类似的数字模式

Question

好的,我们假设我们有members桌子.有一个叫做的领域,比方说about_member.1-1-2-1-2每个人都会有这样的字符串.假设member_1具有此字符串,1-1-2-2-1并且他搜索具有相似字符串或尽可能相似的字符串.例如,如果member_2具有字符串,1-1-2-2-1则它将是100%匹配,但是如果member_3具有这样的字符串,2-1-1-2-1则它将是60%匹配.它必须按比例百分比排序.使用MYSQL和PHP最好的方法是什么？这很难解释我的意思,但也许你得到它,如果没有,请问我.谢谢.

编辑:请不要使用Levenshtein方法给我想法.那个答案会得到赏金.谢谢.(赏金将在我能够做到的时候公布)

Answer 1

将您的数字序列转换为位掩码并使用BIT_COUNT(列^搜索)作为相似度函数,范围从0(= 100%匹配,字符串相等)到[位长](= 0%,字符串完全不同).要将此相似度函数转换为百分比值使用

100 * (bit_length - similarity) / bit_length

例如,"1-1-2-2-1"变为"00110"(假设您只有两个状态),2-1-1-2-1为"10010",bit_count(00110 ^ 10010)= 2,位长= 5,并且100*(5-2)/ 5 = 60%.

Answer 2

Jawa最初发布了这个想法; 这是我的尝试.

^是XOR功能.它逐位比较2个二进制数,如果两个位相同则返回0,否则返回1.

    0 1 0 0 0 1 0 1 0 1 1 1  (number 1)
 ^  0 1 1 1 0 1 0 1 1 0 1 1  (number 2)
 =  0 0 1 1 0 0 0 0 1 1 0 0  (result)

这是如何适用于您的问题:

  // In binary...
  1111 ^ 0111 = 1000 // (1 bit out of 4 didn't match: 75% match)
  1111 ^ 0000 = 1111 // (4 bits out of 4 didn't match: 0% match)

  // The same examples, except now in decimal...
    15 ^    7 = 8  (1000 in binary) // (1 bit out of 4 didn't match: 75% match)
    15 ^    0 = 15 (1111 in binary) // (4 bits out of 4 didn't match: 0% match)

我们如何计算MySQL中的这些位:

BIT_COUNT(b'0111') = 3 // Bit count of binary '0111'
BIT_COUNT(7) = 3       // Bit count of decimal 7 (= 0111 in binary)
BIT_COUNT(b'1111' ^ b'0111') = 1 // (1 bit out of 4 didn't match: 75% match)

所以要获得相似性 ......

// First we focus on calculating mismatch.
(BIT_COUNT(b'1111' ^ b'0111') / YOUR_TOTAL_BITS) = 0.25 (25% mismatch)
(BIT_COUNT(b'1111' ^ b'1111') / YOUR_TOTAL_BITS) = 0 (0% mismatch; 100% match)

// Now, getting the proportion of matched bits is easy
1 - (BIT_COUNT(b'1111' ^ b'0111') / YOUR_TOTAL_BITS) = 0.75 (75% match)
1 - (BIT_COUNT(b'1111' ^ b'1111') / YOUR_TOTAL_BITS) = 1.00 (100% match)

如果我们可以将您的about_member字段存储数据作为位(并用整数表示),我们可以轻松完成所有这些操作!而不是1-2-1-1-1,使用0-1-0-0-0,但没有破折号.

以下是PHP如何帮助我们:

bindec('01000') == 8;
bindec('00001') == 1;
decbin(8) == '01000';
decbin(1) == '00001';

最后,这是实现:

// Setting a member's about_member property...
$about_member = '01100101';
$about_member_int = bindec($about_member);
$query = "INSERT INTO members (name,about_member) VALUES ($name,$about_member_int)";

// Getting matches...
$total_bits = 8; // The maximum length the member_about field can be (8 in this example)
$my_member_about = '00101100';
$my_member_about_int = bindec($my_member_about_int);
$query = "
    SELECT 
        *,
        (1 - (BIT_COUNT(member_about ^ $my_member_about_int) / $total_bits)) match 
    FROM members
    ORDER BY match DESC
    LIMIT 10";

最后一个查询将选择与我最相似的10个成员!

现在,用外行的话来概括,

我们使用二进制文件,因为它使事情更容 二进制数就像一长串的灯开关.我们希望保存"灯光开关配置"以及查找具有最相似配置的成员.

的^操作者,给定2点光开关的配置,为我们做一个比较.结果又是一系列开关; 一个开关将是ON如果2个原始开关分别在不同的位置,并且OFF如果它们在相同的位置.

BIT_COUNT告诉我们有多少交换机 - ON让我们知道有多少交换机是不同的.YOUR_TOTAL_BITS是交换机的总数.

但是二进制数仍然只是数字......所以1和0的字符串实际上只代表133或94这样的数字.但如果我们使用十进制数字,那么可视化我们的"灯开关配置"要困难得多.这就是PHP的decbin和bindec进来了.

详细了解二进制数字系统.

希望这可以帮助!