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