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