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

Index Structures for Supporting Block Edit Distance

在近似字符串匹配中,传统的编辑距离不能很好地衡量诸如人名、地址等数据的相似关系,而块编辑距离可以很好地衡量两个字符串的相似性.如何有效地支持块编辑距离,进行近似字符串查询处理具有重要的意义.计算两个字符串的块编辑距离是一个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.