正則表達(dá)式在漢英對(duì)照中國(guó)文化術(shù)語(yǔ)抽取中應(yīng)用

姚振軍, 黃德根, 紀(jì)翔宇

(1.大連理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,遼寧大連 116024;2.東北財(cái)經(jīng)大學(xué)國(guó)際商務(wù)外語(yǔ)學(xué)院,遼寧大連 116024)

0 引 言

當(dāng)前對(duì)于正則表達(dá)式的研究集中于3個(gè)方面:一是應(yīng)用正則表達(dá)式解決實(shí)際問題,即基于正則表達(dá)式的深度包檢測(cè)算法[1],對(duì)專利信息提取[2],對(duì)Web數(shù)據(jù)提取[3],編程題自動(dòng)閱卷[4]以及電子政務(wù)客戶端認(rèn)證[5],設(shè)計(jì)基于正則表達(dá)式的關(guān)系數(shù)據(jù)庫(kù)模式生成算法和通用抽取與組裝算法[6];二是通過對(duì)正則表達(dá)式語(yǔ)句的優(yōu)化來提高匹配效率[7];三是集中于正則表達(dá)式引擎的優(yōu)化,通過將NFA轉(zhuǎn)化為DFA引擎來提高匹配效率[1、8].此外,還存在對(duì)于模式匹配算法及優(yōu)化的研究[9、10].

本文的研究背景是設(shè)計(jì)一個(gè)基于網(wǎng)絡(luò)的漢英對(duì)照的中國(guó)文化術(shù)語(yǔ)詞典,在建設(shè)詞典過程中,需要建立一個(gè)中國(guó)文化術(shù)語(yǔ)漢英對(duì)照詞庫(kù).使用計(jì)算機(jī)自動(dòng)完成從異構(gòu)的現(xiàn)有的典籍英譯文獻(xiàn)中抽取漢語(yǔ)典籍詞匯以及與之對(duì)應(yīng)的英文翻譯成為快速擴(kuò)充詞庫(kù)的最好手段.這個(gè)抽取面臨的問題主要有兩個(gè):其一,實(shí)現(xiàn)具有特定模式的文本的匹配,即在文獻(xiàn)中快速找出漢語(yǔ)典籍詞匯以及與之對(duì)應(yīng)的英文翻譯;其二,面對(duì)來源廣泛的文獻(xiàn),每種文獻(xiàn)的目標(biāo)抽取文本的模式略有不同,要保證程序的通用性.針對(duì)這兩個(gè)問題,本文選擇正則表達(dá)式來實(shí)現(xiàn)目標(biāo)文本的匹配,首先,正則表達(dá)式是用于模式匹配的專用語(yǔ)言;其次,針對(duì)不同的模式,正則表達(dá)式可以靈活地構(gòu)造不同的專用語(yǔ)言來實(shí)現(xiàn)模式匹配.所以,正則表達(dá)式可以很好解決項(xiàng)目中詞庫(kù)建立的問題.

在使用正則表達(dá)式實(shí)現(xiàn)詞匯抽取的過程中,本研究通過簡(jiǎn)化正則表達(dá)式規(guī)則來提高正則表達(dá)式運(yùn)行效率,通過設(shè)計(jì)正則表達(dá)式生成器來降低正則表達(dá)式的使用難度.

1 正則表達(dá)式及其元字符簡(jiǎn)述

正則表達(dá)式是一個(gè)用來描述或者匹配一系列符合某個(gè)模式的字符串的單個(gè)字符串.許多文本編輯器軟件(比如Unix上的編輯器ed)以及軟件開發(fā)語(yǔ)言(比如Java語(yǔ)言有Jakarta-ORO正則表達(dá)式庫(kù)來提供使用正則表達(dá)式的API,腳本語(yǔ)言JavaScript也提供函數(shù)處理正則表達(dá)式)都使用正則表達(dá)式處理文本字符串,通過正則表達(dá)式將字符串中符合某一模式的文本進(jìn)行查找和替換.一個(gè)正則表達(dá)式用來描述一種模式,如M[AI]KE這個(gè)正則表達(dá)式就可以描述MIKE、MAKE這兩個(gè)單詞的模式.目前應(yīng)用中通用的正則表達(dá)式規(guī)則中元字符部分如表1所示.

表1 通用的正則表達(dá)式部分元字符Tab.1 Part of themeta-characters o f regular exp ression

