如何加速这个字谜算法？

Question

我正在制作一个用于查找回文和部分匹配的移动应用程序。移动设备的计算能力有限，效率至关重要。

该算法可以接受任意数量的字母输入，包括重复字母，并使用每个字母仅一次，从中找出由这些字母组成的最长单词。我也希望快速找到前几个结果，对于底部（较短的结果）并不是非常关心，只要满足N就可以。例如：

STACK => stack, tacks, acts, cask, cast, cats…

我已经进行了一些搜索，找到了几种算法，我想出了一种我认为很有效的算法，但效率不如我所希望的那样高。

我有一个预先制作的查找字典，将排序后的键映射到生成该键的实际单词。

"aelpp" => ["apple", "appel", "pepla"]

我进一步根据键的长度将每个字典分成不同的部分。因此，长度为5个字母的键在一个字典中，长度为6个字母的键在另一个字典中。这些字典都在一个数组中，其中索引是在字典中找到的键的长度。

anagramArray[5] => dictionary5
dictionary5["aelpp"] => ["apple", "appel", "pepla"]

我的算法从输入单词"lappe"开始，对其进行排序：

"lappe" => "aelpp"

现在，对于每个内容最多为5个字母的字典，我进行比较以将其提取出来。以下是伪代码：

word = input.sort
for (i = word.length; i > 0; i--)
    dictionaryN = array[i]
    for (key in dictionaryN)
        if word matches key
            add to returnArray
        end
    end
    if returnArray count > N
      break
    end
end

returnArray.sort by longest word, alphabetize

这个词典里只有约17万个单词，但对于12个字母的输入，搜索需要长达20秒。我的match方法会将关键字转换为正则表达式：

"ackst" => /a.*c.*k.*s.*t.*/

例如，一个四位字母密钥，如acst（acts），将匹配ackst（stack），因为：

"ackst" matches /a.*c.*s.*t.*/

我看到其他应用在更短的时间内完成了相同的操作，我想知道我的方法是垃圾还是只需要一些调整。

如何获得生成单词的前N个最长回文构词法的最大计算效率？

- coneybeare

---

CodeReview上的相关问题：http://codereview.stackexchange.com/questions/1690/optimizing-java-anagram-checker-compare-2-strings - Bart Kiers

我设计了一个漂亮的字典结构优化方案，使用记录数组而不是树形结构、数组内相对偏移以及一些位压缩技巧。如果您感兴趣，我可以详细说明。 - Dialecticus

我其实是用自己的方法解决了它，借鉴了mcdowella的提示。这种方法非常快，不使用字典树，并且在原单词上使用dfs进行搜索。我不再寻求进一步优化，但如果你写了一篇博客文章，我会去看的。 - coneybeare

Answer 1

如果你把字典看作是一个字母树（可能甚至还代表着它），你就可以避免查看大量节点。如果"stack"在字典中，则从根到标记为a-c-k-s-t的叶子上会有一条路径。如果输入的单词是"attacks"，则将其排序为aackstt。您可以编写一个递归程序，跟随链接从根向下消耗aackstt中的字母。当您到达a-c-k时，您的字符串中将剩下stt，因此您可以跟随s到达ackst，但您可以排除跟随u到达a-c-k-u及其后代，v到达a-c-k-v及其后代等等。

实际上，使用这种方案，您可以只使用一个树来保存任意数量字母的单词，这应该可以节省您进行多个搜索的时间，每个搜索都针对目标长度。

- mcdowella

---

问题在于“边读边消耗字母”的部分。如果我的输入中有n个字母，那么即使在排序单词后，树中仍然有2^n条路径需要跟随，对吧？对于排序后输入中的每个字母，我可以选择将其保留在搜索字符串中或将其删除，是吗？这意味着对于16个字母，我必须搜索65536条路径。我错了吗？ - coneybeare

以上代码仍然有效。只需将搜索字符串（S）递归地分解为子字符串，然后在每个子字符串上进行搜索即可。 - selbie

我知道它能工作，但这并没有解决我担心的问题，即有2^n个子字符串，因此有2^n个树路径需要搜索。 - coneybeare

我的答案与这个类似（但更详细），所以给你点赞。 - Dialecticus

无论如何，成本都由您访问的节点数量确定。您最多访问每个节点一次，因此它受树中节点数量的限制，这是扫描整个字典的成本。实际上，因为您不访问不包含输入字母的节点后代，所以除非您的输入字符串包含字母表中的每个字母，否则您不必支付所有这些成本。一旦找到一个好的解决方案，您可以找到一些情况，即子树中没有任何东西可能导致更好的解决方案，并停止在那里寻找。 - mcdowella

在我看来，这并不像你所说的那么容易，因为“anagram”意味着任何字母都可能不存在。是的，在长度相同的情况下，构成变位词并不难，但在长度相同或更小的情况下，它就更加困难了，因为它不再是a-c-k-s-t，而是任意字母的组合。我的方法是使用否定条件，并从搜索中删除具有不存在字母的单词。 - luky

Answer 2

