對(duì)火車站身份證號(hào)碼校核的分析(數(shù)學(xué)建模與算法設(shè)計(jì))

1、中國(guó)礦業(yè)大學(xué)全校通識(shí)選修課數(shù)學(xué)建模與算法設(shè)計(jì)課程論文題目：對(duì)火車站身份證號(hào)碼校核的分析成績(jī)：評(píng)閱人：姓名 學(xué)院 化工學(xué)院 班級(jí) 能源化學(xué)工程14-1 學(xué)號(hào) 我的郵箱是：ziqiang_xu時(shí)間：摘要計(jì)算機(jī)在生活中扮演著越來(lái)越重要的角色，并且已經(jīng)為人類的進(jìn)步做出過(guò)巨大貢獻(xiàn)。比如航空航天、軍事、天氣預(yù)測(cè)、工程模擬等等諸多領(lǐng)域。計(jì)算機(jī)作為高速計(jì)算模擬設(shè)備，除了需要先進(jìn)的硬件制造工藝之外，還需要優(yōu)秀的軟件的配合。而軟件的核心是算法，高性能的算法才能合理的調(diào)動(dòng)有效的資源。老師在上課的時(shí)候講了一個(gè)關(guān)于火車站身份證核查的問(wèn)題，我覺得有更好的方法來(lái)進(jìn)行查詢。并且估計(jì)目前所采用的正是這樣的方法。中國(guó)居民身份證號(hào)

2、碼是中國(guó)公民的識(shí)別碼，居民身份證是國(guó)家法定的證明個(gè)人身份的證件。中國(guó)的人口規(guī)模大概是十四億。關(guān)鍵詞：算法；查詢；身份證號(hào)碼；分段；結(jié)構(gòu)；地址碼；出生日期碼；順序碼；校驗(yàn)碼；模擬；python；C語(yǔ)言；計(jì)算機(jī)；火車站。正文1、 問(wèn)題描述：在火車站，為了掌握乘客的真實(shí)信息，工作人員需要對(duì)乘客的身份進(jìn)行核查，一般是對(duì)身份證進(jìn)行核查，并使用儀器進(jìn)行掃描識(shí)別。需要讀取身份證號(hào)碼，并從身份證數(shù)據(jù)庫(kù)里獲取照片和更加詳細(xì)的信息。中國(guó)有近十四億人口，如果逐一進(jìn)行比對(duì)查詢，將會(huì)有一個(gè)十分龐大的計(jì)算量產(chǎn)生。試分析使用枚舉比對(duì)方法，并指出它的弊端，并提出一個(gè)更好的核對(duì)辦法。2、 問(wèn)題分析與解決方案：（1）枚舉法：大家

3、都十分熟悉，在進(jìn)行身份證掃描的時(shí)候，是一個(gè)識(shí)別終端讀取身份證信息，然后傳到工作人員的電腦里；再上傳到國(guó)家的身份證服務(wù)站，服務(wù)站反饋乘客的信息，如是否存在此條數(shù)據(jù)以及乘客照片；工作人員再進(jìn)一步進(jìn)行核實(shí)。（考慮到信息安全，全國(guó)公民的信息被完全下載在本地電腦的可能性非常低）對(duì)十四億組數(shù)據(jù)進(jìn)行逐一比對(duì)的方法是簡(jiǎn)單的，但是絕對(duì)是不可取的。這種方法對(duì)計(jì)算機(jī)資源占用太大。根據(jù)概率論的知識(shí)，x表示核查一個(gè)人的身份證號(hào)碼需要進(jìn)行的數(shù)據(jù)比對(duì)的次數(shù)，則x的期望E（x）=7億。為了進(jìn)行進(jìn)一步的驗(yàn)證7億次查詢的計(jì)算量的巨大，由于不會(huì)使用c語(yǔ)言，我使用python語(yǔ)言對(duì)查詢過(guò)程進(jìn)行模擬。先隨機(jī)產(chǎn)生7000萬(wàn)條數(shù)據(jù)（由于p

