基于信用卡的BIN的算法優(yōu)化

吳鵬洋

摘 要：針對(duì)銀行的信用卡BIN數(shù)據(jù)的存儲(chǔ)、增刪和搜索提出一種建立在十叉樹(shù)結(jié)構(gòu)的高效處理方法及其相關(guān)算法。該算法具有易用、節(jié)省存儲(chǔ)、快速查詢和可擴(kuò)展的應(yīng)用特征，解決了信用卡BIN數(shù)據(jù)的存儲(chǔ)和搜索效率難題，為信用卡BIN的規(guī)則變化和拓展提供了一種可用的技術(shù)解決方案。

關(guān)鍵詞：信用卡；存儲(chǔ)；十叉樹(shù)；卡BIN搜索

1 引言

當(dāng)前中國(guó)的信息化發(fā)展很快，信用卡的應(yīng)用范圍和占零售額的比例不斷上升。在信用卡的交易中對(duì)信用卡的校驗(yàn)、存儲(chǔ)和快速搜索的要求越來(lái)越高，以前交易處理系統(tǒng)簡(jiǎn)單地按卡號(hào)順序全匹配的方式在大數(shù)據(jù)量的信用卡的系統(tǒng)里越來(lái)越不適應(yīng)。快速有效地存儲(chǔ)和搜索方式能有效提升單位時(shí)間交易筆數(shù)，從而提升系統(tǒng)處理性能。

2 信用卡數(shù)據(jù)的算法搜索與增刪

本文在二叉樹(shù)的基礎(chǔ)上，針對(duì)信用卡行業(yè)的數(shù)據(jù)（通常卡的數(shù)據(jù)主要指卡號(hào)或卡BIN，其中卡號(hào)長(zhǎng)度為13-19位；卡BIN -Bank Identification Number，簡(jiǎn)稱 BIN，指信用卡卡號(hào)前 6 位、用來(lái)區(qū)別發(fā)卡銀行或機(jī)構(gòu)的一套信用卡卡號(hào)編碼[3，4]。這些卡數(shù)據(jù)雖然長(zhǎng)度不一樣，但數(shù)據(jù)特性，處理方式類似，可互相參考，文后以卡BIN為例展開(kāi)描述）的存儲(chǔ)、增刪、搜索而提供的一種建立在樹(shù)結(jié)構(gòu)基礎(chǔ)上的高效、易用、可擴(kuò)展的算法，并兼顧了空間和時(shí)間的效率。解決了通常情況下大量卡或卡BIN段的存儲(chǔ)空間以及搜索效率難題，也提供了在未來(lái)信用卡BIN規(guī)則變化下可靈活拓展的方式，提高了整體的可應(yīng)用性。這些數(shù)據(jù)的特點(diǎn)是都為0-9的數(shù)字組成，數(shù)字重復(fù)性高[5]。本處理方式提供一種高效、易用、靈活的結(jié)構(gòu)來(lái)存儲(chǔ)大量的數(shù)據(jù)（如卡BIN），利用樹(shù)結(jié)構(gòu)的搜索優(yōu)勢(shì)來(lái)達(dá)到快速搜索的目的。主要包括十叉樹(shù)的創(chuàng)建、十叉樹(shù)的搜索以及十叉樹(shù)的增刪三個(gè)部分（以下以卡BIN來(lái)說(shuō)明）：

2.1 十叉樹(shù)的結(jié)構(gòu)

樹(shù)其實(shí)是N（N>=0）個(gè)節(jié)點(diǎn)的有限集合。十叉樹(shù)可以看成是二叉樹(shù)的應(yīng)用拓展，是滿足有且僅有一個(gè)根節(jié)點(diǎn)，除根節(jié)點(diǎn)之外其余節(jié)點(diǎn)被分成10個(gè)互不相交元素的有限集合，其中每個(gè)集合又是一個(gè)十叉樹(shù)。

2.2 十叉樹(shù)的創(chuàng)建

置根節(jié)點(diǎn)為（0，0），對(duì)于每一個(gè)卡BIN從根節(jié)點(diǎn)出發(fā)，每個(gè)節(jié)點(diǎn)定義為（data，flag），其中data對(duì)應(yīng)卡BIN中的一位數(shù)據(jù)。

flag為標(biāo)志位，卡BIN中最后一位數(shù)據(jù)置標(biāo)志位為1，其余為0。創(chuàng)建的流程是讀取每個(gè)卡BIN數(shù)字，然后根據(jù)每一位數(shù)字去判斷節(jié)點(diǎn)是否已存在于樹(shù)上，如果已存在標(biāo)記且讀下一個(gè)卡BIN數(shù)字，否則繼續(xù)往下按照樹(shù)的結(jié)構(gòu)來(lái)創(chuàng)建，由于卡BIN是數(shù)字 集，因此對(duì)于每個(gè)父節(jié)點(diǎn)都只存在[0，9]之間最多十棵子樹(shù)，則創(chuàng)建完后必然是十叉樹(shù)。

2.3 十叉樹(shù)的搜索

對(duì)于每一個(gè)卡BIN，對(duì)十叉樹(shù)采用自根向下結(jié)合樹(shù)結(jié)構(gòu)的 遍歷算法，根據(jù)卡BIN數(shù)字的位數(shù)來(lái)搜索樹(shù)的層次，依次匹配樹(shù)上每個(gè)節(jié)點(diǎn)（data，flag），如果匹配則以當(dāng)前點(diǎn)為根節(jié)點(diǎn)繼續(xù) 往下搜索下一位卡BIN數(shù)字，直到匹配到卡BIN最后一位數(shù)字 在十叉樹(shù)上的標(biāo)志位為1，則搜索成功，否則即為失敗。

