黃　明　林家駿　方　楠

1(華東理工大學(xué)信息科學(xué)與工程學(xué)院　上海 200237)2(上海104研究所　上海 200032)

?

基于加權(quán)有限狀態(tài)機(jī)的電話號(hào)碼規(guī)范解析

黃明1,2林家駿1方楠2

1(華東理工大學(xué)信息科學(xué)與工程學(xué)院上海 200237)2(上海104研究所上海 200032)

摘要針對(duì)社會(huì)數(shù)據(jù)處理中,電話號(hào)碼數(shù)據(jù)寫(xiě)法多樣，難以有效分析利用的問(wèn)題，提出一種基于競(jìng)爭(zhēng)性有限狀態(tài)機(jī)的電話號(hào)碼解析與規(guī)范化方法，并提出相應(yīng)的基于負(fù)反饋的訓(xùn)練算法。經(jīng)過(guò)實(shí)際應(yīng)用檢驗(yàn)，該規(guī)范化方法的處理速度和正確率都能夠滿(mǎn)足應(yīng)用要求，有效解決了在存在輸入差異性的場(chǎng)景下，對(duì)電話號(hào)碼進(jìn)行解析與規(guī)范化的問(wèn)題，具有較好的工程實(shí)用性。

關(guān)鍵詞有限狀態(tài)機(jī)電話號(hào)碼文本解析規(guī)范化負(fù)反饋訓(xùn)練

0引言

隨著社會(huì)步入大數(shù)據(jù)時(shí)代，涉及聯(lián)絡(luò)通信的郵政、電信和物流等行業(yè)都積累了大量的社會(huì)數(shù)據(jù)有待分析。在人們的社會(huì)行為數(shù)據(jù)中，電話(手機(jī))號(hào)碼正扮演著越來(lái)越重要的角色，它已成為個(gè)人身份的一種重要識(shí)別碼，起著標(biāo)識(shí)人員、串聯(lián)行為的作用，在社會(huì)人員活動(dòng)軌跡描繪、行為分析中具有重要意義。

在郵政、海關(guān)和快遞企業(yè)的業(yè)務(wù)數(shù)據(jù)中存在大量跨省、跨境的電話號(hào)碼，這些號(hào)碼寫(xiě)法多樣、歧義性強(qiáng)，給數(shù)據(jù)比對(duì)分析工作帶來(lái)了很大挑戰(zhàn)。當(dāng)前國(guó)內(nèi)多采用正則表達(dá)式對(duì)電話號(hào)碼的進(jìn)行規(guī)范化處理，在號(hào)碼種類(lèi)多、格式差異大的情況下極易產(chǎn)生誤差。本文提出了一種基于競(jìng)爭(zhēng)性有限狀態(tài)機(jī)和統(tǒng)計(jì)知識(shí)庫(kù)的電話號(hào)碼規(guī)范化算法，并提出了相應(yīng)的基于負(fù)反饋的參數(shù)訓(xùn)練方法，有效解決了包含國(guó)際/國(guó)內(nèi)區(qū)號(hào)的電話號(hào)碼規(guī)范化問(wèn)題，并應(yīng)用在了實(shí)際生產(chǎn)環(huán)境中，經(jīng)歷了實(shí)踐檢驗(yàn)，取得了較好的效果。

1問(wèn)題綜述

目前，對(duì)電話號(hào)碼的規(guī)范處理在國(guó)內(nèi)依然是一個(gè)難題，在大數(shù)據(jù)處理中尤為突出，即使公安、郵政等民生部門(mén)也難以有效分析利用手頭的電話號(hào)碼數(shù)據(jù)資源?，F(xiàn)實(shí)中，社會(huì)機(jī)構(gòu)獲取的電話號(hào)碼數(shù)據(jù)普遍存在以下問(wèn)題：

(1) 號(hào)碼串格式寫(xiě)法多樣化