4、ython語(yǔ)言的設(shè)計(jì)，一個(gè)元組不能容納7億條數(shù)據(jù)，故此處只生成了7000萬(wàn)條數(shù)據(jù)，并執(zhí)行十次用以模擬對(duì)七億條數(shù)據(jù)進(jìn)行檢索比對(duì)。）python是解釋性的腳本編程語(yǔ)言，在性能上弱于C語(yǔ)言，但是單純從打印性能上有數(shù)據(jù)表明大約是2比3的比例，參考地址見參考文獻(xiàn)： 預(yù)測(cè)C語(yǔ)言和Python在檢索的性能上比值不會(huì)超過(guò)3倍，以此由圖2的運(yùn)行結(jié)果看可以得出一個(gè)粗略估計(jì)的檢索比對(duì)耗時(shí)：以當(dāng)前硬件配置（如圖3）進(jìn)行檢索查詢的話，至少會(huì)耗費(fèi)大約70秒的時(shí)間。 考慮到實(shí)際情況下數(shù)據(jù)的處理是在云端進(jìn)行，故云端計(jì)算機(jī)的性能是咱們普通PC不可比擬的，進(jìn)行一次數(shù)據(jù)檢索的時(shí)間必定會(huì)大大減少。這是不可否認(rèn)的，但是還應(yīng)該充分考慮到

5、：同一時(shí)間線上會(huì)有多個(gè)查詢請(qǐng)求并行發(fā)生，即全國(guó)各地都在進(jìn)行著身份證的校核。這又會(huì)進(jìn)一步增加這一算法的的復(fù)雜度，就算云端服務(wù)器的性能十分強(qiáng)勁，也是有很大的壓力的，很有可能會(huì)對(duì)其他業(yè)務(wù)造成干擾，甚至導(dǎo)致宕機(jī)這樣的重大事故發(fā)生。源代碼圖片（圖1）運(yùn)行結(jié)果（圖2）計(jì)算機(jī)配置截圖（圖3）(2) 分段檢索法：要高效率地對(duì)身份證號(hào)碼進(jìn)行檢索校核，必須要深入了解身份證號(hào)碼的規(guī)律。通過(guò)查詢百度百科，可以了解到：居民身份證號(hào)碼，根據(jù)中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn) GB 11643-1999中有關(guān)公民身份號(hào)碼的規(guī)定，公民身份號(hào)碼是特征組合碼，由十七位數(shù)字本體碼和一位數(shù)字校驗(yàn)碼組成。排列順序從左至右依次為：六位數(shù)字地址碼，八

6、位數(shù)字出生日期碼，三位數(shù)字順序碼和一位數(shù)字校驗(yàn)碼。 居民身份證是國(guó)家法定的證明公民個(gè)人身份的有效證件。關(guān)于地址碼：第一、二位表示?。ㄗ灾螀^(qū)、直轄市、特別行政區(qū)）；第三、四位表示市（地級(jí)市、自治州、盟及國(guó)家直轄市所屬市轄區(qū)和縣的匯總碼）。其中，01-20，51-70表示省直轄市；21-50表示地區(qū)（自治州、盟）；第五、六位表示縣（市轄區(qū)、縣級(jí)市、旗）。01-18表示市轄區(qū)或地區(qū)（自治州、盟）轄縣級(jí)市；21-80表示縣（旗）；81-99表示省直轄縣級(jí)市。關(guān)于出生日期碼：（身份證號(hào)碼第七位到第十四位）表示編碼對(duì)象出生的年、月、日，其中年份用四位數(shù)字表示，年、月、日之間不用分隔符。例如：1981年05

7、月11日就用19810511表示。關(guān)于順序碼：（身份證號(hào)碼第十五位到十七位）地址碼所標(biāo)識(shí)的區(qū)域范圍內(nèi)，對(duì)同年、月、日出生的人員編定的順序號(hào)。其中第十七位奇數(shù)分給男性，偶數(shù)分給女性。關(guān)于校驗(yàn)碼： 作為尾號(hào)的校驗(yàn)碼，是由號(hào)碼編制單位按統(tǒng)一的公式計(jì)算出來(lái)的，如果某人的尾號(hào)是0-9，都不會(huì)出現(xiàn)X，但如果尾號(hào)是10，那么就得用X來(lái)代替，因?yàn)槿绻?0做尾號(hào)，那么此人的身份證就變成了19位，而19位的號(hào)碼違反了國(guó)家標(biāo)準(zhǔn)，并且中國(guó)的計(jì)算機(jī)應(yīng)用系統(tǒng)也不承認(rèn)19位的身份證號(hào)碼。是羅馬數(shù)字的10，用X來(lái)代替10，可以保證公民的身份證符合國(guó)家標(biāo)準(zhǔn)?，F(xiàn)在假設(shè)工作人員通過(guò)設(shè)備獲取了一位乘客的身份證號(hào)碼為： 500382

