詞類共現(xiàn)頻率的MapReduce并行生成方法

程興國，肖南峰

(華南理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，廣州 510640)

在語言學(xué)中，語料庫(corpus)指大量文本的集合。庫中的文本(稱為語料)經(jīng)過整理通常具有既定的格式與標(biāo)記，特指計算機(jī)存儲的數(shù)字化語料庫。

語料庫是語料庫語言學(xué)研究的基礎(chǔ)資源，也是經(jīng)驗主義語言研究方法的主要資源，應(yīng)用于詞典編纂、語言教學(xué)、傳統(tǒng)語言研究、自然語言處理中基于統(tǒng)計或?qū)嵗难芯康确矫?。詞類共現(xiàn)是其研究內(nèi)容之一，詞類共現(xiàn)頻率以共現(xiàn)矩陣的形式表達(dá)［2］。

共現(xiàn)矩陣是一個n×n的方陣，n是所需處理的語料中的單詞數(shù)(不同單詞的數(shù)量)。矩陣元素mij的值代表單詞wi和wj的共現(xiàn)(共同出現(xiàn))次數(shù)。wi，wj共現(xiàn)定義為:wi，wj在指定的上下文范圍中同時出現(xiàn)。上下文的范圍可以有各種定義，例如同一個句子、同一個段落、同一個文檔或是同一個由連續(xù)k個單詞構(gòu)成的序列(k的值也是可以定義的)。由于共現(xiàn)關(guān)系是對稱關(guān)系，因此m的上三角陣與下三角陣是相同的［3］。

共現(xiàn)矩陣的空間開銷是O(n2)，其中n為詞匯表(vocabulary)的大小(即不同單詞的數(shù)量)。根據(jù)數(shù)據(jù)集的不同，詞匯表的大小也會有差距:英語語料庫中可能包含幾萬個詞匯，而對于Web規(guī)模的語料庫則可能有幾十億大的詞匯表。如果詞匯表不大，共現(xiàn)矩陣能放入單機(jī)內(nèi)存中處理是最好不過的。但是大的語料數(shù)據(jù)往往有很大的詞匯表，以至于共現(xiàn)矩陣過大無法放進(jìn)內(nèi)存。虛存的使用會降低算法性能，即使壓縮能將共現(xiàn)矩陣的空間開銷降低一些，這種基于單機(jī)、主存的處理模式仍是有上限的。本文基于MapReduce模型實現(xiàn)共現(xiàn)矩陣的計算算法，具有良好的可擴(kuò)展性，能處理大規(guī)模語料數(shù)據(jù)。

1 MapReduce編程模型

MapReduce模型是Google實驗室提出的分布式并行編程模型或框架，它能組織集群來處理大規(guī)模數(shù)據(jù)集，成為云計算平臺主流的并行數(shù)據(jù)處理模型。Apache開源社區(qū)的Hadoop項目用Java語言實現(xiàn)了該模型［4－5］。

MapReduce編程模型的基本思路是將大數(shù)據(jù)集分解為成百上千的小數(shù)據(jù)集splits，每個(或若干個)數(shù)據(jù)集分別由集群中的1個節(jié)點(一般是一臺普通的計算機(jī))并行執(zhí)行Map計算任務(wù)(指定了映射規(guī)則)并生成中間結(jié)果，然后這些中間結(jié)果又由大量的節(jié)點并行執(zhí)行Reduce計算任務(wù)(指定了歸約規(guī)則)，形成最終結(jié)果。圖1描述了MapReduce的運行機(jī)制。在數(shù)據(jù)輸入階段，JobTracker獲得待計算數(shù)據(jù)片在NameNode上的存儲元信息;在Map階段，JobTracker指派多個TaskTracker完成Map運算任務(wù)并生成中間結(jié)果;Partition階段完成中間結(jié)果對Reducer的分派;Shuffle階段完成中間計算結(jié)果的混排交換;JobTracker指派Task-Tracker完成Reduce任務(wù);Reduce任務(wù)完成后通知JobTracker與NameNode以產(chǎn)生最后的輸出結(jié)果。MapReduce詳細(xì)執(zhí)行過程如圖1所示［6］。

