生成字谜的最佳策略是什么。
An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; ex.
- 十一加二是十二加一的字谜
- 小数点是I'm a dot in place的字谜
- 天文学家是月球凝视者的字谜
起初它看起来很简单，只是将字母打乱并生成所有可能的组合。但是，只生成字典中的单词的有效方法是什么。
我遇到了这个页面，在 Ruby 中解决字谜。
但是你的想法是什么？
这些答案中的大多数都非常低效和/或只会给出一个单词的解决方案（没有空格）。我的解决方案可以处理任意数量的单词并且非常有效。
你想要的是一个 trie 数据结构。这是一个完整的Python 实现。您只需要保存在一个名为的文件中的单词列表，words.txt 您可以在此处尝试拼字游戏词典单词列表：
http://www.isc.ro/lists/twl06.zip
MIN_WORD_SIZE = 4 # min size of a word in the output
class Node(object):
def __init__(self, letter='', final=False, depth=0):
self.letter = letter
self.final = final
self.depth = depth
self.children = {}
def add(self, letters):
node = self
for index, letter in enumerate(letters):
if letter not in node.children:
node.children[letter] = Node(letter, index==len(letters)-1, index+1)
node = node.children[letter]
def anagram(self, letters):
tiles = {}
for letter in letters:
tiles[letter] = tiles.get(letter, 0) + 1
min_length = len(letters)
return self._anagram(tiles, [], self, min_length)
def _anagram(self, tiles, path, root, min_length):
if self.final and self.depth >= MIN_WORD_SIZE:
word = ''.join(path)
length = len(word.replace(' ', ''))
if length >= min_length:
yield word
path.append(' ')
for word in root._anagram(tiles, path, root, min_length):
yield word
path.pop()
for letter, node in self.children.iteritems():
count = tiles.get(letter, 0)
if count == 0:
continue
tiles[letter] = count - 1
path.append(letter)
for word in node._anagram(tiles, path, root, min_length):
yield word
path.pop()
tiles[letter] = count
def load_dictionary(path):
result = Node()
for line in open(path, 'r'):
word = line.strip().lower()
result.add(word)
return result
def main():
print 'Loading word list.'
words = load_dictionary('words.txt')
while True:
letters = raw_input('Enter letters: ')
letters = letters.lower()
letters = letters.replace(' ', '')
if not letters:
break
count = 0
for word in words.anagram(letters):
print word
count += 1
print '%d results.' % count
if __name__ == '__main__':
main()
当你运行程序时，单词会被加载到内存中的 trie 中。之后，只需输入您要搜索的字母，它就会打印结果。它只会显示使用所有输入字母的结果，不会更短。
它从输出中过滤掉短词，否则结果的数量是巨大的。随意调整MIN_WORD_SIZE设置。请记住，仅使用“astronomers”作为输入，如果MIN_WORD_SIZE为 1，则会得到 233,549 个结果。也许您可以找到一个更短的单词列表，其中只包含更常见的英语单词。
MIN_WORD_SIZE此外，除非您将“im”添加到字典并设置为 2 ，否则缩略词“I'm”（来自您的一个示例）不会出现在结果中。
获取多个单词的技巧是每当您在搜索中遇到一个完整的单词时就跳回树中的根节点。然后你继续遍历 trie，直到所有字母都用完。
对于字典中的每个单词，按字母顺序对字母进行排序。所以“foobar”变成了“abfoor”。
然后当输入字谜出现时，也对其字母进行排序，然后查找。 它和哈希表查找一样快！
对于多个单词，您可以对已排序的字母进行组合，随时进行排序。仍然比生成所有组合快得多。
（有关更多优化和详细信息，请参阅评论）
请参阅华盛顿大学 CSE 系的此作业。
基本上，您有一个数据结构，它只包含单词中每个字母的计数（数组适用于 ascii，如果您需要 unicode 支持，请升级到地图）。您可以减去其中两个字母组；如果计数为负数，您就知道一个词不能是另一个词的字谜。
预处理：
用每个叶子作为已知单词构建一个 trie，按字母顺序键入。
搜索时：
将输入字符串视为多重集。通过像深度优先搜索一样遍历索引树来找到第一个子词。在每个分支上，您都可以问，我输入的其余部分中是否包含字母 x？如果你有一个好的多集表示，这应该是一个恒定时间查询（基本上）。
一旦你有了第一个子词，你就可以保留剩余的多重集并将其视为一个新的输入来查找该字谜的其余部分（如果存在的话）。
通过记忆增强此过程，以更快地查找常见的余数多重集。
这非常快 - 每次 trie 遍历都保证给出一个实际的子字，并且每次遍历在子字的长度上花费线性时间（根据编码标准，子字通常非常小）。但是，如果您真的想要更快的东西，您可以在预处理中包含所有 n-gram，其中 n-gram 是连续 n 个单词的任何字符串。当然，如果 W = #words，那么您将从索引大小 O(W) 跳转到 O(W^n)。也许 n = 2 是现实的，具体取决于字典的大小。
Michael Morton（Mr. Machine Tool）使用名为 Ars Magna 的工具对程序字谜进行了开创性的工作之一。这是一篇基于他的工作的轻文章。
所以这是 Jason Cohen 建议的 Java 中的工作解决方案，它的性能比使用 trie 的解决方案要好一些。以下是一些要点：
下面是找到一组字谜键的主要递归代码：
// recursive function to find all the anagrams for charInventory characters
// starting with the word at dictionaryIndex in dictionary keyList
private Set<Set<String>> findAnagrams(int dictionaryIndex, char[] charInventory, List<String> keyList) {
// terminating condition if no words are found
if (dictionaryIndex >= keyList.size() || charInventory.length < minWordSize) {
return null;
}
String searchWord = keyList.get(dictionaryIndex);
char[] searchWordChars = searchWord.toCharArray();
// this is where you find the anagrams for whole word
if (AnagramSolverHelper.isEquivalent(searchWordChars, charInventory)) {
Set<Set<String>> anagramsSet = new HashSet<Set<String>>();
Set<String> anagramSet = new HashSet<String>();
anagramSet.add(searchWord);
anagramsSet.add(anagramSet);
return anagramsSet;
}
// this is where you find the anagrams with multiple words
if (AnagramSolverHelper.isSubset(searchWordChars, charInventory)) {
// update charInventory by removing the characters of the search
// word as it is subset of characters for the anagram search word
char[] newCharInventory = AnagramSolverHelper.setDifference(charInventory, searchWordChars);
if (newCharInventory.length >= minWordSize) {
Set<Set<String>> anagramsSet = new HashSet<Set<String>>();
for (int index = dictionaryIndex + 1; index < keyList.size(); index++) {
Set<Set<String>> searchWordAnagramsKeysSet = findAnagrams(index, newCharInventory, keyList);
if (searchWordAnagramsKeysSet != null) {
Set<Set<String>> mergedSets = mergeWordToSets(searchWord, searchWordAnagramsKeysSet);
anagramsSet.addAll(mergedSets);
}
}
return anagramsSet.isEmpty() ? null : anagramsSet;
}
}
// no anagrams found for current word
return null;
}
你可以从这里分叉 repo并使用它。我可能错过了许多优化。但是代码有效并且确实找到了所有的字谜。
这是我的新颖解决方案。
Jon Bentley 的书 Programming Pearls 包含一个关于查找单词字谜的问题。该声明：
给定一本英语单词词典，找出所有的字谜。例如，“pots”、“stop”和“tops”都是彼此的字谜，因为每个都可以通过排列其他字母来形成。
我想了一下，我想到解决方案是获取您正在搜索的单词的签名并将其与字典中的所有单词进行比较。一个单词的所有字谜应该有相同的签名。但是如何实现呢？我的想法是使用算术基本定理：
算术基本定理指出
除了重新排列为一个或多个素数的乘积之外，每个正整数（数字 1 除外）都可以用一种方式表示
所以这个想法是使用前 26 个素数的数组。然后对于单词中的每个字母，我们得到相应的素数 A = 2、B = 3、C = 5、D = 7……然后我们计算输入单词的乘积。接下来，我们对字典中的每个单词执行此操作，如果一个单词与我们的输入单词匹配，那么我们将其添加到结果列表中。
性能或多或少可以接受。对于 479828 个单词的字典，获取所有字谜需要 160 毫秒。这大约是 0.0003 毫秒/字，或 0.3 微秒/字。算法的复杂度似乎是 O(mn) 或 ~O(m)，其中 m 是字典的大小，n 是输入单词的长度。
这是代码：
package com.vvirlan;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Scanner;
public class Words {
private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113 };
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String word = "hello";
System.out.println("Please type a word:");
if (s.hasNext()) {
word = s.next();
}
Words w = new Words();
w.start(word);
}
private void start(String word) {
measureTime();
char[] letters = word.toUpperCase().toCharArray();
long searchProduct = calculateProduct(letters);
System.out.println(searchProduct);
try {
findByProduct(searchProduct);
} catch (Exception e) {
e.printStackTrace();
}
measureTime();
System.out.println(matchingWords);
System.out.println("Total time: " + time);
}
private List<String> matchingWords = new ArrayList<>();
private void findByProduct(long searchProduct) throws IOException {
File f = new File("/usr/share/dict/words");
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr);
String line = null;
while ((line = br.readLine()) != null) {
char[] letters = line.toUpperCase().toCharArray();
long p = calculateProduct(letters);
if (p == -1) {
continue;
}
if (p == searchProduct) {
matchingWords.add(line);
}
}
br.close();
}
private long calculateProduct(char[] letters) {
long result = 1L;
for (char c : letters) {
if (c < 65) {
return -1;
}
int pos = c - 65;
result *= PRIMES[pos];
}
return result;
}
private long time = 0L;
private void measureTime() {
long t = new Date().getTime();
if (time == 0L) {
time = t;
} else {
time = t - time;
}
}
}
几个月前，我使用了以下计算字谜的方法：
为字典中的每个单词计算一个“代码”：创建一个从字母表中的字母到素数的查找表，例如以 ['a', 2] 开始并以 ['z', 101] 结束。作为预处理步骤，通过在查找表中查找它包含的每个字母的质数并将它们相乘来计算字典中每个单词的代码。为以后的查找创建一个代码到单词的多重映射。
如上所述计算输入单词的代码。
计算多图中每个代码的 codeInDictionary % inputCode。如果结果为 0，则您找到了一个字谜，您可以查找相应的单词。这也适用于 2 个或更多单词的字谜。
希望这会有所帮助。
Jon Bentley 的《 Programming Pearls》一书很好地涵盖了这类内容。必读。
我怎么看：
你想建立一个表格，将无序的字母集映射到列表单词，即通过字典，这样你就可以结束了，比如说
lettermap[set(a,e,d,f)] = { "deaf", "fade" }
然后从你的起始词，你找到一组字母：
astronomers => (a,e,m,n,o,o,r,r,s,s,t)
然后遍历该组的所有分区（这可能是最技术性的部分，只是生成所有可能的分区），并查找该组字母的单词。
编辑：嗯，这几乎就是 Jason Cohen 发布的内容。
编辑：此外，对问题的评论提到生成“好”字谜，如示例:)。在你建立所有可能的字谜列表后，通过 WordNet 运行它们并找到语义上接近原始短语的那些:)
如果我将字典作为哈希映射，因为每个单词都是唯一的，并且 Key 是该单词的二进制（或十六进制）表示。然后，如果我有一个单词，我可以很容易地以 O(1) 复杂度找到它的含义。
现在，如果我们必须生成所有有效的字谜，我们需要验证生成的字谜是否在字典中，如果它存在于字典中，则它是有效的，否则我们需要忽略它。
我假设一个单词最多 100 个字符（或更多，但有限制）。
所以我们把它当作一个索引序列的任何单词，比如单词“hello”，都可以表示为“1234”。现在“1234”的字谜是“1243”，“1242”..etc
我们唯一需要做的就是为特定数量的字符存储所有此类索引组合。这是一项一次性任务。然后可以通过从索引中选择字符来从组合中生成单词。因此我们得到了字谜。
要验证字谜是否有效，只需索引字典并验证即可。
唯一需要处理的是重复项。这很容易完成。当我们需要与以前在字典中搜索过的进行比较时。
该解决方案强调性能。
前段时间我写了一篇关于如何快速找到两个单词字谜的博客文章。它的工作速度非常快：在 Ruby 程序中，为一个文本文件超过 300,000 个单词（4 兆字节）的单词查找所有 44 个双单词字谜只需要 0.6 秒。
两个单词 Anagram Finder 算法（在 Ruby 中）
当允许将单词列表预处理为从按字母排序的单词到使用这些字母的单词列表的大型哈希映射时，可以使应用程序更快。从那时起，可以序列化和使用这些预处理数据。
在我的脑海中，最有意义的解决方案是从输入字符串中随机挑选一个字母，并根据以该字母开头的单词过滤字典。然后选择另一个，过滤第二个字母等。此外，过滤掉剩下的文本不能组成的单词。然后当你碰到一个单词的结尾时，插入一个空格并用剩余的字母重新开始。您还可以根据单词类型限制单词（例如，您不会有两个相邻的动词，您不会有两个相邻的文章，等等）。
在此之后，您需要进行某种递归、详尽的搜索。伪代码很粗略：
function FindWords(solutionList, wordsSoFar, sortedQuery)
// base case
if sortedQuery is empty
solutionList.Add(wordsSoFar)
return
// recursive case
// InitialStrings("abc") is {"a","ab","abc"}
foreach initialStr in InitalStrings(sortedQuery)
// Remaining letters after initialStr
sortedQueryRec := sortedQuery.Substring(initialStr.Length)
words := words matching initialStr in the dictionary
// Note that sometimes words list will be empty
foreach word in words
// Append should return a new list, not change wordSoFar
wordsSoFarRec := Append(wordSoFar, word)
FindWords(solutionList, wordSoFarRec, sortedQueryRec)
最后，您需要遍历解决方案列表，并打印每个子列表中的单词，它们之间有空格。对于这些情况，您可能需要打印所有订单（例如“我是 Sam”和“Sam I am”都是解决方案）。
当然，我没有对此进行测试，这是一种蛮力方法。