8、 19970116 465 81 地址碼（前六位）：500382 重慶市合川區(qū)（155萬(wàn)人口，2013年數(shù)據(jù)）2 出生日期碼（7-14位）： 1997年01月16日3 順序碼（15-17位）： 4654 校驗(yàn)碼（最后一位）： 8此處的分段檢索法是在枚舉法的基礎(chǔ)上進(jìn)行改進(jìn)的，在枚舉法之前進(jìn)行幾步操作，分層進(jìn)行檢索，逐步地縮小檢索范圍。在服務(wù)器的數(shù)據(jù)庫(kù)里，如果單方面地從查找速度上考慮的話，為身份證信息加入合適的層級(jí)，比如性別，校驗(yàn)碼等，可以進(jìn)一步地提高查找速度。即咱們經(jīng)常聽說(shuō)的樹狀結(jié)構(gòu)，有多個(gè)層級(jí)，對(duì)信息進(jìn)行有條理的分類。示意圖如圖4所示：圖4第一步：根據(jù)前六位號(hào)碼先確定了地址，如戶籍所在地是重慶

9、市合川區(qū)。檢索地址碼耗時(shí)，如果不進(jìn)行分層處理大約幾萬(wàn)條，一萬(wàn)條數(shù)據(jù)在我的電腦上的運(yùn)算耗時(shí)是6微秒，幾乎可以忽略不計(jì)。第二步：即使不再繼續(xù)縮小范圍而是直接進(jìn)行檢索，枚舉150萬(wàn)條信息，（普通的區(qū)縣是沒有這么多人口的，有這么多人口是少數(shù)情況，故在普通狀況下檢索量會(huì)更小一些）在與之前一樣的硬件條件下耗時(shí)約0.133秒，如圖5所示。這與之前的70秒相比較，是一個(gè)非常大的提升，極大地提高了查找效率，如果更進(jìn)一步進(jìn)行更加嚴(yán)密的分類，即使是一般的手持設(shè)備也能勝任這項(xiàng)任務(wù)。150萬(wàn)條數(shù)據(jù)檢索模擬結(jié)果（圖5）3、 結(jié)論： 更優(yōu)的計(jì)算機(jī)算法能夠更加節(jié)省計(jì)算機(jī)硬件資源，更加高效地為我們工作。研究算法不是誰(shuí)的專利，就

10、算作為一個(gè)非專業(yè)研究算法的人，對(duì)一些算法進(jìn)行學(xué)習(xí)和研究是很有益處的。在現(xiàn)實(shí)生活中，一些算法問(wèn)題的有效解決也將節(jié)約大量的資源。所以研究算法是十分有必要的，在此，向算法研究者致敬，我將努力在我所在的領(lǐng)域做出成績(jī)，并在需要的時(shí)候，向算法研究者尋求幫助，也將做出有效的反饋供研究者更好地進(jìn)行分析。參考文獻(xiàn)：1、 Python和C語(yǔ)言打印性能對(duì)比：2、重慶市合川區(qū)人口數(shù)據(jù)來(lái)源：【注：關(guān)于身份證的相關(guān)標(biāo)準(zhǔn)是由網(wǎng)絡(luò)上的資料整理所得，Python和C語(yǔ)言的性能對(duì)比也是引用了網(wǎng)友的帖子，并沒有進(jìn)行嚴(yán)格的測(cè)試?！俊靖剑篜ython數(shù)據(jù)查詢模擬代碼身份證號(hào)碼樣本：一個(gè)虛假身份證號(hào)和隨機(jī)數(shù)進(jìn)行加和運(yùn)算得來(lái)程序一（可自由

11、輸入不不大于7000萬(wàn)的枚舉條數(shù)，主要用于測(cè)試小查詢量耗時(shí)）：from time import *from random import *list_7000=x=int(input('輸入模擬的數(shù)據(jù)枚舉條數(shù)n')num=0for i in range(n): h=int(100000*random() list_7000.append(x+h)start=time()print(str(start)+'n')for i in list_7000: if i num=num+1pri

12、nt('已經(jīng)找到'+str(num)+'個(gè)n')endtime=time()print(str(endtime)+'n')print('總共耗時(shí)'+str(endtime-start)+'秒')程序二（模擬7億次數(shù)據(jù)查詢）：from time import *from random import *list_7000=xum=0for i in range(70000000): h=int(100000*random() list_7000.append(x+h)start=time()print(str(start)for j i