2.4 十叉樹(shù)的增刪十叉樹(shù)的增加

即在搜索的基礎(chǔ)上，針對(duì)卡BIN的每一位數(shù)字遍歷十叉樹(shù)，匹配每一個(gè)節(jié)點(diǎn)（data，flag），當(dāng)匹配不上時(shí)，按照樹(shù)結(jié)構(gòu)建立節(jié)點(diǎn)，直到匹配到最后一位，并置該標(biāo)志位為1；十叉樹(shù)的刪除即在搜索的基礎(chǔ)上，針對(duì)卡BIN的每一位數(shù)字遍歷十叉樹(shù)，匹配每一個(gè)節(jié)點(diǎn)（data，flag），當(dāng)匹配不上時(shí)，退出。直到匹配到最后一位，并置該標(biāo)志位為0。

3 算法比較

當(dāng)前信用卡數(shù)據(jù)的存儲(chǔ)和搜索通常采用數(shù)據(jù)直接原樣存儲(chǔ)，假設(shè)集合內(nèi)有N個(gè)數(shù)據(jù)，則需要N個(gè)空間存儲(chǔ)，由于卡數(shù)量N較大，因此存儲(chǔ)空間的要求較高；其次，從數(shù)組中查找卡數(shù)據(jù)的效率很低，在最壞情況下需要進(jìn)行N次比較。以40萬(wàn)卡數(shù)據(jù)存儲(chǔ)，如果數(shù)據(jù)原樣存儲(chǔ)需要查找的卡號(hào)在第20萬(wàn)個(gè)數(shù)據(jù)，匹配到數(shù)據(jù)查找次數(shù)為例：數(shù)據(jù)原樣存儲(chǔ)20萬(wàn)次十叉樹(shù)與數(shù)據(jù)的長(zhǎng)度有關(guān)，如卡數(shù)據(jù)是234768，查找最多6次；通過(guò)此實(shí)例可以看出在這種情況下十叉樹(shù)查找次數(shù)遠(yuǎn)遠(yuǎn)少于數(shù)據(jù)原樣存儲(chǔ)次數(shù)。

4 綜合與總結(jié)

本文提出和研究采用十叉樹(shù)的結(jié)構(gòu)及其遍歷算法實(shí)現(xiàn)信用卡BIN的存儲(chǔ)和快速匹配在時(shí)空上具有明顯的優(yōu)勢(shì)，概述如下：（1）由于金融行業(yè)數(shù)據(jù)膨大且復(fù)雜，傳統(tǒng)的數(shù)字?jǐn)?shù)據(jù)采用容器來(lái)存儲(chǔ)，不同的數(shù)據(jù)（如卡BIN）是存放于不同的容器中的，而采用十叉樹(shù)來(lái)存儲(chǔ)的方式是按BIN的位數(shù)字存儲(chǔ)，這樣不同卡BIN的相同的位數(shù)字有很大一部分是占用相同的空間，因此存儲(chǔ)比傳統(tǒng)方式小很多。可以大量節(jié)省存儲(chǔ)。（2）十叉樹(shù)的搜索效率跟基數(shù)N無(wú)關(guān)，而是與數(shù)據(jù)（如卡BIN）的長(zhǎng)度相關(guān)，不管多大的數(shù)據(jù)最多只會(huì)比較（卡BIN）的長(zhǎng)度次數(shù)，在大數(shù)據(jù)量的情況下，性能和效果更加突出，更適應(yīng)越來(lái)越快的信用卡的發(fā)展。

十叉樹(shù)的可拓展性較強(qiáng)。由于是按位數(shù)字存儲(chǔ)，因此修改、增加或刪除數(shù)據(jù)（如卡BIN）時(shí)，只要對(duì)位數(shù)字節(jié)點(diǎn)進(jìn)行操作即可，不用修改基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，這樣就節(jié)省了大量的計(jì)算資源。在基于卡BIN是[0，9]的數(shù)字前提下，滿足卡BIN長(zhǎng)度及 規(guī)則業(yè)務(wù)的任何變化。

[參考文獻(xiàn)]

[1]郭芳.三種三叉樹(shù)存儲(chǔ)結(jié)構(gòu)的比較[J].安康師專學(xué)報(bào)，999（1）.

[2]劉洋.一種統(tǒng)一的二叉樹(shù)結(jié)構(gòu)遍歷算法及其實(shí)現(xiàn)[J].贛南師范學(xué)院學(xué)報(bào)，2004（3）.

[3]中國(guó)人民銀行.中華人民共和國(guó)金融行業(yè)標(biāo)準(zhǔn)《信用卡卡片規(guī)范》（JWT0052-2009）[S].2009-07-01.

[4]中國(guó)人民銀行.中華人民共和國(guó)金融行業(yè)標(biāo)準(zhǔn)《信用卡發(fā)卡行標(biāo)識(shí)代碼及卡號(hào)》（JR/T0008-2000）[S].2001-01-01.

[5]全國(guó)信用卡辦公室.信用卡磁條信息格式和使用規(guī)范《中國(guó)信用卡》[S].2001.