基于標志詞的正向自適應長度匹配的地址分詞算法與缺失地址要素補充方法

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

上海健康醫學院附屬第六人民醫院東院 計算機中心，上海 201306

引言

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

結構化的地址數據指地址按照統一的結構存儲，比如按照省、市、區、街道等的結構存儲。而目前醫院電子病歷中的地址數據結構混亂，往往存在地址信息不全面，大量的別名、簡稱，特殊符號（如#、-、/等）等問題。解決這些問題，實現非結構化地址數據向結構化地址數據轉換，就需要將特殊符號轉化成常規的文本信息，比如#表示號樓，然后將地址數據進行分詞并記錄每個分詞的地址能級，并根據分詞結果補充缺失的地址要素，并根據自定義的地址匹配規則庫將別名、簡稱等標準化。

在以上所提要做的工作中，關鍵在于地址分詞和缺失地址要素的補充。中文分詞是目前很多學者的研究方向，主流的分詞方法主要分為兩類：機械分詞法[7-14]和統計分詞法[15-21]。由于地址數據里的地址要素常常會包含一些標志詞，如省、市、區等，劉韜[9]提出了設立切分標志法對地址數據進行分詞。但在實際的地址錄入過程中，很多時候或省略標志詞，如上海普陀曹楊街道，就會造成分詞結果的不準確。馬照亭等[10]在中文自動分詞詞庫的基礎上，添加了《中國地名用詞庫》中的通用地名詞條和一個城市中的專用地名或地址詞條，并為地址要素掛接“標準名稱”和“地址級別”兩個屬性字段，提高了分詞的準確率，但同時增長了分詞的時間。趙陽陽等[4]提出了地址要素識別機制的地名地址分詞算法，該算法依托整詞二分詞典并通過設置當下詞屬性的方式，得到了比較好的分詞精度，但同樣以犧牲運行時間為代價。馮永等[16]提出了基于自適應中文分詞和近似SVM的文本分類算法，能很好的適應不同的預料規劃問題，取得了不錯的成績。但基于二元統計模型的分詞算法計算復雜，與上述三種基于機械分詞方法的算法相比，計算量大，比較耗時。而中文地址分詞與整個中文分詞領域相比，語料之簡單并不能相提并論，故本文方法選用了比較簡單的機械分詞法。比較常見的機械分詞法有正向最大匹配法（Forward Maximum Matching Method，FMM）和逆向最大匹配法。因為地址文本不存在主干成分后置的問題[7]，故在比較簡單的FMM算法原理的基礎上進行改進。為了進一步提高地址分詞的精度和速度，本文先根據標志詞把地址數據進行粗分，在在粗分結果的基礎上，以每個分詞的長度自適應與標準數據庫進行匹配。

1 基于地址要素標志的正向自適應長度匹配分詞模型設計

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

表1 地址要素級別

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

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

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

（3）將粗切分得到的字符數組的第i項先按str[i]的長度與標準庫地址要素formData進行匹配；若匹配成功，則將formData作為一個地址要素，存到輸出數組out中，以及formData所代表的級別存到級別數組level中，并將str[i]中與formData匹配成功的字符移除，退出本循環；若不成功，取str[i]的前str[i].length-1個與標準庫匹配，以此類推，直到匹配成功將formData及級別分別存入out和level中，或匹配結束仍未成功，直接把str[i]存到輸出數組out中。

（4）loop（ 3），直至粗切分數組str每一項都處理完畢。

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

2 缺失的地址要素補充與地址要素重組方法

對于不完整的地址數據，由于我國第二級行政區域的名稱是唯一的，其對應的第一級行政區域也是唯一的，所以省略第一級行政區域并不影響書寫地址的正確性，但如果省略第二級或第三極行政區域，則不一定正確理解地址信息[10]。對于一份殘缺地址，可以根據當前地址要素的parentid找到父級地址要素。為實現補充缺失地址要素的功能以及統一同一個地點不同的表述，設計了自定義的地址匹配規則庫。

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

缺失地址要素的補充是通過上一章分詞所得到的數組，從后往前與自定義的地址匹配規則庫匹配，找個parentid，進而找到父級地址要素，具體流程如下。

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

（2）若parentid不為null，若parentId僅有一個，則可唯一確定一個地址；若parentid為多個，則拿搜索到的父級地址要素與out數組的前一個地址要素匹配，若匹配成功，則可以唯一確定一個地址，若匹配失敗（原因1地址要素漏項較多；原因2書寫錯誤，對于原因2尚未處理），則查找搜索到的父級地址要素的父級地址要素，與out數組的前一個地址要素的前一個要素匹配，直至匹配成功，唯一確定一個地址，或out數組已經遍歷完成，則地址無法唯一確定，對該地址不做處理。

3 結果

3.1 基于標志詞的正向自適應長度匹配的地址分詞算法

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

表2 本文算法與最大長度匹配算法性能比較

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

3.2 缺失地址要素補充方法

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

圖1 缺失地址要素補充方法結果

4 結語

本文通過對電子病歷中的文本數據分析，提取出相對正確的地址，大大減少臨床數據的重復錄入，極大提高了臨床工作效率、方便了數據上報和統計分析。同時補充了不完整的地址，完成地址標準化的工作，極大提高了數據質量，給臨床信息錄入和科研工作打下堅實基礎。不僅如此，該研究成果對于電子病歷中其他數據的標化具有重要指導價值。