7

基本上，Anagrams 就像 string.Eg 的排列一样，都是stackanagrams的（认为上面的词没有意义）。无论如何，您本可以理解我的基本意思。sacktstakcstack

现在，我想要一个anagrams给定数百万个单词的列表，或者只是从字典中说出来。

我的基本问题是Find total number of unique anagrams in a dictionary?

排序和比较不起作用，因为它的时间复杂度非常糟糕。

我想到了使用哈希表，字符串作为键。

但问题是散列函数应该是什么？如果提供一些伪代码会很有帮助。比上述方法更好的其他一些方法也会有所帮助。

谢谢。

4

5 回答 5

24

显而易见的解决方案是将每个字符映射到一个素数并乘以这些素数。所以如果 'a'' -> 2 和 'b' -> 3，那么

  • 'ab' -> 6
  • 'ba' -> 6
  • 'bab' -> 18
  • “阿巴”-> 36
  • “爸爸”-> 36

为了最大限度地减少溢出的机会，可以将最小的素数分配给更频繁的字母（e，t，i，a，n）。注意：第 26 个素数是 101。

更新： 可以在这里找到一个实现

于 2012-06-20T10:07:19.440 回答
2

一个可能的散列函数可以是（假设只有英文单词）每个字母出现次数的排序计数。因此，对于“字谜”，您将生成 [('a', 3), ('g', 1), ('n', 1), ('m', 1), ('r',1)]。

或者，您可以通过从您的单词生成位掩码来获得不精确的分组，其中对于位 0-25，每个位表示该字母的存在或不存在（位 0 表示“a”到位 25 表示“z”）。但是你必须做更多的处理来进一步拆分每个散列组以区分例如“to”和“too”。

这些想法中的任何一个都有帮助吗？考虑到任何特定的实现语言（我可以使用 C++、python 或 Scala）？

编辑：添加了一些示例 Scala 代码和输出：

好的：我目前处于 Scala 模式，所以我已经敲定了一些东西来满足你的要求，但是（咳咳）如果你对 Scala 或函数式编程不太熟悉，可能不太清楚。

从这里使用大量英语单词：http: //scrapmaker.com/data/wordlists/twelve-dicts/2of12.txt

我在它们上运行这个 Scala 代码（在脚本模式下使用 Scala 2.9 大约需要 5 秒，包括编译时间，字典大约有 40,000 个单词。不是最有效的代码，但首先想到的）。

// Hashing function to go from a word to a sorted list of letter counts
def toHash(b:String) = b.groupBy(x=>x).map(v => (v._1, v._2.size) ).toList.sortWith(_._1 < _._1)


// Read all words from file, one word per line
val lines = scala.io.Source.fromFile("2of12.txt").getLines

// Go from list of words to list of (hashed word, word)
val hashed = lines.map( l => (toHash(l), l) ).toList

// Group all the words by hash (hence group all anagrams together)
val grouped = hashed.groupBy( x => x._1 ).map( els => (els._1, els._2.map(_._2)) )

// Sort the resultant anagram sets so the largest come first
val sorted = grouped.toList.sortWith( _._2.size > _._2.size )

for ( set <- sorted.slice(0, 10) )
{
    println( set._2 )
}

这会导出前 10 组字谜（首先是成员最多的组）：

List(caret, cater, crate, react, trace)
List(reins, resin, rinse, risen, siren)
List(luster, result, rustle, sutler, ulster)
List(astir, sitar, stair, stria, tarsi)
List(latrine, ratline, reliant, retinal)
List(caper, crape, pacer, recap)
List(merit, miter, remit, timer)
List(notes, onset, steno, stone)
List(lair, liar, lira, rail)
List(drawer, redraw, reward, warder)

请注意，这使用了第一个建议（字母计数列表），而不是更复杂的位掩码方法。

编辑 2：您可以用对每个单词的字符进行简单排序来替换散列函数（如 JAB 所建议的那样），并使用更清晰/更快的代码获得相同的结果：

def toHash(b:String) = b.toList.sortWith(_<_)
于 2012-06-19T20:17:21.730 回答
1

如果你对每个字符的哈希码值进行异或，然后通过输入长度对结果进行异或，无论单词的顺序如何，你都会得到相同的值，这意味着所有的字谜都会产生相同的哈希值。（按长度异或可防止 'boss' 和 'bo' 返回相同的值，因为 's' 与自身的哈希值始终为 0。）

例子：

int AnagramHash(string input)
{
    int output = 0;

    foreach(char c in input)
        output ^= c.GetHashCode();

    return output ^ input.Length;
}

您仍然需要搜索所有具有相同 AnagramHash 的单词。我会用哈希字段更新字典表（无论您的算法如何）以减少整体计算。

编辑：另外，作为旁注，XOR 是 ALU 执行的最简单的操作，所以如果你最终使用它，你应该能够相当快地生成你的哈希。

于 2012-06-19T20:33:06.700 回答
0

排序和比较不起作用，因为它的时间复杂度非常糟糕。

将时间复杂度换成额外的内存，只需将单词中的字母计数存储为 26- char（或您使用的任何语言的等价物，并假设您使用的是罗马字母表且仅使用字母字符）数组和哈希数组。相对于单词长度，您会遇到 O(n) 时间，但大多数英语单词并没有那么长。

例如stack, sackt, 和stakc都会有一个数组，其中 , , , , == 1 的位置s，t其余a的c都k设置为 0。

根据您的评论，这意味着只要您不对单词本身进行排序，您确实可以对单词的字符进行排序，您可以做一些比 Alex 的回答更简单的事情，只需对单词字符串中的字符进行排序并散列结果。（larsmans 先说，但没有将其发布为答案，所以...）

于 2012-06-19T20:18:59.390 回答
0

使用带有字符串作为键和列表（字符串）作为值的哈希图，其中字符串列表包含键字符串的所有字谜。

该问题类似于“在文件中查找单词的所有字谜”

在此处查看算法和代码http://justprogrammng.blogspot.com/2012/06/determine-anagrams-of-word-in-file.html

于 2012-06-22T15:52:00.883 回答