对火车站身份证号码校核的分析(数学建模与算法设计)

1、中国矿业大学全校通识选修课数学建模与算法设计课程论文题目：对火车站身份证号码校核的分析成绩：评阅人：姓名 学院 化工学院 班级 能源化学工程14-1 学号 我的邮箱是：ziqiang_xu时间：摘要计算机在生活中扮演着越来越重要的角色，并且已经为人类的进步做出过巨大贡献。比如航空航天、军事、天气预测、工程模拟等等诸多领域。计算机作为高速计算模拟设备，除了需要先进的硬件制造工艺之外，还需要优秀的软件的配合。而软件的核心是算法，高性能的算法才能合理的调动有效的资源。老师在上课的时候讲了一个关于火车站身份证核查的问题，我觉得有更好的方法来进行查询。并且估计目前所采用的正是这样的方法。中国居民身份证号

2、码是中国公民的识别码，居民身份证是国家法定的证明个人身份的证件。中国的人口规模大概是十四亿。关键词：算法；查询；身份证号码；分段；结构；地址码；出生日期码；顺序码；校验码；模拟；python；C语言；计算机；火车站。正文1、 问题描述：在火车站，为了掌握乘客的真实信息，工作人员需要对乘客的身份进行核查，一般是对身份证进行核查，并使用仪器进行扫描识别。需要读取身份证号码，并从身份证数据库里获取照片和更加详细的信息。中国有近十四亿人口，如果逐一进行比对查询，将会有一个十分庞大的计算量产生。试分析使用枚举比对方法，并指出它的弊端，并提出一个更好的核对办法。2、 问题分析与解决方案：（1）枚举法：大家

3、都十分熟悉，在进行身份证扫描的时候，是一个识别终端读取身份证信息，然后传到工作人员的电脑里；再上传到国家的身份证服务站，服务站反馈乘客的信息，如是否存在此条数据以及乘客照片；工作人员再进一步进行核实。（考虑到信息安全，全国公民的信息被完全下载在本地电脑的可能性非常低）对十四亿组数据进行逐一比对的方法是简单的，但是绝对是不可取的。这种方法对计算机资源占用太大。根据概率论的知识，x表示核查一个人的身份证号码需要进行的数据比对的次数，则x的期望E（x）=7亿。为了进行进一步的验证7亿次查询的计算量的巨大，由于不会使用c语言，我使用python语言对查询过程进行模拟。先随机产生7000万条数据（由于p

4、ython语言的设计，一个元组不能容纳7亿条数据，故此处只生成了7000万条数据，并执行十次用以模拟对七亿条数据进行检索比对。）python是解释性的脚本编程语言，在性能上弱于C语言，但是单纯从打印性能上有数据表明大约是2比3的比例，参考地址见参考文献： 预测C语言和Python在检索的性能上比值不会超过3倍，以此由图2的运行结果看可以得出一个粗略估计的检索比对耗时：以当前硬件配置（如图3）进行检索查询的话，至少会耗费大约70秒的时间。 考虑到实际情况下数据的处理是在云端进行，故云端计算机的性能是咱们普通PC不可比拟的，进行一次数据检索的时间必定会大大减少。这是不可否认的，但是还应该充分考虑到

5、：同一时间线上会有多个查询请求并行发生，即全国各地都在进行着身份证的校核。这又会进一步增加这一算法的的复杂度，就算云端服务器的性能十分强劲，也是有很大的压力的，很有可能会对其他业务造成干扰，甚至导致宕机这样的重大事故发生。源代码图片（图1）运行结果（图2）计算机配置截图（图3）(2) 分段检索法：要高效率地对身份证号码进行检索校核，必须要深入了解身份证号码的规律。通过查询百度百科，可以了解到：居民身份证号码，根据中华人民共和国国家标准 GB 11643-1999中有关公民身份号码的规定，公民身份号码是特征组合码，由十七位数字本体码和一位数字校验码组成。排列顺序从左至右依次为：六位数字地址码，八

