• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于編輯距離和相似度改進(jìn)的漢字字符串匹配

    2016-10-17 05:43:24清,葉
    電子科技 2016年9期
    關(guān)鍵詞:字符串字符漢字

    邵 清,葉 琨

    (上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

    ?

    基于編輯距離和相似度改進(jìn)的漢字字符串匹配

    邵清,葉琨

    (上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

    為解決中文字符串匹配精度較低的問(wèn)題,提出了一種基于編輯距離和相似度改進(jìn)的漢字字符串近似匹配算法,針對(duì)漢字字符串特點(diǎn),使用漢字拼音和五筆編碼計(jì)算;通過(guò)改進(jìn)動(dòng)態(tài)規(guī)劃算法,能夠有效提高編輯距離的計(jì)算準(zhǔn)確度以及執(zhí)行效率;再引入考慮交換問(wèn)題的歸一化算法,以語(yǔ)義編輯距離與長(zhǎng)句長(zhǎng)度的比值作為歸一化結(jié)果,以此來(lái)提高近似匹配算法的準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明,改進(jìn)后算法計(jì)算的相似度質(zhì)量要優(yōu)于改進(jìn)前的算法結(jié)果,且對(duì)提高算法效率和查全率、查準(zhǔn)率和時(shí)間性能等指標(biāo)均有明顯改善,證明該算法的可行性和有效性。

    編輯距離;相似度;歸一化;中文字符串;近似匹配

    隨著信息技術(shù)的廣泛應(yīng)用,作為基礎(chǔ)性研究的字符串匹配面對(duì)越來(lái)越多的挑戰(zhàn)[1]。從20世紀(jì)70年代開(kāi)始,字符串匹配問(wèn)題的研究[2]就得到許多學(xué)者的關(guān)注,并且研究成果已廣泛應(yīng)用于生物、醫(yī)學(xué)、犯罪取證等領(lǐng)域。目前,計(jì)算字符串相似度的算法有多種,其中編輯距離算法作為常用的字符串相似度求解算法,具有應(yīng)用廣泛、查找有效和時(shí)間復(fù)雜度較低等優(yōu)勢(shì)。文獻(xiàn)[3]將整條記錄看作一個(gè)字符串,計(jì)算兩個(gè)字符串的編輯距離,從而判斷兩條記錄的相似匹配程度,但是由于字符串長(zhǎng)短不一,可能存在冗余屬性對(duì);文獻(xiàn)[4]提出了基于漢語(yǔ)拼音改進(jìn)的編輯距離算法,把漢語(yǔ)拼音按照音調(diào)、聲母和韻母3方面分類(lèi),分別計(jì)算編輯距離,但在計(jì)算時(shí)使用的傳統(tǒng)動(dòng)態(tài)規(guī)劃算法沒(méi)有考慮形近字會(huì)造成相似度較大的情況,所以,該算法并不具有較高的執(zhí)行效率。文獻(xiàn)[5~6]將字符串分解成中文字符和英文字符兩部分,計(jì)算各自的編輯距離,提高了處理效率。不足之處在于,中文的編輯需要依賴輸入法,是由多個(gè)字母按鍵組合而成,因此,假定任意兩個(gè)中文字符串的差別為同一個(gè)值并不代表中文字符串間的實(shí)際距離,在求解編輯距離時(shí),沒(méi)有考慮可能存在的交換問(wèn)題,可能導(dǎo)致錯(cuò)誤結(jié)論。

    針對(duì)以上文獻(xiàn)的不足之處,本文提出的算法,主要針對(duì)編輯距離改進(jìn)和漢字字符串相似度匹配進(jìn)行,首先在預(yù)處理階段對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理,消除數(shù)據(jù)中的冗余屬性對(duì);其次改進(jìn)動(dòng)態(tài)規(guī)劃算法,能夠有效提高編輯距離的計(jì)算準(zhǔn)確度以及執(zhí)行效率;接著考慮可能存在的交換問(wèn)題,對(duì)編輯距離進(jìn)行歸一化處理。該算法綜合考慮了漢字字符串的特點(diǎn),適用于漢字字符串,既能提高字符串近似匹配的精度,還能提高算法的執(zhí)行效率。

    基于字符串近似匹配算法的研究已較為成熟,但已有的解決方案中,字符串的近似匹配主要針對(duì)英文字符串,這些方法在漢字字符串匹配上難以取得同樣好的效果[7]。因此需要對(duì)經(jīng)典算法進(jìn)行改進(jìn),設(shè)計(jì)出能有效識(shí)別漢字字符串的算法。本文將從以下幾個(gè)角度展開(kāi)研究:

    (1)數(shù)據(jù)標(biāo)準(zhǔn)化。這個(gè)階段是模糊匹配過(guò)程中一個(gè)關(guān)鍵階段。由于模糊匹配的前提之一是數(shù)據(jù)源中的數(shù)據(jù)具有完全相同的模式[8]。但實(shí)際上,對(duì)于不同的數(shù)據(jù)源,由于開(kāi)發(fā)人員的習(xí)慣、建立數(shù)據(jù)源的初衷等差異,使得這個(gè)前提基于不存在,因此需要在預(yù)處理階段對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理[9];(2)中文字符串識(shí)別。實(shí)體識(shí)別是找到那些指向相同實(shí)體的數(shù)據(jù)對(duì)象[10]。當(dāng)把實(shí)體識(shí)別應(yīng)用到具體數(shù)據(jù)時(shí),最關(guān)鍵的操作是實(shí)體數(shù)據(jù)對(duì)象的匹配。實(shí)體數(shù)據(jù)對(duì)象匹配是指判斷兩個(gè)數(shù)據(jù)對(duì)象是否指向同一真實(shí)世界的實(shí)體,如當(dāng)兩家商店合并以后,需要合并所有百貨資料,可是有些百貨可能分別存在于原來(lái)的兩個(gè)數(shù)據(jù)源中,且它們還可能有不同的數(shù)據(jù)表現(xiàn)形式[11]。傳統(tǒng)的字符串精確匹配算法無(wú)法跟上信息和技術(shù)的迅速發(fā)展,國(guó)外學(xué)者開(kāi)始對(duì)近似匹配算法展開(kāi)研究,已取得了較大進(jìn)展。隨著近年來(lái)網(wǎng)絡(luò)的迅速普及以及中文檢索等要求的提高[12],我國(guó)逐步展開(kāi)對(duì)中文字符串近似匹配的研究。已有的識(shí)別算法中,主要考慮英文字符串的相似性比較[13],但是因?yàn)橹形淖址奶攸c(diǎn)與英文比較有較大差異,適用于英文字符串的算法可能不適用于中文,因此尋找中文字符串合適的近似匹配算法的需求迫在眉睫。本文將致力于探究中文字符串適用的近似匹配算法;(3)編輯距離改進(jìn)。計(jì)算字符串相似度的現(xiàn)有算法中,以基于編輯距離的計(jì)算方法為主。雖然編輯距離算法在數(shù)據(jù)清理、拼寫(xiě)錯(cuò)誤檢測(cè)方面具有一定的優(yōu)勢(shì)[14],在刪除錯(cuò)誤方面也具有較高的精度,但仍存在一些問(wèn)題。本文將針對(duì)編輯距離進(jìn)行改進(jìn),以提高算法準(zhǔn)確度;(4)相似度改進(jìn)。本文主要從相似度的改進(jìn)這個(gè)方面來(lái)提高算法效率。因?yàn)橄嗨贫人惴ǖ男释鶗?huì)直接影響到整個(gè)模糊匹配的算法結(jié)果和效率,故相似度的計(jì)算是關(guān)鍵。

    1 基于編輯距離和相似度改進(jìn)的匹配算法

    1.1數(shù)據(jù)預(yù)處理

    該處理主要包含4個(gè)步驟:(1)使對(duì)象具有唯一性,本文算法需要將對(duì)象的唯一標(biāo)識(shí)插入屬性結(jié)點(diǎn)表,并通過(guò)這一標(biāo)識(shí)來(lái)檢索對(duì)象;(2)將屬性名統(tǒng)一,本文算法需要通過(guò)相應(yīng)屬性上的屬性結(jié)點(diǎn)表來(lái)定位實(shí)體對(duì)象;(3)消除冗余的屬性對(duì)。冗余的屬性對(duì)對(duì)實(shí)體的描述價(jià)值可以由其中之一替代,為了提高效率,需要消除冗余的屬性對(duì);(4)使所有對(duì)象結(jié)點(diǎn)處于同一層上。

    經(jīng)過(guò)以上幾步預(yù)處理,數(shù)據(jù)中的對(duì)象具備了標(biāo)識(shí)唯一性和屬性統(tǒng)一性,消除了冗余屬性對(duì),且屬性都處于同一層。

    1.2中文字符串識(shí)別

    根據(jù)漢字音、形的特點(diǎn),本文算法將利用漢字可分解的特征,采用拼音編碼和五筆字型編碼,將漢字通過(guò)算法得到對(duì)應(yīng)的編碼,漢字字符編碼示例如表1所示。

    表1 漢字字符編碼示例表

    如表1所示,通過(guò)比較漢字的編碼就可以獲得單個(gè)漢字字符間的相似度,記為[15],然后結(jié)合單個(gè)漢字字符相似度的和以及編輯距離的值得出兩個(gè)字符串的相似度。

    1.3編輯距離計(jì)算

    編輯距離[16]是指從源字符串S到目標(biāo)字符串T的最小編輯操作次數(shù),目的是計(jì)算S與T的相似度。主要的編輯操作包括對(duì)字符串的字符進(jìn)行插入、替換等。即把字符串x與字符串y之間的互相轉(zhuǎn)換所需的最少操作次數(shù)記為編輯距離ed(x,y)。

    例如:將“今天是個(gè)好天氣”轉(zhuǎn)換成“今天天氣好”,至少需4次編輯操作:刪除字符“是”;刪除字符“個(gè)”;刪除字符“好”;在字符“氣”后插入字符“好”。所以,“今天是個(gè)好天氣”轉(zhuǎn)換成“今天天氣好”的編輯距離為4,此過(guò)程如圖1所示。由圖1可知,編輯距離ed(x,y)=4。

    圖1 編輯距離求解過(guò)程

    求兩個(gè)字符串之間編輯距離最為普遍的方法是動(dòng)態(tài)規(guī)劃算法[17]。算法中包含刪除、插入、替換3種操作。該算法從字符串的左邊第一位字符開(kāi)始,依次進(jìn)行比較,然后記錄已經(jīng)比較過(guò)的編輯距離的數(shù)值,最后得到下一個(gè)字符位置時(shí)的編輯距離。多數(shù)情況下,該算法可以有效計(jì)算字符串間的相似度。但是執(zhí)行效率不高,如在使用上式計(jì)算中文的某些表達(dá)方式時(shí), 可能得出錯(cuò)誤的結(jié)果。例如兩個(gè)字符串:“老師你好”和“你好老師”,利用上式計(jì)算得出,這兩個(gè)字符串的編輯距離為4,相似度為0。而實(shí)際上,這兩個(gè)字符串表達(dá)的意思相同。所以,在這種情況下,傳統(tǒng)的動(dòng)態(tài)規(guī)劃算法將不再適用,需要進(jìn)一步改進(jìn)。

    本文提出的改進(jìn)算法通過(guò)考慮在刪除、插入、替換等操作中的操作代價(jià),對(duì)傳統(tǒng)的動(dòng)態(tài)規(guī)劃算法進(jìn)行優(yōu)化,改進(jìn)后的動(dòng)態(tài)規(guī)劃算法,主要步驟如下:

    (1)構(gòu)造|x|+1行,|y|+1列的矩陣D[|x|+1,|y|+1],其中,字符串x和y的長(zhǎng)度分別用|x|和|y|來(lái)表示;

    (2)矩陣元素D[i,j]就表示ed(x1i,y1j),即為上文提到的編輯距離。同理可知,矩陣右下角元素D[|x|+1,|y|+1]的含義就是ed(x,y);

    (3)矩陣D的值通過(guò)如下公式計(jì)算,其中所需要的最少操作次數(shù)

    Di,0=Di-1,0+1

    D0,j=D0,j-1+1

    如果xi=yi,

    Di,j=Di=1,j-1

    (1)

    如果xi≠yi,則

    Di,j=min(Di-1,j-1+cost(x,y),Di-1,j+1,Di,j-1+1)+1

    (2)

    其中,cost(x,y)表示操作代價(jià),且當(dāng)xi≠yi時(shí),cost(x,y)=0。

    實(shí)驗(yàn)表明,雖然改進(jìn)算法在提高結(jié)果準(zhǔn)確度的同時(shí),也增加了時(shí)間復(fù)雜度,但是在能提高效率的前提下,增加時(shí)間復(fù)雜度的代價(jià)也是可以被接受的。

    1.4相似度計(jì)算

    (3)

    通常情況下,編輯距離與相似度成反比。所以,不能簡(jiǎn)單地用編輯距離來(lái)反映相似度。例如,憑感覺(jué),兩個(gè)長(zhǎng)度為2、編輯距離為1的字符串的相似度,要低于長(zhǎng)度為9、編輯距離為2的相似度,實(shí)則不然。因此,為了得出準(zhǔn)確的相似度,對(duì)編輯距離進(jìn)行歸一化[20]處理是必要的。常用的歸一化方法如下

    (4)

    兩個(gè)中文字符串P=“上海理工大學(xué)光電學(xué)院”和Q=“光電信息”以詞語(yǔ)作為編輯單元計(jì)算編輯距離,有k=8,m=10,n=4。

    按照式(6)的歸一化,有

    計(jì)算得到結(jié)果是負(fù)數(shù),與常理不符。這是因?yàn)樵撍惴〞r(shí)空復(fù)雜度較高,而且忽略了交換問(wèn)題帶來(lái)的影響,本文以語(yǔ)義編輯距離與長(zhǎng)句長(zhǎng)度的比值作為歸一化結(jié)果,更加簡(jiǎn)單實(shí)用,得到計(jì)算字符串P與Q相似度的公式如下

    (5)

    式 (7) 中,在插入和刪除代價(jià)均≤1的情況下,有0≤k≤l,所以0≤similar(P,Q)≤1。由此可得出,similar(P,Q)的值越大,表示P與Q越相似。

    1.5匹配算法的實(shí)現(xiàn)

    以下是匹配算法的主要流程:

    (1)輸入兩個(gè)字符串P、Q;

    (2)判斷P、Q是否等值,若相等跳轉(zhuǎn)到步驟(4),否則跳轉(zhuǎn)到步驟(3);

    (3)得到n=length(P)和m=length(Q),首先判斷n與m的值,若n=0,則ed(P,Q)=m;若m=0則ed(P,Q)=n;若n=m,則跳轉(zhuǎn)到步驟(4);否則跳轉(zhuǎn)到步驟(5);

    圖2 匹配算法流程圖

    (4)令i=1,并從位置i開(kāi)始逐字掃描,步長(zhǎng)以1遞增,直至最后一個(gè)字符;得出λ(i);

    (5)使用改進(jìn)的動(dòng)態(tài)規(guī)劃算法計(jì)算編輯距離根據(jù)行列對(duì)應(yīng)值找出所有不匹配的字符;

    (6) 計(jì)算兩個(gè)字符串的相似度。

    匹配算法流程如圖2所示。

    2 實(shí)驗(yàn)結(jié)果與分析

    在安裝有Delphi2007的Windows7測(cè)試環(huán)境下,實(shí)現(xiàn)基于編輯距離和相似度改進(jìn)的漢字字符串匹配,并把實(shí)驗(yàn)結(jié)果與傳統(tǒng)的動(dòng)態(tài)規(guī)劃算法和傳統(tǒng)的相似度計(jì)算方法進(jìn)行比較,選取不同的幾對(duì)中文詞語(yǔ)進(jìn)行實(shí)驗(yàn),一共8組詞語(yǔ),詞長(zhǎng)范圍為2~3,包含形近字和音近字。實(shí)驗(yàn)結(jié)果如表2所示。

    表2 編輯距離和相似度比較表

    上述實(shí)驗(yàn)字符串中,既包含了同音、近音詞的情況,也有形近字和同義詞的情況。從相似度的計(jì)算結(jié)果看,改進(jìn)后算法計(jì)算的相似度質(zhì)量要優(yōu)于舊算法的結(jié)果,也證明了該改進(jìn)算法的可行性和有效性。

    實(shí)驗(yàn)結(jié)果也表明,改進(jìn)后的算法,在算法效率、查全率、查準(zhǔn)率和時(shí)間性能等指標(biāo)上均有明顯改善。

    圖3 各數(shù)據(jù)規(guī)模下的查準(zhǔn)率

    查準(zhǔn)率=查出的相似的數(shù)據(jù)個(gè)數(shù)/算法檢索到的數(shù)據(jù)格式。

    由圖3的實(shí)驗(yàn)結(jié)果可看出,改進(jìn)后的算法在數(shù)據(jù)規(guī)模一致的前提下,查準(zhǔn)率則由72.7%提升到81.5%。

    圖4 各數(shù)據(jù)規(guī)模下的查全率

    查全率=查到的相似的數(shù)據(jù)個(gè)數(shù)/系統(tǒng)中實(shí)際相似的數(shù)據(jù)個(gè)數(shù)。

    由圖4的實(shí)驗(yàn)結(jié)果可以看出,改進(jìn)后的算法在數(shù)據(jù)規(guī)模一致的前提下,查全率由65.6%提升到69.2%。

    圖5 各數(shù)據(jù)規(guī)模下的平均耗時(shí)

    由圖5的實(shí)驗(yàn)結(jié)果可看出,改進(jìn)后的算法在數(shù)據(jù)規(guī)模一致的前提下,平均耗時(shí)由351ms降低到290ms。

    從實(shí)驗(yàn)獲得的結(jié)果來(lái)看,可以得出結(jié)論:改進(jìn)后的算法在數(shù)據(jù)規(guī)模一致的前提下,查全率、查準(zhǔn)率和時(shí)間性能均有提高,證明了改進(jìn)算法的可行性和有效性。

    3 結(jié)束語(yǔ)

    本文針對(duì)傳統(tǒng)近似匹配算法中,編輯距離計(jì)算時(shí)僅考慮英文字符串,并在計(jì)算相似度時(shí)未考慮交換的歸一化等問(wèn)題,提出了一種基于改進(jìn)編輯距離和相似度的漢字字符串的近似匹配算法,通過(guò)改進(jìn)的編輯距離算法提高識(shí)別準(zhǔn)確度,使近似匹配算法更有實(shí)際應(yīng)用的意義;同時(shí)在實(shí)驗(yàn)中給出相似度比較的實(shí)驗(yàn)結(jié)果,用3個(gè)評(píng)價(jià)指標(biāo)驗(yàn)證算法的準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)算法相比,改進(jìn)后的算法在查準(zhǔn)率、查全率和平均耗時(shí)方面都具有明顯優(yōu)勢(shì),提高了推薦算法的性能。

    字符串近似匹配在語(yǔ)言識(shí)別、文件檢索、模式識(shí)別等許多領(lǐng)域應(yīng)用廣泛,但由于語(yǔ)言中大量同義詞、多義詞的存在,導(dǎo)致了在詞形上存在對(duì)應(yīng)關(guān)系的不同實(shí)體不等于語(yǔ)義上也存在對(duì)應(yīng)關(guān)系,因此,僅根據(jù)字符串模糊匹配的方法所獲得的匹配結(jié)果是不夠理想的,還應(yīng)綜合考慮這些實(shí)體的其他相關(guān)屬性,這也將是下一步的研究方向。

    [1]劉顯敏,李建中.實(shí)體識(shí)別問(wèn)題的相關(guān)研究[J].智能計(jì)算機(jī)與應(yīng)用,2013,3(2):1-5,10.

    [2]強(qiáng)寶華.異構(gòu)數(shù)據(jù)庫(kù)語(yǔ)義集成技術(shù)研究[D]. 重慶:重慶大學(xué), 2005.

    [3]LiangJin,ChenLi,MehrotraS.Efficientrecordlinkageinlargedatasets[C].Korea:Proceedingofthe8thInternationalConferenceonDatabaseSystemforAdvancedApplication,2003.

    [4]俞榮華,田增平,周傲英.一種檢測(cè)多語(yǔ)言文本相似重復(fù)記錄的綜合方法[J].計(jì)算機(jī)科學(xué), 2002,29(1):118-121.

    [5]曹犟,鄔曉鈞,夏云慶,等. 基于拼音索引的中文模糊匹配算法[J]. 清華大學(xué)學(xué)報(bào):自然科學(xué)版,2009,49(S1):1328-1332.

    [6]杜艾永,李立順,朱愿,等.基于漢字機(jī)內(nèi)編碼的中文相似重復(fù)記錄消除研究[J].電腦知識(shí)與技術(shù),2009,5(29):8314-8316.

    [7]李鈍,曹元大,萬(wàn)月亮.信息安全中的變形關(guān)鍵詞的識(shí)別[J].計(jì)算機(jī)工程,2007,33(21): 155-156,159.

    [8]VernicaR,CareyMJ,LiC.Efficientparallelset-similarityjoinsusingmapreduce[J].ProceedingofSIGMOD,2010,3(1):218-229.

    [9]Mongeae,Elkancp.Thefieldmatchingproblem:Algorithmandapplications[EB/OL]. (2008-06-16)[2015-01-11]http://www.cecs.csulb.edu/~monge/Papers/kdd96.ps.

    [10]ElmagarmidAK,IpeirotisPG,VerykiosVS.Duplicaterecorddetection:asurvey[J].IEEETransactionsonKnowledgeandDataEngineering, 2007, 19(1): 1-16.

    [11]周建芳,徐海銀,盧正鼎.信息集成中的實(shí)體識(shí)別解決方案[J].小型微型計(jì)算機(jī)系統(tǒng),2009, 30(9):1774-1780.

    [12]車(chē)萬(wàn)翔,劉挺,秦兵,等.基于改進(jìn)編輯距離的中文相似句子檢索[J]. 高技術(shù)通訊,2004(7):15-19.

    [13]范立新.改進(jìn)的中文近似字符串匹配算法[J].計(jì)算機(jī)工程與應(yīng)用,2006,2(1):22-24.

    [14]趙作鵬,尹志民,王潛平,等.一種改進(jìn)的編輯距離算法及其在數(shù)據(jù)處理中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用, 2009,23(12):96-98.

    [15]王靜婷.基于漢字聚類(lèi)特征的中文字符串相似度計(jì)算研究[J].現(xiàn)代圖書(shū)情報(bào)技術(shù),2011(2):48-53.

    [16]LevenshteinVI.Binarycodescapableofcorrectingdeletions,insertionsandreversals[J].ProblemsofInformationTransmission, 1965,1(1): 8-17.

    [17]于志恒.基于筆形相似的文本校對(duì)算法及其接口原型系統(tǒng)的研究[D]. 沈陽(yáng):東北師范大學(xué),2007.

    [18]刁興春,譚明超,曹建軍.一種融合多種編輯距離的字符串相似度計(jì)算方法[J].計(jì)算機(jī)應(yīng)用研究,2010,27(12):4523-4525.

    [19]ChristenP,ChurchesT,HeglandM.Febrl-Aparallelopensourcedatalinkagesystem[M].Berlin:SpringerHeidelberg, 2004.

    [20]張仰森.中文校對(duì)系統(tǒng)中糾錯(cuò)知識(shí)庫(kù)的構(gòu)造及糾錯(cuò)建議的產(chǎn)生算法[J].中文信息學(xué)報(bào), 2001,12(1):41-44,40.

    Chinese Character String Matching Algorithm Based on Improved Edit Distance and Similarity

    SHAO Qing, YE Kun

    (School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

    A Chinese character string approximate matching algorithm based on the improved edit distance and similarity is proposed for better accuracy in Chinese string matching. Firstly the pinyin code is used by considering character of Chinese string, then dynamic programming algorithm is improved to effectively improve the accuracy of calculation; next, a normalization algorithm considering switching problems is introduced. With semantic edit and long distance the ratio of the length of the sentence as the result of the normalization, the accuracy and executive efficiency of approximate matching algorithm is improved. Experimental results show that the quality of the results by the improved algorithm is better than those by traditional algorithms with significant improvement in efficiency, recall, precision, time cost and other indicators.

    edit distance; similarity; normalization; Chinese character string; approximate matching

    2016- 12- 26

    國(guó)家自然科學(xué)基金資助項(xiàng)目(61170277);上海市教委科研創(chuàng)新基金資助項(xiàng)目(02120557)

    邵清(1970-),女,博士,副教授。研究方向:網(wǎng)絡(luò)智能等。葉琨(1993-),女,碩士研究生。研究方向:網(wǎng)絡(luò)智能。

    10.16180/j.cnki.issn1007-7820.2016.09.003

    TP391.41

    A

    1007-7820(2016)09-007-05

    猜你喜歡
    字符串字符漢字
    尋找更強(qiáng)的字符映射管理器
    字符代表幾
    一種USB接口字符液晶控制器設(shè)計(jì)
    電子制作(2019年19期)2019-11-23 08:41:50
    消失的殖民村莊和神秘字符
    漢字這樣記
    漢字這樣記
    一種新的基于對(duì)稱性的字符串相似性處理算法
    依據(jù)字符串匹配的中文分詞模型研究
    一種針對(duì)Java中字符串的內(nèi)存管理方案
    小改字符串讓殺毒軟件閉嘴
    欧美另类一区| 国产成人免费观看mmmm| 免费观看a级毛片全部| 国产一区亚洲一区在线观看| 久久久精品欧美日韩精品| 国产精品女同一区二区软件| 日韩强制内射视频| 99久久精品国产国产毛片| 麻豆精品久久久久久蜜桃| 亚洲美女搞黄在线观看| 男女无遮挡免费网站观看| 乱码一卡2卡4卡精品| 国产午夜精品一二区理论片| 欧美区成人在线视频| 婷婷色麻豆天堂久久| 欧美bdsm另类| 国产国拍精品亚洲av在线观看| 久久久久久久精品精品| 99久久精品国产国产毛片| 日韩一区二区三区影片| 亚洲图色成人| 免费黄频网站在线观看国产| 日韩电影二区| 亚洲,欧美,日韩| 国产男女超爽视频在线观看| 欧美精品人与动牲交sv欧美| 亚洲成人精品中文字幕电影| 99久久精品热视频| 九色成人免费人妻av| 美女xxoo啪啪120秒动态图| 性插视频无遮挡在线免费观看| 久久久色成人| 91精品国产九色| 欧美高清成人免费视频www| 日韩一本色道免费dvd| 2018国产大陆天天弄谢| 久久久久精品性色| av在线老鸭窝| 午夜福利在线观看免费完整高清在| 亚洲国产精品专区欧美| 性插视频无遮挡在线免费观看| 国产精品99久久99久久久不卡 | 一本色道久久久久久精品综合| 美女xxoo啪啪120秒动态图| 一区二区三区免费毛片| 简卡轻食公司| 狠狠精品人妻久久久久久综合| 男女那种视频在线观看| 特级一级黄色大片| 午夜免费男女啪啪视频观看| 女人被狂操c到高潮| 国产一级毛片在线| 久久精品国产a三级三级三级| 蜜桃久久精品国产亚洲av| 岛国毛片在线播放| 亚洲精品成人久久久久久| 最近最新中文字幕免费大全7| 欧美成人一区二区免费高清观看| av线在线观看网站| 永久网站在线| 中文精品一卡2卡3卡4更新| 王馨瑶露胸无遮挡在线观看| 在线观看一区二区三区激情| 精品熟女少妇av免费看| 国产一区亚洲一区在线观看| 久久人人爽人人片av| 波多野结衣巨乳人妻| 国产乱人视频| 免费观看性生交大片5| 亚洲精品中文字幕在线视频 | 一区二区三区免费毛片| 成人一区二区视频在线观看| 午夜日本视频在线| 国产av国产精品国产| 欧美 日韩 精品 国产| 久久精品国产亚洲av涩爱| 日韩欧美精品v在线| 超碰av人人做人人爽久久| 亚洲成人一二三区av| 国产欧美亚洲国产| 欧美性感艳星| 欧美老熟妇乱子伦牲交| 亚洲,欧美,日韩| 国内精品美女久久久久久| 街头女战士在线观看网站| 美女国产视频在线观看| 欧美性猛交╳xxx乱大交人| 亚洲欧美清纯卡通| 极品教师在线视频| 欧美一级a爱片免费观看看| 日韩,欧美,国产一区二区三区| 午夜福利网站1000一区二区三区| 最新中文字幕久久久久| 国产亚洲午夜精品一区二区久久 | 成人综合一区亚洲| 亚洲最大成人中文| 久久精品人妻少妇| 欧美zozozo另类| 亚洲美女搞黄在线观看| 全区人妻精品视频| 亚洲精品国产色婷婷电影| 人妻系列 视频| 一个人看视频在线观看www免费| 哪个播放器可以免费观看大片| 69av精品久久久久久| 国产乱人偷精品视频| 你懂的网址亚洲精品在线观看| 中文精品一卡2卡3卡4更新| 亚洲人与动物交配视频| 欧美激情久久久久久爽电影| 五月玫瑰六月丁香| 建设人人有责人人尽责人人享有的 | 午夜爱爱视频在线播放| 在线播放无遮挡| 精品人妻视频免费看| 久久韩国三级中文字幕| 国产成人精品一,二区| 久久久亚洲精品成人影院| 青春草亚洲视频在线观看| 国产69精品久久久久777片| 亚洲最大成人中文| 自拍欧美九色日韩亚洲蝌蚪91 | 美女cb高潮喷水在线观看| 亚洲丝袜综合中文字幕| 免费观看a级毛片全部| 好男人视频免费观看在线| 国产色爽女视频免费观看| 中文天堂在线官网| 中国国产av一级| 一级av片app| 久久鲁丝午夜福利片| 草草在线视频免费看| 最近手机中文字幕大全| 熟女av电影| 精品久久久久久久久亚洲| 丰满少妇做爰视频| 午夜免费男女啪啪视频观看| 国产精品久久久久久精品电影| 大香蕉97超碰在线| 日韩一区二区视频免费看| 国产午夜精品久久久久久一区二区三区| 久久97久久精品| 高清在线视频一区二区三区| 久久热精品热| 嫩草影院入口| 18+在线观看网站| 精品国产乱码久久久久久小说| 国模一区二区三区四区视频| 免费av观看视频| 日本色播在线视频| 国内精品宾馆在线| 亚洲最大成人中文| 色哟哟·www| 啦啦啦啦在线视频资源| 亚洲第一区二区三区不卡| 欧美国产精品一级二级三级 | 一级黄片播放器| 99久久九九国产精品国产免费| 国产精品国产三级国产av玫瑰| 下体分泌物呈黄色| 色综合色国产| 777米奇影视久久| 色视频www国产| 亚洲成色77777| 自拍欧美九色日韩亚洲蝌蚪91 | 国产成人aa在线观看| 内射极品少妇av片p| 草草在线视频免费看| 麻豆成人午夜福利视频| 国产黄片美女视频| 夫妻午夜视频| 尤物成人国产欧美一区二区三区| 日产精品乱码卡一卡2卡三| 国产成人a∨麻豆精品| 精品久久久噜噜| 亚洲欧美精品专区久久| 在线免费十八禁| 内射极品少妇av片p| av免费在线看不卡| 美女视频免费永久观看网站| av在线蜜桃| 日本av手机在线免费观看| tube8黄色片| 国产黄色免费在线视频| 精品久久久精品久久久| 伦精品一区二区三区| 七月丁香在线播放| 超碰97精品在线观看| 久久久久久久久久人人人人人人| av在线天堂中文字幕| 精品人妻一区二区三区麻豆| 中文欧美无线码| 日韩免费高清中文字幕av| 另类亚洲欧美激情| 亚洲一级一片aⅴ在线观看| 亚洲精品第二区| 精品酒店卫生间| 国产亚洲91精品色在线| 亚洲美女搞黄在线观看| 黄片无遮挡物在线观看| 成年人午夜在线观看视频| 天天一区二区日本电影三级| 日韩三级伦理在线观看| 亚洲不卡免费看| 在线观看av片永久免费下载| 一区二区三区乱码不卡18| 成人午夜精彩视频在线观看| 国内揄拍国产精品人妻在线| 韩国高清视频一区二区三区| 寂寞人妻少妇视频99o| 超碰av人人做人人爽久久| tube8黄色片| 深夜a级毛片| 在现免费观看毛片| 在线a可以看的网站| 成人特级av手机在线观看| 99热这里只有精品一区| 亚洲欧美一区二区三区黑人 | 亚洲精品日韩av片在线观看| 2018国产大陆天天弄谢| 亚洲色图综合在线观看| 丝袜脚勾引网站| 99久久精品一区二区三区| 日韩人妻高清精品专区| a级毛片免费高清观看在线播放| 狂野欧美激情性bbbbbb| 秋霞伦理黄片| 日韩人妻高清精品专区| 久久ye,这里只有精品| 秋霞在线观看毛片| 免费看不卡的av| 一级黄片播放器| 天天一区二区日本电影三级| 亚洲最大成人av| 日日啪夜夜爽| 欧美日韩精品成人综合77777| 在线 av 中文字幕| 人体艺术视频欧美日本| 久久6这里有精品| 可以在线观看毛片的网站| 草草在线视频免费看| 人妻系列 视频| 成人亚洲精品一区在线观看 | 久久97久久精品| 久久这里有精品视频免费| 免费播放大片免费观看视频在线观看| 成人二区视频| 国产高潮美女av| 免费观看无遮挡的男女| 亚洲在久久综合| 又粗又硬又长又爽又黄的视频| 亚洲久久久久久中文字幕| 午夜日本视频在线| 午夜爱爱视频在线播放| 大话2 男鬼变身卡| 日韩欧美精品免费久久| 亚洲欧美日韩东京热| 丰满乱子伦码专区| 免费少妇av软件| 国产一区二区在线观看日韩| 亚洲精品456在线播放app| 我的老师免费观看完整版| 丝袜美腿在线中文| 赤兔流量卡办理| 日日撸夜夜添| 内地一区二区视频在线| 日韩欧美精品v在线| 午夜爱爱视频在线播放| 身体一侧抽搐| 国产成人免费无遮挡视频| 国产精品不卡视频一区二区| 97在线视频观看| 涩涩av久久男人的天堂| 精品久久久久久久久亚洲| 亚洲欧美日韩另类电影网站 | 国产精品偷伦视频观看了| 麻豆成人午夜福利视频| 身体一侧抽搐| 高清欧美精品videossex| 色综合色国产| 国产精品女同一区二区软件| 亚洲丝袜综合中文字幕| 亚洲av免费在线观看| 欧美极品一区二区三区四区| 亚洲真实伦在线观看| 下体分泌物呈黄色| 边亲边吃奶的免费视频| 大香蕉97超碰在线| 波野结衣二区三区在线| 嫩草影院入口| 人人妻人人澡人人爽人人夜夜| 视频中文字幕在线观看| 小蜜桃在线观看免费完整版高清| 高清av免费在线| 国产亚洲av片在线观看秒播厂| 少妇丰满av| 国产视频内射| av在线观看视频网站免费| 亚洲精品日本国产第一区| 免费av不卡在线播放| 观看美女的网站| 久久久精品免费免费高清| 我的女老师完整版在线观看| 高清在线视频一区二区三区| 久久久成人免费电影| 女的被弄到高潮叫床怎么办| 久久国产乱子免费精品| 美女视频免费永久观看网站| 久久国产乱子免费精品| 天堂俺去俺来也www色官网| 国产女主播在线喷水免费视频网站| 97热精品久久久久久| 精品酒店卫生间| 日韩成人av中文字幕在线观看| 成人午夜精彩视频在线观看| 欧美另类一区| 久久久精品免费免费高清| 亚洲av福利一区| 97在线人人人人妻| 欧美bdsm另类| 欧美高清性xxxxhd video| 街头女战士在线观看网站| 午夜激情福利司机影院| 久久久午夜欧美精品| 成年人午夜在线观看视频| 亚洲国产高清在线一区二区三| 在线观看免费高清a一片| 日韩国内少妇激情av| 舔av片在线| 大又大粗又爽又黄少妇毛片口| 亚洲熟女精品中文字幕| 国产黄片视频在线免费观看| 2021天堂中文幕一二区在线观| 精品久久久精品久久久| 免费人成在线观看视频色| 2022亚洲国产成人精品| 国语对白做爰xxxⅹ性视频网站| 99热这里只有是精品50| 蜜臀久久99精品久久宅男| 91精品伊人久久大香线蕉| 久久久精品免费免费高清| 日本与韩国留学比较| 亚洲aⅴ乱码一区二区在线播放| 男女无遮挡免费网站观看| 街头女战士在线观看网站| 日本av手机在线免费观看| av在线老鸭窝| 久久99蜜桃精品久久| 国语对白做爰xxxⅹ性视频网站| 国产成人午夜福利电影在线观看| 少妇丰满av| 最近的中文字幕免费完整| 人人妻人人澡人人爽人人夜夜| 国产亚洲午夜精品一区二区久久 | 身体一侧抽搐| 校园人妻丝袜中文字幕| 亚洲av成人精品一区久久| 久久国产乱子免费精品| 在现免费观看毛片| 国产欧美亚洲国产| 国产一区二区亚洲精品在线观看| 久久久精品免费免费高清| 有码 亚洲区| 大又大粗又爽又黄少妇毛片口| 国产成人精品婷婷| 80岁老熟妇乱子伦牲交| 午夜老司机福利剧场| 最近最新中文字幕大全电影3| 午夜精品一区二区三区免费看| 欧美丝袜亚洲另类| 亚洲国产高清在线一区二区三| 久久精品久久精品一区二区三区| a级毛片免费高清观看在线播放| 极品教师在线视频| 亚洲av欧美aⅴ国产| 亚洲精品影视一区二区三区av| 国产探花极品一区二区| 精品一区在线观看国产| videos熟女内射| 亚洲熟女精品中文字幕| 成年人午夜在线观看视频| 三级男女做爰猛烈吃奶摸视频| 18禁在线播放成人免费| 国产淫语在线视频| 国产精品一及| 99热这里只有精品一区| 黄片wwwwww| 成年人午夜在线观看视频| 黄色一级大片看看| 色哟哟·www| 精品一区二区三卡| 99久久中文字幕三级久久日本| 免费看av在线观看网站| 婷婷色麻豆天堂久久| 亚洲欧美中文字幕日韩二区| 精品少妇黑人巨大在线播放| 成人特级av手机在线观看| 精品视频人人做人人爽| 国产精品国产三级国产av玫瑰| 晚上一个人看的免费电影| av播播在线观看一区| 久久久久精品性色| 国内精品美女久久久久久| 亚洲高清免费不卡视频| 国产欧美亚洲国产| 听说在线观看完整版免费高清| 又黄又爽又刺激的免费视频.| 精品人妻视频免费看| 97精品久久久久久久久久精品| 欧美三级亚洲精品| 亚洲高清免费不卡视频| 欧美激情久久久久久爽电影| 色视频在线一区二区三区| 人人妻人人看人人澡| 亚洲av免费在线观看| 精品99又大又爽又粗少妇毛片| 亚洲一区二区三区欧美精品 | 美女被艹到高潮喷水动态| 免费av毛片视频| 美女视频免费永久观看网站| 亚洲激情五月婷婷啪啪| 日本一二三区视频观看| 五月开心婷婷网| 99九九线精品视频在线观看视频| 在线观看一区二区三区激情| 国产一区二区在线观看日韩| 秋霞在线观看毛片| 在线看a的网站| 97热精品久久久久久| 国产一区二区三区综合在线观看 | 菩萨蛮人人尽说江南好唐韦庄| 欧美3d第一页| 国产午夜精品久久久久久一区二区三区| 特大巨黑吊av在线直播| 免费电影在线观看免费观看| 成人午夜精彩视频在线观看| 久久久久久久精品精品| 久久女婷五月综合色啪小说 | 五月开心婷婷网| 插阴视频在线观看视频| 久久久亚洲精品成人影院| 国产69精品久久久久777片| 精品国产乱码久久久久久小说| 又爽又黄a免费视频| 午夜激情久久久久久久| 亚洲性久久影院| 国产成人a∨麻豆精品| av.在线天堂| 久久久久精品性色| 少妇人妻一区二区三区视频| 丝瓜视频免费看黄片| 国产成年人精品一区二区| 午夜视频国产福利| 女人十人毛片免费观看3o分钟| 免费av不卡在线播放| 五月天丁香电影| 欧美亚洲 丝袜 人妻 在线| 蜜桃亚洲精品一区二区三区| 免费电影在线观看免费观看| 人人妻人人看人人澡| 国产高清有码在线观看视频| 国产伦理片在线播放av一区| 一级二级三级毛片免费看| 精品酒店卫生间| 国产亚洲av嫩草精品影院| 亚洲精品亚洲一区二区| 久久久久久久国产电影| 中文精品一卡2卡3卡4更新| 免费av观看视频| 丝袜美腿在线中文| av在线蜜桃| 色视频www国产| 日本wwww免费看| 亚洲三级黄色毛片| 深爱激情五月婷婷| 国产老妇女一区| 亚洲欧美一区二区三区国产| 成人黄色视频免费在线看| av在线app专区| 九色成人免费人妻av| 国产毛片在线视频| 性色avwww在线观看| 天天躁夜夜躁狠狠久久av| 亚洲精品456在线播放app| 日日撸夜夜添| 亚洲精华国产精华液的使用体验| av卡一久久| 边亲边吃奶的免费视频| 蜜桃亚洲精品一区二区三区| 爱豆传媒免费全集在线观看| 色5月婷婷丁香| 欧美日韩国产mv在线观看视频 | 久久久精品欧美日韩精品| 看十八女毛片水多多多| 好男人在线观看高清免费视频| 国产黄频视频在线观看| 乱码一卡2卡4卡精品| 男女边吃奶边做爰视频| 伦理电影大哥的女人| 久久久色成人| 黄片无遮挡物在线观看| 丝袜喷水一区| 欧美性猛交╳xxx乱大交人| 欧美最新免费一区二区三区| 乱系列少妇在线播放| 亚洲熟女精品中文字幕| 国产日韩欧美在线精品| 校园人妻丝袜中文字幕| 国产成人精品久久久久久| 热re99久久精品国产66热6| 亚洲国产av新网站| 午夜免费观看性视频| 女人十人毛片免费观看3o分钟| 寂寞人妻少妇视频99o| 女人被狂操c到高潮| 亚洲一级一片aⅴ在线观看| 熟女av电影| 一级毛片我不卡| 免费高清在线观看视频在线观看| av黄色大香蕉| 国产精品精品国产色婷婷| 国产精品一区二区在线观看99| 在线免费十八禁| 久久精品国产自在天天线| 国产淫语在线视频| 69av精品久久久久久| 成人毛片a级毛片在线播放| 亚洲精品456在线播放app| 亚洲自偷自拍三级| 十八禁网站网址无遮挡 | 六月丁香七月| 男人舔奶头视频| 久久精品国产鲁丝片午夜精品| 激情五月婷婷亚洲| 在线a可以看的网站| 少妇熟女欧美另类| 精品一区二区免费观看| 亚洲人成网站在线观看播放| 国模一区二区三区四区视频| 免费看a级黄色片| 国产日韩欧美亚洲二区| 久久久精品欧美日韩精品| 精品国产露脸久久av麻豆| 青春草国产在线视频| 高清日韩中文字幕在线| 国产伦在线观看视频一区| 大香蕉97超碰在线| 五月伊人婷婷丁香| 午夜免费观看性视频| 男男h啪啪无遮挡| 日韩人妻高清精品专区| 亚洲国产精品国产精品| 欧美性猛交╳xxx乱大交人| 中文资源天堂在线| 国产精品久久久久久av不卡| 亚洲精品亚洲一区二区| 极品少妇高潮喷水抽搐| 超碰av人人做人人爽久久| 国产免费福利视频在线观看| 晚上一个人看的免费电影| 有码 亚洲区| 黄色日韩在线| 久久人人爽人人片av| 国产精品av视频在线免费观看| 免费av观看视频| 欧美性猛交╳xxx乱大交人| 美女脱内裤让男人舔精品视频| 性色av一级| 欧美精品国产亚洲| 免费大片黄手机在线观看| 人妻少妇偷人精品九色| 看非洲黑人一级黄片| 秋霞伦理黄片| 午夜老司机福利剧场| 国产真实伦视频高清在线观看| 大又大粗又爽又黄少妇毛片口| 视频中文字幕在线观看| 三级国产精品欧美在线观看| 99热这里只有精品一区| 激情 狠狠 欧美| 天堂中文最新版在线下载 | 欧美亚洲 丝袜 人妻 在线| 国产精品麻豆人妻色哟哟久久| 国产av国产精品国产| 久久精品人妻少妇| 老女人水多毛片| 亚洲色图综合在线观看| 亚洲精品视频女| 观看免费一级毛片| 精品少妇久久久久久888优播| 我的老师免费观看完整版| 高清毛片免费看| 偷拍熟女少妇极品色| 人妻夜夜爽99麻豆av| 国产91av在线免费观看| 嫩草影院精品99| 身体一侧抽搐| av线在线观看网站| 亚洲av一区综合| 22中文网久久字幕| 最近最新中文字幕大全电影3| 一区二区三区四区激情视频| 亚洲一区二区三区欧美精品 | 欧美一区二区亚洲| 边亲边吃奶的免费视频| 高清在线视频一区二区三区| 天美传媒精品一区二区| 男女啪啪激烈高潮av片| 乱码一卡2卡4卡精品| 国精品久久久久久国模美| 亚洲精品久久久久久婷婷小说| 欧美一级a爱片免费观看看| 六月丁香七月| 亚洲熟女精品中文字幕| 国产午夜精品一二区理论片|