基于標(biāo)志詞的正向自適應(yīng)長(zhǎng)度匹配的地址分詞算法與缺失地址要素補(bǔ)充方法

李凈，朱貴鮮，周亮，鄭西川

上海健康醫(yī)學(xué)院附屬第六人民醫(yī)院東院 計(jì)算機(jī)中心，上海 201306

引言

隨著紙質(zhì)病歷的逐漸退出，結(jié)構(gòu)化電子病歷成為各醫(yī)院基本選擇[1-2]。但門診患者類型復(fù)雜、時(shí)效性較強(qiáng)、結(jié)構(gòu)化病歷轉(zhuǎn)換復(fù)雜等因素，妨礙了門診電子病歷的深入應(yīng)用[3-6]。其中患者住址為病人基本信息中的一條重要數(shù)據(jù)，但由于起初地址錄入模型設(shè)計(jì)的不規(guī)范，導(dǎo)致患者地址信息地填寫也不規(guī)范。這些非結(jié)構(gòu)化的數(shù)據(jù)，對(duì)信息的提取工作造成了一定程度的困難。因此，將這些非結(jié)構(gòu)化的地址數(shù)據(jù)轉(zhuǎn)化為結(jié)構(gòu)化的地址數(shù)據(jù)，顯得尤為重要。

結(jié)構(gòu)化的地址數(shù)據(jù)指地址按照統(tǒng)一的結(jié)構(gòu)存儲(chǔ)，比如按照省、市、區(qū)、街道等的結(jié)構(gòu)存儲(chǔ)。而目前醫(yī)院電子病歷中的地址數(shù)據(jù)結(jié)構(gòu)混亂，往往存在地址信息不全面，大量的別名、簡(jiǎn)稱，特殊符號(hào)（如#、-、/等）等問(wèn)題。解決這些問(wèn)題，實(shí)現(xiàn)非結(jié)構(gòu)化地址數(shù)據(jù)向結(jié)構(gòu)化地址數(shù)據(jù)轉(zhuǎn)換，就需要將特殊符號(hào)轉(zhuǎn)化成常規(guī)的文本信息，比如#表示號(hào)樓，然后將地址數(shù)據(jù)進(jìn)行分詞并記錄每個(gè)分詞的地址能級(jí)，并根據(jù)分詞結(jié)果補(bǔ)充缺失的地址要素，并根據(jù)自定義的地址匹配規(guī)則庫(kù)將別名、簡(jiǎn)稱等標(biāo)準(zhǔn)化。

