問號表達式

《?然語?處理技術綜述（第三版）》（1）----正則表達式

寫在前?：

由于?前原作者還沒有開放第?章，我將從第?章開始介紹給?家。因業(yè)務和翻譯?平有限，?求?家明?，不當之處請?家多多包

涵，并不吝賜教。同時，本?均為我?字?字敲寫，如有與其他?雷同，純屬巧合。

第?章正則表達式、?本歸?化和編輯距離

上?的對話來??個早期的?然語?處理系統(tǒng)——ELIZA，，它可以模仿羅杰尼亞?理治療者的反應，與?戶進?有限的交談

（WeieNebAUM，1966）。ELIZA程序的簡單程度令?吃驚，它使?模式匹配來識別“你是X”之類的短語，并將它們轉換成合適的輸

出，?如“什么讓你認為我是X？”。這個簡單的技術在這個領域成功了，因為ELIZA實際上不需要知道任何東西就可以模仿?理醫(yī)?。正

如Weizenbaum所指出的，這是少數(shù)?個聽眾對其表現(xiàn)毫?察覺的對話類型。ELIZA對?類對話的模仿是?常成功的：許多與ELIZA互動的

?開始相信它真的理解他們和他們的問題。即使把程序的操作原理解釋給他們之后（WeieNebAUM，1976），許多?還繼續(xù)相信ELIZA

的能?。即使在今天，這種聊天機器?也是?種有趣的娛樂?式。

當然，現(xiàn)代會話系統(tǒng)不僅僅是?種轉換，他們可以回答問題、預訂航班或找餐館，這些功能依賴于對?戶意圖更為復雜的理解。這些

內容在第29章中我們會將介紹到。盡管如此，基于ELIZA和其他聊天機器?的簡單的基于模式的?法在?然語?處理中起著?關重要的作

?。

本章節(jié)，我們將從描述?本模式的最重要?具開始：正則表達式。正則表達式可以?來指定我們希望從?檔中提取的字符串；可以從

上?的ELIZA中轉換為“您是X”；可以來定義從?檔中提取價格表的字符串，?如$199或$24.99。

然后，我們將轉向?組稱為?本歸?化的任務，其中正則表達式起著重要的作?。歸?化?本意味著將它轉換成更?便、更標準的形

式。例如，分詞的任務，我們將要處理的?部分語?依賴于先從?本中分離或標記單詞。英語單詞通常是?空格分隔的，但空格并不總是充

分的。NewYork和rock’n’roll有時被視為?個?詞，盡管它們含有空格。?有時我們需要將I’m分為兩個詞I和am。為了處理

tweets博?或?本，我們需要標記出：）這樣的表情或標記出#nlproc這樣的標簽。有些語?，?如漢語，在單詞之間沒有空格，所以單

詞標記法更加困難。

?本歸?化的另?部分是詞形還原，任務是確定兩個詞具有相同的詞根，但它們的?字表?是有差異。例如，sang,sung,和sings

這三個詞是動詞sing的形。sing這個詞是這些詞的詞根，詞形還原器將這些詞映射為sing。詞形還原是處理形態(tài)復雜的語?必不可少的，

如阿拉伯語。詞?抽取是指?個簡單的詞形還原版本，主要是從詞尾中除去后綴。?本規(guī)范化還包括句?劃分：使?標點符號如句號或感嘆

號，將?本分解成單個句?。

最后，我們需要?較單詞和其他字符串相似度的?具。我們將引??個稱為編輯距離的算法，這個算法可以度量兩個字符串是如何根

據(jù)編輯（插?、刪除、替換）的數(shù)量來改變?個字符串到另?個字符串的。編輯距離算法的應?貫穿整個語?處理過程，從拼寫校正、語?

識別到指代消解都有應?。

2.1正則表達式

正則表達式（RE）是計算機科學標準化的成就之?，它是?種?于指定?本搜索字符串的語?。這種實?語?在每種計算機語?、

?字處理器和?本處理?具中都有使?，如UNIX?具grep或Emacs。形式上，正則表達式是?于表征?組字符串的代數(shù)表?法。它們在進

??本檢索時特別有?。當我們有?個搜索模板和?個?本語料庫來進?搜索時，正則表達式搜索整個語料庫，返回與模板匹配的所有?

本。語料庫可以是單個?檔或集合。例如，UNIX命令??具grep就是使?正則表達式，返回輸??檔中與表達式匹配的每??。

