支持字符串近似查询的索引关键技术的研究

《支持字符串近似查询的索引关键技术的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文支持字符串近似查询的索引关键技术的研究RESEARCHONINDEXTECHNOLOGYOFSTRINGAPPROXIMATEQUERY佟星哈尔滨工业大学2012年6月国内图书分类号：TP393.02学校代码：10213国际图书分类号：62-5密级：公开工学硕士学位论文支持字符串近似查询的索引关键技术的研究硕士研究生：佟星导师：黄铭钧申请学位：工学硕士学科：计算机技术所在单位：计算机科学与技术学院答辩日期：2012年7月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP393.02U.D.C:62-5

2、DissertationfortheMasterDegreeinEngineeringRESEARCHONINDEXTECHNOLOGYOFSTRINGAPPROXIMATEQUERYCandidate：XingTongSupervisor：Prof.HuangMingjunAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：ComputerTechnologyAffiliation：SchoolofComputerScienceandTechnologyDateofD

3、efence：June,2012Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学硕士学位论文摘要随着社会信息化的不断普及，字符串处理在当今计算机领域的应用也不断拓展，并凸显出更为重要的意义。一方面，字符串表示的含义更加多元化所以处理的方法也更为宽广，另一方面，数据质量问题的出现使得准确的进行字符串查询处理出现一些困难，所以研究人员不得不对字符串进行近似查询处理。在一个字符串集合中，通过一些字符串的相似性函数寻找与查询字符串相似的字符串集合被称为字符

4、串的近似查找。字符串的近似查询处理面临着度量函数的定义，索引结构的建立，大数据量的处理，考虑字符串权值等诸多挑战，所以字符串近似查询处理成为当下研究领域的重要研究课题。本文分析了已有的字符串近似查询的工作（包括带权值的和不带权值的字符串近似查询），发现当前的字符串近似查询索引结构都普遍存在着一些问题。这些问题主要有索引结构不能够很好地更新，查询效率低，支持查询种类有限，支持的查询字符串长度有限，只适用于固定阈值等等。针对这些问题，本文提出了新的索引结构Fgramtree和Weitree，并基于这两种索引结构给出了新的查询算法。

5、其中，Fgramtree能够将相似的字符串定位到同样的结点中，这样就能显著加快查找的速度。Weitree主要用于带权值的字符串近似查询，实现了字符串与数值类型数据的混合查找。通过在真实数据集上进行的实验，验证了我们提出的索引结构及查询算法的有效性。关键词：索引；数据质量；字符串近似查询；权值I哈尔滨工业大学硕士学位论文AbstractWiththegrowingpopularityoftheinformationsociety,Stringhandlingplaysamoreimportantroleininformation

6、systemscontainingmorebroadsignificance.Ononehand,manynewproblemscanbeconvertedintoastringmanipulationproblemwithnovelapproach.Ontheotherhand,thedataqualityproblemmakestheexactstringqueryprocessingdifficult.Asaresult,manyresearchershadpaidmoreattentiontoapproximatest

7、ringqueryprocessing.Anapproximatesearchqueryonacollectionofstringsfindsthosestringsinthecollectionthataresimilartoagivenquerystring,wheresimilarityisdefinedusingagivensimilarityfunction.Approximatestringmatchingbringssometechnicalchallengesincludingthedefinitionofth

8、emetricfunctionforthestringapproximatequeryprocessing,theestablishmentoftheindexstructure,alargeamountofdataprocessing,theintroductionofth