找到最频繁有序词对在一个文档

这是S. Skiena的问题的书，这个问题的说法是：找到最频繁有序词对在一个文档

提供的算法发现的有序字对（例如“纽约”）在给定的网页中以最大的频率出现。你会使用哪种数据结构？优化时间和空间。

一个显而易见的解决方案是将每一个有序对一个哈希地图，然后再遍历所有的人，找到最频繁的一个，但是，肯定应该有更好的方式，任何人都可以提出什么吗？

2014-09-28 Susan

为什么要肯定有更好的方法？ – 2014-09-28 19:35:29

'纽约新'和'纽约'一样吗？怎么样'新的。 “纽约”与“新纽约”一样，与“纽约”相同？ – dawg 2014-09-28 19:37:08

@OliverCharlesworth，因为它使用O（n^2）时间和内存，如果n是文档中的单词数量，这太多了。另外，正如我的讲师所说，你应该问自己：“我们可以做得更好吗？” :) – Susan 2014-09-28 19:46:08

我认为首先要注意的是找到最频繁的有序词对没有比找到最频繁的词困难（或更少）。唯一的区别是，不是由标点或空格分隔的由字母a..z + AZ组成的单词，而是寻找由字母a..z + A..Z + exactly_one_space组成的单词对，类似地由标点符号或空格分隔。

如果您的网页有n个词，那么只有n-1个词对。因此，散列每个字对，然后遍历散列表将O（n）在时间和内存中。即使n是〜10^6（即平均小说的长度），这也应该很快。除非n相当小，否则我无法想象任何效率更高，在这种情况下，构造有序的字对列表（而不是哈希表）所产生的内存节省可能会超过增加O（nlogn）时间复杂度的成本

来源

2014-09-28 20:17:54 Penguino

此外，您可以使用它们出现的文本中的位置，而不是将字符串用作散列键。 – 2017-01-05 23:23:55

为什么不保留AVL树中的所有有序对与10个元素数组来跟踪前10个有序对。在AVL中，我们将保留所有的订单对和它们的出现次数，前10名将保留在数组中。通过这种方式搜索任何有序对将是O（log N）并且遍历将是O（N）。

来源

2015-08-01 21:22:43

我认为我们不可能比O（n）在时间上做得更好，因为人们不得不至少看到每个元素一次。所以时间复杂度不能进一步优化。

但是我们可以使用trie来优化使用的空间。在一个页面中，经常有重复的单词，所以这可能会导致空间使用量的显着减少。特里结构中的叶节点冷存储有序对的频率，并使用两个指针在文本中迭代，其中一个指向当前词，另一个指向前一个词。

来源

2017-01-05 22:13:13

找到最频繁有序词对在一个文档

回答

相关问题