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

Question

好的，假设我们有一个名为members的表。有一个字段叫做，比如说，about_member。每个人都会有像这样的字符串1-1-2-1-2。假设成员_1有这个字符串1-1-2-2-1，他搜索谁有相似的字符串或尽可能相似的字符串。例如，如果成员_2有字符串1-1-2-2-1，那么它将是100%匹配，但如果成员_3有这样的字符串2-1-1-2-1，那么它将是60％的匹配。并且必须按匹配百分比排序。使用MYSQL和PHP完成它的最佳方法是什么？很难解释我的意思，但也许你懂了，如果不懂，请问我。谢谢。

编辑：请给我一些不使用Levenshtein方法的想法。那个答案将获得悬赏。谢谢。（悬赏将在我能够操作时宣布）

- good_evening

---

不是真的...你呢？ - good_evening

它总是一个位掩码（1或2）吗？ - Pekka

标题：在表格中查找相似数字模式，怎么样？ - Pekka

我不确定关系型数据库是解决您所述问题的最佳选择。然而，如果每个数字放在不同的列中而不是一个单独的字符串中，则可能会有更好的解决方案。 - banx

好的，Banx。假设我们可以将它放在不同的列中，那么你有什么建议？ - good_evening

Answer 1

将您的数字序列转换为位掩码，并使用BIT_COUNT(column ^ search)作为相似性函数，其范围从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%。

- user187291

---

你能用查询语句来解释一下吗？如果可以的话，奖励归你。谢谢。 - good_evening

我认为他的意思是这个： $sql = "SELECT BIT_COUNT(about_member ^ '{$search}') AS similarity FROM members"; 注意，about_member 中的数据应该像00101这样保存，而不是1-1-2-1-2。 - Mischa

Answer 2

Jawa最初发布了这个想法，这是我的尝试。

^ 是异或函数。它逐位比较两个二进制数，如果两个位相同，则返回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字段存储数据为位（并由整数表示），那么我们可以轻松地完成所有这些操作！使用0-1-0-0-0而不是1-2-1-1-1，但不要使用破折号。

以下是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，否则为OFF。

BIT_COUNT告诉我们有多少开关是ON——给我们一个不同开关的计数。 YOUR_TOTAL_BITS是总开关数。

但是二进制数字仍然只是数字...因此，一串1和0实际上只代表像133或94这样的数字。但是，如果我们使用十进制数，很难将我们的“灯开关配置”可视化。这就是PHP的decbin和bindec发挥作用的地方。

了解更多关于二进制数系统的信息。

希望这可以帮助你！

- Tim

Answer 3

一种方法是计算您的搜索字符串与每个成员的about_member字段之间的Levenshtein距离。这里有一个MySQL存储函数实现该函数。

有了这个，你可以做到：

SELECT name, LEVENSHTEIN(about_member, '1-1-2-1-2') AS diff 
FROM members 
ORDER BY diff ASC

相似度的百分比与diff有关；如果diff=0，那么百分比是100%，如果diff等于字符串的大小（减去破折号的数量），则为0%。

- NullUserException

---

哇，这很有趣。那性能如何？它是慢查询吗？会消耗大量托管资源吗？ - good_evening

@hey 老实说，我不知道。你得试着去找出来。 - NullUserException

如果您在Order By或Where子句中使用函数结果，它将强制进行表扫描。在大型表上，这可能不会表现良好。如果您告诉我们更多关于为什么使用这种模式，我们可能能够帮助您找到一个基于集合的解决方案，以提高性能。 - Thomas

嘿：最好仔细看一下Levenshtein距离是如何工作的。我有点怀疑这是否符合你的意思，但也可能是我错了…… - VolkerK

假设成员有问题，他们可以回答问题是或否，如果他们回答是，则将放置值1，如果回答否，则放置值2。我真的不知道如何更好地解释它... - good_evening

不，VolkerK。我真的需要这个。虽然这种方法是正确的，但如果像Thomas所说的那样会强制进行表扫描，那就不是最好的选择了。 - good_evening