圖1 MapReduce詳細(xì)執(zhí)行過程

2 詞類共現(xiàn)頻率的MapReduce方法

2.1 pair算法

表1展示了一種基于pair的MapReduce共現(xiàn)矩陣計算算法(以下簡稱為pair算法)。

表1 pair算法偽代碼清單

mapper接受(docid，doc)對作為輸入，對于每個共現(xiàn)對(w，u)都產(chǎn)生一個輸出key-value對(見表1的第5行)。這里采用直觀的二層循環(huán)的方式完成:第1層循環(huán)遍歷所有單詞;第2層循環(huán)遍歷所有與當(dāng)前單詞相鄰(共現(xiàn))的單詞。如果將共現(xiàn)矩陣看作一張圖(graph)，這相當(dāng)于每次輸出圖中的一條邊上的一個計數(shù)。

reducer將所有具有相同key值的((w，u)，1)相加得出最終的((w，u)，s)集合，集合中的每個元素對應(yīng)共現(xiàn)矩陣中的一個元素，因此這個集合等價于共現(xiàn)矩陣。

2.2 stripe算法

表2展示了一種基于stripe的MapReduce共現(xiàn)矩陣計算算法(以下簡稱為stripe算法)。

表2 stripe算法偽代碼清單

mapper構(gòu)造當(dāng)前文檔的共現(xiàn)對的過程與表1所示算法類似，也是通過二層循環(huán)，但mapper記錄與輸出數(shù)據(jù)的方式有了一些變化:對于當(dāng)前文檔的每個單詞/術(shù)語(term)w，維護(hù)一個關(guān)聯(lián)數(shù)組H，使得H{u}記錄的是共現(xiàn)對(w，u)出現(xiàn)的次數(shù)。reduce操作則是對分配到當(dāng)前reducer的由mapper產(chǎn)生的(w，H)對進(jìn)行加和合并，最后得到一個(w，H)的集合。對于其中每個元素，w是一個單詞/術(shù)語，H中存儲的是所有與w共現(xiàn)的單詞u以及共現(xiàn)對(w，u)出現(xiàn)的次數(shù)。這個集合同樣等價于共現(xiàn)矩陣。

為了更好地理解stripe算法，下面結(jié)合例子來說明。例如，對于如下的共現(xiàn)對輸入:

文檔 1(1，2)(1，2)(1，3)(2，3)

文檔 2(2，4)(1，4)(3，4)

輸出共現(xiàn)矩陣(共現(xiàn)對計數(shù)):

(1，2)∶2(1，3)∶1(2，3)∶1(2，4)∶1(1，4)∶1(3，4)∶1

stripe模式在mapper內(nèi)對于當(dāng)前單詞wi維護(hù)一個關(guān)聯(lián)數(shù)組(可以是哈希表、treemap等k－v結(jié)構(gòu))H。在H中，k是與wi存在共現(xiàn)關(guān)系的單詞wj，v是共現(xiàn)對(wi，wj)的計數(shù)。例如，對于上面給出的實例，當(dāng)處理文檔1時，mapper有如表3所示的處理過程。

表3 stripe模式算法處理過程

隨后，reducer接受(w，［H1，H2，H3…］)，合并H1，H2，H3…后輸出結(jié)果，共現(xiàn)矩陣計算完畢。

2.3 pair算法與stripe算法的比較

pair算法與stripe算法代表了兩種從觀察集中發(fā)現(xiàn)、計數(shù)共現(xiàn)事件(在本例中即為從語料庫中構(gòu)造共現(xiàn)矩陣)的方法。這兩種算法的思路在很多類問題中都能得到有效應(yīng)用(例如文本處理、數(shù)據(jù)挖掘、生物信息計算等)。

直觀比較下，基于stripe的算法數(shù)據(jù)表示更為緊湊，而基于pair的算法會產(chǎn)生比基于stripe的算法多得多的中間結(jié)果key-value對。因此執(zhí)行時基于pair的算法需要排序的元素數(shù)更多。

進(jìn)一步來看，pair算法與stripe算法又是統(tǒng)一的，兩者只是記錄的粒度不同:pair算法單獨記錄每一次共現(xiàn)，而stripe算法將滿足某種條件的共現(xiàn)記錄在一起。