由于個(gè)人寫(xiě)法習(xí)慣和單位錄入標(biāo)準(zhǔn)不同，同一電話號(hào)碼依據(jù)是否分節(jié)和分節(jié)方式存在多種寫(xiě)法。如手機(jī)號(hào)就存在不分節(jié)、“3-4-4”和“4-4-3”幾種常見(jiàn)寫(xiě)法。

(2) 國(guó)內(nèi)城市區(qū)號(hào)解析

國(guó)內(nèi)電話號(hào)碼的前幾位或中間幾位可能是國(guó)內(nèi)城市區(qū)號(hào)，需要與主號(hào)部分區(qū)別提取出來(lái)。城市區(qū)號(hào)長(zhǎng)度為2位或3位，與主號(hào)部分可能分隔也可能連在一起，有些數(shù)據(jù)還會(huì)在區(qū)號(hào)前加0。

(3) 國(guó)際區(qū)號(hào)解析

海關(guān)、郵政等部門(mén)的業(yè)務(wù)數(shù)據(jù)中包含大量國(guó)際電話號(hào)碼，這些號(hào)碼多以國(guó)際區(qū)號(hào)開(kāi)頭，各國(guó)的國(guó)際區(qū)號(hào)長(zhǎng)度從1位到3位不等，與后續(xù)號(hào)碼部分可能分隔也可能連在一起，一些國(guó)家(如美國(guó))的數(shù)據(jù)習(xí)慣在國(guó)際區(qū)號(hào)前加“+”號(hào)或“00”。

(4) 分機(jī)號(hào)解析

許多國(guó)內(nèi)電話號(hào)碼中都含有分機(jī)號(hào)，即超過(guò)當(dāng)?shù)毓潭娫掗L(zhǎng)度的末尾部分。大部分情況下，分機(jī)號(hào)都會(huì)通過(guò)分隔符與主機(jī)號(hào)分隔開(kāi)來(lái)。

因此，電話號(hào)碼解析是一項(xiàng)精細(xì)復(fù)雜的任務(wù)，既要從前端解析可能存在的國(guó)際區(qū)號(hào)和國(guó)內(nèi)區(qū)號(hào)，又要在后端解析可能存在的分機(jī)號(hào)，再加上要識(shí)別固定電話、手機(jī)號(hào)、國(guó)內(nèi)/國(guó)際長(zhǎng)途號(hào)碼的各種寫(xiě)法格式，往往一條號(hào)碼就存在多條解析路線，需要結(jié)合匹配程度和出現(xiàn)概率挑選出最佳解析路線。

當(dāng)前常用的電話號(hào)碼解析技術(shù)有全文檢索文本分析器[1]和正則表達(dá)式[2]，前者可用于提取號(hào)碼片段和檢索比對(duì)，但是無(wú)法將號(hào)碼串轉(zhuǎn)化為規(guī)范化的數(shù)據(jù)結(jié)構(gòu)。后者則一來(lái)對(duì)于存在的多種可能解析方案的電話號(hào)碼，難以進(jìn)行有效的評(píng)價(jià)和取舍；二來(lái)在數(shù)據(jù)質(zhì)量不高的情況下要窮舉各種可能情況，會(huì)造成正則表達(dá)式過(guò)于復(fù)雜。

加權(quán)的有限狀態(tài)機(jī)[3～5]能夠較好地解決字符串識(shí)別中的多義性問(wèn)題。特別是基于馬爾可夫鏈[6,7]的概率統(tǒng)計(jì)有限狀態(tài)機(jī)[8]已成為當(dāng)今自然語(yǔ)言處理的主流技術(shù)。然而該技術(shù)主要根據(jù)前后字詞出現(xiàn)的條件概率來(lái)選取解析路徑，而電話號(hào)碼中大部分位置上的數(shù)字都是平均分布的，難以直接套用。因此，基于加權(quán)有限狀態(tài)機(jī)的技術(shù)思路，本人提出了競(jìng)爭(zhēng)性的有限狀態(tài)機(jī)，對(duì)可能的解析方案進(jìn)行整體的比較和推選，從而較好地解決了電話號(hào)碼的識(shí)別與解析問(wèn)題。