如果匹配結果不??個，搜索可以設計為返回每??或者只返回第?個匹配。在下?的?例中，我們著重介紹正則表達式匹配的每?

部分，并僅顯?第?個匹配。我們將?兩個斜杠來表達正則表達式的起始。但注意，斜杠不是正則表達式的?部分。

2.1.1基本正則表達式模板

最簡單的正則表達式是?系列簡單字符。例如，使?模板/woodchuck/來查找woodchuck。使?表達式/Buttercup/匹配包含?字

符串Buttercup的任何字符串，使?這個表達式，grep將返回I’mcalledlittleButtercup。搜索字符串可以由單個字符組成（類似/!/）

或?系列字符（如/url/）。

圖2.1?些簡單的正則表達式搜索

正則表達式是區(qū)分??寫的；?寫/s/與?寫/S/是不同的（/s/匹配?寫s?不是?寫字母S）。這意味著模板/woodchucks/將不

匹配字符串Woodchucks。我們可以??括號[]來解決這個問題。括號內的字符串指定要匹配的字符的分離。例如，圖2.2表?模

式/[WW]/匹配包含w或W的模式。

圖2.2使??括號[]表??個字符串的分離

雖然這些數(shù)字或字母類是表達式中的重要組成部分，但?正則表達式/[1234567890]/指定任?數(shù)字，

[ABCDFIGHYKLMNOPQRSTUVWXYZ]表?任??寫字母，就顯得很笨拙。括號可以與短橫線（-）?起使?，來指定?個字符范圍。模

板/[2-5]/指定字符2,3,4或5中的任何?個。模板/[b-g]指定字符b、c、d、e、f或g中的?個。圖2.3中?出了?些其他?例。

圖2.3?括號[]與-?起指定字符范圍

否定操作符：?括號中第?個符號使?插?符^，可以?來表?不包含某單個字符。例如，模式/[^a]/表?除了a之外的任何單個字

符（包括特殊字符）都匹配。如果^出現(xiàn)在其他地?，它僅表??個插?符號。圖2.4顯?了?些例?。

圖2.4^表?否定以及僅僅表??個字符

接下來我們討論可選操作符，如果想表達查找woodchuck和woodchucks，其中s是可選元素如何做？簡單的使?中括號是不?

的，因為?前只有這種形式[sS]，但它僅表?“s”或“S”，?法表達有或者沒有s的意思。在這種情況下，引?問號操作符/?/，他表

?“前?的字符出現(xiàn)或不出現(xiàn)”，如圖2.5所?。

圖2.5問號?操作符表?前?的表達式是可選的

我們可以把問號看作“問號前的字符出現(xiàn)0或?次”。也就是說，它是?種指定我們想要多少個的?法，在正則表達式中是?常重要

的。但如何表達更多次出現(xiàn)呢？例如，考慮某些“?語”，它由如下的字符串組成：

baa!

baaa!

baaaa!

baaaaa!

...

這種語?以?個b開頭，后??少有兩個a，結尾是感嘆號。這時，我們引?星號*操作符來表?“?些a”，通常叫克林*。克林*表

?“星號前?的字符或正則表達式出現(xiàn)的零或多次”。/a*/意味著“0或多個a”。它可以匹配a或aaaa，也可以匹配OffMinor，因為字符

串OffMinor有0個a。因此，匹配?個或多個a的正則表達式是/aa*/，即?個a后?跟著0或多個a。*不僅可以重復單個字符還可以重復模

板。所以/[ab]*/意味著“零或更多的a或a”（?不是“零或更多的右?括號”）。他可以匹配像aaaa或ababab或bbbb的字符串。

對于查找價格等多個數(shù)字符的情況，我們可以擴展/[0-9]/為?個整數(shù)的正則表達式/[0－9][0～9]*/。（?家可以想?下為什么

不只是/[0-9]*/？）

上?這種為數(shù)字寫兩次正則表達式的?法很啰嗦。因此有?種較短的?式來指定某個字符的“?少?個”。這就是克林+，意思

是“前?個字符或表達式出現(xiàn)?次或多次”。因此，/[0-9]+/是指定“數(shù)字序列”的標準?式。此時，我們有兩種?法來指定?語

?：/baaa*！/或者/baa+！/。

?個?常重要的特殊字符是通配符（/./），可以與任何單個字符（除了回車符）匹配的通配符表達式，如圖2.6所?。

