lucene中facet实现统计分析的思路——本质上和word count计数无异,像splunk这种层层聚合(先filed1统计,再field2统计,最后field3统计)lucene是排序实现-阿里云开发者社区

开发者社区> 桃子红了呐> 正文

lucene中facet实现统计分析的思路——本质上和word count计数无异,像splunk这种层层聚合(先filed1统计,再field2统计,最后field3统计)lucene是排序实现

简介:
+关注继续查看

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,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
统计分析SQL Server Profiler 跟踪的SQL
--跟踪文件读入到表中分析 SELECT * INTO ZGSJY FROM fn_trace_gettable('E:\wxxcdbprofiler.trc', default); --某时间内,最耗时SQL select TOP 100 SUBSTRING(Textdata,1,660) as '名称', count(*) as '数量', sum(duration/1000) as
698 0
基于Numpy的统计分析实战
标题中的英文首字母大写比较规范,但在python实际使用中均为小写。 2018年7月27日笔记 学习内容: 1.从文件中读取数据 2.将数据写入文件 3.利用数学和统计分析函数完成实际统计分析应用 4.掌握数组相关的常用函数 1.文本文件读写 1.1使用numpy.savetxt方法写入文本文件 numpy.savetxt方法需要2个参数:第1个参数是文件名,数据类型为字符串str; 第2个参数是被写入文件的nda数据,数据类型为ndarray对象。
1023 0
带你读《物联网渗透测试》之三:固件分析与漏洞利用
本书介绍物联网渗透测试的原理和实用技术。主要内容包括IOT威胁建模、固件分析及漏洞利用、嵌入式web应用漏洞、IOT移动应用漏洞、IOT设备攻击、无线电入侵、固件安全和移动安全最佳实践、硬件保护以及IOT高级漏洞的利用与安全自动化。
2837 0
精益化运营:10款移动统计分析工具推荐
移动应用和游戏的运营离不开大量用户数据的支持。目前国内市场的移动应用分析领域的公司则有友盟、Talking Data、App Annie、百度等,都是开发者比较熟悉的平台。相对来说,国外有哪些靠谱的移动应用分析工具呢?我们从中整理了10款,希望对开发者有所帮助。
1567 0
【POI word】使用POI实现对Word的读取以及生成
项目结构如下:   那第一部分:先是读取Word文档 1 package com.it.WordTest; 2 3 import java.io.FileInputStream; 4 import java.
2014 0
PostgreSQL · 特性分析 · 统计信息计算方法
一条SQL在PG中的执行过程是: ----> SQL输入 ----> 解析SQL,获取解析后的语法树 ----> 分析、重写语法树,获取查询树 ----> 根据重写、分析后的查询树计算各路径代价,从而选择一条成本最优的执行树 ----> 根据执行树进行执行 ----> 获取结果并返回
1581 0
《数据挖掘:实用案例分析》——1.3 信息类BI应用与知识类BI应用
本节书摘来自华章计算机《数据挖掘:实用案例分析》一书中的第1章,第1.3节,作者 张良均 陈俊德 刘名军 陈荣,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1103 0
4269
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载