database - 在给定子集的集合中查找最接近完成字符串

Question

假设我有一组单词，其中字符在 a-z 的集合中。我们还假设单词最长 10 个字符 并且该集合可以由所有组合 构建(没有排列，所以我不关心顺序)没有重复的此类字符。数据库中的集合一开始是空的，必须有人填充它。我对如何构建数据库以使其对该查询高效而言拥有完全的自由。让我们从一个例子开始。

有人通过插入这些词来填充数据库:

"ab"
"ac"
"abcde"
"def"
"xyz"

现在我的子集是这个:

"cabd"

我的查询/算法应该做的是，它应该返回按“完成”排序的单词列表。为了更清楚，上面的查询应该按顺序返回这些词:

"ab"
"ac"
"abcde"
"def"
"xyz"

让我们解释一下:

• “ab”和“ac”应该在顶部(在这种情况下我不关心哪个先出现)因为我的子集包含这个词中的所有字符。
• “abcde”是第三个，因为我拥有除“e”以外的所有单词，所以我只缺少 1 个字符
• “def”稍后出现，因为我缺少单词的 2 个字符(“e”和“f”)
• “xyz”在最后，因为我在其中没有任何字符

进一步观察:如您所见，我不关心顺序。如果我的子集查询是“abcd”，结果应该完全相同。

现在事情变得复杂了:每个单词都以 ID 作为主键存储在数据库中。理想的解决方案应该是算法应该打印 10 个(或有限数量的)ID，我将使用这些 ID 来自己查询单词。仅供引用，我正在使用 Firebase，所以目前我不能依赖 SQL

暴力解决方案是在不同的表中存储一个字符-词关系。因此，要存储包含特定字符的所有单词 ID:

a : {
    "id1",
    "id2",
    "id3",
    "id4",
    ....
}
b : {
    "id1",
    "id4",
    ....
}

ID 在哪里:

id1 : {
    "ab"
}
id2 : {
    "ac"
}
id3 : {
    "ad"
}
id4 : {
    "abc"
}

如您所见，通过这种方法，算法会提供数千个我需要查询和排序的结果，因此它不可扩展。有没有其他解决方案或聪明的方法来解决这个问题？

Answer 1

最佳解决方案可能取决于您使用的 SQL 引擎，因为某些引擎将具有解决某些所需步骤的功能。

这是一个想法:

在包含单词的表中，您可以添加一个整数 列来表示单词中出现的字母。一个整数有足够的位可用于存储字母表中每个字母的一位信息:1 表示对应的字母出现，0 表示不出现。因此需要 26 位来表示 a-z 范围内的字符。

然后您可以在该表上创建一个触发器，以便每当您在该表中插入一个新词时计算并存储该整数。

然后对于给定的输入词 X，您还将计算该整数。为了获得正确的顺序，您将对该整数与表中的每个整数执行按位或运算，并计算结果中的 1 位。 1 位越少，匹配越好。最少的 1 位数将对应于 X 的整数表示中的位数。在此之上计算的每一位表示表行中未出现在 X 中的字符。

这是在 MySql 中进行设置的脚本:

--/
create function bitset(str varchar(10)) returns int
begin
declare num int;
    set num = 0;
    while length(str) > 0 do
        set num = num | power(2, ord(str) - ord('a'));
        set str = substr(str, 2);
    end while;
    return num;
end
/

create table words (
    word varchar(10),
    bits int
);

create trigger ins_word before insert on words for each row
    set new.bits = bitset(new.word);

insert into words(word) values ('ab'), ('ac'), ('abcde'), ('def'), ('xyz');

select   word, 
         bits,
         bit_count(bitset('cabd') | bits) bitwise_or
from     words
order by 3;

最终查询使用自定义函数 bitset 和 MySql 中的原生函数 bit_count。

最终查询的输出如下所示:

 word |    bits  | bitwise_or
------+----------+-----------
ab    |        3 |    4
ac    |        5 |    4
abcde |       31 |    5
def   |       56 |    6
xyz   | 58720256 |    7