支持块编辑距离的索引结构
外文标题：Index Structures for Supporting Block Edit Distance
文献类型：期刊
作者：王斌[1]
机构：东北大学信息科学与工程学院,沈阳,110004;东北大学信息科学与工程学院,沈阳,110004;中国人民大学数据工程与知识工程教育部重点实验室,北京,100872
通讯作者：Wang, B.(binwang@mail.neu.edu.cn)
年：2010
期刊名称：计算机研究与发展
卷：47
期：1
页码范围：191-199
增刊：增刊
收录情况：EI(20101512841053)
所属部门：数据工程与知识工程教育部重点实验室
语言：中文
ISSN：1000-1239
链接地址：http://d.g.wanfangdata.com.cn/Periodical_jsjyjyfz201001023.aspx
基金：国家自然科学基金; 新世纪优秀人才支持计划; 中国人民大学数据与知识工程教育部重点实验室开放课题
关键词：近似字符串匹配;块编辑距离;压缩;索引;NP完全问题
摘要：在近似字符串匹配中,传统的编辑距离不能很好地衡量诸如人名、地址等数据的相似关系,而块编辑距离可以很好地衡量两个字符串的相似性.如何有效地支持块编辑距离,进行近似字符串查询处理具有重要的意义.计算两个字符串的块编辑距离是一个NP完全问题,因此希望提供有效的方法可以增强过滤能力,并减少假通过率.设计了一种支持移动编辑距离的新颖的索引结构SHV-Trie,通过研究移动编辑距离的操作特性,使用字母出现的频率作为支持移动编辑距离操作的一个下界,并且提出相应的查询过滤算法,同时,针对索引SHV-Trie的空间开销过大的问题,提出一种优化字母排列的索引结构和一种压缩的索引结构及相关查询过滤算法.真实数据集上的实验结果与分析显示了所提出的索引结构具有良好的过滤能力,并通过减少效率假通过率提高查询的效率.
作者其他论文
新媒体与基层社会的传播动员机制--"江门反核行动"个案研究.王斌.暨南学报（哲学社会科学版）.2014,130-139.
用户,服务与关系的聚合机制--新浪微博运营模式分析.王斌;董芃飞.编辑之友.2015,84-89.
社区童书馆的理念与运行:以"小考拉"为例.王萍;王斌;康萌.出版广角.2014,14-17.
从"内容生产"到"社会关系编织"--以社交电视的发展为例.王斌;诸葛亚寒.新闻与写作.2014,28-31.
激励方式对员工创新能力的影响机制.杨晶;刘舶航;王斌,等.人类工效学.2015,21(1),57-60,65.
