专栏首页Python七号如何用有限状态机识别地址的有效性?

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

在收发快递填写地址的时候,我们会经常手动输入地址让程序智能识别,标准的地址比如,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 表,相当于把所有正确转移的情况都穷举了一遍,它穷尽了在任何一种情况下,对应任何的输入,需要转义的状态。

最后的话

本文分享了如何实现一个简单的有限状态机,代码比较通用,前文这个编程题,让人欲罢不能也是套用这个代码实现的,如果对你有所帮助,还请点赞、关注支持,赠人在看,手留余香。

附有限状态机的开源实现:

  1. django-fsm[1]
  2. python-state-machine[2]

关注我,每天学习一个 Python 小技术。

参考资料

[1]

django-fsm: https://github.com/viewflow/django-fsm

[2]

python-state-machine: https://github.com/jtushman/state_machine

本文分享自微信公众号 - Python七号(PythonSeven),作者:somenzz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-09-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【学习】数学之美系列十:有限状态机和地址识别

    数学之美系列十:有限状态机和地址识别 地址的识别和分析是本地搜索必不可少的技术,尽管有许多识别和分析地址的方法,最有效的是有限状态机。 一个有限状态机是一个特...

    小莹莹
  • 加权有限状态机在语音识别中的应用

    WFST 在语音识别中的应用,要从 Mohri 的《Weighted Finite-State Transducers in Speech Recognitio...

    李炼
  • 如何以面向对象的思想设计有限状态机

    有限状态机又称有限状态自动机,简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型,用英文缩写也被简称为 FSM。 FSM 会响应“事...

    wenzid
  • 如何以面向对象的思想设计有限状态机

    有限状态机又称有限状态自动机,简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型,用英文缩写也被简称为 FSM。

    wenzid
  • 使用NGINX和NGINX Plus速率限速

    NGINX最有用但经常被误解和配置错误的特征之一就是速率限制。 它允许您限制用户在给定时间段内可以执行的HTTP请求数量。 速率限制可以用于安全目的,例如减慢...

    用户1263954
  • Web安全学习笔记之HTTP协议

    Jetpropelledsnake21
  • 一个基于Java的开源URL嗅探器

    今天,我们很高兴做一个分享,因为我所在的 Linkedin 公司 开源了我们做的一个ULR探测工具:URL-Detector Java 库。

    哲洛不闹
  • 一个基于Java的开源URL嗅探器

    这是一个可以检测并规范化文本中的URL地址的Java库。 ? 今天,我们很高兴做一个分享,因为我所在的 Linkedin 公司 开源了我们做的一个ULR探测工具...

    用户1667431
  • 我是如何在两天内做完一个网站的

    有点标题党的嫌疑,不过确实网站的主体是在两天内的完成的,后面只是抓取了素材和完善细节。以下内容绝对是赤裸裸的干货。

    lyb-geek
  • PAMI-2021:5篇顶级GNN论文

    PAMI(IEEE Transactions on Pattern Analysis and Machine Intelligence),IEEE模式分析与机器...

    Houye
  • GetLastError错误代码

    〖0〗-操作成功完成。   〖1〗-功能错误。   〖2〗-系统找不到指定的文件。   〖3〗-系统找不到指定的路径。   〖4〗-系统无法打开文件。 ...

    战神伽罗
  • 一文拿下SSRF攻击利用及绕过保护机制

    断断续续地继续漏洞之旅,这次讨论一下一个常见web漏洞:SSRF,浅析一下它是如何导致攻击者进入网络,以及如何发现它并且利用。

    字节脉搏实验室
  • 区块链技术面试常被问到的Hyberledger Fabric关键概念

    先给英文官方原文地址:https://hyperledger-fabric.readthedocs.io/en/latest/overview.html

    圆方圆学院
  • STM32H7的CAN FD学习笔记整理贴(2021-03-15)

    CAN FD(CAN with flexible data-rate)是CAN2.0协议的扩展,CAN-FD由博世开发,并由 ISO 11898-1:2015标...

    armfly
  • Web安全学习笔记之Nmap命令参考指南

    在网络技术中,端口(Port)包括逻辑端口和物理端口两种类型。物理端口指的是物理存在的端口,如ADSL Modem、集线器、交换机、路由器上用 于连接其他网络设...

    Jetpropelledsnake21
  • NeurIPS 2020 | 时间序列相关论文一览(附原文源码)

    NeurIPS,全称神经信息处理系统大会(Conference and Workshop on Neural Information Processing Sy...

    VachelHu
  • ZooKeeper面试题(2020最新版)

    Java架构师必看
  • 【HTTP】267- HTTP 的15个常见知识点复习

    自从入职新公司到现在,我们前端团队内部一直在做 ?每周一练 的知识复习计划,我之前整理了一个 [每周一练 之 数据结构与算法] (https://juejin....

    pingan8787
  • 【HTTP】267- HTTP 的15个常见知识点复习

    自从入职新公司到现在,我们前端团队内部一直在做 ?每周一练 的知识复习计划,我之前整理了一个 [每周一练 之 数据结构与算法] (https://juejin....

    用户1462769

扫码关注云+社区

领取腾讯云代金券