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

Research on the String Similarity Query Based on q-gram

相似性查询在实际应用中用途广泛,例如相似网页检测、相似图像检索、语言识别、数据清理等。而基于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.