Python編程使用有限狀態(tài)機識別地址有效性
在收發(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)。
最后的話
本文分享了如何實現(xiàn)一個簡單的有限狀態(tài)機
附有限狀態(tài)機的開源實現(xiàn):
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編程使用有限狀態(tài)機識別地址有效性的詳細(xì)內(nèi)容,更多關(guān)于Python之有限狀態(tài)機識別地址的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Python+pandas編寫命令行腳本操作excel的tips詳情
這篇文章主要介紹了Python+pandas編寫命令行腳本操作excel的tips詳情,文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有一定的參考價值,需要的朋友可以參考一下2022-07-07Python中用post、get方式提交數(shù)據(jù)的方法示例
最近在學(xué)習(xí)使用Python,發(fā)現(xiàn)網(wǎng)上很少提到如何使用post,所以下面這篇文章主要給大家介紹了關(guān)于Python中用post、get方式提交數(shù)據(jù)的方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起看看吧。2017-09-09python數(shù)據(jù)操作之lambda表達(dá)式詳情
這篇文章主要介紹了python數(shù)據(jù)操作之lambda表達(dá)式詳情,文章基于python的相關(guān)資料展開lambda表達(dá)式具體的內(nèi)容,感興趣的小伙伴可以參考一下2022-05-05python33 urllib2使用方法細(xì)節(jié)講解
Python 標(biāo)準(zhǔn)庫中有很多實用的工具類,這里總結(jié)一些 urllib2 的使用細(xì)節(jié):Proxy 的設(shè)置、Timeout 設(shè)置、在 HTTP Request 中加入特定的 、Cookie、使用 HTTP 的 PUT 和 DELETE 方法2013-12-12Django自定義YamlField實現(xiàn)過程解析
這篇文章主要介紹了Django自定義YamlField實現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-11-11python實現(xiàn)NB-IoT模塊遠(yuǎn)程控制
這篇文章主要為大家詳細(xì)介紹了python實現(xiàn)NB-IoT模塊遠(yuǎn)程控制,具有一定的參考價值,感興趣的小伙伴們可以參考一下2018-06-06