Python編程使用有限狀態機識別地址有效性

Posted on by

在收發快遞填寫地址的時候，我們會經常手動輸入地址讓程序智能識別，標準的地址比如，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]

參考資料

[1]

django-fsm:

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

[2]

python-state-machine:

 https://github.com/jtushman/state_machine

以上就是Python編程使用有限狀態機識別地址有效性的詳細內容，更多關於Python之有限狀態機識別地址的資料請關註WalkonNet其它相關文章！

推薦閱讀：