查找文档中最常见的有序词对
这是S. Skiena的“算法.设计手册”中的一个问题，问题陈述是：
给出一个算法来寻找一个有序的词对(例如“纽约”)，在给定的网页中出现频率最高的词对。您会使用哪种数据结构？优化时间和空间。
一个明显的解决方案是在散列映射中插入每个有序对，然后遍历它们，找到最频繁的一个，但是，肯定有更好的方法，有人能给出什么建议吗？
回答 4
Stack Overflow用户
发布于 2019-02-05 08:45:49
在带有n单词的文本中，我们有确切的n - 1顺序词对(当然不是不同的)。一种解决方案是使用最大优先级队列；如果还没有出现，我们只需将每一对插入频率为1的最大PQ中。如果存在，则增加密钥。但是，如果使用Trie，则不需要分别表示所有n - 1对。以以下案文为例：
纽约的一只新小狗对纽约的生活很满意。
由此产生的Trie如下所示：
如果我们在叶节点中存储一对出现的次数，就可以很容易地在线性时间内计算出最大出现次数。因为我们需要看每一个单词，这是我们所能做的最好的，时间明智。
下面使用Scala代码。官方网站有一个Python中的解决方案。
class TrieNode(val parent: Option[TrieNode] = None,
val children: MutableMap[Char, TrieNode] = MutableMap.empty,
var n: Int = 0) {
def add(c: Char): TrieNode = {
val child = children.getOrElseUpdate(c, new TrieNode(parent = Some(this)))
child.n += 1
child
}
def letter(node: TrieNode): Char = {
node.parent
.flatMap(_.children.find(_._2 eq node))
.map(_._1)
.getOrElse('\u0000')
}
override def toString: String = {
Iterator
.iterate((ListBuffer.empty[Char], Option(this))) {
case (buffer, node) =>
node
.filter(_.parent.isDefined)
.map(letter)
.foreach(buffer.prepend(_))
(buffer, node.flatMap(_.parent))
}
.dropWhile(_._2.isDefined)
.take(1)
.map(_._1.mkString)
.next()
}
}
def mostCommonPair(text: String): (String, Int) = {
val root = new TrieNode()
@tailrec
def loop(s: String,
mostCommon: TrieNode,
count: Int,
parent: TrieNode): (String, Int) = {
s.split("\\s+", 2) match {
case Array(head, tail @ _*) if head.nonEmpty =>
val word = head.foldLeft(parent)((tn, c) => tn.add(c))
val (common, n, p) =
if (parent eq root) (mostCommon, count, word.add(' '))
else if (word.n > count) (word, word.n, root)
else (mostCommon, count, root)
loop(tail.headOption.getOrElse(""), common, n, p)
case _ => (mostCommon.toString, count)
}
}
loop(text, new TrieNode(), -1, root)
}受问题这里的启发。
Stack Overflow用户
发布于 2014-09-28 20:17:54
我认为首先要注意的一点是，找到最频繁的有序词对并不比查找最频繁的单词更困难。唯一的区别是，不是由由标点符号或空格分隔的字母a..z+A.Z组成的单词，而是寻找由字母a..z+A..Z+exactly_one_space组成的单词对，类似地，由标点符号或空格隔开。
如果您的网页有n个单词，那么只有n-1字对.因此，散列每个字对，然后迭代哈希表将O(n)在时间和内存。即使n是10^6(即一本普通小说的长度)，这也应该是相当快的。在这种情况下，构造一个有序的单词对列表(而不是哈希表)所节省的内存可能会超过将时间复杂度增加到O(nlogn)的成本。
Stack Overflow用户
发布于 2015-08-01 21:22:43
为什么不将所有的有序对保存在AVL树中，用10个元素数组来跟踪前10个有序对。在AVL中，我们将保留所有顺序对及其出现的计数，前10位将保留在数组中。这样，任何有序对的搜索将是O(log )，遍历将是O(N)。
https://stackoverflow.com/questions/26088818
复制相似问题
腾讯云开发者
