postgresql - 以任意顺序选择包含子集字符的行

Question

我有一个包含英语单词列表的表格，我试图从中选择所有可以用给定字符串“hand”组成的单词(就像在游戏拼字游戏中一样)

+--------+
|  word  |
+--------+
| test   |
| father |
| woman  |
| zebra  |
+--------+

到目前为止，我的查询只会检查手中的任何字符是否出现在单词中。

SELECT * FROM words WHERE word SIMILAR to '%e%|%z%|%h%';
/* returns test, father and zebra as they all contain either e,z or h */

然而，这并没有考虑到一个单词是否比手包含一个字符的次数更多，我在 python 中使用的代码来检查一个单词是否有效

def isValidWord(word, hand):
    """Return true or false can the word be made using the characters in the hand"""
    for i in word: # for each character in word
        if hand.count(i)<word.count(i): # is the character in the hand enough times
            return False
    return True # if every character in the word is present in the hand

我的问题是如何构建一个查询来检查单词中的每个字符并确保该字符的出现次数不大于字符串中的出现次数？或者这不是数据库的工作？

提前致谢。

Answer 1

坦率地说，这不是(关系)数据库的工作。

由于英语中的几千个单词，即使你将它们放大到所有可以想象的偏角，也不会超过大约 10 万个单词，我真的不明白你为什么要为此使用数据库。只需在 python 中编写一个内存中的单词列表，您就可以简单地线性浏览它。

有多种方法可以更快地搜索大量数据，但关系数据库无法应用其中任何一种。此外，考虑到字母是单字节数据，速度增益应该可以忽略不计。

如果您担心性能:是的，在 python 中执行此操作确实会产生很大的运行时开销，因为计算字母的速度非常快并且可以高度优化，但 python 本身是一种复杂的语言，执行它会设置一些限制。

考虑到要处理的数据量很小，我的做法是:

1. 准备一个单词列表:按字母顺序对字典中每个单词的字母进行排序，并将排序后的字符串用作实际单词的键。您会发现一个排序的字符串可以映射到多个单词。
2. 将手写的字母排序
3. 对于单词列表中的每个键，检查它是否是您手中的子集。这应该非常快，因为之前的排序可以避免冗余检查(即如果你在单词列表的开头，第一个单词以 a 开头，但你的最低手写字母是 e，跳到以 e 开头的第一个单词。

从算法上讲，任何类型的树结构都可以更快，但在大多数 PC 风格的处理器上，编写良好的 C 代码将编译为非常快速的 SIMD 字符串比较。