http://stackoverflow.com/questions/185697/the-most-efficient-way-to-find-top-k-frequent-words-in-a-big-word-sequence
http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/
http://cs.stackexchange.com/questions/26427/word-frequency-with-ordering-in-on-complexity
思路大致如下：
（1）hash表统计单词出现次数，然后寻找top k出现的，其中top k可以使用n*log(k)的堆思路，或者快排思路，或者是桶排序思路（以前fbt里实现实时的积分排序）；
（2）使用trie来统计单词出现次数，然后便利trie，利用堆排序思路求top k；
（3）使用桶排序，尤其是当你知道最大出现次数时候，类似以前做fbt实现的实时积分排序，然后从大到小取出top k；
（4）用map reduce。
（5）直接排序，然后统计。
如果只是统计top K上面的思路没有任何问题，如果是统计所有的呢？则时间复杂度无疑是n*log(n)，相当于是排序了，和5一样！
lucene里是如何做的呢？
下面三篇文章针对源码分析提到了：
http://wandzk.iteye.com/blog/2187858
http://wandzk.iteye.com/blog/2187975
http://wandzk.iteye.com/blog/2188229
摘录最核心和本质的东西：
例子中有如下docs：
Doc0:
doc.add(new SortedSetDocValuesFacetField("Author", "Bob"));
doc.add(new SortedSetDocValuesFacetField("Publish Year", "2010"));
Doc1:
doc.add(new SortedSetDocValuesFacetField("Author", "Lisa"));
doc.add(new SortedSetDocValuesFacetField("Publish Year", "2010"));
Doc2:
doc.add(new SortedSetDocValuesFacetField("Author", "Lisa"));
doc.add(new SortedSetDocValuesFacetField("Publish Year", "2012"));
Doc3:
doc.add(new SortedSetDocValuesFacetField("Author", "Susan"));
doc.add(new SortedSetDocValuesFacetField("Publish Year", "2012"));
Doc4:
doc.add(new SortedSetDocValuesFacetField("Author", "Frank"));
doc.add(new SortedSetDocValuesFacetField("Publish Year", "1999"));
根据上章分析所有的dim（就是filed name，此处为author和publish year）,label（filed value） 将会拼接在一起，而且生成termid, 其term id 与term对应关系如下: (注lucene存贮字符串是用utf8存储为了便于理解这里还是用字符串显示但是中间分隔符是1f)
0 ----- "Author1fBob" 1 ----- "Publish Year1f2010" 2 ----- "Author1fLisa" 3 ----- "Publish Year1f2012" 4 ----- "Author1fSusan" 5 ----- "Author1fFrank" 6 ----- "Publish Year1f1999" sortedValues 在排序后就是: [0, 5, 2, 4, 6, 1, 3]
同时它会记录每个doc id对应的所有term ids，因为每个filed value都有filed id嘛！
lucene做聚合的本质是：排序！例如要实现聚合：先filed1统计，再field2统计，最后field3统计。那么lucene的处理思路是filed1+2+3所有的字段值都事先排序！（当然，要先设置好filed1,2,3是facet filed，动态设置应该不支持！）
搜索的时候，根据搜索到的所有id，去filed1+2+3字段值排序好的来过滤，例如先过滤所有包含field1的，针对排序做统计！
针对单个filed1聚合的时间复杂度：(字段123所有的数值）*log(字段123所有的数值)；后续的聚合分析，例如再针对filed2聚合，排序来做！
本文转自张昺华-sky博客园博客，原文链接：http://www.cnblogs.com/bonelee/p/6351298.html，如需转载请自行联系原作者
