论文部分内容阅读
高频数据项的挖掘问题属于不确定数据流处理1范畴的算法问题。在该领域的算法研究主要用于数据库Iceberg Query、服务器DOS攻击监测、搜索引擎热门搜索统计和社交网络热门话题挖掘等。早在1982年,Misra和Gries就提出了第一个解决该问题的确定性算法MG算法。30年来,用于解决该问题的算法也层出不穷,并且在时间、空间和准确率上都有良好的表现。 随着互联网数据规模的不断增长和需求的日益变化和中文信息处理的特殊性,用于解决该问题的一些经典算法应用到中文信息处理领域时,仍有较大的提高空间。本文提出了适用于中文信息处理的新算法——瓦片表算法,该算法利用了中文数据项之间的关联性,通过已统计的高频项信息推测当前数据流中的数据项是高频项的概率,从而做到高频项过滤的作用。该算法可以与其他已有高频项统计算法相结合使用,通用性很好。 本文首先对已有高频统计算法进行了相关的实验和对比,然后对瓦片表算法的参数选择进行了详尽的实验,并将瓦片表算法用于优化其他算法的结果。实验结果表明,瓦片表算法能够在同等空间耗费下将单纯使用其他算法所得到的结果的准确率提高0.1~0.3,并且能够让在很小的空间耗费下达到同样的结果准确率。 本文还将瓦片表算法用于高阶N-gram统计,未登录词识别,无监督中文分词,热门词汇/热门话题挖掘等领域,设计和实现了有针对性的相关算法和进行了相关的实验对比,实验结果表明,瓦片表算法拥有广泛的应用场景和良好的高频项过滤效果。