圖2.6使?通配符.來表?任何單?字符

通配符經常與星號?起使?表?“任何字符串”。例如，我們想找aardvark出現(xiàn)兩次的句?。我們可以?正則表達

式/aardvark.*aardvark/。

錨點是將正則表達式錨定到字符串中特定位置的特殊字符。最常見的錨點是插?符號^和美元符號$。插?符號匹配??的開頭。模

板/^The/?于匹配以The開頭的?。因此，插?符號有三種?法：1）匹配??的開頭；2）在正?括號內表??個否定；3）表?插?符號

本?。?家此時可以思考?下grep或python在什么情況下能夠判斷插?符起的作?？。美元符號$匹配??的結尾。因此，模板?$是?于

匹配?末是空格的句?。/^Thedog.$/匹配只包含Thedog.的??。(我們必須使?反斜杠，因為我們想要句號?不是通配符。)

這?還有另外兩個錨：b匹配?個單詞邊界，B匹配?個?邊界。因此，/btheb/匹配單詞the?不是單詞other。從技術上講，

?于正則表達式檢索的?標“單詞”定義：任何序列的數(shù)字、下劃線或字母；這是基于編程語?中“單詞”的定義。例如，/b99b/將匹

配字符串99，Thereare99bottlesofbeeronthewall（因為99跟隨在?個空格后?）。但下?的句?，Thereare299bottlesof

beeronthewall這種情況下99不是?個詞（因為99跟在?個數(shù)字后?）。有?些例外，如，這個模板可以匹配$99中的99（因為99緊跟

在美元符號（$）后?，可是$不是?個數(shù)字，下劃線，或字母）。

2.1.2分離，分組和優(yōu)先級

假設我們需要搜索關于寵物的?字，也許我們對貓狗特別感興趣。在這種情況下，我們可能要搜索字符串cat或字符串dog。因為我們

不能??括號來搜索“cat或dog”（為什么我們不能?[catdog]？）我們需要?個新的操作符，即分離操作符，也稱為管符號。模

板/cat|dog/可以匹配cat或dog。

有時我們需要在更?的范圍內使?這個分離操作符。例如，假設我想為我的表弟戴維搜索寵物魚的信息。我怎么能指定guppy和

guppies？顯然我們不能簡單地說/guppy|ies/，因為這將只匹配字符串guppy和ies。這是因為guppy這種字符串的優(yōu)先級要?分離操作符

的優(yōu)先級?。為了使分離操作符應?在這種特定的場景，我們需要使?括號操作符（和）。?圓括號將|或*操作符括起來，讓他們看上去像

?個獨?的字符。因此，模板/gupp（y|ies）/可以實現(xiàn)我們想要分離后綴y和ies的意圖。

上?提到了，圓括號操作符可以?在*操作符上。和|不同的是，*操作符只能作?與?個獨?的字符上，?不是?個字符串上。假設我

們希望匹配字符串的重復實例，例如我們有?個包括多欄?標題（Colunmn1，Column2，Column3）的??。如果我們使?表達

式/Column?[0-9]+?*/將匹配不到所有欄?標題；相反，它僅能匹配到?個欄?標題，這個標題后?跟著任意數(shù)量的空格；這是因為*操作

符只作?于它前?的?，?不是整個序列。我們可以?括號寫表達式/(Column?[0-9]+?*)*/來匹配單詞Column，其后跟著?個數(shù)字和任

意個?，整個模板重復任意次數(shù)。

?個操作符可以優(yōu)先于另?個操作符，有時我們還會使?括號來凸顯我們的意思，這就形成了正則表達式的運算符優(yōu)先級層次。下表

給出了RE運算符從最?優(yōu)先級到最低優(yōu)先級的順序。

因此，由于*操作符具有?序列?的優(yōu)先級，/the*/匹配theeee，?不是匹配thethe。由于序列?分離具有更?的優(yōu)先

級，/the|any/匹配the或者any，但不匹配theny。

模板的應?還有另?個暗含規(guī)則。例如表達式/[a-z]*/在與?本onceuponatime匹配的時候。因為/[a-z]*/匹配零個或多個字

母，這個表達式可以匹配任何東西，或者o、on、onc或once。在這種情況下，正則表達式總是匹配最?的字符串；我們稱這是模板的貪婪

性，覆蓋盡可能多的字符串。