由表1可知,在通用的正則表達(dá)式規(guī)則中元字符有11個(gè),為了處理這些元字符,正則表達(dá)式處理程序中至少要出現(xiàn)11個(gè)判斷語(yǔ)句,即正則表達(dá)式中的一個(gè)字符可能要經(jīng)過11次判斷才能斷定與待搜索文本中對(duì)應(yīng)字符是否匹配,所以,現(xiàn)有的正則表達(dá)式軟件包都非常龐大.grep中的代碼長(zhǎng)度超過500行(大約10頁(yè)書的文字長(zhǎng)度),并且在代碼周圍還有復(fù)雜的上下文環(huán)境[1].Java中開源的正則表達(dá)式處理包則更為龐大,比如Jakarta-ORO包就有65.7 kb.這是因?yàn)檫@些軟件包要綜合考慮靈活性、通用性、運(yùn)行速度以及各種復(fù)雜的應(yīng)用環(huán)境.

2 正則表達(dá)式規(guī)則簡(jiǎn)化方案

2.1 具體方案

在使用標(biāo)準(zhǔn)正則表達(dá)式過程中,如果用戶希望在完成文本匹配時(shí)實(shí)現(xiàn)效率的提升,唯一的辦法是通過先分析待檢索的文本的特性,然后寫出符合待檢索文本模式的正則表達(dá)式字符串.這樣做可以在降低一部分匹配正確率的基礎(chǔ)上提高程序的運(yùn)行效率.比如針對(duì)通用的 HTTP URL:http://hostname/path.htm l,其對(duì)應(yīng)的簡(jiǎn)單正則表達(dá)式為http://[ ]＊.htm l?很明顯,對(duì)于一般的URL,這條正則表達(dá)式可以匹配,但是對(duì)于形如http://.../.htm l的URL,該正則表達(dá)式也可以匹配,所以如果用戶可以確認(rèn)預(yù)搜索的文本中不含有形如http://.../.htm l的URL,就可以使用上面這種簡(jiǎn)單的正則表達(dá)式實(shí)現(xiàn)對(duì)目標(biāo)文本中URL的匹配.

不過上述方法對(duì)于效率的提升空間是有限的,由上章可知,通用的正則表達(dá)式的元字符有11個(gè),有很多時(shí)間會(huì)花費(fèi)在元字符的判斷上,如果可以根據(jù)需要減少元字符個(gè)數(shù),對(duì)于正則表達(dá)式效率上的提升將是巨大的.

本文提出的解決辦法,是根據(jù)待搜索文本的實(shí)際情況,選擇使用元字符,建立符合特定需要的正則表達(dá)式.項(xiàng)目中各種不同來源的中國(guó)文化術(shù)語(yǔ)及其翻譯的結(jié)構(gòu)格式一般為“儒林外史(The Scholars)”;“儒 林外史 The Scholars” ;“(The Scholars)儒林外史”.抽象成模式為“中文詞組(英文詞組)”;“中文詞組 英文詞組”;“(英文詞組)中文詞組”.項(xiàng)目中的文本匹配中只要處理中文字符和英文字符,模式中出現(xiàn)的其他符號(hào)只要原樣匹配,就建立了簡(jiǎn)化的正則表達(dá)式模型,如表2所示.

表2 簡(jiǎn)化方案元字符表Tab.2 The meta-characters of the simp lified regular expression

本項(xiàng)目的重點(diǎn)不是通用性,而是運(yùn)行效率,所以項(xiàng)目選擇使用自行設(shè)計(jì)正則表達(dá)式程序來處理模式匹配,這樣做雖然降低了正則表達(dá)式通用性,但是與使用標(biāo)準(zhǔn)的Java正則表達(dá)式軟件包相比,系統(tǒng)處理特定模式文本的效率更高.與標(biāo)準(zhǔn)的規(guī)則相比,這個(gè)簡(jiǎn)化版的規(guī)則將元字符的個(gè)數(shù)精簡(jiǎn)到3個(gè).

2.2 方案程序?qū)崿F(xiàn)