在以上所提要做的工作中，關(guān)鍵在于地址分詞和缺失地址要素的補(bǔ)充。中文分詞是目前很多學(xué)者的研究方向，主流的分詞方法主要分為兩類：機(jī)械分詞法[7-14]和統(tǒng)計(jì)分詞法[15-21]。由于地址數(shù)據(jù)里的地址要素常常會(huì)包含一些標(biāo)志詞，如省、市、區(qū)等，劉韜[9]提出了設(shè)立切分標(biāo)志法對(duì)地址數(shù)據(jù)進(jìn)行分詞。但在實(shí)際的地址錄入過(guò)程中，很多時(shí)候或省略標(biāo)志詞，如上海普陀曹楊街道，就會(huì)造成分詞結(jié)果的不準(zhǔn)確。馬照亭等[10]在中文自動(dòng)分詞詞庫(kù)的基礎(chǔ)上，添加了《中國(guó)地名用詞庫(kù)》中的通用地名詞條和一個(gè)城市中的專用地名或地址詞條，并為地址要素掛接“標(biāo)準(zhǔn)名稱”和“地址級(jí)別”兩個(gè)屬性字段，提高了分詞的準(zhǔn)確率，但同時(shí)增長(zhǎng)了分詞的時(shí)間。趙陽(yáng)陽(yáng)等[4]提出了地址要素識(shí)別機(jī)制的地名地址分詞算法，該算法依托整詞二分詞典并通過(guò)設(shè)置當(dāng)下詞屬性的方式，得到了比較好的分詞精度，但同樣以犧牲運(yùn)行時(shí)間為代價(jià)。馮永等[16]提出了基于自適應(yīng)中文分詞和近似SVM的文本分類算法，能很好的適應(yīng)不同的預(yù)料規(guī)劃問(wèn)題，取得了不錯(cuò)的成績(jī)。但基于二元統(tǒng)計(jì)模型的分詞算法計(jì)算復(fù)雜，與上述三種基于機(jī)械分詞方法的算法相比，計(jì)算量大，比較耗時(shí)。而中文地址分詞與整個(gè)中文分詞領(lǐng)域相比，語(yǔ)料之簡(jiǎn)單并不能相提并論，故本文方法選用了比較簡(jiǎn)單的機(jī)械分詞法。比較常見(jiàn)的機(jī)械分詞法有正向最大匹配法（Forward Maximum Matching Method，F(xiàn)MM）和逆向最大匹配法。因?yàn)榈刂肺谋静淮嬖谥鞲沙煞趾笾玫膯?wèn)題[7]，故在比較簡(jiǎn)單的FMM算法原理的基礎(chǔ)上進(jìn)行改進(jìn)。為了進(jìn)一步提高地址分詞的精度和速度，本文先根據(jù)標(biāo)志詞把地址數(shù)據(jù)進(jìn)行粗分，在在粗分結(jié)果的基礎(chǔ)上，以每個(gè)分詞的長(zhǎng)度自適應(yīng)與標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)進(jìn)行匹配。

1 基于地址要素標(biāo)志的正向自適應(yīng)長(zhǎng)度匹配分詞模型設(shè)計(jì)

一條地址數(shù)據(jù)中往往包含幾種不同級(jí)別的地址要素，把這些不同級(jí)別的地址要素記作：A級(jí)代表省，B級(jí)代表市，C級(jí)代表區(qū)，D級(jí)代表街道，E級(jí)代表門牌，F(xiàn)級(jí)代表縣，G級(jí)代表鄉(xiāng)鎮(zhèn)，H級(jí)代表村，I級(jí)代表建筑或單位名稱，J表示其他，如表1所示。結(jié)構(gòu)化的地址模型的組合方式主要包括兩類三組：第一類，省下各區(qū)域ABCDE，ABFGHJ；第二類，直轄市或特別行政區(qū)BCDE。

表1 地址要素級(jí)別

由于地址數(shù)據(jù)里的地址要素往往包含不同級(jí)別的地址標(biāo)志詞，如省、市、路、街、弄、號(hào)、村、鎮(zhèn)、鄉(xiāng)等，本文提出了基于地址要素標(biāo)志的正向自適應(yīng)匹配中文地址分詞算法。自適應(yīng)在于將常規(guī)的FMM中的機(jī)器詞典中的最長(zhǎng)詞條的長(zhǎng)度替換為通過(guò)按照地址要素標(biāo)志切分后所得的字符數(shù)組各項(xiàng)的長(zhǎng)度，以減少匹配次數(shù)，提高匹配速度。本文提出的算法是建立在構(gòu)建的存儲(chǔ)標(biāo)準(zhǔn)地址數(shù)據(jù)集的標(biāo)準(zhǔn)地址庫(kù)的基礎(chǔ)上。該數(shù)據(jù)庫(kù)存放了全國(guó)各地的地址要素，主要信息包括地址要素的名稱（如上海市、黃浦區(qū)等）和級(jí)別（如省A，市B）等相關(guān)信息，用于本文分詞算法的標(biāo)準(zhǔn)匹配庫(kù)。本文的分詞算法先通過(guò)設(shè)置地址要素的常規(guī)地址標(biāo)志，如省，以及一些特殊字符作標(biāo)志，如#代表幾號(hào)樓等，對(duì)地址數(shù)據(jù)進(jìn)行粗分；然后對(duì)粗分后的字符數(shù)組進(jìn)行正向自適應(yīng)長(zhǎng)度的匹配操作。具體流程如下。