6、位数字出生日期码，三位数字顺序码和一位数字校验码。 居民身份证是国家法定的证明公民个人身份的有效证件。关于地址码：第一、二位表示省（自治区、直辖市、特别行政区）；第三、四位表示市（地级市、自治州、盟及国家直辖市所属市辖区和县的汇总码）。其中，01-20，51-70表示省直辖市；21-50表示地区（自治州、盟）；第五、六位表示县（市辖区、县级市、旗）。01-18表示市辖区或地区（自治州、盟）辖县级市；21-80表示县（旗）；81-99表示省直辖县级市。关于出生日期码：（身份证号码第七位到第十四位）表示编码对象出生的年、月、日，其中年份用四位数字表示，年、月、日之间不用分隔符。例如：1981年05

7、月11日就用19810511表示。关于顺序码：（身份证号码第十五位到十七位）地址码所标识的区域范围内，对同年、月、日出生的人员编定的顺序号。其中第十七位奇数分给男性，偶数分给女性。关于校验码： 作为尾号的校验码，是由号码编制单位按统一的公式计算出来的，如果某人的尾号是0-9，都不会出现X，但如果尾号是10，那么就得用X来代替，因为如果用10做尾号，那么此人的身份证就变成了19位，而19位的号码违反了国家标准，并且中国的计算机应用系统也不承认19位的身份证号码。是罗马数字的10，用X来代替10，可以保证公民的身份证符合国家标准。现在假设工作人员通过设备获取了一位乘客的身份证号码为： 500382

8、 19970116 465 81 地址码（前六位）：500382 重庆市合川区（155万人口，2013年数据）2 出生日期码（7-14位）： 1997年01月16日3 顺序码（15-17位）： 4654 校验码（最后一位）： 8此处的分段检索法是在枚举法的基础上进行改进的，在枚举法之前进行几步操作，分层进行检索，逐步地缩小检索范围。在服务器的数据库里，如果单方面地从查找速度上考虑的话，为身份证信息加入合适的层级，比如性别，校验码等，可以进一步地提高查找速度。即咱们经常听说的树状结构，有多个层级，对信息进行有条理的分类。示意图如图4所示：图4第一步：根据前六位号码先确定了地址，如户籍所在地是重庆

9、市合川区。检索地址码耗时，如果不进行分层处理大约几万条，一万条数据在我的电脑上的运算耗时是6微秒，几乎可以忽略不计。第二步：即使不再继续缩小范围而是直接进行检索，枚举150万条信息，（普通的区县是没有这么多人口的，有这么多人口是少数情况，故在普通状况下检索量会更小一些）在与之前一样的硬件条件下耗时约0.133秒，如图5所示。这与之前的70秒相比较，是一个非常大的提升，极大地提高了查找效率，如果更进一步进行更加严密的分类，即使是一般的手持设备也能胜任这项任务。150万条数据检索模拟结果（图5）3、 结论： 更优的计算机算法能够更加节省计算机硬件资源，更加高效地为我们工作。研究算法不是谁的专利，就

10、算作为一个非专业研究算法的人，对一些算法进行学习和研究是很有益处的。在现实生活中，一些算法问题的有效解决也将节约大量的资源。所以研究算法是十分有必要的，在此，向算法研究者致敬，我将努力在我所在的领域做出成绩，并在需要的时候，向算法研究者寻求帮助，也将做出有效的反馈供研究者更好地进行分析。参考文献：1、 Python和C语言打印性能对比：2、重庆市合川区人口数据来源：【注：关于身份证的相关标准是由网络上的资料整理所得，Python和C语言的性能对比也是引用了网友的帖子，并没有进行严格的测试。】【附：Python数据查询模拟代码身份证号码样本：一个虚假身份证号和随机数进行加和运算得来程序一（可自由

11、输入不不大于7000万的枚举条数，主要用于测试小查询量耗时）：from time import *from random import *list_7000=x=int(input('输入模拟的数据枚举条数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('已经找到'+str(num)+'个n')endtime=time()print(str(endtime)+'n')print('总共耗时'+str(endtime-start)+'秒')程序二（模拟7亿次数据查询）：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