3

我正在尝试编写一些 SQL 来接受一组字母并返回它可以生成的所有可能的单词。我的第一个想法是创建一个基本的三表数据库，如下所示：

Words -- contains 200k words in real life
------
1 | act
2 | cat

Letters -- contains the whole alphabet in real life
--------
1  | a
3  | c
20 | t

WordLetters --First column is the WordId and the second column is the LetterId
------------
1  | 1
1  | 3
1  | 20
2  | 3
2  | 1
2  | 20

但是我有点坚持如何编写一个查询，该查询返回在 WordLetters 中为传入的每个字母都有一个条目的单词。它还需要考虑具有两个相同字母的单词。我从这个查询开始，但它显然不起作用：

SELECT DISTINCT w.Word 
FROM Words w
INNER JOIN WordLetters wl
ON wl.LetterId = 20 AND wl.LetterId = 3 AND wl.LetterId = 1

我将如何编写查询以仅返回包含传入的所有字母并考虑重复字母的单词？

其他信息：

我的 Word 表包含近 200,000 个单词，这就是我尝试在数据库端而不是在代码中执行此操作的原因。如果有人关心，我正在使用enable1 单词列表。

4

3 回答 3

5

暂时忽略问题的 SQL 部分，我使用的算法相当简单：首先获取字典中的每个单词，然后生成一个版本，其中包含按排序顺序的字母，以及返回的指针到那个词的原始版本。

这将给出一个包含以下条目的表：

sorted_text word_id
act         123    /* we'll assume `act` was word number 123 in the original list */
act         321    /* we'll assume 'cat' was word number 321 in the original list */

然后，当我们收到一个输入（比如“tac”）时，我们对它的字母进行排序，在与原始单词表相连的排序字母表中查找它，这给了我们一个可以从中创建的单词列表那个输入。

如果我这样做，我会在 SQL 数据库中拥有相应的表，但可能会使用其他东西将单词列表预处理为排序形式。同样，我可能会将用户输入的字母排序留给我用来创建前端的任何内容，因此 SQL 将留给它擅长的事情：关系数据库管理。

于 2012-04-19T17:26:00.900 回答
0

如果您使用您提供的解决方案，您需要在 WordLetters 表中添加一个订单列。否则，无法保证您检索到的行与插入它们的顺序相同。

但是，我认为我有更好的解决方案。根据您的问题，您似乎希望找到所有具有相同组成字母的单词，而与出现的顺序或次数无关。这意味着您的可能性有限。如果将字母表中的每个字母转换为不同的 2 次幂，则可以为每个字母组合创建一个唯一值（也称为位掩码）。然后，您可以简单地将单词中每个字母的值相加。这将使匹配单词变得微不足道，因为具有相同字母的所有单词都将映射到相同的值。这是一个例子：

WITH letters
     AS (SELECT Cast('a' AS VARCHAR) AS Letter,
                1                    AS LetterValue,
                1                    AS LetterNumber
         UNION ALL
         SELECT Cast(Char(97 + LetterNumber) AS VARCHAR),
                Power(2, LetterNumber),
                LetterNumber + 1
         FROM   letters
         WHERE  LetterNumber < 26),
     words
     AS (SELECT 1 AS wordid, 'act' AS word
         UNION ALL SELECT 2, 'cat'
         UNION ALL SELECT 3, 'tom'
         UNION ALL SELECT 4, 'moot'
         UNION ALL SELECT 5, 'mote')
SELECT wordid,
       word,
       Sum(distinct LetterValue) as WordValue
FROM   letters
       JOIN words
         ON word LIKE '%' + letter + '%'
GROUP  BY wordid, word

如果您运行此查询，您将看到，“act”和“cat”具有相同的 WordValue，“tom”和“moot”也是如此，尽管字符数不同。

是什么让这比您的解决方案更好？您不必构建很多非单词来清除它们。这将大大节省执行任务所需的存储和处理。

于 2012-04-19T17:38:45.053 回答
0

SQL中有一个解决方案。它涉及使用一种技巧来计算每个字母在单词中出现的次数。以下表达式计算“a”出现的次数：

select len(word) - len(replace(word, 'a', ''))

这个想法是计算单词中所有字母的总和，看看它是否与总长度匹配：

select w.word, (LEN(w.word) - SUM(LettersInWord))
from 
(
  select w.word, (LEN(w.word) - LEN(replace(w.word, wl.letter))) as LettersInWord
  from word w 
  cross join wordletters wl
) wls
having (LEN(w.word) = SUM(LettersInWord))

这种特殊的解决方案允许一个字母多次出现。我不确定在原始问题中是否需要这样做。如果我们想要达到一定数量的出现，那么我们可以执行以下操作：

select w.word, (LEN(w.word) - SUM(LettersInWord))
from 
(
   select w.word,
     (case when (LEN(w.word) - LEN(replace(w.word, wl.letter))) <= maxcount 
         then (LEN(w.word) - LEN(replace(w.word, wl.letter))) 
         else maxcount end) as LettersInWord
   from word w 
   cross join
   (
      select letter, count(*) as maxcount
      from wordletters wl
      group by letter
   ) wl
) wls
having (LEN(w.word) = SUM(LettersInWord))

如果您想要与字母完全匹配，那么 case 语句应该使用" = maxcount"而不是" <= maxcount".

以我的经验，我实际上已经看到了小交叉连接的良好性能。这实际上可能在服务器端工作。在服务器上进行这项工作有两大优势。首先，它利用了盒子上的并行性。其次，需要通过网络传输的数据要少得多。

于 2012-04-19T17:56:23.877 回答