关于不可知的语言：生成字谜的算法

Algorithm to generate anagrams

生成字谜的最佳策略是什么。

1
2
3
4
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.

Eleven plus two is anagram of Twelve plus one

A decimal point is anagram of I'm a dot in place

Astronomers is anagram of Moon starers

起初看起来很简单，只是弄乱字母并生成所有可能的组合。但是什么是仅生成字典中单词的有效方法。

我碰到了这个页面，用Ruby解决字谜。

但是您有什么想法？

这些答案中的大多数效率极低，并且/或者只能给出一个单词的解决方案(无空格)。我的解决方案可以处理任意数量的单词，并且非常有效。

您想要的是trie数据结构。这是完整的Python实现。您只需要将单词列表保存在名为words.txt的文件中，即可在此处尝试拼字游戏词典单词列表：

http://www.isc.ro/lists/twl06.zip

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

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设置。请记住，如果MIN_WORD_SIZE为1，仅使用" astronomers "作为输入将得到233,549结果。也许您会找到一个较短的单词列表，其中仅包含更常见的英语单词。

此外，除非您在字典中添加" im "并将MIN_WORD_SIZE设置为2，否则收缩" I \\'m "(来自您的示例之一)不会显示在结果中。

获取多个单词的技巧是，每当您在搜索中遇到完整的单词时，都将跳回到trie中的根节点。然后，您将继续遍历该Trie，直到所有字母都被使用。

对于词典中的每个单词，请按字母顺序对字母进行排序。因此" foobar "变为" abfoor。"

然后，当输入字谜出现时，也对其字母进行排序，然后查找。它与哈希表查找一样快！

对于多个单词，您可以对已排序字母进行组合，然后再进行排序。仍然比生成所有组合快得多。

(有关更多优化和详细信息，请参见评论)

请参阅华盛顿大学CSE系的这项作业。

基本上，您有一个数据结构，该数据结构只包含一个单词中每个字母的计数(数组适用于ascii，如果需要unicode支持，则升级到地图)。您可以减去其中两个字母集。如果计数为负，则您知道一个词不能成为另一个词的字谜。

预处理：

以每个叶子作为已知单词构建一个trie，按字母顺序键入。

在搜索时：

将输入字符串视为多集。通过像深度优先搜索中那样遍历索引来找到第一个子词。在每个分支机构，您都可以问，我输入的其余部分中的字母x是吗？如果您具有良好的多集表示形式，则这应该是一个固定时间的查询(基本上)。

一旦有了第一个子词，就可以保留其余的多集并将其作为新输入来查找该字谜的其余部分(如果存在)。

通过记忆扩展此过程，以更快地查找常见余数多集。

这非常快-每次遍历都保证给出一个实际的子字，并且每次遍历都花费线性时间(在子字的长度上，按照编码标准，子字通常很小)。但是，如果您真的想要更快的速度，则可以在预处理过程中包含所有n-gram，其中n-gram是连续n个单词的任何字符串。当然，如果W = #words，那么您将从索引大小O(W)跳到O(W ^ n)。也许n = 2是现实的，具体取决于字典的大小。

这是我的新颖解决方案。

乔恩·本特利(Jon Bentley)的《编程珍珠》(Programming Pearls)中有一个有关查找字谜的问题。
声明：

Given a dictionary of english words, find all sets of anagrams. For
instance,"pots","stop" and"tops" are all anagrams of one another
because each can be formed by permuting the letters of the others.

我想了一下，得出的解决方案是获取您要搜索的单词的签名，并将其与词典中的所有单词进行比较。一个单词的所有字谜都应具有相同的签名。但是如何实现呢？我的想法是使用算术基本定理：

算术的基本定理指出，

every positive integer (except the number 1) can be represented in
exactly one way apart from rearrangement as a product of one or more
primes

因此，想法是使用前26个素数组成的数组。然后，对于单词中的每个字母，我们得到相应的素数A = 2，B = 3，C = 5，D = 7…然后，我们计算输入单词的乘积。接下来，我们对字典中的每个单词进行此操作，如果单词与输入单词匹配，则将其添加到结果列表中。

性能差不多可以接受。对于479828个单词的字典，要花费所有160毫秒才能获得所有字谜。这大约是0.0003 ms /字，或0.3微秒/字。算法的复杂度似乎是O(mn)或?O(m)，其中m是字典的大小，n是输入单词的长度。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

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;
}
}
}

因此，这是Jason Cohen建议的Java工作解决方案，它的性能要比使用trie的解决方案好一些。以下是一些要点：

