支持块编辑距离的索引结构  

Index Structures for Supporting Block Edit Distance

作　　者：王斌[1] 郭庆[1] 李中博[1] 杨晓春[1,2] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110004 [2]中国人民大学数据工程与知识工程教育部重点实验室,北京100872

出　　处：《计算机研究与发展》2010年第1期191-199,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60828004;60973018);教育部新世纪优秀人才支持计划基金项目(NCET-06-0290);中国人民大学数据与知识工程教育部重点实验室开放课题(2008002)

摘　　要：在近似字符串匹配中,传统的编辑距离不能很好地衡量诸如人名、地址等数据的相似关系,而块编辑距离可以很好地衡量两个字符串的相似性.如何有效地支持块编辑距离,进行近似字符串查询处理具有重要的意义.计算两个字符串的块编辑距离是一个NP完全问题,因此希望提供有效的方法可以增强过滤能力,并减少假通过率.设计了一种支持移动编辑距离的新颖的索引结构SHV-Trie,通过研究移动编辑距离的操作特性,使用字母出现的频率作为支持移动编辑距离操作的一个下界,并且提出相应的查询过滤算法,同时,针对索引SHV-Trie的空间开销过大的问题,提出一种优化字母排列的索引结构和一种压缩的索引结构及相关查询过滤算法.真实数据集上的实验结果与分析显示了所提出的索引结构具有良好的过滤能力,并通过减少效率假通过率提高查询的效率.In approximate string matching,the traditional edit distance cannot evaluate the similarity between strings very well,especially for the name,address datasets,etc. The block edit distance,however,can do the job easily. It is important to efficiently support block edit distance for approximate string query processing. Since computing the block edit distance between two strings is an NP-Complete problem,it is desired to provide solutions to increase filterability and decrease false positives. In this paper,a novel index structure,called SHV-Trie,is proposed. A lower bound of the block edit distances is presented according to the features of the block edit distance with move operations,i.e. the frequencies of each character in a string. A corresponding query filter approach is proposed based on the lower bound on character frequencies. Meanwhile,considering the large space cost problem,an optimized ordered character index structure and a compressed index structure are proposed. The corresponding query filtering approaches are further given based on the optimized and compressed index structures. The experimental results and analysis on real data sets show that the proposed index structures can provide good filtering ability and high query performance by decreasing false positives.

关 键 词：近似字符串匹配 块编辑距离 压缩 索引 NP完全问题 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]