国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

“數學之美”系列十：有限狀態機和地址識別

libxd / 698人閱讀

地址的識別和分析是本地搜索必不可少的技術，盡管有許多識別和分析地址的方法，最有效的是有限狀態機。

一個有限狀態機是一個特殊的有向圖（參見有關圖論的系列），它包括一些狀態（節點）和連接這些狀態的有向弧。下圖是一個識別中國地址的有限狀態機的簡單的例子。

每一個有限狀態機都有一個啟始狀態和一個終止狀態和若干中間狀態。每一條弧上帶有從一個狀態進入下一個狀態的條件。比如，在上圖中，當前的狀態是“省”，如果遇到一個詞組和（區）縣名有關，我們就進入狀態“區縣”；如果遇到的下一個詞組和城市有關，那么我們就進入“市”的狀態，如此等等。如果一條地址能從狀態機的起始狀態經過狀態機的若干中間狀態，走到終止狀態，那么這條地址則有效，否則無效。比如說，“北京市雙清路83號”對于上面的有限狀態來講有效，而“上海市遼寧省馬家莊”則無效（因為無法從市走回到省）。


使用有限狀態機識別地址，關鍵要解決兩個問題，即通過一些有效的地址建立狀態機，以及給定一個有限狀態機后，地址字串的匹配算法。好在這兩個問題都有現成的算法。有了關于地址的有限狀態機后，我們就可又用它分析網頁，找出網頁中的地址部分，建立本地搜索的數據庫。同樣，我們也可以對用戶輸入的查詢進行分析，挑出其中描述地址的部分，當然，剩下的關鍵詞就是用戶要找的內容。比如，對于用戶輸入的“北京市雙清路附近的酒家”，Google 本地會自動識別出地址“北京市雙清路”和要找的對象“酒家”。


上述基于有限狀態機的地址識別方法在實用中會有一些問題：當用戶輸入的地址不太標準或者有錯別字時，有限狀態機會束手無策，因為它只能進行嚴格匹配。（其實，有限狀態機在計算機科學中早期的成功應用是在程序語言編譯器的設計中。一個能運行的程序在語法上必須是沒有錯的，所以不需要模糊匹配。而自然語言則很隨意，無法用簡單的語法描述。）


為了解決這個問題，我們希望有一個能進行模糊匹配、并給出一個字串為正確地址的可能性。為了實現這一目的，科學家們提出了基于概率的有限狀態機。這種基于概率的有限狀態機和離散的馬爾可夫鏈（詳見前面關于馬爾可夫模型的系列）基本上等效。


在八十年代以前，盡管有不少人使用基于概率的有限狀態機，但都是為自己的應用設計專用的有限狀態機的程序。九十年代以后，隨著有限狀態機在自然語言處理的廣泛應用，不少科學家致力于編寫通用的有限狀態機程序庫。其中，最成功的是前 AT&T 實驗室的三位科學家，莫瑞（Mohri）, 皮瑞爾（Pereira） 和瑞利（Riley）。他們三人花了很多年時間，編寫成一個通用的基于概率的有限狀態機 C 語言工具庫。由于 AT&T 有對學術界免費提供各種編程工具的好傳統，他們三人也把自己多年的心血拿出來和同行們共享。可惜好景不長，AT&T 實驗室風光不再，這三個人都離開了 AT&T，莫瑞成了紐約大學的教授，皮瑞爾當了賓西法尼亞大學計算機系系主任，而瑞利成了 Google 的研究員，AT&T 實驗室的新東家不再免費提供有限狀態機 C 語言工具庫。雖然此前莫瑞等人公布了他們的詳細算法，但是省略了實現的細節。因此在學術界，不少科學家能夠重寫同樣功能的工具庫，但是很難達到 AT&T 工具庫的效率（即運算速度），這的確是一件令人遺憾的事。

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/4303.html

相關文章

  • “數學之美”系列十一： Google 阿卡 47 的制造者阿米特.辛格博士

    摘要：的杰出工程師阿米特辛格博士就是為設計阿卡沖鋒槍的人，在公司內部，的排序算法便是以他的名字命名的。每一次，辛格總是堅持找簡單有效的解決方案。辛格非常鼓勵年輕人不怕失敗，大膽嘗試。 槍迷或者看過尼古拉斯.凱奇（Nicolas Cage)主演的電影戰爭之王（Lord of War)的人也許還記得影片開頭的一段話：（在所有輕武器中，）最有名的是阿卡 47( AK47)沖鋒槍(也就是中國的五六式沖鋒槍...

    zilu 評論0 收藏0

  • 數據分析師必讀書單分享

    摘要：楚江數據經常浪跡各類有關數據類文章中網站中，做做搬運工。在這里跟大家分享下數據分析師的知識結構，數據分析師的知識結構應當包括數據能力業務思維方法三個維度。下面書單，選取的都是行業里面的經典書籍，內容較多，建議大家采取階段性學習。 楚江數據經常浪跡各類有關數據類文章中網站中，做做搬運工。在這里跟大家分享下數據分析師的知識結構，數據分析師的知識結構應當包括數據能力、業務sense、思維方法...

    KunMinX 評論0 收藏0

  • 開始學習機器學習之前你必須要了解的知識有哪些？機器學習系列入門篇

    摘要：進入當前程序的學習系統的所有樣本稱作輸入，并組成輸入空間。結束語注意這篇文章僅僅是我接下來的機器學習系列的第一篇，后續還會有更多的內容。 往期回顧：統計學習方法第...

    leoperfect 評論0 收藏0

發表評論

0條評論

libxd

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<