基于海明距离的相似查找索引算法研究

摘要

相似查找问题在信息检索、数据库应用和模式识别等领域都是一个重要的应用。随着网络信息不断增长，数据表现的形式也更加丰富，如何在海量的数据中快速有效地检索出目标信息一直是信息检索领域一项重要研究课题。如何建立高效便捷的索引，在一定时间内返回准确全面的查询结果，是一项具有挑战的热点问题与难点问题。
　　本文主要研究海明空间下的相似查找问题，给定一个数据集D和查询串Q，在尽可能少的时间内返回数据集D中与Q相似的所有字符串，称该问题为相似词典查询问题。相似词典查询问题可以划分为两个阶段来解决:1)Search阶段:利用建好的索引查找出可能相似的目标候选集;2)Check阶段:在这些候选集上运用某种策略进行快速检查，筛选出真正符合查找条件的结果。本文分别在Search阶段和Check阶段进行研究，主要工作内容如下:
　　(1)首先使用Simhash方法完成数据的预处理操作，经过提取、加权、合并和降维等操作将高维数据处理成容易进行相似度比较的Simhash指纹(二进制串)形式。
　　(2)提出基于海明空间的多索引Search算法，主要用于筛选数据集中可能的相似结果候选集。结合基于海明空间的多索引算法的分块建索引的思想，先把二进制指纹化成b个block块，改进的多索引Search算法根据参数k与b之间的关系将多个block块结合在一起建立索引，获得了更好的查询效率。
　　(3)提出两种基于中心点的Check算法，将聚类的思想应用到候选集的筛选策略上，应用于高效筛选Search阶段产生的候选集。基于中心点的贪心Check算法，通过贪心算法选出中心点P，并且每一个中心点P对应一个集群。并将两个基于中心点的Check算法与线性扫描法进行对比实验，得出基于中心点的贪心Check算法具有更好的查询效率。

目录

声明

致谢

摘要

1引言

1．1研究背景与意义

1．2研究现状

1．3研究内容

1．4论文的组织结构

2 相似查找及其相关技术

2．1 相似查找及相似词典查询问题

2．2相似性计算与距离度量

2．2．1相似性计算方法

2．2．2距离度量

2．3基于Simhash的近似文本检测

2．3．1 Simhash介绍

2．3．2基于Simhash的近似文本检测流程

2．3．3本文Simhash方法使用

2．4本章小结

3 基于海明空间的多索引Search算法

3．1 静态海明距离的相似查找问题描述

3．2静态海明足巨离的相似查找算法研究

3．3基于海明空间的多索引算法

3．3．1 多索引算法主要研究内容

3．3．2 Manku的多索引Search算法

3．4基于海明空间的多索引Search算法

3．4．1算法基本思想

3．4．2索引结构设计

3．4．3参数k与b对候选集数目的影响

3．5本章小结

4基于中心点的Check算法

4．1基于中心点的Check算法基本思想和索引结构

4．1．1基于中心点的Check算法基本思想

4．1．2索引结构设计

4．2基于中心点的一般Check算法

4．3基于中心点的贪心Check算法

4．3．1 贪心策略

4．3．2参数及临界条件分析

4．4本章小结

5实验与分析

5．1评价标准

5．2实验条件

5．2．1实验数据集

5．2．2实验环境和工具

5．3实验预处理和实验过程

5．3．1实验的预处理

5．3．2实验过程

5．4 多索引Search算法实验与分析

5．4．1 平均候选集数目对比实验与分析

5．4．2平均查询时间对比实验与分析

5．5基于中心点的Check算法实验与分析

5．5．1 平均查询时间对比实验与分析

5．5．2平均检查的候选集数目对比实验与分析

5．6本章小结

6总结与展望

6．1 工作总结

6．2未来展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集