mapreduce 算法

這篇文章是介紹MapReduce算法的系列文章的另一部分，該書在使用MapReduce進行數(shù)據(jù)密集型文本處理中找到。 先前的文章是Local Aggregation ， Local Aggregation PartII和創(chuàng)建共現(xiàn)矩陣 。 這次我們將討論階數(shù)反轉(zhuǎn)模式。 順序反轉(zhuǎn)模式利用的MapReduce來計算所需要的提前將被操縱的數(shù)據(jù)的減速推送數(shù)據(jù)的排序階段..你關閉此作為MapReduce的邊緣狀態(tài)之前，我強烈推薦您閱讀作為我們將討論如何利用排序的優(yōu)勢，并使用自定義分區(qū)程序進行覆蓋，這兩個實用程序都是有用的工具。

盡管許多MapReduce程序是用較高級別的抽象（即Hive或Pig）編寫的，但了解較低級的情況仍然有幫助。順序反轉(zhuǎn)模式可在使用MapReduce進行數(shù)據(jù)密集型文本處理的第3章中找到。 。 為了說明順序倒置模式，我們將從同現(xiàn)矩陣模式中使用Pairs方法。 創(chuàng)建同現(xiàn)矩陣時，我們會跟蹤單詞一起出現(xiàn)的總次數(shù)。 在較高的層次上，我們采用“成對”方法并稍加改動，除了使映射器發(fā)出諸如（“ foo”，“ bar”）之類的單詞對外，我們還將發(fā)出（“ foo”，“ *”），并且將對每個單詞對執(zhí)行此操作，因此我們可以輕松得出最左單詞出現(xiàn)頻率的總計數(shù)，并使用該計數(shù)來計算我們的相對頻率。 這種方法提出了兩個具體問題。 首先，我們需要找到一種方法來確保單詞對（“ foo”，“ *”）首先到達減速器。 其次，我們需要確保所有具有相同左單詞的單詞對都到達相同的縮減詞。 在解決這些問題之前，讓我們看一下我們的映射器代碼。

映射器代碼

首先，我們需要使用Pairs方法修改映射器。 在發(fā)出特定單詞的所有單詞對之后，在每個循環(huán)的底部，我們將發(fā)出特殊標記WordPair（“ word”，“ *”）以及在左側(cè)找到單詞的次數(shù)。

public class PairsRelativeOccurrenceMapper extends Mapper<LongWritable, Text, WordPair, IntWritable> {private WordPair wordPair = new WordPair();private IntWritable ONE = new IntWritable(1);private IntWritable totalCount = new IntWritable();@Overrideprotected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {int neighbors = context.getConfiguration().getInt('neighbors', 2);String[] tokens = value.toString().split('\\s+');if (tokens.length > 1) {for (int i = 0; i < tokens.length; i++) {tokens[i] = tokens[i].replaceAll('\\W+','');if(tokens[i].equals('')){continue;}wordPair.setWord(tokens[i]);int start = (i - neighbors < 0) ? 0 : i - neighbors;int end = (i + neighbors >= tokens.length) ? tokens.length - 1 : i + neighbors;for (int j = start; j <= end; j++) {if (j == i) continue;wordPair.setNeighbor(tokens[j].replaceAll('\\W',''));context.write(wordPair, ONE);}wordPair.setNeighbor('*');totalCount.set(end - start);context.write(wordPair, totalCount);}}}
}

現(xiàn)在，我們已經(jīng)生成了一種跟蹤遇到一個特定單詞的總次數(shù)的方法，我們需要確保那些特殊字符首先到達化簡器，以便可以計算出總數(shù)以計算相對頻率。 通過修改WordPair對象上的compareTo方法，我們將在MapReduce流程的排序階段為我們處理此問題。

修改后的排序

我們修改WordPair類上的compareTo方法，以便在右側(cè)遇到“ *”字符時，將特定對象推到頂部。

@Overridepublic int compareTo(WordPair other) {int returnVal = this.word.compareTo(other.getWord());if(returnVal != 0){return returnVal;}if(this.neighbor.toString().equals('*')){return -1;}else if(other.getNeighbor().toString().equals('*')){return 1;}return this.neighbor.compareTo(other.getNeighbor());}

通過修改compareTo方法，我們現(xiàn)在可以確保將具有特殊字符的所有WordPair排在最前面，然后首先到達reducer。 這導致了我們的第二個專業(yè)化，我們?nèi)绾伪ＷC具有給定左單詞的所有WordPair對象都將被發(fā)送到相同的reducer？ 答案是創(chuàng)建一個自定義分區(qū)程序。

自定義分區(qū)

通過計算鍵的哈希碼對還原器的數(shù)量取模，將中間鍵改編為還原器。 但是我們的WordPair對象包含兩個單詞，因此采用整個對象的哈希碼顯然是行不通的。 我們需要修改一個自定義的分區(qū)程序，該分區(qū)程序在確定將哪個縮減程序發(fā)送到輸出時僅考慮左邊的單詞。

