想法是这样的，根据一个随手输入的乡村地名，匹配出其严格的五级行政地址。例如输入的”无极县东侯坊乡南池阳村助农点“，便要匹配出”河北省-石家庄市-无极县-东侯坊乡-南池阳村“。后面的这个五级的行政地址是已知存在数据库里的。
大概的思路是首先进行分词，如上面的分成”无极县“，”东侯坊乡“，”南池阳村“，然后再匹配看有没有包含这几个词的五级行政地名。
第一部分：分词
1.构建分词的地名字典
要分词首先要有字典。这里我们已经明确都是行政地名，所以构建这样的地名字典还是很简单的。还是上面的例子”河北省-石家庄市-无极县-东侯坊乡-南池阳村“，拆分成”河北省“，”石家庄市“，”无极县“，”东侯坊乡“，”南池阳村“便就可存入地名字典了。这个地名字典属于是静态且可重复利用的，这部分我便就在数据库端处理了。
创建地名字典表namedict
CREATE TABLE `namedict` ( `id` INT(11) NOT NULL AUTO_INCREMENT, `name` COLLATE , PRIMARY KEY (`id`) )
之后往表里插入记录
` (name) ,,(substring_index(substring_index(village_name,,,(substring_index(substring_index(village_name,,,(substring_index(substring_index(village_name,,,(substring_index(substring_index(village_name,,,
统计了一下地名字典表namedict里共计33万多条的记录。
2.分词判断
有了地名字典就可以进行分词判断了。比如”无极县“，拿这个词到字典里匹配一下是否存在，就知道是否有这个地名了。而”无极县东“在字典里是不存在的，那就可以知道这个地名是不存在的，就不能这样分词了。这里面要注意匹配时判断的效率问题，要避免全扫描，不能每次匹配判断都把33万条记录都扫描一遍，因为一个名字是要经过多次的分词判断才能够得到结果的。也正是这个原因，我把地名字典的所有条目都加载到python的变量里的，这样能够避免多次地和数据库交互。
a.首先先进行hash判断
把33万条记录存放到python的字典变量dict里，那么通过一次hash判断就知道这个地名是否存在。
b.然后再进行范围扫描判断
我们都知道”石家庄市“和”石家庄“是一个意思，但是在dict里面存”石家庄市“而用”石家庄“去匹配是匹配不到的，这里就需要用到范围扫描。
1)把33万个名字再存放到一个list里面，并以一定的规则从小到大排序，如[a1,a2,a3,a4,...,an],且(a1<a2<a3<a4<...an)。
2)if x<a1 or x>an，那就表示x不在list的范围里，也就表示x不在名字字典的范围里，那就不用考虑了。
3)if not (x<a1 or x>an)，那么可以先对排序的列表进行分组，每1000元素个作为一个分组。因为是递增排序的，从最右边（最大的）的分组开始，对每个分组的第一个元素（每个分组中最小的元素）进行比较。如果小于等于了这个分组的第一个元素，就表示了这个x在这个分组的范围之内。再以这个分组的第一个元素为开始，向后查询。如果x<=list[i]，那么i就是这个范围的起点；如果x>list[j],那么j就是这个范围的终点。这种方式其实就是参考了数据库的索引范围查找算法(B+Tree index range scan)，虽说也不算高效，但也比全扫描要好很多了。
3.分词
分词以两个字为起点开始分词，以“无极县东侯坊乡南池阳村助农点”为例：
“无极”是一个词，“无极县”是一个词，“无极县东”不是一个词，那把“无极县”提取出来后面的“东侯坊乡南池阳村助农点”继续。直到拆分成“无极县”，“东侯坊乡”，“南池阳村”。
二.根据分词对五级村名进行匹配
这部分其实也很简单，只要一条SQL语句就能搞定最后的匹配了：
mysql; village_name 河北省row in set (0.62 sec)
这样的语句是不能走索引的只能全表扫描，不过好在全表也就66万多条记录，总共就几十M的大小，完全可以缓存在数据库的内存里的。
不过即便如此也还是有可优化的空间的。首先把所有的66万个五级行政村名都放到python的list里面，其后可以采取类似数据库全文索引的方法。全文索引的难点在于分词以及stopword的鉴定，而我们这里的条目天然就是已分词好的：”河北省-石家庄市-无极县-东侯坊乡-南池阳村“，也不存在stopword。这里我们需要做的只是记录下每个词所在列表的位置。还是上面那个例子：
fullindex["无极县"]=set([58414, 58415, 58416, 58417, 58418, 58419, 58420, 58421, 58422, 58423,...])
fullindex["东侯坊乡"]=set([58445, 58446, 58447, 58448, 58449, 58450, 58451, 58452, ...])
fullindex["南池阳村"]=set([58460])
再对这几个集合做交集操作得到set([58460])，那list[58460]就是我们要找的“河北省-石家庄市-无极县-东侯坊乡-南池阳村”。（这里得到的是最好的情况有且仅有一个，也有可能会有多个例如只写了个“河北”，那会把河北省所有的村都匹配出来；也有可能一个也没有，那就是地名写的不对，一个也匹配不出来。）
三.运行情况：
1.占用内存
因为对于数据库的操作就是开始的时候加载了两份数据：地名字典（33万）和五级行政村名（66万），大部分的操作都是通过代码实现的，所以最后统计了下比较重要的几个python变量所占用的内存：
存储地名字典的列表：2678096
存储地名字典的dict:12583184
存储五级村名的列表：5429648
存储分词位置的dict:12583184
总共看下来程序运行大概会占用33M左右的内存。
2.花费时间
整个程序运行一次要47秒左右，其中从数据库加载数据的时间比较长，大概要42秒，程序进行分词再对村名进行匹配大概用了5秒左右。如果把程序改成服务端的，那只要在启动的时候加载一次数据即可。要是在分词匹配村名之前能够确认省份的话，那这一动作就能降到1秒左右，就基本能够满足线上操作的要求了。
最后大致的代码如下：
相关文章
精彩导读
热门资讯
关注我们
