实现词频分析

[问答题]

假设你只有一台内存2G的笔记本，I5的四核CPU以及4T的硬盘，请设计一个程序，实现对1T英文数据进行词频分析，完成以下两个小题：

（1）求所有词的词频，把相应的值存入文件；

（2）找出这些词里卖弄出现频次最高的100个词，并用代码实现

名词解释：1T=1024G，为硬盘空间单位，词频，每个单词出现的次数

查看答案及解析

loveCoding

<div> 方法一： </div> <div> 每个英文单词存储成硬盘上面的一个文件，文件内容为该单词出现的频次。遍历完一遍单词后，通过读取每个文件会得到每个单词的词频。然后根据快速排序对这些词频进行排序，找出频次最高的前100个单词。快速排序的时间复杂度是O(N)。 </div> <div> <br /> </div> <div> 方法二： </div> <div> 可以通过建立字典树，除了树根之外，树中的每个节点包含字母和对应的路径上该单词出现的频次信息，这样查找每个单词的频次直接遍历树即可。找出频次最高的100个单词可以用快速排序或者最大堆。 </div>

发表于 2015-09-14 14:51:12 回复(0)

更多回答

小小

(1).

将1T的数据使用哈希函数映射到10000个文件当中去，这样做可以将所有一样的数据映射到同一个文件当中。依次将10000个文本文件读入内存，使用hashmap对每一个文本中每一个单词进行词频统计，将单词作为key，单词出现次数作为value，每读入一个单词，都查看其在hashmap中是否存在，存在则将value值加1，不存在就将其加入hashmap，并将value值置为1，然后将结果写入一个文件即可。文件的每一行只存储一个单词以及这个单词出现的次数，并且二者之间用空格隔开.

(2).

要求出现次数最高的100个单词。可以建立只有100个元素的小根堆来实现目的。首先取出100个元素建立小根堆，继续从文件中取出元素与小根堆的堆顶元素进行比较，如果比堆顶元素大，就替换掉堆顶元素，并且重建为小根堆，依次做下去，最后堆中保留的100个元素就是top100. 使用hashmap进行词频统计的时候，先用小根堆统计出每个文件中

Top100，然后10000个文件的top100汇总到一起后在使用上述同样的方法得到最终的top100.

发表于 2015-09-14 10:44:12 回复(1)