Python编程使用有限状态机识别地址有效性

夏知夏

发布时间：2026-10-14| 5人浏览过

原创

本文介绍如何利用Python中的有限状态机（FSM）来识别和验证中国地址的有效性。通过定义状态和转移规则，程序可以判断地址字符串是否符合标准格式，如省、市、区、街道及门号段的正确组合。文章提供了具体的代码示例，展示了如何构建状态机以处理不同层级的地址信息，并讨论了其在实际应用中的局限性与扩展方式。

在收发快递填写地址时，我们常需手动输入地址供程序智能识别。标准地址格式通常为“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

此处未对地址字符串进行分词，而是直接将地址写为列表形式，旨在说明状态机的实现与应用。上述代码仅能从格式上保证地址有效，并不能确保地址真实存在。若要判断地址是否真实有效，需建立包含全国所有省、市、区县、街道的哈希表，并将门牌号用范围表示，再进行状态转移判断。

上述代码中的`transfer`即为一个哈希表，相当于穷举了所有正确转移的情况。它涵盖了在任何情况下，对应任何输入所需转移的状态。