如何用有限状态机识别地址的有效性?
在收发快递填写地址的时候,我们会经常手动输入地址让程序智能识别,标准的地址比如,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号 就是无效地址,无法从市走到省。
现在我们通过一个简单的优先状态机来实现,代码有注释,很容易看懂
from enum import Enum
def isAddress(address: str) -> bool:
#定义状态
State = Enum("State", [
"STATE_INITIAL", #开始
"STATE_PROVINCE", # 省
"STATE_CITY", # 市
"STATE_AREA", # 区 / 县
"STATE_STREET", # 街道
"STATE_NUM", #号
"STATE_END", #结束
"STATE_ILLEGAL", #错误状态
])
def toAddressType(addr_slice : str) -> State:
if "省" in addr_slice:
return State.STATE_PROVINCE
elif "市" in addr_slice:
return State.STATE_CITY
elif "区" in addr_slice or "县" in addr_slice:
return State.STATE_AREA
elif "路" in addr_slice or "街道" in addr_slice:
return State.STATE_STREET
elif "号" in addr_slice:
return State.STATE_NUM
else:
return State.STATE_ILLEGAL
#定义状态转移
transfer = {
#开始可以转为 省或市
State.STATE_INITIAL: {
State.STATE_PROVINCE,
State.STATE_CITY,
},
#省可以转 市或区县
State.STATE_PROVINCE:{
State.STATE_CITY,
State.STATE_AREA,
},
#市可以转区或街道
State.STATE_CITY: {
State.STATE_AREA,
State.STATE_STREET,
},
#区县可以转街道
State.STATE_AREA: {
State.STATE_STREET,
},
#街道可以转号或终止
State.STATE_STREET: {
State.STATE_NUM,
State.STATE_END,
},
#号只能转终止
State.STATE_NUM: {
State.STATE_END,
},
}
st = State.STATE_INITIAL
for ch in address:
current_state = toAddressType(ch)
if current_state not in transfer[st]:
return False
st = current_state
return st in [State.STATE_STREET, State.STATE_NUM,State.STATE_END]
if __name__ == '__main__':
address1 = ["江苏省","苏州市", "吴中区", "中山北路", "208号"]
address2 = ["苏州市","吴中区", "中山北路", "208号"]
address3 = ["苏州市","吴江区", "中山北路", "208号"]
address4 = ["苏州市","吴江区","208号"]
address5 = ["苏州市","中山北路"]
assert isAddress(address1)
assert isAddress(address2)
assert isAddress(address3)
assert isAddress(address5)
assert isAddress(address4) == False
这里没有对整个地址字符串进行分词,而是直接将地址写成了列表的形式,主要为了说明状态机的实现和应用,上述代码仅能从格式上保证地址是有效的,并不能确保地址真实有效,如果要判断是真实有效的,那就需要将全国所有的省、市、区县、街道建立一个 hash 表,门牌号可以用范围表示,再进行状态转移判断。
上述代码的 transfer 就是一个 hash 表,相当于把所有正确转移的情况都穷举了一遍,它穷尽了在任何一种情况下,对应任何的输入,需要转义的状态。
最后的话
本文分享了如何实现一个简单的有限状态机,代码比较通用,前文这个编程题,让人欲罢不能也是套用这个代码实现的,如果对你有所帮助,还请点赞、关注支持,赠人在看,手留余香。
附有限状态机的开源实现:
django-fsm[1] python-state-machine[2]
关注我,每天学习一个 Python 小技术。
参考资料
django-fsm: https://github.com/viewflow/django-fsm
[2]python-state-machine: https://github.com/jtushman/state_machine