（1）輸入一條中文地址字符串S。

（2）split (S) — str[n]，規(guī)則：按照制定的標(biāo)志詞，如果標(biāo)志詞在句首，不做切分；如果兩個(gè)標(biāo)志詞間距為零，只在后面的標(biāo)志詞進(jìn)行切分；若兩標(biāo)志詞距離大于0，每個(gè)標(biāo)志詞都進(jìn)行切分。

（3）將粗切分得到的字符數(shù)組的第i項(xiàng)先按str[i]的長(zhǎng)度與標(biāo)準(zhǔn)庫(kù)地址要素formData進(jìn)行匹配；若匹配成功，則將formData作為一個(gè)地址要素，存到輸出數(shù)組out中，以及formData所代表的級(jí)別存到級(jí)別數(shù)組level中，并將str[i]中與formData匹配成功的字符移除，退出本循環(huán)；若不成功，取str[i]的前str[i].length-1個(gè)與標(biāo)準(zhǔn)庫(kù)匹配，以此類推，直到匹配成功將formData及級(jí)別分別存入out和level中，或匹配結(jié)束仍未成功，直接把str[i]存到輸出數(shù)組out中。

（4）loop（ 3），直至粗切分?jǐn)?shù)組str每一項(xiàng)都處理完畢。

其中，（3）與（4）過(guò)程算法偽代碼如下：

2 缺失的地址要素補(bǔ)充與地址要素重組方法

對(duì)于不完整的地址數(shù)據(jù)，由于我國(guó)第二級(jí)行政區(qū)域的名稱是唯一的，其對(duì)應(yīng)的第一級(jí)行政區(qū)域也是唯一的，所以省略第一級(jí)行政區(qū)域并不影響書寫地址的正確性，但如果省略第二級(jí)或第三極行政區(qū)域，則不一定正確理解地址信息[10]。對(duì)于一份殘缺地址，可以根據(jù)當(dāng)前地址要素的parentid找到父級(jí)地址要素。為實(shí)現(xiàn)補(bǔ)充缺失地址要素的功能以及統(tǒng)一同一個(gè)地點(diǎn)不同的表述，設(shè)計(jì)了自定義的地址匹配規(guī)則庫(kù)。

自定義的地址匹配規(guī)則庫(kù)用于補(bǔ)充缺失的地址要素，并把以建筑物或單位名稱（I級(jí)）書寫的地址要素轉(zhuǎn)化成D級(jí)地址要素（街道名稱）。因此該庫(kù)包含的信息主要為地址要素名稱，父級(jí)地址要素名稱parentid等信息。相同位置的D級(jí)地址要素和I級(jí)地址要素具有相同的parentid，因此可以完成兩種類型的地址要素間的轉(zhuǎn)化。同時(shí)，根據(jù)parentid，也能找到缺失的地址要素。

缺失地址要素的補(bǔ)充是通過(guò)上一章分詞所得到的數(shù)組，從后往前與自定義的地址匹配規(guī)則庫(kù)匹配，找個(gè)parentid，進(jìn)而找到父級(jí)地址要素，具體流程如下。

（1）從out數(shù)組從后往前查找，若parentid為null，向前移一個(gè)分詞查找。

（2）若parentid不為null，若parentId僅有一個(gè)，則可唯一確定一個(gè)地址；若parentid為多個(gè)，則拿搜索到的父級(jí)地址要素與out數(shù)組的前一個(gè)地址要素匹配，若匹配成功，則可以唯一確定一個(gè)地址，若匹配失?。ㄔ?地址要素漏項(xiàng)較多；原因2書寫錯(cuò)誤，對(duì)于原因2尚未處理），則查找搜索到的父級(jí)地址要素的父級(jí)地址要素，與out數(shù)組的前一個(gè)地址要素的前一個(gè)要素匹配，直至匹配成功，唯一確定一個(gè)地址，或out數(shù)組已經(jīng)遍歷完成，則地址無(wú)法唯一確定，對(duì)該地址不做處理。