Answer 4

显而易见的解决方案是查看levenstein距离（mysql中没有内置实现，但可以使用其他实现，例如pl/sql和一些扩展，这个），然而通常情况下，解决问题的正确方式应该是在第一时间就对数据进行规范化处理。

- symcbean

Answer 5

阅读原问题的澄清评论后，可以得出莱文斯坦距离并不是你要找的答案。

你并不是在计算将一个字符串更改为另一个字符串所需的最小编辑次数。

你正在尝试比较一组数字与另一组数字。你要找的是两组数字之间差异的最小（加权）总和。

将每个答案放在单独的列中（Ans1、Ans2、Ans3、Ans4等）。

假设您正在寻找与1-2-1-2相似之处。

SELECT UserName，Abs（Ans1-1）+ Abs（Ans2-2）+ Abs（Ans3-1）+ Abs（Ans4-2）作为Difference ORDER BY Difference ASC

将按与答案1-2-1-2相似度列出用户，假设所有问题都是平等加权的。

如果您想使某些答案更重要，请将每个术语乘以加权因子。

如果问题始终是是/否，并且答案数量足够少，以至于所有答案都可以适合单个整数，并且所有答案具有相同的权重，则可以将所有答案编码为单个列，并使用BIT_COUNT建议。这将是更快速和更节省空间的实现。

- MZB

Answer 6

我会选择 PHP 内置的 similar_text() 方法。它看起来正是你想要的：

$percent = 0;
similar_text($string1, $string2, $percent);

echo $percent;

它按照问题的期望工作。

- Félix Saparelli

Answer 7

如果你将答案模式表示为位序列，你可以使用公式 (100 * (bit_length - similarity) / bit_length)。

根据上述示例，当我们将 "1" 转换成位关闭，将 "2" 转换成位打开时，"1-1-2-2-1" 变成了 6（作为基数10，二进制为00110），"2-1-1-2-1" 变成了18（10010b）等等。

此外，我认为你应该把答案的位存储在最低有效位中，但只要不同成员的答案对齐一致就行了。

这里有一个针对 MySQL 运行的示例脚本。

DROP TABLE IF EXISTS `test`;

CREATE TABLE `members` (
    `id` VARCHAR(16) NOT NULL ,
    `about_member` INT NOT NULL
) ENGINE = InnoDB;

INSERT INTO `members`
    (`id`, `about_member`)
VALUES
    ('member_1', '6'),
    ('member_2', '18');

SELECT 100 * ( 5 - BIT_COUNT( about_member ^ (
    SELECT about_member
    FROM members
    WHERE id = 'member_1' ) ) ) / 5
FROM members;

在脚本中神奇的数字5是答案的数量（公式中的bit_length）。根据您的情况更改该数字，无论实际数据类型使用了多少位，因为BIT_COUNT不知道您使用了多少字节。

BIT_COUNT返回设置的位数，并在MySQL手册中有解释。^是MySQL中的二进制异或运算符。

这里将member_1的答案与所有人（包括他们自己）进行比较-自然结果是100％匹配。

- Jawa

---

如何将“1-1-2-2-1”转换为6？ - good_evening

BIT_COUNT(N ^ N) 是什么意思？ - good_evening

当您将“1”替换为位关闭（0），将“2”替换为位打开（1）时，“1-1-2-2-1”-> 00110（二进制）-> 6（十进制）。 - Jawa

更新的。如需进一步澄清，请参阅http://en.wikipedia.org/wiki/Bitwise_operation#XOR - Jawa

Answer 8

如果您的字段不太多，可以在about_member的整数表示上创建索引。然后，您可以通过在about_member字段上进行精确匹配找到100％，然后通过更改1位来找到80％匹配项，通过更改2位来找到60％匹配项，以此类推。

- Joshua Martell

Answer 9

我会选择Levenshtein距离方法，你可以在MySQL或PHP中使用它。

- Alix Axel