資訊專欄INFORMATION COLUMN
地址的識別和分析是本地搜索必不可少的技術(shù)，盡管有許多識別和分析地址的方法，最有效的是有限狀態(tài)機。
一個有限狀態(tài)機是一個特殊的有向圖（參見有關(guān)圖論的系列），它包括一些狀態(tài)（節(jié)點）和連接這些狀態(tài)的有向弧。下圖是一個識別中國地址的有限狀態(tài)機的簡單的例子。
每一個有限狀態(tài)機都有一個啟始狀態(tài)和一個終止?fàn)顟B(tài)和若干中間狀態(tài)。每一條弧上帶有從一個狀態(tài)進(jìn)入下一個狀態(tài)的條件。比如，在上圖中，當(dāng)前的狀態(tài)是“省”，如果遇到一個詞組和（區(qū)）縣名有關(guān)，我們就進(jìn)入狀態(tài)“區(qū)縣”；如果遇到的下一個詞組和城市有關(guān)，那么我們就進(jìn)入“市”的狀態(tài)，如此等等。如果一條地址能從狀態(tài)機的起始狀態(tài)經(jīng)過狀態(tài)機的若干中間狀態(tài)，走到終止?fàn)顟B(tài)，那么這條地址則有效，否則無效。比如說，“北京市雙清路83號”對于上面的有限狀態(tài)來講有效，而“上海市遼寧省馬家莊”則無效（因為無法從市走回到?。?。
使用有限狀態(tài)機識別地址，關(guān)鍵要解決兩個問題，即通過一些有效的地址建立狀態(tài)機，以及給定一個有限狀態(tài)機后，地址字串的匹配算法。好在這兩個問題都有現(xiàn)成的算法。有了關(guān)于地址的有限狀態(tài)機后，我們就可又用它分析網(wǎng)頁，找出網(wǎng)頁中的地址部分，建立本地搜索的數(shù)據(jù)庫。同樣，我們也可以對用戶輸入的查詢進(jìn)行分析，挑出其中描述地址的部分，當(dāng)然，剩下的關(guān)鍵詞就是用戶要找的內(nèi)容。比如，對于用戶輸入的“北京市雙清路附近的酒家”，Google 本地會自動識別出地址“北京市雙清路”和要找的對象“酒家”。
上述基于有限狀態(tài)機的地址識別方法在實用中會有一些問題：當(dāng)用戶輸入的地址不太標(biāo)準(zhǔn)或者有錯別字時，有限狀態(tài)機會束手無策，因為它只能進(jìn)行嚴(yán)格匹配。（其實，有限狀態(tài)機在計算機科學(xué)中早期的成功應(yīng)用是在程序語言編譯器的設(shè)計中。一個能運行的程序在語法上必須是沒有錯的，所以不需要模糊匹配。而自然語言則很隨意，無法用簡單的語法描述。）
為了解決這個問題，我們希望有一個能進(jìn)行模糊匹配、并給出一個字串為正確地址的可能性。為了實現(xiàn)這一目的，科學(xué)家們提出了基于概率的有限狀態(tài)機。這種基于概率的有限狀態(tài)機和離散的馬爾可夫鏈（詳見前面關(guān)于馬爾可夫模型的系列）基本上等效。
在八十年代以前，盡管有不少人使用基于概率的有限狀態(tài)機，但都是為自己的應(yīng)用設(shè)計專用的有限狀態(tài)機的程序。九十年代以后，隨著有限狀態(tài)機在自然語言處理的廣泛應(yīng)用，不少科學(xué)家致力于編寫通用的有限狀態(tài)機程序庫。其中，最成功的是前 AT&T 實驗室的三位科學(xué)家，莫瑞（Mohri）, 皮瑞爾（Pereira） 和瑞利（Riley）。他們?nèi)嘶撕芏嗄陼r間，編寫成一個通用的基于概率的有限狀態(tài)機 C 語言工具庫。由于 AT&T 有對學(xué)術(shù)界免費提供各種編程工具的好傳統(tǒng)，他們?nèi)艘舶炎约憾嗄甑男难贸鰜砗屯袀児蚕怼？上Ш镁安婚L，AT&T 實驗室風(fēng)光不再，這三個人都離開了 AT&T，莫瑞成了紐約大學(xué)的教授，皮瑞爾當(dāng)了賓西法尼亞大學(xué)計算機系系主任，而瑞利成了 Google 的研究員，AT&T 實驗室的新東家不再免費提供有限狀態(tài)機 C 語言工具庫。雖然此前莫瑞等人公布了他們的詳細(xì)算法，但是省略了實現(xiàn)的細(xì)節(jié)。因此在學(xué)術(shù)界，不少科學(xué)家能夠重寫同樣功能的工具庫，但是很難達(dá)到 AT&T 工具庫的效率（即運算速度），這的確是一件令人遺憾的事。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/4303.html
摘要：的杰出工程師阿米特辛格博士就是為設(shè)計阿卡沖鋒槍的人，在公司內(nèi)部，的排序算法便是以他的名字命名的。每一次，辛格總是堅持找簡單有效的解決方案。辛格非常鼓勵年輕人不怕失敗，大膽嘗試。 槍迷或者看過尼古拉斯.凱奇（Nicolas Cage)主演的電影戰(zhàn)爭之王（Lord of War)的人也許還記得影片開頭的一段話：（在所有輕武器中，）最有名的是阿卡 47( AK47)沖鋒槍(也就是中國的五六式?jīng)_鋒槍...
摘要：楚江數(shù)據(jù)經(jīng)常浪跡各類有關(guān)數(shù)據(jù)類文章中網(wǎng)站中，做做搬運工。在這里跟大家分享下數(shù)據(jù)分析師的知識結(jié)構(gòu)，數(shù)據(jù)分析師的知識結(jié)構(gòu)應(yīng)當(dāng)包括數(shù)據(jù)能力業(yè)務(wù)思維方法三個維度。下面書單，選取的都是行業(yè)里面的經(jīng)典書籍，內(nèi)容較多，建議大家采取階段性學(xué)習(xí)。 楚江數(shù)據(jù)經(jīng)常浪跡各類有關(guān)數(shù)據(jù)類文章中網(wǎng)站中，做做搬運工。在這里跟大家分享下數(shù)據(jù)分析師的知識結(jié)構(gòu)，數(shù)據(jù)分析師的知識結(jié)構(gòu)應(yīng)當(dāng)包括數(shù)據(jù)能力、業(yè)務(wù)sense、思維方法...
摘要：進(jìn)入當(dāng)前程序的學(xué)習(xí)系統(tǒng)的所有樣本稱作輸入，并組成輸入空間。結(jié)束語注意這篇文章僅僅是我接下來的機器學(xué)習(xí)系列的第一篇，后續(xù)還會有更多的內(nèi)容。 往期回顧：統(tǒng)計學(xué)習(xí)方法第...
閱讀 2868·2021-11-22 14:44
閱讀 614·2021-11-22 12:00
閱讀 3756·2019-08-30 15:54
閱讀 1646·2019-08-29 17:15
閱讀 1973·2019-08-29 13:50
閱讀 1182·2019-08-29 13:17
閱讀 3576·2019-08-29 13:05
閱讀 1236·2019-08-29 11:31
