資源描述：
《基于改進(jìn)編輯距離的字符串相似度求解算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、第40卷第1期計(jì)算機(jī)工程2014年1月Vol.40No.1ComputerEngineeringJanuary2014·人工智能及識(shí)別技術(shù)·文章編號(hào)：1000—3428(2014)01—0222—06文獻(xiàn)標(biāo)識(shí)碼：A中圖分類號(hào)：TP311.12基于改進(jìn)編輯距離的字符串相似度求解算法a,ba,ba,ba,ba,b姜華，韓安琪，王美佳，王崢，吳雲(yún)玲(東北師范大學(xué)a.計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院；b.智能信息處理吉林省高校重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)春130117)摘要：編輯距離(LD)算法在求解兩個(gè)字符串的相似問(wèn)題時(shí)只考慮了編輯操作次數(shù)，未考慮字符串之間的公共子串對(duì)
2、相似度的影響。為此，提出一種基于改進(jìn)編輯距離的字符串相似度求解算法，對(duì)字符串相似度度量公式及Levenshtein矩陣計(jì)算方法進(jìn)行改進(jìn)。在計(jì)算編輯距離時(shí)，以原有矩陣求出兩字符串的最長(zhǎng)公共子串及所有LD回溯路徑。選取一個(gè)單詞作為源串，一組與源串不同程度相似的單詞為目標(biāo)串，將改進(jìn)的相似度度量公式與現(xiàn)有的字符串相似度計(jì)算方法進(jìn)行比較，改進(jìn)公式減少了進(jìn)入勝者表的目標(biāo)串?dāng)?shù)，相似度的樣本極差和標(biāo)準(zhǔn)差分別為0.331和0.150。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在不改變空間復(fù)雜度的情況下，計(jì)算字符串相似度的準(zhǔn)確性更高，且查詢方式更靈活。關(guān)鍵詞：編輯距離；LD算法；回
3、溯路徑；最長(zhǎng)公共子串；相似度；模糊查詢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概述在應(yīng)用領(lǐng)域方面，編輯距離近似字符串和空間結(jié)合以支持字符串相似問(wèn)題在文本比較、信
