如何用有限状态机识别地址的有效性？

在收发快递填写地址的时候，我们会经常手动输入地址让程序智能识别，标准的地址比如，xx省xx市xx县/区xx路xx号，不过有时候也可以简单写：xx市xx县/区xx路xx号，或者xx省xx县/区xx路xx号，或者xx市xx路xx号。

但是有些就不是合法的地址了，比如 xx省xx街道xx号，或者 xx市xx省xx区xx号。

那么问题来了，如何识别一个地址是否有效，确切的讲，如何编程识别一个中国地址是否有效?

虽然我们大脑可以一眼识别，但是让计算器去识别，可以不是一件容易的事，根本原因在于地址的描述虽然看上去简单，但是它依然是比较复杂的上下文有关的文法。

比如 “上海市北京东路 xx 号，南京市北京东路 xx 号”，扫描到北京东路时，它后面的门牌号是否构成正确的地址要看上下文，即城市名。

所幸的是，地址的上下文比较简单，是有限的，虽然我们可以暴力穷举所有省、市、区、街道。但有效的方法还是有限状态机。

每一个有限状态机都有一个开始状态和一个终止状态，以及若干中间状态，每一条弧上带着一个状态进入下一个状态的条件，比如在上图中当前的状态如果是省，如果遇到下一个词组和区有关就进入区，如果遇到下一个词组和城市有关那么就进入市。

如果一条地址能从状态机的开始状态，经过状态机的若干中间状态，最终走到终止状态，则这条地址有效，否则无效。

比如 xx市xx省xx区xx号 就是无效地址，无法从市走到省。

