CAJ | 학술논문

在近似字符串匹配中,传统的编辑距离不能很好地衡量诸如人名、地址等数据的相似关系,而块编辑距离可以很好地衡量两个字符串的相似性.如何有效地支持块编辑距离,进行近似字符串查询处理具有重要的意义.计算两个字符串的块编辑距离是一个NP完全问题,因此希望提供有效的方法可以增强过滤能力,并减少假通过率.设计了一种支持移动编辑距离的新颖的索引结构SHV-Trie,通过研究移动编辑距离的操作特性,使用字母出现的频率作为支持移动编辑距离操作的一个下界,并且提出相应的查询过滤算法,同时,针对索引SHV-Trie的空间开销过大的问题,提出一种优化字母排列的索引结构和一种压缩的索引结构及相关查询过滤算法.真实数据集上的实验结果与分析显示了所提出的索引结构具有良好的过滤能力,并通过减少效率假通过率提高查询的效率.
재근사자부천필배중,전통적편집거리불능흔호지형량제여인명、지지등수거적상사관계,이괴편집거리가이흔호지형량량개자부천적상사성.여하유효지지지괴편집거리,진행근사자부천사순처리구유중요적의의.계산량개자부천적괴편집거리시일개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.