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

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

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

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

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

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

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

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

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

2.1 行名抽取

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

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

2.2 省市名抽取

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

2.3 尾名清理

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

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

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

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

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

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

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

3.1 逐層尋路規(guī)則

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

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

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

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

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

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

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

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

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

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

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

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

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