正則表達式在漢英對照中國文化術語抽取中應用

姚振軍, 黃德根, 紀翔宇

(1.大連理工大學計算機科學與技術學院,遼寧大連 116024;2.東北財經大學國際商務外語學院,遼寧大連 116024)

0 引 言

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

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

在使用正則表達式實現詞匯抽取的過程中,本研究通過簡化正則表達式規則來提高正則表達式運行效率,通過設計正則表達式生成器來降低正則表達式的使用難度.

1 正則表達式及其元字符簡述

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

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

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

2 正則表達式規則簡化方案

2.1 具體方案

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

不過上述方法對于效率的提升空間是有限的,由上章可知,通用的正則表達式的元字符有11個,有很多時間會花費在元字符的判斷上,如果可以根據需要減少元字符個數,對于正則表達式效率上的提升將是巨大的.

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

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

本項目的重點不是通用性,而是運行效率,所以項目選擇使用自行設計正則表達式程序來處理模式匹配,這樣做雖然降低了正則表達式通用性,但是與使用標準的Java正則表達式軟件包相比,系統處理特定模式文本的效率更高.與標準的規則相比,這個簡化版的規則將元字符的個數精簡到3個.

2.2 方案程序實現

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

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

3 正則表達式生成器

3.1 正則表達式可讀性問題的提出

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

正則表達式生成器即是針對正則表達式可讀性差、難以使用的問題提出的.生成器的基本思想是:首先,用戶將一個待搜索文本的例子輸入系統;然后,系統將這個例子的模式分析出來,轉換成標準的正則表達式;最后使用上一步得到的正則表達式文本到目標字符串中去模式匹配.比如說,用戶只需要輸入XXX,系統會自動學習將輸入的文本轉換成正則表達式YYY,這樣就ZZZ.這種生成器的實際應用比較簡單,主要原因有兩個:其一,項目使用的正則表達式規則簡單,表達式元字符少且含義簡單;其二,項目設計針對的目標模式相對固定,結構簡單.

3.2 正則表達式生成器程序流程

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

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

4 實驗結果與討論

本項目中的實驗樣本選自由中華人民共和國教育部主管,高等教育出版社與施普林格(Springer)公司共同創立的“中國學術前沿期刊網”中的“文學研究前沿”(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,該樣本中中國文化術語在文中的格式為“中文術語(英文翻譯)”.運用本項目中設計的正則表達式系統進行匹配,使用的正則表達式為″#＊(@＊)″,匹配時間為16～32m s,正確抽取177個中英文對照的詞條;使用Java自帶的正則表達式進行處理,其正則表達式為″([ u4e00- u9fa5])+{2,2}([(][a-zA-z]+[)])″,時間為47 ～ 68 m s,正確抽取177個中英文對照的詞條.樣本2:M etal typography, stone lithography and the dissemination of M ing-Qing popular fictions in Shanghaibetween 1874 and 1911,運用本項目中設計的正則表達式系統進行匹配,使用的正則表達式為″#＊(@＊)″,匹配時間為 15 ～ 16 ms,正確抽取65個中英文對照的詞條;使用Java自帶的正則表達式進行處理,其正則表達式為″([ u4e00- u9fa5])+{2,2}([(][a-zA-z]+[)])″,時間為16～31m s,正確抽取65個中英文對照的詞條.從時間上看,本研究中設計的系統可以將抽取效率提高1倍左右,正確率可以達到100%.

同時,采用本項目中的正則表達式系統,用戶在使用時不用書寫復雜的正則表達式,只要將一個目標文本的例子輸入系統,系統就可以自動生成目標正則表達式.比如上面的應用,用戶只要輸入″紅樓夢(A Dream of Red M ansions)″,系統就可以生成″#＊(@＊)″,并用生成的正則表達式在目標典籍中匹配目標文本.

5 結 語

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

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

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

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

[4]佘石泉,周肆清.正則表達式在編程題自動閱卷中的應用[J].計算機技術與發展,2007,17(7):224-246

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

[6]鄧緒斌,朱揚勇.ReDE:一個基于正則表達式的生物數據抽取方法[J].計算機研究與發展,2005,42(12):2184-2191

[7]葛漢強,陳和平.Java正則表達式優化[J].計算機系統應用,2008,17(9):102-104

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

[9]陳曙暉,蘇金樹,范慧萍,等.一種基于深度報文檢測的FSM狀態表壓縮技術[J].計算機研究與發展,2008,45(8):1299-1305

[10]李偉男,鄂躍鵬,葛敬國,等.多模式匹配算法及硬件實現[J].軟件學報,2006,17(12):2403-2415