基于q-gram的字符串相似性查询研究  

Research on the String Similarity Query Based on q-gram

作　　者：米琳[1,2] 

机构地区：[1]四川大学计算机学院,成都610065 [2]四川大学视觉合成图形图像技术国防重点学科实验室,成都610065

出　　处：《现代计算机》2014年第4期12-16,共5页Modern Computer

基　　金：国家自然科学基金(No.61202161);国家863项目(No.2012AA011804)

摘　　要：相似性查询在实际应用中用途广泛,例如相似网页检测、相似图像检索、语言识别、数据清理等。而基于q-gram的字符串相似性查询作为主流方法之一,在查询的效率和灵活性上相对于其他方法都有很大的优势。实现基于q-gram的基本过滤器,并构成过滤器组合模型,用来过滤掉不匹配的字符串,得到候选集。实验结果表明,与传统的依靠编辑距离来比较每一对字符串的值相比,基于q-gram的过滤器能在保证相似性查询结果准确的前提下,在效率方面有显著的提升。In practical applications, similarity query is widely used, such as detection of similar pages, similar image retrieval, language identifica- tion, data cleaning, and so on. As one of the main methods in similarity queries, q-gram method has a great advantage in both efficiency and flexibility. Based on the basic realization of the q-gram filter and the constitution of the filter pattern, and uses it to filter out the mismatching string to obtain the candidate set. The experimental result show that compared with the conventional edit distance method, the q-gram filter has markedly improved in efficiency while guarantee the accuracy of the similarity query results.

关 键 词：相似性查询 q-gram 过滤器 过滤器模型 

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]