仅使用单词是给定单词集的子集加载词典
字典将是已排序单词的哈希作为键，而实际单词的集合则作为值(如Jason建议的那样)
遍历字典键中的每个单词，并进行递归前向查找，以查看是否为该键找到了任何有效的七字谜
只做正向查找，因为应该已经找到所有已经遍历的单词的字谜
合并与按键相关的所有单词，例如如果\\'enlist \\'是要查找其字谜的单词，并且要合并的一组键之一是[ins]和[elt]，而[ins]的实际单词是[sin]和[ins ]，而键[elt]为[let]，则合并词的最终集合将为[sin，let]和[ins，let]，它们将成为我们最终字谜列表的一部分
另请注意，此逻辑将仅列出唯一的一组单词，即"十一加二"和"二加十一"将是相同的，并且其中只有一个会在输出中列出

下面是主要的递归代码，用于查找字谜键集：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// 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;
}

您可以从此处分叉存储库并进行操作。我可能会错过许多优化。但是代码可以工作并且确实找到了所有的字谜。

关于编程七巧板的开创性著作之一是迈克尔·莫顿(Mr. Machine Tool)，他使用的是称为Ars Magna的工具。这是一篇基于他的工作的浅文。

乔恩·本特利(Jon Bentley)的《编程珍珠》(Programming Pearls)一书很好地涵盖了这类内容。必读。

两个月前，我使用以下方式计算字谜的方式：

为字典中的每个单词计算一个" code "：创建一个查找表，从字母中的字母到质数，例如以[\\'a \\'，2]开头，以[\\'z \\'，101]结尾。在预处理步骤中，通过在查找表中查找组成的每个字母的质数并将其相乘，来计算字典中每个单词的代码。为了以后的查找，请创建一个多代码映射到单词。
如上所述计算输入单词的代码。
为multimap中的每个代码计算codeInDictionary％inputCode。如果结果为0，则说明您找到了一个字谜，可以查找适当的单词。这也适用于2字或更多字的字谜。

希望是有帮助的。

如果我将字典作为哈希映射，因为每个单词都是唯一的，并且键是该单词的二进制(或十六进制)表示形式。然后，如果我有一个单词，我可以轻松地以O(1)复杂度找到它的含义。

现在，如果我们必须生成所有有效的字谜，我们需要验证所生成的字谜是否在字典中，如果它存在于字典中，则它是一个有效的字母，我们需要忽略它。

我假设一个单词最多可以包含100个字符(或更多，但有限制)。

因此，我们将其视为索引序列的任何单词(例如单词" hello")都可以表示为
" 1234 "。
现在" 1234 "的字谜是" 1243 "，" 1242 " ..etc

我们唯一需要做的就是存储所有特定数量字符的索引组合。这是一项一次性的任务。
然后可以通过从索引中选择字符来从组合中生成单词。因此，我们得到了字谜。

要验证字谜是否有效，只需在字典中建立索引并进行验证。

唯一需要处理的是重复项，这很容易做到。作为一种情况，我们需要与在词典中搜索到的先前版本进行比较。

该解决方案强调性能。

前一段时间，我写了一篇博客文章，介绍如何快速找到两个词字谜。它的工作速度非常快：在Ruby程序中，为一个文本文件超过300,000个单词(4兆字节)的单词查找所有44个两个单词的字谜只需0.6秒。

两个词的字谜查找器算法(在Ruby中)

当允许将单词表预处理为大的散列映射(从按字母排序的单词到使用这些字母的单词列表)时，可以使应用程序更快。此预处理的数据可以随后进行序列化和使用。

我怎么看：

您想建立一个表格，将无序的字母集映射到列出的单词，即浏览字典，这样您就可以说出

1	lettermap[set(a,e,d,f)] = {"deaf","fade" }

然后从您的起始单词中找到一组字母：

1	astronomers => (a,e,m,n,o,o,r,r,s,s,t)

然后遍历该组的所有分区(这可能是最技术性的部分，只是生成所有可能的分区)，并查找该组字母的单词。

编辑：嗯，这几乎就是杰森·科恩(Jason Cohen)发表的内容。

edit：此外，对问题的评论提到生成" good "字谜，如示例：)。在建立了所有可能的七字组的列表之后，通过WordNet运行它们，找到在语义上与原始短语接近的那些：)

正如Jason所建议的那样，准备一个字典制作哈希表，并按字母顺序对关键字进行单词排序，然后对单词本身进行赋值(每个关键字可能有多个值)。

删除空格并在查询之前对查询进行排序。

此后，您需要进行某种递归，详尽的搜索。伪代码非常粗略：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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)

最后，您需要遍历solutionList，并打印每个子列表中的单词，并在它们之间留有空格。对于这些情况，您可能需要打印所有订单(例如" I am Sam "和" Sam I am "都是解决方案)。

当然，我没有对此进行测试，这是蛮力的方法。

在我的头上，最有意义的解决方案是从输入字符串中随机选择一个字母，然后根据以此开头的单词过滤字典。然后选择另一个，过滤第二个字母，依此类推。此外，过滤掉无法用其余文本构成的单词。然后，当您敲一个单词的末尾时，插入一个空格，然后从其余字母开始。您可能还会根据单词类型来限制单词(例如，彼此之间不会有两个动词，彼此之间不会有两个词，等等)。