資源描述：
《基于改進(jìn)編輯距離的字符串相似度求解算法.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第40卷第1期計(jì)算機(jī)工程2014年1月Vb1．40NO．1ComputerEngineeringJanuary2014·人工智能及識(shí)別技術(shù)·文章編號(hào)：1000—-3428(2014)01—__0222—06文獻(xiàn)標(biāo)識(shí)碼：A中圈分類號(hào)：TP311·12基于改進(jìn)編輯距離的字符串相似度求解算法姜華，韓安琪，王美佳，王崢，吳霎玲(東北師范大學(xué)a．計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院；b．智能信息處理吉林省高校重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)春130117)摘要：編輯距離(LD)算法在求解兩個(gè)字符串的相似問(wèn)題時(shí)只考慮了編輯操作次數(shù)，未考慮字符串之間的公共
2、子串對(duì)相似度的影響。為此，提出一種基于改進(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)差分別為O．331和0．150。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在不改變空間復(fù)雜度的情況下，計(jì)算字符串相似度的準(zhǔn)確性更高，且查詢方式更
3、靈活。關(guān)健詞：編輯距離；LD算法；回溯路徑；最長(zhǎng)公共子串；相似度；模糊查詢SolutionAlgorithm0fStringSimilarityB1一asetl'onlTmDroven1L一evenslht?einDi-st·anceJIANGHua，HANAn-qi。，WANGMei-jia，WANGZheng，WUYun-ling’“(a．SchoolofComputerScienceandInformationTechnology；b．UniversityKeyLaboratoryofIntelligent
4、InformationProcessinginJilinProvince，NortheastNormalUniversity,Changchun130117，China)[Abstract]Whencalculatingthesimilarityofstrings，theLevenshteinDistance(LD)algorithmonlyconsiderstheoperatingtimesandignoresthecommonsubstringsoftwostrings．Aimingatthisproblem
5、，animprovedLevenshteindistancealgorithmisproposedtocalculatethesimilarity．ThenewalgorithmimprovestheformulaofsimilarityandtheLevenshteinmatrix．Whencalculatingthedistance，thenewalgorithmcalculatesthelongestcommonsubstringandalltheLDbacktrackingpathsintheorigin
6、almatrixatthesametime．Selectingawordintheexperimentasasourcestring，asetofsimilarwordsofthediferentdegreesofthesourcestringasatargetstring，thenewsimilaritymeasuretbrmulaiscomparedwiththeexistingstringsimilaritycalculationmethod，thenewformulareducesthenumberoft
7、argetstringsintothewinnertablewithsimilaritysamplerangeandstandarddeviationofO．331and0．150．respectively．Experimentalresultsshowthatthenewalgorithmhashigheraccuracyandmoreflexiblesearchingwayinthesamespacecomplexity．[Keywords]LevenshteinDistance(LD)；LDalgorith
8、m；backtrackingpath；thelongestcommonsubstring；similarity；fuzzyqueryDOI：10．3969／j．issn．1000-3428．2014．01．047相結(jié)合，編輯距離在中文背景下增加“替換”原子操作；1概述在應(yīng)用領(lǐng)域方面，編輯距離近似字符串和空間結(jié)合以支持字符串相似問(wèn)題在文本比較、信息處理等領(lǐng)域，具有多種查詢，