stripe算法工作的前提是對于每個mapper輸入((docid，doc)對)，其對應(yīng)產(chǎn)生的關(guān)聯(lián)數(shù)組都能放入內(nèi)存之中，虛存的引入將會大大降低其性能。因此，stripe在詞匯表很大的情況下難以勝任，一般處理幾個GB的語料數(shù)據(jù)沒有問題，而TB甚至PB級的數(shù)據(jù)就可能會導(dǎo)致內(nèi)存溢出。相比之下，pair算法則不存在這個問題。

3 stripe算法內(nèi)存瓶頸的解決

3.1 分治解決內(nèi)存瓶頸

在stripe算法中，可以將語料數(shù)據(jù)的詞匯表劃分為b個桶(比如通過哈希)，這樣原stripe就會被劃分為b個“子 stripe(sub-stripe)”。這種方法可以解決詞匯表很大時stripe算法內(nèi)存不足的問題。需要注意的是，當(dāng)b=1時，即為標(biāo)準(zhǔn)的stripe算法;當(dāng)b=|V|(其中|V|是詞匯表中的詞匯數(shù))時，stripe算法即等價于pair算法。

單詞表很大的情況下，每個文檔可能包含的單詞量非常多。此時對于每個wi可能都有非常多的單詞與之共現(xiàn)。假如對于每個單詞wi，與之共現(xiàn)的不同的wj單詞數(shù)平均是一個相對于詞匯表規(guī)模的固定比例r(例如1%)，那么對于規(guī)模為n的單詞表，維護(hù)一個特定單詞wi的H平均需要存儲r×n個k－v對。如果H的空間利用率是常數(shù)的話(例如50%或100%)，那么維護(hù)H的空間開銷是O(n)。

簡而言之，詞匯表很大會導(dǎo)致與每個wi共現(xiàn)的不同wj很多，最終導(dǎo)致H變得很大。考慮stripe的應(yīng)用情境:mapper內(nèi)維護(hù)H，可以得出stripe受限于單機(jī)內(nèi)存容量的結(jié)論(一個mapper任務(wù)在一臺機(jī)器上運行)。因此stripe雖然高效，卻不能直接應(yīng)用于詞匯表很大的語料數(shù)據(jù)。

內(nèi)存瓶頸問題的本質(zhì)是每個wi需要維護(hù)的wj過多，導(dǎo)致H過大，如圖2所示。

圖2 詞匯表中wi和wj構(gòu)成

為簡單考慮，先假設(shè)這r×n個wj均勻分布在整個詞匯表區(qū)間里。如果能對該詞匯表做劃分，那么就可減少一次需要統(tǒng)計的wj的數(shù)量，從而減小H。劃分情況如圖3所示。

圖3 詞匯表拆分b桶

將詞匯表劃分為b個桶后，對于每個桶單獨統(tǒng)計就可減小H，而b的值是可變的。這樣即使詞匯表過大，也可以通過增大b縮小需要一次處理的詞匯表大小，從而使得stripe模式能應(yīng)用至任意大小的詞匯表。

3.2 算法實現(xiàn)

分治可以通過在原有的stripe算法上增加一次預(yù)處理實現(xiàn)。預(yù)處理的功能即劃分詞匯表，代碼見表4。

表4 stripe算法預(yù)處理偽代碼清單

經(jīng)過預(yù)處理后，數(shù)據(jù)集被劃分為b個子數(shù)據(jù)集(桶)，其中第 i個數(shù)據(jù)集中只包含(wi，wj)，hash(wj)mod b=i。對這b個數(shù)據(jù)集分別使用stripe算法計算共現(xiàn)矩陣。由于數(shù)據(jù)集根據(jù)wj劃分，可知每個數(shù)據(jù)集的計算結(jié)果都是最終全局共現(xiàn)矩陣的其中幾列，而數(shù)據(jù)集之間的計算結(jié)果無交集。因此只需要將各數(shù)據(jù)集的結(jié)果簡單合并即可得到全局共現(xiàn)矩陣，如圖4所示。

圖4 拆分為b個桶示意圖

4 實驗和結(jié)果分析