然?，有?些?法來執(zhí)?“?貪婪”匹配，這就?到了限定符？。例如*？表?*操作符匹配盡量少的?本。+？表?+操作符匹配盡可

能少的?本。

2.1.3?個簡單的例?

假設我們想寫?個RE來查找英??章中the的例?。?個簡單的模板可能是：

/the/

有?個問題是，這種模板會漏掉以?寫T開始的字符串（?如The）。我們將模板進?以下改進：

/[tT]he/

但是我們仍然會錯誤地檢索到包含這個the這三個字母的詞（例如，other或theology）。因此，我們需要指定兩邊都有單詞邊界：

/b[tT]heb/

有時，我們可能想在?些上下?中找到后?跟著下劃線或數(shù)字的the（the_或the25）。由于/b/不會把下劃線和數(shù)字當作單詞邊

界，這時我們不想使?/b/。我們需要指定，the的兩側沒有字母：

/[?a-zA-Z][tT]he[?a-zA-Z]/

但是這個模式有?個問題：當the位于??的開始時，就匹配不到了。這是因為我們?yōu)榱吮苊獍瑃he的詞被搜索到?引?了^操作

符，^操作符意味著the前?必須有?個單獨的（雖然?字母）字符。為了解決這個問題，我們可以通過指定要么是?的開始，要么是?字母

的字符開始。在末尾也是同樣的處理?式來避免這?點：

/(?|[?a-zA-Z])[tT]he([?a-zA-Z]|$)/

我們剛剛經歷的過程是基于修復兩種錯誤：1）假陽性，我們錯誤地匹配到了不想要的結果，如other或there。2）假陰性，我們沒

有匹配到想要的字符串，如The。在實現(xiàn)語?和語?處理系統(tǒng)中，經常需要解決這兩類錯誤。因此，減少應?程序的整體錯誤率，應在以下

兩??努?：

提?精確度（盡量減少假陽性）

增加召回（最?化假陰性）

2.1.4?個更復雜的例?

這?節(jié)，我們嘗試?個更加典型的例?，以彰顯RE的能?。假設我們想構建?個應?程序來幫助?戶在?絡上購買?臺計算機。?

戶可能希望“任何超過6GHz和500GB的磁盤空間?于1000美元的機器”。要做到這種檢索，我們?先需要能夠尋找像6GHz或500

GB或$999.99的表達式。在本節(jié)，我們將為這個任務設計?些簡單的正則表達式。

?先，讓我們完成價格的正則表達式。下?是?個美元符號的規(guī)則表達式，后?是?個數(shù)字串：

/$[0-9]+/

注意，$字符在這?不是前?討論的?結束的功能。正則表達式分析器實際上是?夠聰明的，知道這?的$并不意味著結束。（這?

留?個作業(yè)，請思考正則表達式分析器如何從上下?中計算出$的功能。）

現(xiàn)在我們在整數(shù)美元后?添加?個?數(shù)點和兩個數(shù)字：

/$[0-9]+.[0-9][0-9]/

這種模式只允許$199.99，但不匹配“$199.”。我們需要變?yōu)槊婪挚蛇x的，并且確保我們處于單詞邊界：

/b$[0-9]+(.[0-9][0-9])?b/

接下來，看?下電腦選型時處理器速度的規(guī)格如何檢索？這?有?個模板：

/b[0-9]+?*(GHz|[Gg]igahertz)b/

請注意，我們使?/?*/意味著“零或更多的?”，是因為這?可能出現(xiàn)多個空格。還需要?持可選的?數(shù)（如5.5GB）；注意在s后

使?了？，以表達s是可選的：

/b[0-9]+(.[0-9]+)??*(GB|[Gg]igabytes?)b/

2.1.5更多操作符

圖2.7顯?了常?范圍的別名，主要?于保存類型。除了*和+之外，我們還可以使?顯式數(shù)字作為計數(shù)器，將它們括在?括號中。正

則表達式/{3}/意味著“前3個字符或表達式要確切出現(xiàn)3次”。那么，/a.{24}z/將匹配?個字母a，后?有24個點，再后?是字母

z（但不是a后?跟23個或25個點，然后后?是Z）。

圖2.7常?字符集別名

?括號也可以指定?個數(shù)字區(qū)間。例如/{n,m}/指定從前?個字符或表達式的n到m出現(xiàn)；/{n,}/意味著前?的表達式?少出現(xiàn)n