match()函數(shù)采用遞進(jìn)的方式在目標(biāo)字符串中進(jìn)行模式匹配.match中textpos的值會(huì)以步長(zhǎng)1自加,從而遍歷一遍字符串.″matchhere()==1″這句是調(diào)用matchhere函數(shù)執(zhí)行匹配操作,通過返回值判斷是否找到一個(gè)匹配的模式文本的.如果找到,則打印模式匹配到的文本;如果沒找到 ,執(zhí)行語(yǔ)句″if(regepos>0)textpos--;″這條語(yǔ)句用來控制對(duì)于目標(biāo)字符串的遞進(jìn)操作回溯.邏輯上,如果字符串與正則表達(dá)式在除了第一個(gè)字符外的某個(gè)位置上發(fā)生不匹配,則新的匹配應(yīng)在字符串中發(fā)生不匹配的位置重新開始;但是如果字符串與正則表達(dá)式在第一個(gè)字符處發(fā)生不匹配,則新的模式匹配應(yīng)該從字符串中不匹配發(fā)生的下一個(gè)位置重新開始.這句代碼就是實(shí)現(xiàn)這個(gè)邏輯,通過判斷匹配不成功時(shí)正則表達(dá)式進(jìn)行到的位置來控制目標(biāo)字符串中匹配重新開始的位置,通過將regepos歸0來表示模式匹配重新開始,將textpos增1表示從下一個(gè)位置開始新的匹配.

matchhere()是完成匹配操作的函數(shù).第1個(gè)判斷是這個(gè)遞歸函數(shù)的結(jié)束條件之一,如果對(duì)正則表達(dá)式的遍歷完成,則說明1次模式匹配操作成功結(jié)束,找到1條匹配的模式文本,函數(shù)返回值為1.第2個(gè)判斷是第2個(gè)結(jié)束條件,判斷字符串是否結(jié)束,這個(gè)判斷中還有一個(gè)子判斷:如果字符串結(jié)束而且正則表達(dá)式遍歷到最后一位則說明找到一個(gè)匹配文本,返回值為1,否則返回值為0.第3個(gè)判斷是對(duì)″＊″號(hào)操作,根據(jù)模型,″＊″這個(gè)符號(hào)表示匹配正則表達(dá)式中前一個(gè)字符的0個(gè)或者多個(gè)出現(xiàn),這個(gè)判斷中會(huì)調(diào)用matchstar()函數(shù).matchstar(c,rege,text)將字符串與c所對(duì)應(yīng)的符號(hào)進(jìn)行盡可能多的匹配.在matchstar()中,首先判斷c是中文字符還是英文字符,然后將當(dāng)前指向的字符串字符與c匹配,如果匹配,則通過遞歸調(diào)用matchhere()函數(shù)來對(duì)c與字符串中下一個(gè)字符匹配;如果不匹配,說明對(duì)c的盡可能多的匹配已經(jīng)完成,正則表達(dá)式會(huì)遞進(jìn)到下一位.第4個(gè)判斷是原樣字符匹配,如果正則表達(dá)式中當(dāng)前字符不是特殊字符,就進(jìn)行原樣字符匹配,然后通過遞歸調(diào)用matchhere()函數(shù)開始下一個(gè)位置的匹配.第5個(gè)判斷是對(duì)于中文字符的匹配.第6個(gè)判斷是對(duì)于英文字符的匹配.這個(gè)函數(shù)是一個(gè)遞歸函數(shù),通過自調(diào)用來實(shí)現(xiàn)一次完整模式匹配操作,函數(shù)中通過textpos來控制目標(biāo)字符串中當(dāng)前指向字符的位置,regepos來控制正則表達(dá)式中當(dāng)前指向字符的位置,這兩個(gè)變量是全局變量,保證了模式匹配的操作在全局范圍是統(tǒng)一的.

3 正則表達(dá)式生成器

3.1 正則表達(dá)式可讀性問題的提出

比如模式″中文詞組(英文詞組)″,用標(biāo)準(zhǔn)正則表達(dá)式描述為″[ u4e00- u9fa5]＊([A-Zaz]＊)″,用項(xiàng)目中的正則表達(dá)式描述為″#＊(@＊)″.由此可見,不論是標(biāo)準(zhǔn)的正則表達(dá)式,還是項(xiàng)目中的,都是不可讀的,一個(gè)沒有使用正則表達(dá)式經(jīng)驗(yàn)的人不知道正則表達(dá)式文本的含義,也就更談不上使用正則表達(dá)式了.正則表達(dá)式的書寫需要書寫者熟悉正則表達(dá)式的語(yǔ)法規(guī)則,同時(shí)要具有一定的計(jì)算機(jī)知識(shí)(比如用戶要知道漢字以UTF-8編碼表示的范圍是4e00到9fa5).雖然項(xiàng)目使用的正則表達(dá)式規(guī)則簡(jiǎn)單,但是″#＊(@＊)″這樣不易理解的描述仍然讓用戶手足無措,如何讓普通的、不具有專業(yè)知識(shí)的用戶書寫符合規(guī)范的正則表達(dá)式文本是正則表達(dá)式使用中的難題.