3 結(jié)果

3.1 基于標(biāo)志詞的正向自適應(yīng)長(zhǎng)度匹配的地址分詞算法

本文以本院病案首頁(yè)中的地址數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)。為了驗(yàn)證本文所提的分詞算法的效果，從病案首頁(yè)的地址數(shù)據(jù)中隨機(jī)選取1000條數(shù)據(jù)，分為10、100和1000條3組進(jìn)行實(shí)驗(yàn)，并與FMM算法作對(duì)比，以觀察批量處理地址數(shù)據(jù)時(shí)，隨之輸入數(shù)據(jù)的增多，算法在性能上的變化。實(shí)驗(yàn)結(jié)果如表2所示。

表2 本文算法與最大長(zhǎng)度匹配算法性能比較

從表2可以看出，本文所提出的算法，隨著輸入的變化，不論是在地址分詞的精度還是在消耗的時(shí)間上，與FMM算法相比，都有一定程度的提高。這兩種方法差異的主要原因在于，首先從精度上講，中文地址與普通中文文本相比，其語(yǔ)料非常簡(jiǎn)單，而且常常有明顯的標(biāo)志詞，通過(guò)劃分標(biāo)志詞的方法比按照中文復(fù)雜的語(yǔ)料直接匹配斷句更為精確；從時(shí)間上講，按照標(biāo)志詞作預(yù)劃分，其結(jié)果本身比較接近真實(shí)情況，而且每輪匹配長(zhǎng)度的初始值按照預(yù)劃分分項(xiàng)的長(zhǎng)度，不僅使匹配長(zhǎng)度自適應(yīng)，與FMM算法每次按最大長(zhǎng)度匹配相比也減少了匹配次數(shù)，進(jìn)而節(jié)省時(shí)間。

3.2 缺失地址要素補(bǔ)充方法

圖1為本文缺失地址要素補(bǔ)充方法得到的幾條實(shí)驗(yàn)結(jié)果。從結(jié)果可以看出，能夠唯一確定一條地址記錄的數(shù)據(jù)（如1、2、4、5），缺失的地址要素能夠很好的補(bǔ)充完整；對(duì)于數(shù)據(jù)3，由于地址要素缺失嚴(yán)重，無(wú)法唯一確定一條地址，在該算法對(duì)此數(shù)據(jù)是不做處理的（寧愿地址具有模糊也不應(yīng)該補(bǔ)進(jìn)去一個(gè)可能錯(cuò)誤的要素），但為了顯示實(shí)驗(yàn)效果，說(shuō)明不作處理的原因，數(shù)據(jù)3實(shí)驗(yàn)結(jié)果仍保留了多條匹配記錄。對(duì)于數(shù)據(jù)4，補(bǔ)充的結(jié)果出現(xiàn)兩個(gè)“號(hào)”，在今后的工作中對(duì)“號(hào)”與“弄”等諸如此類的差別需要做的更精細(xì)，也需要更多的數(shù)據(jù)支撐。

圖1 缺失地址要素補(bǔ)充方法結(jié)果

4 結(jié)語(yǔ)

本文通過(guò)對(duì)電子病歷中的文本數(shù)據(jù)分析，提取出相對(duì)正確的地址，大大減少臨床數(shù)據(jù)的重復(fù)錄入，極大提高了臨床工作效率、方便了數(shù)據(jù)上報(bào)和統(tǒng)計(jì)分析。同時(shí)補(bǔ)充了不完整的地址，完成地址標(biāo)準(zhǔn)化的工作，極大提高了數(shù)據(jù)質(zhì)量，給臨床信息錄入和科研工作打下堅(jiān)實(shí)基礎(chǔ)。不僅如此，該研究成果對(duì)于電子病歷中其他數(shù)據(jù)的標(biāo)化具有重要指導(dǎo)價(jià)值。