8

我正在制作一个移动应用程序来查找字谜和部分匹配。移动很重要，因为没有大量的计算能力，而效率是关键。

该算法采用任意数量的字母，包括重复字母，并找到由其字母组成的最长单词，每个字母只使用一次。我也有兴趣快速找到最佳结果，只要满足 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

该词典中只有大约 170,000 个单词，但对于 12 个字母的输入，搜索最多需要 20 秒。我的match方法从密钥中生成了一个正则表达式：

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

这样，例如，一个 4 个字母的键，如acst(acts)，将匹配ackst(stack)，因为：

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

我已经看到其他应用程序在更短的时间内做同样的事情，我想知道我的方法是垃圾还是只需要一些调整。

我怎样才能获得最大的计算效率来从一个单词中生成前 N 个字谜，按最大长度排序？

4

5 回答 5

6

如果您将（甚至可能表示）字典视为字母树，则可以避免查看大量节点。如果“堆栈”在字典中，则将有一条从根到标记为 ackst 的叶的路径。如果输入单词是“attacks”，那么对它进行排序以获得 aackstt。您可以编写一个递归例程来跟踪从根开始的链接，同时使用来自 aackstt 的字母。当您到达 ack 时，您的字符串中会留下 stt，因此您可以按照 s 到达 ackst，但您可以排除按照 u 到达 acku 及其后代，v 到达 ackv 及其后代，等等。

事实上，使用这种方案，您可以只使用一棵树来保存任意数量字母的单词，这样可以节省您进行多次搜索，每个目标长度一次。

于 2011-07-02T04:56:54.580 回答
0

生成正则表达式有点昂贵，因此您可能不想在循环中执行此操作。

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

于 2011-07-02T04:13:53.047 回答
0

构建你的字典如下：

 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

现在我没有介绍如何处理“子字符串”搜索（搜索长度小于搜索词的字谜词。如果这是一个要求，我有点困惑。你的说明暗示结果集应该有与搜索词完全相同的字符集。但您可能会枚举搜索字符串的所有子字符串，并通过上述搜索算法运行每个子字符串。

于 2011-07-02T05:40:55.373 回答
0

这只是一个想法，但也许这就是您正在寻找的。您只有一个可以迭代的结构，所有大小的单词都在其中。在每个迭代步骤中，您都会多引入一个字母，并将搜索范围缩小到没有比已经引入的字母“更大”的字母。例如，如果你引入 M，你就不能再引入 NZ 范围内的任何东西。

该结构可以是一棵二叉树，其中一个字母的引入会进一步引导您进入几个树级别。每个节点都有一个字母，分支到其余的小字母，分支到其余的大字母，一个分支到下一个缩小搜索的根，以及一个指向完全用字母构建的单词列表的指针介绍到此为止。如果该搜索子空间中没有可能的单词，则分支可能为空，但您不能同时为 3 个分支设置空值，同时为指向单词列表的指针设置空值。（你可以，作为一种优化，现在无关紧要）。除了指向单词列表的指针之外，您还可以使用一个标志来表示具有给定字母的单词的存在，但这些单词可以存储在其他字典中。

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

于 2011-07-02T09:38:39.437 回答
-1

O(N) 时间和 O(1) 解决方案来检查 2 个字符串是否是字谜

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。（因此算法）

于 2015-05-04T14:48:12.137 回答