搜索文件中最常出现的模式

Question

您将如何在文本文件中找到n个最常出现的模式.你会使用什么数据结构？这里,模式不是单个单词,而是单词序列.例如,"this is a"可能是文件中经常出现的模式.

后续问题:

• 如果文件非常大(以GB为单位)怎么办？
• 如果文件包含多种语言的文本(英语,日语等)怎么办？

PS:我知道使用哈希表或BST可以相对容易地找到最常出现的单词.只是想不出我们如何找到多字符串.

Answer 1

短语频率的一种方法是使用专门的数据结构,如后缀数组(参见http://en.wikipedia.org/wiki/Suffix_array,如果你喜欢学术论文,http://www.mitpressjournals.org/doi/pdf/ 10.1162/089120101300346787).

如果要有数十亿字节的数据要编制索引,请在大型集群上使用hadoop!:-)