正則表達(dá)式生成器即是針對(duì)正則表達(dá)式可讀性差、難以使用的問題提出的.生成器的基本思想是:首先,用戶將一個(gè)待搜索文本的例子輸入系統(tǒng);然后,系統(tǒng)將這個(gè)例子的模式分析出來,轉(zhuǎn)換成標(biāo)準(zhǔn)的正則表達(dá)式;最后使用上一步得到的正則表達(dá)式文本到目標(biāo)字符串中去模式匹配.比如說,用戶只需要輸入XXX,系統(tǒng)會(huì)自動(dòng)學(xué)習(xí)將輸入的文本轉(zhuǎn)換成正則表達(dá)式Y(jié)YY,這樣就ZZZ.這種生成器的實(shí)際應(yīng)用比較簡(jiǎn)單,主要原因有兩個(gè):其一,項(xiàng)目使用的正則表達(dá)式規(guī)則簡(jiǎn)單,表達(dá)式元字符少且含義簡(jiǎn)單;其二,項(xiàng)目設(shè)計(jì)針對(duì)的目標(biāo)模式相對(duì)固定,結(jié)構(gòu)簡(jiǎn)單.

3.2 正則表達(dá)式生成器程序流程

圖1描述了程序如何從一段作為示例的文本中自動(dòng)提取模式的過程,這個(gè)圖做了一定的簡(jiǎn)化,省略了對(duì)目標(biāo)字符串的遍歷過程.程序完全使用Java的基本包編寫,不用添加任何Java擴(kuò)展包.通過″if(text[i]>=0x4e00&&text[i]<=0x9fa5)″這句代碼判斷當(dāng)前例子中指向字符是否為中文,Java中對(duì)于字符是按照UTF-8編碼進(jìn)行處理的,漢字在UTF-8碼中的范圍是16進(jìn)制的4e00到9fa5.″match+=″#＊″是在正則表達(dá)式中添加代表漢字的特殊字符以及″＊″,加上″＊″說明漢字字符可以重復(fù)出現(xiàn).例如用戶輸入一個(gè)例子″中國(guó)(China)″,系統(tǒng)會(huì)將這個(gè)例子轉(zhuǎn)換成系統(tǒng)可以識(shí)別的正則表達(dá)式″#＊(@＊)″;又比如用戶輸入的例子是″美國(guó)the USA″,系統(tǒng)會(huì)識(shí)別例子,抽象出對(duì)應(yīng)的正則表達(dá)式″#＊@＊″.如此,用戶就可以在不了解正則表達(dá)式規(guī)則的情況下使用正則表達(dá)式來工作.

圖1 正則表達(dá)式生成器流程圖Fig.1 The flow chart of the generating engine of regular exp ression

4 實(shí)驗(yàn)結(jié)果與討論

本項(xiàng)目中的實(shí)驗(yàn)樣本選自由中華人民共和國(guó)教育部主管,高等教育出版社與施普林格(Springer)公司共同創(chuàng)立的“中國(guó)學(xué)術(shù)前沿期刊網(wǎng)”中的“文學(xué)研究前沿”(Frontiers of Literary Studies in China)部分的.pdf格式的文章.樣本1:The eastw ard transition of Chinese cu lture in the Eastern Han Dynasty and the north-south difference of scholarship &literature in the Eastern Jin,Southern and Northern Dynasties,該樣本中中國(guó)文化術(shù)語(yǔ)在文中的格式為“中文術(shù)語(yǔ)(英文翻譯)”.運(yùn)用本項(xiàng)目中設(shè)計(jì)的正則表達(dá)式系統(tǒng)進(jìn)行匹配,使用的正則表達(dá)式為″#＊(@＊)″,匹配時(shí)間為16～32m s,正確抽取177個(gè)中英文對(duì)照的詞條;使用Java自帶的正則表達(dá)式進(jìn)行處理,其正則表達(dá)式為″([ u4e00- u9fa5])+{2,2}([(][a-zA-z]+[)])″,時(shí)間為47 ～ 68 m s,正確抽取177個(gè)中英文對(duì)照的詞條.樣本2:M etal typography, stone lithography and the dissemination of M ing-Qing popular fictions in Shanghaibetween 1874 and 1911,運(yùn)用本項(xiàng)目中設(shè)計(jì)的正則表達(dá)式系統(tǒng)進(jìn)行匹配,使用的正則表達(dá)式為″#＊(@＊)″,匹配時(shí)間為 15 ～ 16 ms,正確抽取65個(gè)中英文對(duì)照的詞條;使用Java自帶的正則表達(dá)式進(jìn)行處理,其正則表達(dá)式為″([ u4e00- u9fa5])+{2,2}([(][a-zA-z]+[)])″,時(shí)間為16～31m s,正確抽取65個(gè)中英文對(duì)照的詞條.從時(shí)間上看,本研究中設(shè)計(jì)的系統(tǒng)可以將抽取效率提高1倍左右,正確率可以達(dá)到100%.

