[[422204]]

在收發(fā)快遞填寫地址的時候，我們會經(jīng)常手動輸入地址讓程序智能識別，標(biāo)準(zhǔn)的地址比如，xx省xx市xx縣/區(qū)xx路xx號，不過有時候也可以簡單寫：xx市xx縣/區(qū)xx路xx號，或者xx省xx縣/區(qū)xx路xx號，或者xx市xx路xx號。

但是有些就不是合法的地址了，比如 xx省xx街道xx號，或者 xx市xx省xx區(qū)xx號。

那么問題來了，如何識別一個地址是否有效，確切的講，如何編程識別一個中國地址是否有效?

雖然我們大腦可以一眼識別，但是讓計算器去識別，可以不是一件容易的事，根本原因在于地址的描述雖然看上去簡單，但是它依然是比較復(fù)雜的上下文有關(guān)的文法。

比如 “上海市北京東路 xx 號，南京市北京東路 xx 號”，掃描到北京東路時，它后面的門牌號是否構(gòu)成正確的地址要看上下文，即城市名。

所幸的是，地址的上下文比較簡單，是有限的，雖然我們可以暴力窮舉所有省、市、區(qū)、街道。但有效的方法還是有限狀態(tài)機。

每一個有限狀態(tài)機都有一個開始狀態(tài)和一個終止?fàn)顟B(tài)，以及若干中間狀態(tài)，每一條弧上帶著一個狀態(tài)進入下一個狀態(tài)的條件，比如在上圖中當(dāng)前的狀態(tài)如果是省，如果遇到下一個詞組和區(qū)有關(guān)就進入?yún)^(qū)，如果遇到下一個詞組和城市有關(guān)那么就進入市。

如果一條地址能從狀態(tài)機的開始狀態(tài)，經(jīng)過狀態(tài)機的若干中間狀態(tài)，最終走到終止?fàn)顟B(tài)，則這條地址有效，否則無效。

比如 xx市xx省xx區(qū)xx號 就是無效地址，無法從市走到省。

現(xiàn)在我們通過一個簡單的優(yōu)先狀態(tài)機來實現(xiàn)，代碼有注釋，很容易看懂

from enum import Enum 
 
def isAddress(address: str) -> bool: 
 
    #定義狀態(tài) 
    State = Enum("State", [ 
        "STATE_INITIAL", #開始 
        "STATE_PROVINCE", # 省 
        "STATE_CITY", # 市 
        "STATE_AREA", # 區(qū) / 縣 
        "STATE_STREET", # 街道 
        "STATE_NUM", #號 
        "STATE_END", #結(jié)束 
        "STATE_ILLEGAL", #錯誤狀態(tài) 
    ]) 
 
    def toAddressType(addr_slice : str) -> State: 
        if "省" in addr_slice: 
            return State.STATE_PROVINCE 
        elif "市" in addr_slice: 
            return State.STATE_CITY 
        elif "區(qū)" 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 
     
    #定義狀態(tài)轉(zhuǎn)移 
     
    transfer = { 
 
        #開始可以轉(zhuǎn)為 省或市 
        State.STATE_INITIAL: { 
            State.STATE_PROVINCE,  
            State.STATE_CITY, 
        }, 
 
        #省可以轉(zhuǎn) 市或區(qū)縣 
        State.STATE_PROVINCE:{ 
            State.STATE_CITY, 
            State.STATE_AREA, 
        }, 
 
        #市可以轉(zhuǎn)區(qū)或街道 
        State.STATE_CITY: { 
            State.STATE_AREA, 
            State.STATE_STREET, 
        }, 
 
        #區(qū)縣可以轉(zhuǎn)街道 
        State.STATE_AREA: { 
            State.STATE_STREET, 
        }, 
 
        #街道可以轉(zhuǎn)號或終止 
        State.STATE_STREET: { 
            State.STATE_NUM, 
            State.STATE_END, 
        }, 
 
        #號只能轉(zhuǎn)終止 
        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 = ["江蘇省","蘇州市", "吳中區(qū)", "中山北路", "208號"] 
    address2 = ["蘇州市","吳中區(qū)", "中山北路", "208號"] 
    address3 = ["蘇州市","吳江區(qū)", "中山北路", "208號"] 
    address4 = ["蘇州市","吳江區(qū)","208號"] 
    address5 = ["蘇州市","中山北路"] 
 
    assert isAddress(address1) 
    assert isAddress(address2) 
    assert isAddress(address3) 
    assert isAddress(address5) 
    assert isAddress(address4) == False 

這里沒有對整個地址字符串進行分詞，而是直接將地址寫成了列表的形式，主要為了說明狀態(tài)機的實現(xiàn)和應(yīng)用，上述代碼僅能從格式上保證地址是有效的，并不能確保地址真實有效，如果要判斷是真實有效的，那就需要將全國所有的省、市、區(qū)縣、街道建立一個 hash 表，門牌號可以用范圍表示，再進行狀態(tài)轉(zhuǎn)移判斷。

上述代碼的 transfer 就是一個 hash 表，相當(dāng)于把所有正確轉(zhuǎn)移的情況都窮舉了一遍，它窮盡了在任何一種情況下，對應(yīng)任何的輸入，需要轉(zhuǎn)義的狀態(tài)。

本文轉(zhuǎn)載自微信公眾號「Python七號」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系Python七號公眾號。