尋路算法在中文金融機構(gòu)名匹配中的應(yīng)用

摘 要：金融機構(gòu)網(wǎng)點多，命名規(guī)則不一致，名稱錄入時的縮減文字、級別混淆等非規(guī)范操作，都嚴(yán)重影響業(yè)務(wù)辦理效率。在對大量銀行機構(gòu)名分析之后，本文采用分支限界策略[3]，來得到這個將機構(gòu)名定位的尋路算法（PFA，Pathfinding algorithm）。基本思路是：將中文金融機構(gòu)名分成銀行名、省名、市名和尾部混合名四部分，逐層剝離，去類型關(guān)鍵字，然后分別匹配來獲取一系列原始匹配矩陣系數(shù)，再根據(jù)分支限界思想逐步修正匹配矩陣，最終得到最優(yōu)解。該應(yīng)用不使用數(shù)據(jù)庫，純程序語言處理，匹配精確高。

關(guān)鍵詞：機構(gòu)名匹配; 分段匹配; 組織機構(gòu)名稱識別; 尋路算法; 分支限界策略

中圖分類號：TP391

The application of PFA on matching Chinese financial institution names

YIN Chi-dong1，HUANG Sheng-ye2，E Zhi-feng3

(1.College of Information Science and Engineering， Hunan University， Changsha， 410082， China;

2.College of Information Science and Engineering， Hunan University， Changsha， 410082， China;

3.Department of Science and Technology， Changsha Branch， Guangdong Development Bank， Changsha， 410005， China)

Abstract：There are many factors that affect work efficiency seriously such as various branches，different naming rules，inputing omission，level confusion. After analyzing numerous names，the paper adopts Branch and Bound Strategy[3] to obtain the Pathfinding algorithm of defining institution name.The basic idea is as following: 1.Dividing the complete institution name into bank name，province name，city name and the rear name. 2.Extracting each name as above in order. 3.Removing all type keywords. 4.Matching each part to get some raw matrix coefficients. 5.Adjusting these matrix coefficients step by step according to Branch and Bound Strategy to get the optimal solution. The application does not involve database. Data is processed by programme language completely. Matching degree is high.

Key words：matching financial institution names; segment matching;distinguish of organization names; Pathfinding algorithm; Branch and Bound Strategy

1 引 言

當(dāng)前，銀行業(yè)務(wù)中的機構(gòu)名匹配一直都是靠人工核對的，工作效率低，很多銀行甚至不愿接相關(guān)業(yè)務(wù)。個別銀行采取了一些積極措施，在存在一定錯誤率的代價下，大大提高了工作效率。銀行數(shù)據(jù)的海量性，使錯誤量幾何級數(shù)般放大。所以現(xiàn)有的解決辦法亟待完善。本文課題正是應(yīng)這種需求而產(chǎn)生，更具體說是作為銀行“代付保費業(yè)務(wù)系統(tǒng)”的核心算法單獨展開的。

我們先來探討一下需求的必要性和需求到底是什么。比方說，保險公司交給銀行一份數(shù)百人的賠付名單，名單上賠付對象的開戶行填寫情況紛亂繁多，存在各種縮寫和混淆情況，又沒有機構(gòu)編號（保險公司沒有記錄）。銀行根據(jù)這份名單轉(zhuǎn)賬前必須將這些開戶行名稱準(zhǔn)確地對應(yīng)上它們的標(biāo)準(zhǔn)名稱，否則轉(zhuǎn)賬就會出錯。本文需求由此產(chǎn)生。除了將名單上的機構(gòu)名正確地一一對應(yīng)上它們的標(biāo)準(zhǔn)名稱，還有兩個需求點必須告知讀者。第一，考慮到安裝和使用方便，不能使用數(shù)據(jù)庫服務(wù)器，那就完全只能使用程序語言，借助算法來實現(xiàn)匹配。第二，所有關(guān)鍵詞庫要便于維護，最好的選擇是以記事本文件形式存放在程序包內(nèi)。程序運行的時候，自動從相應(yīng)位置讀取需要的數(shù)據(jù)。第三，名單是Excel文件的電子形式，反饋出來的信息也必須是Excel文件。

