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

黃　明　林家駿　方　楠

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

?

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

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

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

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

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

0引言

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

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

1問題綜述

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

(1) 號碼串格式寫法多樣化

由于個人寫法習慣和單位錄入標準不同，同一電話號碼依據(jù)是否分節(jié)和分節(jié)方式存在多種寫法。如手機號就存在不分節(jié)、“3-4-4”和“4-4-3”幾種常見寫法。

(2) 國內(nèi)城市區(qū)號解析

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

(3) 國際區(qū)號解析

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

(4) 分機號解析

許多國內(nèi)電話號碼中都含有分機號，即超過當?shù)毓潭娫掗L度的末尾部分。大部分情況下，分機號都會通過分隔符與主機號分隔開來。

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

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

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

2解決方案

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

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

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

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

S=pa

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

圖1　區(qū)號解析

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

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

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

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

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

關(guān)于該有限狀態(tài)機有以下幾點說明：

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

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

3) 從一個狀態(tài)開始，以“/”為開始端的路徑為排它路徑，即當前狀態(tài)如果滿足該路徑則跳過其它解析路徑，以減少計算量。

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

3反饋訓練

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

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

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

圖3　反饋訓練

錯誤路徑的整體通過概率為：

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

4實際測試

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

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

表1　反饋效果表

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

圖4　測試對比

5結(jié)語

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

參考文獻

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

[2] 鄧凱元,姜磊.正則表達式匹配引擎性能分析[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)機的動態(tài)匹配詞圖生成算法[J].電子與信息學報,2014,36(1):140-146.

[5] 張倩,郭嗣琮.基于有限狀態(tài)機和Trie數(shù)的分級地址模型[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].計算機應(yīng)用研究,2006(11):29-30.

[10] 溫銳,朱巧明,李培峰.HMM和負反饋模型在詞性標注中的應(yīng)用[J].蘇州大學學報:自然科學版,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ù)挖掘。林家駿，教授。方楠，工程師。

中圖分類號TP391

文獻標識碼A

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