2解決方案

我們的目的是設(shè)計(jì)一種高效、可行的算法機(jī)制，對(duì)大量現(xiàn)實(shí)數(shù)據(jù)中的電話號(hào)碼進(jìn)行識(shí)別處理，提取出原始號(hào)碼中的國(guó)際區(qū)號(hào)、國(guó)內(nèi)城市區(qū)號(hào)、本機(jī)號(hào)和分機(jī)號(hào)等屬性，將原始號(hào)碼轉(zhuǎn)換為規(guī)范化的數(shù)據(jù)結(jié)構(gòu)，以便于后續(xù)的分析利用。

競(jìng)爭(zhēng)性有限狀態(tài)機(jī)的構(gòu)想是在解析輸入串時(shí)，若遇到分歧路線，則遞歸或并行地按照分歧路線分別行進(jìn)，獨(dú)立計(jì)算分值，最終比較分值，選取分值最高的一條路徑作為輸入串的最優(yōu)解析方案。

應(yīng)用有限狀態(tài)機(jī)對(duì)電話號(hào)碼進(jìn)行解析時(shí)，先設(shè)置一個(gè)初始適宜系數(shù)p0，解析中若滿(mǎn)足了特定匹配或篩選條件，通過(guò)了對(duì)應(yīng)解析路段(例如匹配出以中國(guó)國(guó)際區(qū)號(hào)86開(kāi)頭)，則認(rèn)為獲取了額外的信息，需對(duì)當(dāng)前解析路徑上的適宜系數(shù)進(jìn)行加權(quán)。設(shè)當(dāng)前路徑上的適宜系數(shù)為p，加權(quán)路段ek上的加權(quán)值為pk，則加權(quán)后的適宜系數(shù)為p+pk。

在電話號(hào)碼解析中，最終能否識(shí)別出一個(gè)合理的手機(jī)或座機(jī)號(hào)是衡量一條解析路徑是否正確的重要依據(jù)。因此，我們針對(duì)不同的終結(jié)狀態(tài)(是否識(shí)別出有效號(hào)碼)設(shè)定不同的基準(zhǔn)分值，當(dāng)一條解析路徑達(dá)到終結(jié)狀態(tài)時(shí)，設(shè)當(dāng)前適宜系數(shù)為p，終結(jié)狀態(tài)基準(zhǔn)分值為a，則路徑得分為：

S=pa

需要注意的是在國(guó)際/國(guó)內(nèi)區(qū)號(hào)解析路段，由于各區(qū)號(hào)分布不均勻，在確定適宜系數(shù)的加權(quán)值時(shí)應(yīng)考慮匹配區(qū)號(hào)的出現(xiàn)概率。設(shè)區(qū)號(hào)解析路段ek的基礎(chǔ)加權(quán)值為pk，匹配區(qū)號(hào)的出現(xiàn)概率為pc，則加權(quán)值為pkpc。我們通過(guò)統(tǒng)計(jì)國(guó)際/國(guó)內(nèi)區(qū)號(hào)在真實(shí)數(shù)據(jù)中的出現(xiàn)概率準(zhǔn)備了兩張區(qū)號(hào)概率表，例如，經(jīng)統(tǒng)計(jì)出現(xiàn)最多的幾個(gè)境外國(guó)際區(qū)號(hào)是1(美國(guó)，占25%)、81(日本，占15%)和82(韓國(guó)，占12%)?；诟怕时?，區(qū)號(hào)解析過(guò)程實(shí)際上可以分解為包含多分路的兩步解析過(guò)程，如圖1所示。

圖1　區(qū)號(hào)解析