public class WordPairPartitioner extends Partitioner<WordPair,IntWritable> {@Overridepublic int getPartition(WordPair wordPair, IntWritable intWritable, int numPartitions) {return wordPair.getWord().hashCode() % numPartitions;}
}

現(xiàn)在，我們保證將所有具有相同左單詞的WordPair對象發(fā)送到相同的reducer。 剩下的就是構(gòu)造一個化簡器以利用發(fā)送數(shù)據(jù)的格式。

減速器

為倒序反轉(zhuǎn)模式構(gòu)建減速器很簡單。 這將涉及保持計數(shù)器變量和“當前”字變量。 減速器將檢查輸入鍵WordPair中右側(cè)的特殊字符“ *”。 如果左邊的單詞不等于“當前”單詞，我們將重新設置計數(shù)器并求和所有值，以獲得觀察到給定當前單詞的總次數(shù)。 現(xiàn)在，我們將處理下一個WordPair對象，對計數(shù)求和并除以我們的計數(shù)器變量，以獲得相對頻率。 該過程將繼續(xù)進行，直到遇到另一個特殊字符并重新開始。

public class PairsRelativeOccurrenceReducer extends Reducer<WordPair, IntWritable, WordPair, DoubleWritable> {private DoubleWritable totalCount = new DoubleWritable();private DoubleWritable relativeCount = new DoubleWritable();private Text currentWord = new Text('NOT_SET');private Text flag = new Text('*');@Overrideprotected void reduce(WordPair key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException {if (key.getNeighbor().equals(flag)) {if (key.getWord().equals(currentWord)) {totalCount.set(totalCount.get() + getTotalCount(values));} else {currentWord.set(key.getWord());totalCount.set(0);totalCount.set(getTotalCount(values));}} else {int count = getTotalCount(values);relativeCount.set((double) count / totalCount.get());context.write(key, relativeCount);}}private int getTotalCount(Iterable<IntWritable> values) {int count = 0;for (IntWritable value : values) {count += value.get();}return count;}
}

通過處理排序順序并創(chuàng)建自定義分區(qū)程序，我們已經(jīng)能夠在計算所需的數(shù)據(jù)到達之前將數(shù)據(jù)發(fā)送到計算所需的化簡器。 盡管此處未顯示，但使用組合器來運行MapReduce作業(yè)。 這種方法也是“映射器內(nèi)”合并模式的不錯選擇。

示例與結(jié)果

鑒于假期即將來臨，我覺得現(xiàn)在是時候針對查爾斯·狄更斯（Charles Dickens）的小說《圣誕節(jié)頌歌》（A Christmas Carol）進行訂單倒置模式的例子了。 我知道這很老套，但它能達到目的。

new-host-2:sbin bbejeck$ hdfs dfs -cat relative/part* | grep Humbug
{word=[Humbug] neighbor=[Scrooge]}	0.2222222222222222
{word=[Humbug] neighbor=[creation]}	0.1111111111111111
{word=[Humbug] neighbor=[own]}	0.1111111111111111
{word=[Humbug] neighbor=[said]}	0.2222222222222222
{word=[Humbug] neighbor=[say]}	0.1111111111111111
{word=[Humbug] neighbor=[to]}	0.1111111111111111
{word=[Humbug] neighbor=[with]}	0.1111111111111111
{word=[Scrooge] neighbor=[Humbug]}	0.0020833333333333333
{word=[creation] neighbor=[Humbug]}	0.1
{word=[own] neighbor=[Humbug]}	0.006097560975609756
{word=[said] neighbor=[Humbug]}	0.0026246719160104987
{word=[say] neighbor=[Humbug]}	0.010526315789473684
{word=[to] neighbor=[Humbug]}	3.97456279809221E-4
{word=[with] neighbor=[Humbug]}	9.372071227741331E-4

結(jié)論

雖然計算相對單詞出現(xiàn)頻率可能不是常見的任務，但我們已經(jīng)能夠演示排序和使用自定義分區(qū)程序的有用示例，這是構(gòu)建MapReduce程序時可以使用的好工具。 如前所述，即使您的大多數(shù)MapReduce是像Hive或Pig那樣以更高的抽象級別編寫的，了解幕后的情況仍然很有幫助。 謝謝你的時間。

參考： MapReduce算法-來自JCG合作伙伴 Bill Bejeck的《 隨機編碼思考》博客中的順序反轉(zhuǎn) 。

翻譯自: https://www.javacodegeeks.com/2012/12/mapreduce-algorithms-order-inversion.html

mapreduce 算法

總結(jié)

以上是生活随笔為你收集整理的mapreduce 算法_MapReduce算法–顺序反转的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。