次。可計數(shù)的RE總結在圖2.8中。

圖2.8?于計數(shù)的正則表達式運算符。

最后，某些字符通過使?反斜杠轉義后表達特殊含義，?如n表?另起??，t表?tab。另外，特殊字符在表達字符原本含義時需

要反斜杠（）進?轉義。例如,*[在表達這些符號本?含義時，需要使?/./，/*/，/[/，/。（參見圖2.9）。

圖2.9需要反斜杠的字符

2.1.6正則表達式替換、捕獲組和ELIZA

正則表達式的?個重要?途是替換。例如，在Python和Unix命令（如vim或d）中通過使?s/regexp1/pattern/的正則表達式，

來完成?個字符串替換另?個字符串的功能，例如

s/colour/color/

在實際應?中，我們還經常?到，將匹配到的字符串變形后?于替換。這?有?個任務，假如我們想將?本中所有的數(shù)字前后加上尖

括號<>，如將the35boxes改為the<35>boxes。我們想??種?法來引?我們找到的整數(shù)，這樣我們就可以很容易地添加括號。要做到

這?點，我們使?圓括號（）將第?個模板括起來，并在第?個模式中使?數(shù)字運算符1來回溯。這就是它的樣?：

s/([0-9]+)/<1>/

括號和數(shù)字運算符還可以指定某個字符串或表達式必須在?本中出現(xiàn)兩次。例如，假設我們要檢索“theXertheywere,theXer

theywillbe”這種句?，約定兩個X代表形同的字符串。我們可以這樣做：?括號運算符將第?個X括起來，然后?數(shù)字運算符1替換第?

個X，如下：

/the(.*)ertheywere,the1ertheywillbe/

在這?，1將被替換為第?個匹配項匹配的任何字符串。使?這個模板可以匹配Thebiggertheywere,thebiggertheywillbe，

但匹配不到Thebiggertheywere,thefastertheywillbe。

使?圓括號將模式存儲在內存中稱為捕獲組。每次使?捕獲組（即圓括號包圍模板）時，捕獲組中的模板匹配到的結果將存儲在?個

數(shù)字編號寄存器中，通過“數(shù)字”提取出來。如果有兩個捕獲組，那么2代表第?個捕獲組匹配到的內容。因此/the(.*)erthey(.*),the

1erwe2/將匹配到Thefastertheyran,thefasterweran，但不能匹配Thefastertheyran,thefasterweate。同樣，第三捕獲

組存儲在3，第四個是4，等等。

因此，括號在正則表達式中具有雙重功能；它們?于分組或優(yōu)先級，即指定操作符的順序，另?個作?是，使?寄存器捕獲某些東

西。有時我們可能希望使?圓括號?于進?分組，但不想使?捕獲組的模式。在這種情況下，我們使??捕獲組，形式是在左圓括號后?加

上?:即(?:模板)。例如

/(?:some|afew)(people|cats)likesome1/

將匹配到somecatslikesomepeople，但匹配不到somepeoplelikesomeafew。

替換和捕獲組在實現(xiàn)簡單的聊天機器?（如ELIZA）中?常有?。回憶ELIZA模擬羅杰斯?理學家進?的以下對話：

ELIZA是通過?系列或級聯(lián)的正則表達式替換來?作的，每個正則表達式替換和改變輸??的某些部分。?先是將my替換為

YOUR，將I’m替換為YOUARE。然后替換輸?中匹配到的內容。下?是?些例?：

由于多個替換都可以應?于給定的輸?，那么替換被賦予?個秩并按順序應?。更多關于創(chuàng)建模板的題?請查看練習2.3。我們將在

第29章中詳細說明ELIZA體系結構的細節(jié)。

2.1.7預測斷?

最后，我們介紹?下預測斷?：在?本中只檢查是否匹配，但不移動匹配游標。

預測斷?使?了（？語法，類似的語法我們在?捕獲組的定義中看到過。操作符(?=pattern)，表?如果模板能匹配上則該斷?返

回true，但為零寬度，即匹配指針不前進。操作符(?!pattern)只有在不匹配時返回true，但同樣是零寬度，不前進光標。在?些復雜的模

板中，要排除?個特殊的情況時，通常使?否定的斷?。例如，假設我們查找?個開頭單詞不是“Volcano”的句?。我們可以?否定的

預測斷?來做到這?點：

/(??!Volcano)[A-Za-z]+/