5

假设我们有一本大约 250.000 个单词的字典。算法应该将 12 个字母作为一个数组或一个字符串，并从字典中找到匹配最长单词的变体。

当然，人们总是可以暴力破解它，但我想知道最优雅的方法是什么？

如果使用 PHP 以外的语言的答案不使用任何特定于语言的函数作为主要问题的快捷方式，则也将被接受。

注意：单词存储在数据库中，但我可以将它们拉入内存以提高速度。虽然我不确定 PHP 的索引是否优于 MySQL 数据库？

4

5 回答 5

4

您应该计算每个单词的签名，只计算一次并将其与单词一起保存到数据库中。

该表应该是这样的：

   word varchar(12), 
   a int,
   b int, 
   c int,
    ...
   w int,
   z int;

并且从 a 到 z 的字段必须包含单词中包含的字母数，例如 anagram 将有如下记录：

word,    a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
anagram, 3,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0

一旦你有十二个字母，你必须计算集合的签名并使用它来创建一个这样的选择：

select word, length(word) as wordlen
from dictionary
where
a <= 4 and
b <= 0 and
c <= 1 and
d <= 2 and
e <= 0 and
f <= 0 and
 ....
z <= 0
order by wordlen desc;

为了拥有可以使用您拥有的字母集创建的所有单词。

没有排列，没有组合，虽然工作（编译字典）只完成一次并且离线。

只是另一个提示，从数据库中删除所有超过十二个字符的单词

于 2009-09-28T12:37:14.360 回答
3

我会在这里对字谜问题的答案进行稍微修改的版本

对于字典中的每个单词，按字母顺序对字母进行排序。所以“foobar”变成了“abfoor”。

从您的完整输入开始，按字母顺序排序。如果没有找到，删除一个字母，重新搜索。对每个字母都这样做。然后删除两个字母......等等。

最坏的情况：根本找不到“字谜”。您将必须测试所有可能的输入组合，这将为您提供大约 2^n 次查找，其中 n 是输入字符的数量（在您的示例中：12）但是，算法的速度不取决于字典的大小在运行时（当然，按字母顺序对单词进行排序）在我看来这是最重要的事情。

于 2009-09-28T12:17:25.263 回答
1

Eric Lippert 写了一篇关于字谜搜索的博文。这些示例都使用 c#，但这些技术可用于任何语言。

在字典中有效搜索字谜的诀窍是要意识到所有字谜都有相同的字母，只是顺序不同。如果您“规范化”每个单词，使其字母大写并按字母顺序排列，那么检查一个单词是否是另一个单词的变位词就像比较它们的规范形式一样简单

使用这种技术，您可以轻松地从哈希表或平衡树中查找字谜。

于 2009-09-29T15:16:11.017 回答
0

如果你想找到最长的匹配词，我会先尝试按词长对字典进行排序，这样你就可以把最大的精力放在最长的词上

于 2009-09-28T10:22:13.467 回答
-1

我的点子：

伪代码：

int_32 letter_mask
int_32 permutation_match_mask
if(((letter_mask XOR permutation_match_mask) AND letter_mask)  == 0)
        YOU_HAVE_HIT;

当你在字母掩码中有非重复字母时，这很有效，但是如果你有更多的字母（你可能有），那么你可以扩展leter和permutationmatchmask

编辑

另一个想法

按字母顺序对词汇表中的单词进行排序。

如果有 12 个字母并且它们都不同，那么就有 4095 个可能的组合（只是 sum i= 1->12 binomial(12 over i) ）（对于字母 ABCD，有 (ABCD,ABC,ABD,ACD ,BCD,AB,AC,AD,BC,BD,CD,A,B,C,D) 正如我所说，12 个不同的字母中有 4095 个，如果某些字母相同，则更少。

复杂度 4095*Log2(250000) 大约是 75000。值得一试。

对每个组合进行精确搜索。

于 2009-09-28T10:55:03.277 回答