設(shè)有限狀態(tài)機(jī)中的一條解析路徑為Γ，計(jì)算適宜系數(shù)加權(quán)值涉及到匹配項(xiàng)出現(xiàn)概率的解析路段構(gòu)成路段集W，一般解析路段構(gòu)成路段集T。初始適宜系數(shù)為p0，路徑上一段解析路段的ek的適宜系數(shù)加權(quán)值為pk。終結(jié)狀態(tài)f對(duì)應(yīng)一個(gè)基準(zhǔn)分值af。設(shè)S(Γ)為路徑的最終得分，則有：

設(shè)輸入電話號(hào)碼可能的解析路徑集為P，通過(guò)競(jìng)爭(zhēng)性有限狀態(tài)機(jī)找到的最優(yōu)解析路徑Γm應(yīng)滿(mǎn)足：

S(Γm)=Max(S(Γ))?！蔖

在實(shí)際應(yīng)用中，我們構(gòu)造如圖2所示的競(jìng)爭(zhēng)性有限狀態(tài)機(jī)，輸入電話號(hào)碼在經(jīng)過(guò)替換非數(shù)字字符、縮并空格等預(yù)處理后進(jìn)入有限狀態(tài)機(jī)進(jìn)行解析，解析完成后輸出規(guī)范化的數(shù)據(jù)結(jié)構(gòu)。

圖2　電話號(hào)碼解析狀態(tài)機(jī)

關(guān)于該有限狀態(tài)機(jī)有以下幾點(diǎn)說(shuō)明：

1) 在狀態(tài)0根據(jù)輸入號(hào)碼是否分節(jié)分為兩條完全不同的解析路徑。這是因?yàn)殡娫捥?hào)碼的分節(jié)本身就包含一定的辨識(shí)信息，從分節(jié)中提取出的號(hào)碼部分可信度更高。

2) 狀態(tài)2、狀態(tài)12表示成功解析出了國(guó)內(nèi)手機(jī)號(hào)。包含國(guó)際區(qū)號(hào)的國(guó)外號(hào)碼中只有美國(guó)號(hào)碼以1開(kāi)頭，且總長(zhǎng)度為10位；國(guó)內(nèi)電話號(hào)碼只有北京區(qū)號(hào)以1開(kāi)頭，總長(zhǎng)度為10位。因此，以1開(kāi)頭，有效位數(shù)11位可以作為當(dāng)前國(guó)內(nèi)手機(jī)號(hào)的判別條件。

3) 從一個(gè)狀態(tài)開(kāi)始，以“/”為開(kāi)始端的路徑為排它路徑，即當(dāng)前狀態(tài)如果滿(mǎn)足該路徑則跳過(guò)其它解析路徑，以減少計(jì)算量。

4) 從一個(gè)狀態(tài)開(kāi)始，以“○”為開(kāi)始端的路徑構(gòu)成一個(gè)互斥的分組，即當(dāng)前狀態(tài)如果滿(mǎn)足分組中的一條路徑則跳過(guò)組中其它路徑，以減少計(jì)算量。但組外路徑依然需要遍歷。

3反饋訓(xùn)練

有限狀態(tài)機(jī)的初始參數(shù)根據(jù)經(jīng)驗(yàn)設(shè)定，為提升有限狀態(tài)機(jī)解析規(guī)范電話號(hào)碼的準(zhǔn)確率，需根據(jù)應(yīng)用反饋對(duì)系統(tǒng)參數(shù)進(jìn)行校正，對(duì)自動(dòng)機(jī)進(jìn)行調(diào)優(yōu)。在實(shí)際應(yīng)用場(chǎng)景中，電話號(hào)碼規(guī)范結(jié)果的正確與否最終只能依靠業(yè)務(wù)人員的知識(shí)經(jīng)驗(yàn)來(lái)判斷，需要耗費(fèi)一定人工，因此大范圍的收集應(yīng)用反饋不現(xiàn)實(shí)。相比較而言，用戶(hù)對(duì)于號(hào)碼規(guī)范解析中出現(xiàn)的錯(cuò)誤較為敏感，比較容易建立一套錯(cuò)誤用例的收集、匯總機(jī)制。因此，我們?cè)O(shè)計(jì)了一種基于負(fù)反饋的有限狀態(tài)機(jī)優(yōu)化算法，通過(guò)對(duì)出現(xiàn)解析錯(cuò)誤的用例進(jìn)行分析學(xué)習(xí)，進(jìn)而調(diào)節(jié)參數(shù)，提升性能[9,10]。