4.1 環(huán)境搭建

實驗中云計算平臺的結(jié)構(gòu):1臺機(jī)器作為NameNode和JobTracker的服務(wù)節(jié)點，其他8臺機(jī)器作為DataNode和TaskTracker的服務(wù)節(jié)點。每臺節(jié)點硬件配置如下:CPU型號為Intel(R)Core(TM)Duo T8300@2.40GHz;內(nèi)存為 2GB;硬盤為2TB;基于hadoop-0.20.2版本構(gòu)建集群。

4.2 實驗對照

為達(dá)到對照的效果，分別進(jìn)行pair算法、stripe算法(下稱算法1)和分桶的stripe算法(下稱算法2)。算法2中，桶的個數(shù)分別為40和80個，取得的實驗數(shù)據(jù)如表5所示。

表5 對照實驗數(shù)據(jù)

從表5和圖5可以得出:pair算法較stripe算法性能差，并且隨著詞匯表的增加，其時間急劇增加，直至報內(nèi)存不足;而stripe拆分算法(stripe算法2)較stripe算法1并沒有明顯的性能優(yōu)勢，反而時間有所增加，原因是算法2增加了一個預(yù)處理階段，耗費了一定的時間;但隨著詞匯表的增大，算法2的優(yōu)勢逐漸凸顯，海量的詞匯表時也沒有報內(nèi)存不足，只是時間稍長，如果適當(dāng)增加集群的大小，時間會有相當(dāng)程度的降低。

圖5 對照實驗數(shù)據(jù)曲線

5 結(jié)束語

本文闡述了基于MapReduce模型的兩個并行算法:pairs和stripes算法。針對stripes模式在詞匯表很大時存在內(nèi)存溢出問題，本文給出了劃分詞匯表的解決方法，對輸入詞匯表進(jìn)行拆分，此過程也可利用MapReduce模型進(jìn)行預(yù)處理。實驗數(shù)據(jù)證明利用MapReduce的并行性能較好地提高海量語料庫中詞類共現(xiàn)頻率統(tǒng)計的效率和性能。

上述算法可以進(jìn)行改進(jìn)，例如都可以應(yīng)用combiner(Map階段產(chǎn)生的中間結(jié)果合并)。對于stripe算法，應(yīng)用combiner算法很簡單，效率也很高，只需要合并關(guān)聯(lián)數(shù)組即可，且合并的步數(shù)不會超過語料數(shù)據(jù)詞匯表的尺寸(因為需要合并的關(guān)聯(lián)數(shù)組元素數(shù)不會超過語料數(shù)據(jù)詞匯表的尺寸);而pair算法的合并工作量就大很多，它只能合并那些具有相同(w，u)值的((w，u)，1)對，而(w，u)的可能取值通常很多。

這兩種算法都可以應(yīng)用mapper內(nèi)合并。無論具體做法是什么，有一點與使用combiner相同:pair算法產(chǎn)生的中間結(jié)果key-value對在key的取值范圍內(nèi)呈現(xiàn)稀疏分布的特征，因此即使對其應(yīng)用局部合并，能真正合并的項也是很少的。另外，(w，u)的可能取值非常大，也使得pair應(yīng)用mapper內(nèi)合并時很有可能遇到內(nèi)存不足的問題。of Computer and System Sciences

［1］Jimmy Lin，Chris Dyer.Data-Intensive Text Processing with MapReduce［J］.Morgan ＆ Claypool Publishers，2010(7):26－28.

［2］馮志偉，自然語言處理的歷史與現(xiàn)狀［J］.中國外語，2008(1):14－22.

［3］楊代慶，張智雄.基于Hadoop的海量共現(xiàn)矩陣生成方法［J］.現(xiàn)代圖書情報技術(shù)，2009(4):23－26.

［4］Apache Hadoop，Hadoop［EB/OL］.［2011 － 02 － 15］.http://hadoop.apache.org.

［5］Hadoop MapReduce［EB/OL］.［2008－12－16］.http://wiki.apache.org/hadoop/HadoopMapReduce.

［6］Tom White，Hadoop.The Definitive Guide［Z］.OReilly Yahoo Press，2ndedition.