现在我们通过一个简单的优先状态机来实现，代码有注释，很容易看懂

 
 
 
 
    
  
  
  
  
  1. from enum import Enum
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. def isAddress(address: str) -> bool:
    4. 
  
  
  
  
  4. 
  
  
  
  
  5.     #定义状态
    6. 
  
  
  
  
  6.     State = Enum("State", [
    7. 
  
  
  
  
  7.         "STATE_INITIAL", #开始
    8. 
  
  
  
  
  8.         "STATE_PROVINCE", # 省
    9. 
  
  
  
  
  9.         "STATE_CITY", # 市
    10. 
  
  
  
  
  10.         "STATE_AREA", # 区 / 县
    11. 
  
  
  
  
  11.         "STATE_STREET", # 街道
    12. 
  
  
  
  
  12.         "STATE_NUM", #号
    13. 
  
  
  
  
  13.         "STATE_END", #结束
    14. 
  
  
  
  
  14.         "STATE_ILLEGAL", #错误状态
    15. 
  
  
  
  
  15.     ])
    16. 
  
  
  
  
  16. 
  
  
  
  
  17.     def toAddressType(addr_slice : str) -> State:
    18. 
  
  
  
  
  18.         if "省" in addr_slice:
    19. 
  
  
  
  
  19.             return State.STATE_PROVINCE
    20. 
  
  
  
  
  20.         elif "市" in addr_slice:
    21. 
  
  
  
  
  21.             return State.STATE_CITY
    22. 
  
  
  
  
  22.         elif "区" in addr_slice or "县" in addr_slice:
    23. 
  
  
  
  
  23.             return State.STATE_AREA
    24. 
  
  
  
  
  24.         elif "路" in addr_slice or "街道" in addr_slice:
    25. 
  
  
  
  
  25.             return State.STATE_STREET
    26. 
  
  
  
  
  26.         elif "号" in addr_slice:
    27. 
  
  
  
  
  27.             return State.STATE_NUM
    28. 
  
  
  
  
  28.         else:
    29. 
  
  
  
  
  29.             return State.STATE_ILLEGAL
    30. 
  
  
  
  
  30.     
    31. 
  
  
  
  
  31.     #定义状态转移
    32. 
  
  
  
  
  32.     
    33. 
  
  
  
  
  33.     transfer = {
    34. 
  
  
  
  
  34. 
  
  
  
  
  35.         #开始可以转为 省或市
    36. 
  
  
  
  
  36.         State.STATE_INITIAL: {
    37. 
  
  
  
  
  37.             State.STATE_PROVINCE, 
    38. 
  
  
  
  
  38.             State.STATE_CITY,
    39. 
  
  
  
  
  39.         },
    40. 
  
  
  
  
  40. 
  
  
  
  
  41.         #省可以转 市或区县
    42. 
  
  
  
  
  42.         State.STATE_PROVINCE:{
    43. 
  
  
  
  
  43.             State.STATE_CITY,
    44. 
  
  
  
  
  44.             State.STATE_AREA,
    45. 
  
  
  
  
  45.         },
    46. 
  
  
  
  
  46. 
  
  
  
  
  47.         #市可以转区或街道
    48. 
  
  
  
  
  48.         State.STATE_CITY: {
    49. 
  
  
  
  
  49.             State.STATE_AREA,
    50. 
  
  
  
  
  50.             State.STATE_STREET,
    51. 
  
  
  
  
  51.         },
    52. 
  
  
  
  
  52. 
  
  
  
  
  53.         #区县可以转街道
    54. 
  
  
  
  
  54.         State.STATE_AREA: {
    55. 
  
  
  
  
  55.             State.STATE_STREET,
    56. 
  
  
  
  
  56.         },
    57. 
  
  
  
  
  57. 
  
  
  
  
  58.         #街道可以转号或终止
    59. 
  
  
  
  
  59.         State.STATE_STREET: {
    60. 
  
  
  
  
  60.             State.STATE_NUM,
    61. 
  
  
  
  
  61.             State.STATE_END,
    62. 
  
  
  
  
  62.         },
    63. 
  
  
  
  
  63. 
  
  
  
  
  64.         #号只能转终止
    65. 
  
  
  
  
  65.         State.STATE_NUM: {
    66. 
  
  
  
  
  66.             State.STATE_END,
    67. 
  
  
  
  
  67.         },
    68. 
  
  
  
  
  68.     }
    69. 
  
  
  
  
  69. 
  
  
  
  
  70.     st = State.STATE_INITIAL
    71. 
  
  
  
  
  71.     for ch in address:
    72. 
  
  
  
  
  72.         current_state = toAddressType(ch)
    73. 
  
  
  
  
  73.         if current_state not in transfer[st]:
    74. 
  
  
  
  
  74.             return False
    75. 
  
  
  
  
  75.         st = current_state 
    76. 
  
  
  
  
  76. 
  
  
  
  
  77.     return st in [State.STATE_STREET, State.STATE_NUM,State.STATE_END]
    78. 
  
  
  
  
  78. 
  
  
  
  
  79. if __name__ == '__main__':
    80. 
  
  
  
  
  80.     address1 = ["江苏省","苏州市", "吴中区", "中山北路", "208号"]
    81. 
  
  
  
  
  81.     address2 = ["苏州市","吴中区", "中山北路", "208号"]
    82. 
  
  
  
  
  82.     address3 = ["苏州市","吴江区", "中山北路", "208号"]
    83. 
  
  
  
  
  83.     address4 = ["苏州市","吴江区","208号"]
    84. 
  
  
  
  
  84.     address5 = ["苏州市","中山北路"]
    85. 
  
  
  
  
  85. 
  
  
  
  
  86.     assert isAddress(address1)
    87. 
  
  
  
  
  87.     assert isAddress(address2)
    88. 
  
  
  
  
  88.     assert isAddress(address3)
    89. 
  
  
  
  
  89.     assert isAddress(address5)
    90. 
  
  
  
  
  90.     assert isAddress(address4) == False
    91.

这里没有对整个地址字符串进行分词，而是直接将地址写成了列表的形式，主要为了说明状态机的实现和应用，上述代码仅能从格式上保证地址是有效的，并不能确保地址真实有效，如果要判断是真实有效的，那就需要将全国所有的省、市、区县、街道建立一个 hash 表，门牌号可以用范围表示，再进行状态转移判断。

上述代码的 transfer 就是一个 hash 表，相当于把所有正确转移的情况都穷举了一遍，它穷尽了在任何一种情况下，对应任何的输入，需要转义的状态。

本文转载自微信公众号「Python七号」，可以通过以下二维码关注。转载本文请联系Python七号公众号。

网页题目：如何用有限状态机识别地址的有效性？
本文地址：http://www.shufengxianlan.com/qtweb/news44/383394.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

域名注册知识

分类信息网站

梓潼网站制作公司　　 　成都店面装修公司　　 　成都租用服务器　　 　广汉锦华　　 　简阳做网站　　 　红锐电子　　 　成都棕数机房　　 　网站建设方案　　 　成都网站优化　　 　企业官网建设　　 　成都网站制作　　 　成都西信机房托管　　 　彭州网站建设　　 　led无边发光字　　 　东方电机技改服务有限公司　　 　定制网站建设　　 　品牌网站建设　　 　晟和广告　　 　LED显示屏厂家　　 　网站排名优化