該算法的主要思想是：對(duì)于每個(gè)錯(cuò)誤用例，算出其當(dāng)前錯(cuò)誤解析路徑和正確解析路徑間最終分值的差值?；诓钪?，提升正確解析路徑上各個(gè)路段的適宜系數(shù)加權(quán)值，降低錯(cuò)誤解析路徑上各個(gè)路段的適宜系數(shù)加權(quán)值。由于采用基于負(fù)反饋的調(diào)優(yōu)，我們假設(shè)除錯(cuò)誤用例外的其他用例都得到了正確解析。因此，為了維持系統(tǒng)的穩(wěn)定性，我們基于各路段的通過(guò)概率(易在系統(tǒng)運(yùn)行中統(tǒng)計(jì))對(duì)適宜系數(shù)加權(quán)值進(jìn)行調(diào)節(jié)：通過(guò)概率高的認(rèn)為是經(jīng)過(guò)驗(yàn)證的普遍情形，適宜系數(shù)加權(quán)值調(diào)節(jié)幅度小；通過(guò)概率低的認(rèn)為是作用于當(dāng)前錯(cuò)例的特殊情形，適宜系數(shù)加權(quán)值調(diào)節(jié)幅度大。

以圖3為例，算法具體描述如下：

圖3　反饋訓(xùn)練

錯(cuò)誤路徑的整體通過(guò)概率為：

對(duì)正確路徑上每條路段的適宜系數(shù)加權(quán)值進(jìn)行放大，設(shè)路段為ei，則放大增量為：

4實(shí)際測(cè)試

該技術(shù)應(yīng)用于實(shí)際生產(chǎn)環(huán)境中，搭配200余條的國(guó)際區(qū)號(hào)概率知識(shí)庫(kù)和300余條的國(guó)內(nèi)區(qū)號(hào)概率知識(shí)庫(kù)，配合曙光八核服務(wù)器，日均處理電話號(hào)碼數(shù)據(jù)700多萬(wàn)條。經(jīng)測(cè)試，單線程每秒可處理號(hào)碼1.3萬(wàn)條，處理速度能夠滿(mǎn)足實(shí)際應(yīng)用的需要。

如表1所示，應(yīng)有本文所述的負(fù)反饋訓(xùn)練算法優(yōu)化有限狀態(tài)機(jī)，經(jīng)過(guò)幾輪訓(xùn)練后，電話號(hào)碼規(guī)范解析的正確率顯著提高，每日?qǐng)?bào)告錯(cuò)例數(shù)大幅減少。在目前的實(shí)際應(yīng)用中，解析正確率超過(guò)99.9%，被報(bào)告的錯(cuò)例基本上也都是在缺少輔助信息的情況下，人工也難以判別的輸入號(hào)碼。

表1　反饋效果表

以20萬(wàn)條國(guó)內(nèi)電話號(hào)碼，2萬(wàn)條國(guó)際電話號(hào)碼作為測(cè)試數(shù)據(jù)，分別運(yùn)用文本分析器、正則表達(dá)式和本文所述方法進(jìn)行解析測(cè)試。測(cè)試結(jié)果如圖4所示。顯然，與文本分析器、正則表達(dá)式技術(shù)相比，本文所述的電話號(hào)碼解析方法在正確率上具有明顯優(yōu)勢(shì)，具有實(shí)用價(jià)值。

圖4　測(cè)試對(duì)比

5結(jié)語(yǔ)