在機構(gòu)名識別領(lǐng)域，國內(nèi)外的通用做法都是建立龐大的數(shù)據(jù)庫，借助各種算法對識別對象進行訓(xùn)練、配對、糾正，來達到目標(biāo)。這個領(lǐng)域已經(jīng)有了很多成果，也有很多的不足，還在不斷完善中。作為機構(gòu)名識別的子領(lǐng)域，機構(gòu)名匹配相對簡單很多。因為中英文的書寫差異性、縮寫差異性，國外相關(guān)研究對本文的幫助意義不大，本文沒有深入研究國外成果，只專注于中文金融機構(gòu)名匹配的研究。

中文金融機構(gòu)名匹配領(lǐng)域，國內(nèi)應(yīng)用現(xiàn)狀是：部分銀行采用全名剪枝后求最長公共子串匹配算法（LCSMA，longest common substring match algorithm），即剪除象“省”、“縣”、“分行”、“儲蓄所”等類型關(guān)鍵詞后剩余子串合并為一個字符串再進行最長公共子串匹配。多數(shù)銀行仍舊靠人工核對。研究者們還提出一種算法，就是全關(guān)鍵詞窮舉匹配算法（EMAKA，exhaustive matching all keywords algorithm）。這種算法理論簡單，需要建立龐大的地名關(guān)鍵詞數(shù)據(jù)庫來為之服務(wù)，效率低，其可靠度依賴于關(guān)鍵詞庫的豐富度，實用起來有很大障礙。但其優(yōu)點是毋庸置疑的：在界定前邊界的時候，依靠關(guān)鍵詞庫搜索匹配，準(zhǔn)確無誤，效率高，且這部分匹配工作所需要的關(guān)鍵詞數(shù)比較少，基本不需要維護。

2 算法應(yīng)用前提的設(shè)計

本文依據(jù)HNC（概念層次網(wǎng)絡(luò)）理論[1]，設(shè)計了30個銀行類關(guān)鍵詞庫（共155個詞）、4個地名類型或機構(gòu)類型關(guān)鍵詞庫（共43個詞）、4個地名關(guān)鍵詞庫（共101個詞），借以將中文金融機構(gòu)名（簡稱機構(gòu)名）分解成銀行名（簡稱行名）、省名、市名、尾部混合名（簡稱尾名）四層[4]。分解出的各部分必須具有唯一性。因此，分解過程，可說是至關(guān)重要。然后，行名對行名、省名對省名、市名對市名、尾名對尾名，逐個匹配，得到各自獨立的初始匹配系數(shù)。最后，根據(jù)分支限界策略設(shè)計出本文的核心算法----尋路算法。以下為該算法應(yīng)用前，必須考慮的幾點。

2.1 行名抽取

由于各大銀行存在多種叫法，如工行、工商銀行、中國工商銀行、中國工商銀行股份有限公司等。所以行名抽取應(yīng)適應(yīng)模糊匹配需求，必須建立工行、農(nóng)行等各自單獨的關(guān)鍵詞庫[6]。

幾類特殊銀行（如：農(nóng)村合作銀行、村鎮(zhèn)銀行、信用社等）可根據(jù)行名一致的特點，按行名歸類統(tǒng)一建詞庫，這樣既大大降低了建詞庫的工作量，也便于邏輯處理。

2.2 省市名抽取

