資源描述：
《基于改進編輯距離的字符串相似度求解算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。
1、第40卷第1期計算機工程2014年1月Vol.40No.1ComputerEngineeringJanuary2014·人工智能及識別技術·文章編號：1000—3428(2014)01—0222—06文獻標識碼：A中圖分類號：TP311.12基于改進編輯距離的字符串相似度求解算法a,ba,ba,ba,ba,b姜華，韓安琪，王美佳，王崢，吳雲(yún)玲(東北師范大學a.計算機科學與信息技術學院；b.智能信息處理吉林省高校重點實驗室，長春130117)摘要：編輯距離(LD)算法在求解兩個字符串的相似問題時只考慮了編輯操作次數(shù)，未考慮字符串之間的公共子串對
2、相似度的影響。為此，提出一種基于改進編輯距離的字符串相似度求解算法，對字符串相似度度量公式及Levenshtein矩陣計算方法進行改進。在計算編輯距離時，以原有矩陣求出兩字符串的最長公共子串及所有LD回溯路徑。選取一個單詞作為源串，一組與源串不同程度相似的單詞為目標串，將改進的相似度度量公式與現(xiàn)有的字符串相似度計算方法進行比較，改進公式減少了進入勝者表的目標串數(shù)，相似度的樣本極差和標準差分別為0.331和0.150。實驗結(jié)果表明，改進算法在不改變空間復雜度的情況下，計算字符串相似度的準確性更高，且查詢方式更靈活。關鍵詞：編輯距離；LD算法；回
3、溯路徑；最長公共子串；相似度；模糊查詢SolutionAlgorithmofStringSimilarityBasedonImprovedLevenshteinDistancea,ba,ba,ba,ba,bJIANGHua,HANAn-qi,WANGMei-jia,WANGZheng,WUYun-ling(a.SchoolofComputerScienceandInformationTechnology;b.UniversityKeyLaboratoryofIntelligentInformationProcessinginJilinProv
4、ince,NortheastNormalUniversity,Changchun130117,China)【Abstract】Whencalculatingthesimilarityofstrings,theLevenshteinDistance(LD)algorithmonlyconsiderstheoperatingtimesandignoresthecommonsubstringsoftwostrings.Aimingatthisproblem,animprovedLevenshteindistancealgorithmispropos
5、edtocalculatethesimilarity.ThenewalgorithmimprovestheformulaofsimilarityandtheLevenshteinmatrix.Whencalculatingthedistance,thenewalgorithmcalculatesthelongestcommonsubstringandalltheLDbacktrackingpathsintheoriginalmatrixatthesametime.Selectingawordintheexperimentasasourcest
6、ring,asetofsimilarwordsofthedifferentdegreesofthesourcestringasatargetstring,thenewsimilaritymeasureformulaiscomparedwiththeexistingstringsimilaritycalculationmethod,thenewformulareducesthenumberoftargetstringsintothewinnertablewithsimilaritysamplerangeandstandarddeviationo
7、f0.331and0.150,respectively.Experimentalresultsshowthatthenewalgorithmhashigheraccuracyandmoreflexiblesearchingwayinthesamespacecomplexity.【Keywords】LevenshteinDistance(LD);LDalgorithm;backtrackingpath;thelongestcommonsubstring;similarity;fuzzyqueryDOI:10.3969/j.issn.1000-3
8、428.2014.01.047相結(jié)合，編輯距離在中文背景下增加“替換”原子操作；1概述在應用領域方面，編輯距離近似字符串和空間結(jié)合以支持字符串相似問題在文本比較、信
