生成字形的algorithm
什么是生成字形的最佳策略？
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.
- 十一二 加一是十二加一
- 小数点是我是一个点的地方
- 天文学家是月亮的星号
起初看起来非常简单，只是混淆了字母并生成了所有可能的组合。 但是，在字典中只生成单词的有效方法是什么呢？
我遇到了这个页面， 在Ruby中解决anagrams 。
但是你有什么想法？
这些答案中的大部分是非常低效的和/或将只给出一个字的解决scheme（没有空格）。 我的解决scheme将处理任何数量的单词，是非常有效的。
你想要的是一个trie数据结构。 这是一个完整的 Python实现。 您只需要一个名为words.txt的文件中保存的单词列表您可以在这里尝试Scrabble词典单词列表：
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中。 之后，只需input要search的字母，就会打印结果。 它只会显示使用所有input字母的结果，不会更短。
它从输出中过滤出短的单词，否则结果的数量是巨大的。 随意调整MIN_WORD_SIZE设置。 请记住，只要使用“天文学家”作为input，如果MIN_WORD_SIZE为1，则可得到233,549个结果。也许你可以find一个较短的单词列表，其中只包含更多常见的英语单词。
此外，除非您在字典中添加“im”并将MIN_WORD_SIZE设置为2，否则收缩“我”（来自您的一个示例）不会显示在结果中。
获取多个单词的技巧是在search中遇到完整的单词时跳回到trie中的根节点。 然后你继续遍历所有的字母被使用。
对于字典中的每个单词，按字母顺序排列字母。 所以“foobar”变成“abfoor”。
然后，当input的字谜进来时，也要对其字母进行分类，然后查看它。 它和散列表查询一样快！
对于多个单词，您可以对已sorting的字母进行组合，随意sorting。 比生成所有组合还要快得多。
（请参阅评论以获得更多优化和细节）
请参阅华盛顿大学CSE部门的这项任务 。
基本上，你有一个数据结构，只是在一个单词中的每个字母的计数（一个数组适用于ascii，如果你想unicode支持升级到地图）。 你可以减去这两个字母集; 如果一个计数是负的，你就知道一个单词不能成为另一个单词。
前处理：
用每个叶子作为一个已知单词build立一个树状结构，按字母顺序排列。
在search时间：
将inputstring视为多重集。 通过在深度优先search中遍历索引triefind第一个子词。 在每个分支你可以问，在我的input的其余部分是字母x？ 如果你有一个很好的multiset表示，这应该是一个恒定的时间查询（基本上）。
一旦你有第一个子字，你可以保留多余的集合，并把它作为一个新的input，以find该字谜的其余部分（如果有的话）。
使用记忆增强此过程，以加快查找常用剩余多重集。
这是非常快的 – 每个树遍历保证给一个实际的子字，并且每个遍历在子字的长度中占用线性时间（通过编码标准，子字通常相当小）。 然而，如果你真的想要更快的东西，你可以在你的预处理过程中包含所有的n元组，其中n-gram是连续n个字的任何string。 当然，如果W =＃个字，那么你将从索引大小O（W）跳到O（W ^ n）。 也许n = 2是现实的，这取决于你的字典的大小。
关于程序化字典的开创性着作之一是Michael Morton（机床工具），使用了一种名为Ars Magna的工具。 这是一篇以他的作品为基础的文章 。
Jon Bentley的“ 编程珍珠 ”一书很好地涵盖了这种东西。 必读。
所以这里是 Java的工作解决scheme，Jason Cohenbuild议，它比使用trie的更好。 以下是一些要点：
- 只能使用给定单词集的子集来加载字典
- 字典将被sorting的单词的哈希值作为键和实际单词的集合作为值（如贾森build议）
- 迭代字典键中的每个单词，并进行recursion正向查找，以查看是否find该键的任何有效字母
- 只有前向查找，因为所有已经遍历的单词的字符都应该已经find了
- 合并与键相关的所有单词，例如，如果“enlist”是要find字符的单词，并且要合并的一组键是[ins]和[elt]，并且键[ins ]是[sin]和[ins]，对于key [elt]是[let]，那么最后一组合并词将是[sin，let]和[ins，let]，这将成为我们最终的anagrams列表的一部分
- 另外要注意的是，这个逻辑将只列出唯一的一组词，即“十一加二”和“二加十一”将是相同的，只有其中一个将被列在输出
下面是find一组关键字的主要recursion代码：
// 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; }
你可以从这里分叉回购，并玩它。 有很多优化，我可能错过了。 但代码的作品，并确实find所有的字谜。
这是我的新解决scheme。
Jon Bentley的“编程珍珠”（Programming Pearls）一书包含了一个关于寻找单词的问题。 该声明：
给定一个英文单词字典，find所有的字符集。 例如，“jar”，“停”和“上”是互相之间的所有变体，因为每一个都可以通过排列其他字母来形成。
我想了一下，find解决办法是获得你正在search的单词的签名，并将其与词典中的所有单词进行比较。 一个单词的所有字母都应该具有相同的签名。 但是如何实现这个？ 我的想法是使用算术的基本定理：
算术的基本定理指出
除了重排之外，每个正整数（数字1除外）都可以用一个或多个素数
所以这个想法是使用前26个素数的数组。 然后，对于单词中的每个字母，我们得到相应的素数A = 2，B = 3，C = 5，D = 7 …，然后计算我们的input词的乘积。 接下来，我们为字典中的每个单词执行此操作，如果一个单词与我们的input单词匹配，则将其添加到结果列表中。
performance或多或less是可以接受的。 对于479828字的词典，需要160毫秒才能得到所有字母。 这大概是0.0003毫秒/字，或0.3微秒/字。 algorithm的复杂性似乎是O（mn）或〜O（m），其中m是字典的大小，n是input字的长度。
代码如下：
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; } } }
我如何看待它：
你会想要build立一个表格，将无序的字母集合映射到列表中，即通过字典，所以你可以说，
lettermap[set(a,e,d,f)] = { "deaf", "fade" }
然后从你的开始词，你会发现一组字母：
astronomers => (a,e,m,n,o,o,r,r,s,s,t)
然后遍历该集合的所有分区（这可能是最技术的部分，只是生成所有可能的分区），并查找该字母集的单词。
编辑：嗯，这几乎是什么杰森科恩张贴。
编辑：此外，关于问题的意见提到生成“好”的字谜，就像例子:)。 在build立所有可能的字典的列表之后，通过WordNet运行它们，并find在语义上接近原始语句的字符:)
几个月前，我已经使用了下面的计算方法：
-
计算字典中每个单词的“代码”：从字母表中的字母到素数创build一个查找表，例如以['a'，2]开始并以['z'，101]结尾。 作为预处理步骤，通过查找查找表中每个字母的素数来计算字典中每个单词的代码，并将它们相乘。 为了以后的查找，创build一个代码到单词的多图。
-
如上所述计算input单词的代码。
-
计算multimap中每个代码的codeInDictionary％inputCode。 如果结果是0，你已经find了一个字谜，你可以查找适当的单词。 这也适用于2个或更多字的字谜。
希望有帮助。
前一阵子，我写了一篇关于如何快速find两个字的字符的博客文章。 它的工作速度非常快：在一个Ruby程序中，为一个文本文件超过300,000字（4兆字节）的单词find所有44个双字的字典只需要0.6秒。
两个字Anagram Finderalgorithm（在Ruby中）
当允许应用程序更快速地对应用程序进行预处理时，应用程序可能会更快，从而使用这些字母将信息按字母顺序排列成单词列表。 这个预处理的数据可以被序列化并且从那以后被使用。
如果我将字典作为散列表，因为每个单词都是唯一的，而密钥是该单词的二进制（或hex）表示。 然后，如果我有一个词，我可以很容易地find与O（1）复杂性的意义。
现在，如果我们必须生成所有有效的字母，我们需要validation生成的字母是否在字典中，如果它存在于字典中，那么它是一个有效的字母，否则我们需要忽略它。
我会假设可以有最多100个字符（或更多，但有一个限制）的单词。
所以我们把它看作是一个单词“hello”的索引序列，可以表示为“1234”。 现在“1234”的字形是“1243”，“1242”等
我们唯一需要做的就是存储所有这些索引组合的特定数量的字符。 这是一次性任务。 然后，通过从索引中挑选字符，可以从这些组合中产生单词。因此，我们得到字符。
为了validation字典是否有效，只需在字典中进行索引并validation即可。
唯一需要处理的是重复项，这可以很容易地完成。 作为一个时候，我们需要比较以前在字典中search过的。
解决scheme强调性能。
关于我的头顶，最有意义的解决scheme是从inputstring中随机选取一个字母，并根据以此开头的单词过滤字典。 然后select另一个，过滤第二个字母等。另外，过滤掉不能用剩余文本进行的单词。 然后，当你点击一个单词的末尾时，插入一个空格，并用剩余的字母重新开始。 你也可以根据单词types来限制单词（例如，你不会有两个动词相邻，你不会有两个相邻的文章等）。
- 正如Jason所build议的那样，准备一个字典制作哈希表，其中字母按字母顺序sorting，而且字符本身（每个键可以有多个值）。
- 删除空格并在查询之前sorting查询。
之后，你需要做一些recursion的，详尽的search。 伪代码非常粗略：
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，并在每个子列表中打印包含空格的单词。 您可能需要打印这些案件的所有订单（例如“我是山姆”和“我是山姆”都是解决scheme）。
当然，我没有testing这个，这是一个powershell的方法。