省市名相對數(shù)量有限，且基本不存在多種稱呼情況，不必模糊匹配，所以應(yīng)分別建省名詞庫和市名詞庫，并且依據(jù)這兩個詞庫抽取出的省名和市名必須有效截除“省”、“自治區(qū)”、“市”、“自治州”等類型關(guān)鍵詞[4]（如“建行湖南省岳陽市華容支行”，截取省名關(guān)鍵詞“湖南”和市名關(guān)鍵詞“岳陽”，剩余子串中去掉“省”、“市”）。要點：如果根據(jù)詞庫截除后，后半子串緊跟著以“縣”、“自治縣”、“區(qū)”開頭，則抽取出的省市名置空，子串返回被抽取前狀態(tài)[7]。

2.3 尾名清理

尾名數(shù)量龐大、雜亂無序，無法采用前述方案，建立有效詞庫來抽取。因此，本文對尾名先進行清理，過濾掉“縣”、“區(qū)”、“村”、“分行”、“支行”、“儲蓄所”等類型名[4]，然后直接參與匹配。

需要注意的是，存在這樣的情況：對于如“南縣”、“道縣”和“衡南縣”、“通道縣”等地名，既需要保留前者中的“縣”字，又需要去掉后者中的“縣”字。因而本文研究項目設(shè)計了兩個特殊地名詞庫專門進行這樣的篩選處理[7]。

2.4 初始匹配系數(shù)矩陣獲取規(guī)則

2.4.1遵循行對行、省對省、市對市、尾對尾的匹配規(guī)則。

2.4.2前三層匹配系數(shù)矩陣的元素值只能為-1，、0、1。-1表示匹配雙方都有值，且不相匹配；0表示雙方至少有一方為空；1表示雙方均不為空，且匹配成功。這樣，就能分別獲得行名匹配矩陣（Aij）、省名匹配矩陣（Bij）、市名匹配矩陣（Cij）三個矩陣。

2.4.3尾對尾匹配獲取兩個匹配系數(shù)矩陣，第一個是根據(jù)尾部驅(qū)動原則[2]計算出末端雙字匹配矩陣（Dij），元素值只能為-1、0、1。這里需要說明一下，由于我省不存在單字地名，而三字以上地名只取末尾兩字也是具有比較意義的，因此這里采用末端雙字來匹配。第二個是尾部最長公共子串長度矩陣（Eij）。矩陣E與矩陣A、B、C、D維度相同，元素值為大于或等于0的自然數(shù)。

3 基于分支限界策略的尋路算法

3.1 逐層尋路規(guī)則

3.1.1根據(jù)Bayes法則[5]，我們確定了潛在地名前邊界確定原則和尾部驅(qū)動原則[2]。結(jié)合邏輯要求，總結(jié)以下幾點：

3.1.1.1行名匹配值為1或0時，省名匹配值保留，否則改為-1。

3.1.1.2省名匹配值為1或0時，市名匹配值保留，否則改為-1。

3.1.1.3市名匹配值為1或0時，末端雙字匹配值保留，否則改為-1。

3.1.1.4末端雙字匹配值為1時，尾部最長公共子串長度值保留，否則改為0。

3.1.1.5比較尾部最長公共子串長度值中的非零值，行最大值的位置坐標(biāo)就對應(yīng)上了匹配結(jié)果。存在多個行最大值相等的情況，那這幾個值的坐標(biāo)對應(yīng)的記錄都列入匹配結(jié)果人工校正待選項，用不同顏色標(biāo)記提醒。

3.1.2由此，本文設(shè)計了如下五條尋路規(guī)則：

規(guī)則一后續(xù)規(guī)則中的X、Y指代A、B、B'、C、C'、D、D'、E、E’，X、Y的選取按指定順序。

規(guī)則二X集合元素值大于或等于0時，Y集合對應(yīng)元素值保留，否則改為-1，返回Y'集合。

規(guī)則三X集合元素值大于0時，Y集合對應(yīng)元素值保留，否則改為0，返回Y'集合。

規(guī)則四X集合元素值若全為0，則剔除X集合。

規(guī)則五判斷X集合（矩陣）元素值行最大值，則返回其坐標(biāo)。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文