本文提出了一種基于競(jìng)爭(zhēng)性有限狀態(tài)機(jī)的電話號(hào)碼解析與規(guī)范化方法，并提出了相應(yīng)的基于負(fù)反饋的訓(xùn)練算法，有效解決了在存在輸入差異性的場(chǎng)景下，對(duì)電話號(hào)碼進(jìn)行解析與規(guī)范化的問(wèn)題。該規(guī)范化方法在實(shí)際生產(chǎn)環(huán)境中投入了應(yīng)用，經(jīng)過(guò)實(shí)踐檢驗(yàn)，取得了良好的效果，處理速度和正確率都達(dá)到了應(yīng)用要求，充分證明了該方法具有工程實(shí)用性。

參考文獻(xiàn)

[1] 義元鵬,陳啟安.基于Lucene的中文分析器分詞性能比較研究[J].計(jì)算機(jī)工程,2012(22):279-282.

[2] 鄧凱元,姜磊.正則表達(dá)式匹配引擎性能分析[J].計(jì)算機(jī)與現(xiàn)代化,2011(7):105-107.

[3]MehryarM,FernandoP,MichaelRiley.Weightedfinite-statetransducersinspeechrecognition[J].ComputerSpeechandLanguage,2002,16(1):69-88.

[4] 郭宇弘,黎塔,肖業(yè)鳴,等.基于加權(quán)有限狀態(tài)機(jī)的動(dòng)態(tài)匹配詞圖生成算法[J].電子與信息學(xué)報(bào),2014,36(1):140-146.

[5] 張倩,郭嗣琮.基于有限狀態(tài)機(jī)和Trie數(shù)的分級(jí)地址模型[J].計(jì)算機(jī)應(yīng)用,2013,33(3):854-857.

[6]BaumLE,PetrieT.Statisticalinferenceofprobabilisticfunctionsoffinitestatemarkovchains[J].TheAnnalsofMathematicalStatistics,1966,37(6):1554-1563.

[7]BaumLE,EagonJA.AninequalitywithapplicationstostatisticalestimationforprobabilisticfunctionsofMarkovprocessesandtoamodelforecology[J].BulletinoftheAmericanMathematicalSociety,1967,73(3):360-363.

[8]JohnLafferty,AndrewMcCallum,FernandoPereira.Conditionalrandomfields:probabilisticmodelsforsegmentingandlabelingsequencedata[C]//ProcofICML,2001.

[9] 姚全珠,張杰.基于數(shù)據(jù)挖掘的搜索引擎技術(shù)[J].計(jì)算機(jī)應(yīng)用研究,2006(11):29-30.

[10] 溫銳,朱巧明,李培峰.HMM和負(fù)反饋模型在詞性標(biāo)注中的應(yīng)用[J].蘇州大學(xué)學(xué)報(bào):自然科學(xué)版,2005(3):39-42.

STANDARDISATION AND ANALYSIS OF PHONE NUMBERS BASED ON WEIGHTED FSM

Huang Ming1,2Lin Jiajun1Fang Nan2

1(College of Information,East China University of Science and Technology,Shanghai 200237,China)2(Shanghai 104 Research Institute,Shanghai 200032,China)

AbstractWe proposed a competitive FSM-based phone numbers analysis and standardisation method in light of the problem that in social data processing the phone numbers data are written in various section formats and are difficult to analyse and utilise, and presented the corresponding negative feedback-based training algorithm as well. By verification with practical applications, this standardisation approach can meet the application requirements in both processing speed and accuracy, this effectively solves the problem of analysing and standardising phone numbers under the circumstance with input differences, and has preferable project applicability.

KeywordsFinite-state machine (FSM)Phone numberText analyseStandardisationNegative feedback training

收稿日期：2015-01-09。黃明，工程師，主研領(lǐng)域：數(shù)據(jù)挖掘。林家駿，教授。方楠，工程師。

中圖分類(lèi)號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.06.019