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

<br><br>一個有限狀態(tài)機是一個特殊的有向圖（參見有關圖論的系列），它包括一些狀態(tài)（節(jié)點）和連接這些狀態(tài)的有向弧。下圖是一個識別中國地址的有限狀態(tài)機的簡單的例子。<br><br><br><br>每一個有限狀態(tài)機都有一個啟始狀態(tài)和一個終止狀態(tài)和若干中間狀態(tài)。每一條弧上帶有從一個狀態(tài)進入下一個狀態(tài)的條件。比如，在上圖中，當前的狀態(tài)是“省”，如果遇到一個詞組和（區(qū)）縣名有關，我們就進入狀態(tài)“區(qū)縣”；如果遇到的下一個詞組和城市有關，那么我們就進入“市”的狀態(tài)，如此等等。如果一條地址能從狀態(tài)機的起始狀態(tài)經(jīng)過狀態(tài)機的若干中間狀態(tài)，走到終止狀態(tài)，那么這條地址則有效，否則無效。比如說，“北京市雙清路83號”對于上面的有限狀態(tài)來講有效，而“上海市遼寧省馬家莊”則無效（因為無法從市走回到?。?。<br><br>使用有限狀態(tài)機識別地址，關鍵要解決兩個問題，即通過一些有效的地址建立狀態(tài)機，以及給定一個有限狀態(tài)機后，地址字串的匹配算法。好在這兩個問題都有現(xiàn)成的算法。有了關于地址的有限狀態(tài)機后，我們就可又用它分析網(wǎng)頁，找出網(wǎng)頁中的地址部分，建立本地搜索的數(shù)據(jù)庫。同樣，我們也可以對用戶輸入的查詢進行分析，挑出其中描述地址的部分，當然，剩下的關鍵詞就是用戶要找的內容。比如，對于用戶輸入的“北京市雙清路附近的酒家”，Google 本地會自動識別出地址“北京市雙清路”和要找的對象“酒家”。<br><br>上述基于有限狀態(tài)機的地址識別方法在實用中會有一些問題：當用戶輸入的地址不太標準或者有錯別字時，有限狀態(tài)機會束手無策，因為它只能進行嚴格匹配。（其實，有限狀態(tài)機在計算機科學中早期的成功應用是在程序語言編譯器的設計中。一個能運行的程序在語法上必須是沒有錯的，所以不需要模糊匹配。而自然語言則很隨意，無法用簡單的語法描述。）<br><br>為了解決這個問題，我們希望有一個能進行模糊匹配、并給出一個字串為正確地址的可能性。為了實現(xiàn)這一目的，科學家們提出了基于概率的有限狀態(tài)機。這種基于概率的有限狀態(tài)機和離散的馬爾可夫鏈（詳見前面關于馬爾可夫模型的系列）基本上等效。<br><br>在八十年代以前，盡管有不少人使用基于概率的有限狀態(tài)機，但都是為自己的應用設計專用的有限狀態(tài)機的程序。九十年代以后，隨著有限狀態(tài)機在自然語言處理的廣泛應用，不少科學家致力于編寫通用的有限狀態(tài)機程序庫。其中，最成功的是前 AT&T 實驗室的三位科學家，莫瑞（Mohri）, 皮瑞爾（Pereira） 和瑞利（Riley）。他們三人花了很多年時間，編寫成一個通用的基于概率的有限狀態(tài)機 C 語言工具庫。由于 AT&T 有對學術界免費提供各種編程工具的好傳統(tǒng)，他們三人也把自己多年的心血拿出來和同行們共享。可惜好景不長，AT&T 實驗室風光不再，這三個人都離開了 AT&T，莫瑞成了紐約大學的教授，皮瑞爾當了賓西法尼亞大學計算機系系主任，而瑞利成了 Google 的研究員，AT&T 實驗室的新東家不再免費提供有限狀態(tài)機 C 語言工具庫。雖然此前莫瑞等人公布了他們的詳細算法，但是省略了實現(xiàn)的細節(jié)。因此在學術界，不少科學家能夠重寫同樣功能的工具庫，但是很難達到 AT&T 工具庫的效率（即運算速度），這的確是一件令人遺憾的事。