短语字谜的高效算法

Question

如何高效地生成给定字符串的短语变位词？

我要解决的问题

假设您有一个包含n个单词的单词列表。给定一个输入字符串，比如“peanutbutter”，生成所有短语变位词。一些可能的结果是：pea nut butter、A But Ten Erupt等。

我的解决方案

我有一个包含给定单词列表中所有单词的trie。给定一个输入字符串，我计算它的所有排列组合。对于每个排列，我使用递归解决方案（类似于this）来确定该特定排列的字符串是否可以被拆分为单词。例如，如果peanutbutter的一个排列是“abuttenerupt”，我使用这种方法将其拆分为“a but ten erupt”。我使用trie来确定一个字符串是否是有效的单词。

有什么不好的地方

我的问题是，因为我计算了所有的排列组合，所以对于长度超过10个字符的短语，我的解决方案运行非常缓慢，这让人很失望。我想知道是否有其他方法来做到这一点。 像https://wordsmith.org/anagram/这样的网站可以在不到一秒钟的时间内完成任务，我很好奇他们是如何做到的。

- Ravi

Answer 1

你面临的问题可以分解为两个子问题：

1. 找到使用输入字符串所有字符的单词组合
2. 找到第一个子问题中找到的单词的所有排列

子问题#2是基本算法，你可以在大多数编程语言中找到现有的标准实现。让我们专注于子问题#1。

首先将输入字符串转换为“字符池”。我们可以将字符池实现为数组oc，其中oc[c] = 字符c出现的次数。

然后，我们使用回溯算法来查找适合字符池的单词，如下伪代码所示：

result = empty;

function findAnagram(pool)
  if (pool empty) then print result;
  for (word in dictionary) {
    if (word fit in charpool) {
      result = result + word;
      update pool to exclude characters in word;
      findAnagram(pool);

      // as with any backtracking algorithm, we have to restore global states
      restore pool;
      restore result;
    }
  }
}

注意：如果我们通过值传递charpool，那么我们就不需要恢复它了。但是由于它非常大，我更喜欢通过引用传递它。

现在我们删除冗余的结果并应用一些优化：

- 假设A在字典中出现在B之前。如果我们选择第一个单词是B，那么我们就不必考虑单词A在后续步骤中的情况，因为这些结果（如果我们选A）已经包含在选择A作为第一个单词的情况下。 - 如果字符集足够小（<64个字符最好），我们可以使用位掩码快速过滤无法放入池中的单词。位掩码标记哪些字符在单词中出现，无论它出现多少次。

更新伪代码以反映这些优化：

function findAnagram(charpool, minDictionaryIndex)
  pool_bitmask <- bitmask(charpool);
  if (pool empty) then print result;
  for (word in dictionary AND word's index >= minDictionaryIndex) {
    // bitmask of every words in the dictionary should be pre-calculated
    word_bitmask <- bitmask(word)
    if (word_bitmask contains bit(s) that is not in pool_bitmask)
      then skip this for iteration
    if (word fit in charpool) {
      result = result + word;
      update charpool to exclude characters in word;
      findAnagram(charpool, word's index);

      // as with any backtracking algorithm, we have to restore global states
      restore pool;
      restore result;
    }
  }
}

这是我对子问题#1的C++实现，其中字符集仅包含小写字母'a'..'z': http://ideone.com/vf7Rpl。

- Can Nguyen

Answer 2

与其生成排列然后尝试将其分解成单词，不如在递归生成排列时检查有效单词。如果您当前的部分完成排列与任何有效单词都不对应，则停止并不再递归。这意味着您不会浪费时间生成无用的排列。例如，如果您生成“tt”，则没有必要排列“peanubuter”并将所有排列附加到“tt”上，因为没有以tt开头的英语单词。

假设您正在进行基本的递归排列生成，跟踪您已生成的当前部分单词。如果在任何时候它是有效单词，则可以输出一个空格并开始一个新单词，并递归排列剩余字符。您还可以尝试将剩余字符中的每个字符添加到当前部分单词中，仅当这样做导致有效的部分单词（即存在以这些字符开头的单词）时才递归。

类似于以下内容（伪代码）：

 void generateAnagrams(String partialAnagram, String currentWord, String remainingChars)
 {
      // at each point, you can either output a space, or each of the remaining chars:

      // if the current word is a complete valid word, you can output a space
      if(isValidWord(currentWord))
      {
           // if there are no more remaining chars, output the anagram:
           if(remainingChars.length == 0)
           {
               outputAnagram(partialAnagram);
           }
           else
           {
               // output a space and start a new word
               generateAnagrams(partialAnagram + " ", "", remainingChars);
           }
      }

      // for each of the chars in remainingChars, check if it can be
      // added to currentWord, to produce a valid partial word (i.e.
      // there is at least 1 word starting with these characters)
      for(i = 0 to remainingChars.length - 1)
      {
          char c = remainingChars[i];
          if(isValidPartialWord(currentWord + c)
          {
              generateAnagrams(partialAnagram + c, currentWord + c,
                  remainingChars.remove(i));
          }
      }
 }

你可以这样调用它。

 generateAnagrams("", "", "peanutbutter");

你可以进一步优化这个算法，通过传递与当前部分完成的字相对应的trie节点以及将currentWord作为字符串传递。这会使你的isValidPartialWord检查更快。

你可以通过将isValidWord检查更改为仅在该单词按升序（大于或等于）排列时与先前输出的单词相比返回true，从而强制唯一性。您可能还需要另一个检查来捕获可以输出两个相同单词的情况。

- samgak

---

我认为使用部分单词是个好主意。我在考虑可以在 trie 中查找它：检查是否有以该部分单词开头的单词。谢谢。 - Ravi