按照以下方式构建您的字典：

 For each word W in the English language (or whatever word set you have)

     Sort the characters in W by alphabetical order (e.g. "apple" -> "aelpp") into a new string called W'

     Compute Hash H into W' using any fast hash algorithm (e.g CRC32.  You could likely invent anything yourself that has a low number of collisions)

     Store W and H as an element in the dictionary array
     That is:
        Word.original = W;
        Word.hash = Hash(W');
        Dictionary.append(Word);

  Sort the dictionary by hash values.

现在要找到所有的变位词或搜索单词S

  Sort the characters in S by alphabetical order (e.g. "apple" -> "aelpp") into a new string called S'

  Compute Hash H of S' using the same fast hash algorithm above

  Now do a binary search on the dictionary for H.  The binary search should return an index F into Dictionary

  If the binary search fails to return an index into the Dictionary array, exit and return nothing

  I = F

  // Scan forward in the dictionary array looking for matches
  // a matching hash value is not a guarantee of an anagram match
  while (I < Dictionary.size) && (Dictionary[I].hash == H)
       if (IsAnagram(Dictonary[I], S)
           ResultSet.append(Dictionary[I].original)

  // Scan backwards in the dictionary array looking for matches
  I = F-1;
  while (I >= 0) && (Dictionary[I].hash == H)
       if (IsAnagram(Dictonary[I], S)
           ResultSet.append(Dictionary[I].original)


  return ResultSet     

现在我没有涵盖如何处理“子字符串”搜索（搜索长度小于搜索词的变位词单词）。我有点困惑这是否是一个要求。您的说明意味着结果集中的变位词应该具有与搜索词完全相同的字符集。但您可以可能枚举搜索字符串的所有子字符串，并将每个子字符串运行通过上面描述的搜索算法。

- selbie

---

我正在寻找所有的子字符串。我认为问题的前两个部分和示例已经解决了这个问题，但我可以回去让它更清晰明了。 - coneybeare

Answer 3

生成正则表达式有点昂贵，所以您可能不想在循环内部执行该操作。

一个选项（不一定是超级高效的，但在这种特殊情况下似乎很有用）是，不要搜索字典中所有单词，而是尝试删除各种组合中的字母，并检查结果字符串是否在字典中。这将最多进行2^n次迭代（其中n是单词中字母的数量），对于n < 18，这比170k更好。请注意，这种特定方法无法处理长输入，但否则应该非常快速。

- Steve Wang

---

我预计大多数输入为12个字母，因此找到删除字母的所有排列方式将是12！（12的阶乘为4.79亿）。这对我来说似乎不是更有效的方法。 - coneybeare

不，要么有一个字母，要么没有——将每个字母视为具有两种可能状态（存在/不存在）的开关。请记住，“stack”去掉“ck”与去掉“kc”是相同的，等等。实现这个的一种方法是在深入时仅删除最后一个删除的字符右侧的字符。 - Steve Wang

没错，昨晚太晚了我有些糊涂了。这只是2^n个排列。 - coneybeare

Answer 4

这只是一个想法，但也许这正是你在寻找的。您只有一个结构进行迭代，并且所有大小的单词都在其中。每次迭代步骤中，您会引入一个字母，并仅缩小搜索范围以选择没有比已引入的字母“大”的字母的单词。例如，如果您引入M，则再也不能在N-Z范围内引入任何内容。

该结构可以是二叉树，其中引入一个字母会导致您进一步遍历几个树层。每个节点都有一个字母，分支到其他较小字母和其他较大字母的分支，以及下一个缩小搜索的根分支和已完全用已引入的字母构建的单词列表的指针。如果该搜索子空间中没有可能的单词，分支可以为null，但是您不能同时为3个分支和指向单词列表的指针设置为null。（好吧，您可以，作为某种优化，现在与此无关）。您可以使用标志来表示具有给定字母的单词的存在，而这些单词可以存储在其他字典中，而不是指向单词列表的指针。

假设我们有字母ACKST。从结构的根开始，在循环中搜索所有这些字母，但是在K之后，您只能继续使用A和C进行搜索（因为S和T在K之上）。因为我们最感兴趣的是最大的单词，所以我们应该从最大的字母（在这种情况下是T）开始搜索，并用下一个最大的字母继续搜索。对于单词CAT，我们只能按照特定顺序搜索字母T、C、A才能到达。一旦我们到达那个A，就会有一个指向以下单词列表的指针：ACT、CAT。

- Dialecticus

Answer 5

检查两个字符串是否为变位词的O(N)时间复杂度和O(1)解决方案

bool Anagram( const  char *s1, const char *s2)
{
    unsigned int sum=0;

    if ( s1 == NULL || s2 == NULL)
        return false;

    while ( *s1 != '\0' && s2 != '\0')
    {
                   sum ^= *s1;
                   sum ^= *s2;
                   s1++;
                   s2++;
    }

    if ( s1 != '\0' || s2 != '\0')
        return false;

    if (sum) return false;

    return true;
}

如果你对两个相等的数字进行异或运算，结果将为0。（因此这就是该算法的原理）

- Sorin C