同時(shí),采用本項(xiàng)目中的正則表達(dá)式系統(tǒng),用戶在使用時(shí)不用書寫復(fù)雜的正則表達(dá)式,只要將一個(gè)目標(biāo)文本的例子輸入系統(tǒng),系統(tǒng)就可以自動(dòng)生成目標(biāo)正則表達(dá)式.比如上面的應(yīng)用,用戶只要輸入″紅樓夢(mèng)(A Dream of Red M ansions)″,系統(tǒng)就可以生成″#＊(@＊)″,并用生成的正則表達(dá)式在目標(biāo)典籍中匹配目標(biāo)文本.

5 結(jié) 語(yǔ)

本文提出了結(jié)合應(yīng)用需求,通過簡(jiǎn)化正則表達(dá)式的規(guī)則來提高正則表達(dá)式在特定應(yīng)用需求中文本匹配效率的思想,并通過程序證明了這種提高的可能性.通過精簡(jiǎn)元字符的個(gè)數(shù),提高了正則表達(dá)式對(duì)特定數(shù)據(jù)庫(kù)中的文本處理的速度,在對(duì)大數(shù)據(jù)量處理時(shí),本文的方法就會(huì)有良好的效果.同時(shí)通過正則表達(dá)式生成器,嘗試解決正則表達(dá)式應(yīng)用過程中可讀性差、用戶使用難度大的問題.本研究下一步將提高項(xiàng)目中正則表達(dá)式應(yīng)用系統(tǒng)代碼效率,以及在全規(guī)則的正則表達(dá)式系統(tǒng)中進(jìn)行符合用戶需求的正則表達(dá)式生成器設(shè)計(jì)來降低用戶使用難度.

[1]丁 晶,陳曉嵐,吳 萍.基于正則表達(dá)式的深度包檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用,2007,27(9):2185-2186

[2]邱清盈,鄭國(guó)民,馮培恩,等.基于正則表達(dá)式的專利信息提取方法研究[J].中國(guó)機(jī)械工程,2007,18(10):2326-2329

[3]劉松業(yè).正則表達(dá)式的W eb數(shù)據(jù)提取研究[J].電腦編程技巧與維護(hù),2008,16(16):89-91

[4]佘石泉,周肆清.正則表達(dá)式在編程題自動(dòng)閱卷中的應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(7):224-246

[5]王功明,吳華瑞,趙春江,等.正則表達(dá)式在電子政務(wù)客戶端校驗(yàn)中的應(yīng)用[J].計(jì)算機(jī)工程,2007,33(9):269-271

[6]鄧緒斌,朱揚(yáng)勇.ReDE:一個(gè)基于正則表達(dá)式的生物數(shù)據(jù)抽取方法[J].計(jì)算機(jī)研究與發(fā)展,2005,42(12):2184-2191

[7]葛漢強(qiáng),陳和平.Java正則表達(dá)式優(yōu)化[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2008,17(9):102-104

[8]王 艷,李冬梅.基于正則表達(dá)式的協(xié)議識(shí)別方案[J].軟件導(dǎo)刊,2009,8(2):47-49

[9]陳曙暉,蘇金樹,范慧萍,等.一種基于深度報(bào)文檢測(cè)的FSM狀態(tài)表壓縮技術(shù)[J].計(jì)算機(jī)研究與發(fā)展,2008,45(8):1299-1305

[10]李偉男,鄂躍鵬,葛敬國(guó),等.多模式匹配算法及硬件實(shí)現(xiàn)[J].軟件學(xué)報(bào),2006,17(12):2403-2415