如何用Hadoop实现字符串匹配算法？

Question

我想使用 Hadoop 实现一个字符串匹配 (Boyer-Moore) 算法。我刚开始使用 Hadoop，所以我不知道如何在 Java.

中编写 Hadoop 程序

目前看到的示例程序都是字数统计示例，没有找到字符串匹配的示例程序。

我尝试搜索一些教程，这些教程教授如何使用 Java 编写 Hadoop 应用程序，但没有找到。你能推荐一些教程让我学习如何使用 Java.

编写 Hadoop 应用程序吗

提前致谢。

Answer 1

我还没有测试下面的代码，但这应该能让你入门。我使用了可用的 BoyerMoore 实现 here

下面的代码在做什么：

目标是在输入文档中搜索模式。 BoyerMoore class 使用配置中设置的模式在设置方法中初始化。

映射器一次接收每一行，并使用 BoyerMoore 实例查找模式。如果找到匹配项，我们将使用上下文编写它。

这里不需要reducer。如果在不同的映射器中多次找到该模式，则输出将具有多个偏移量（每个映射器 1 个）。

package hadoop.boyermoore;

import java.io.IOException;
import java.util.StringTokenizer;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

public class BoyerMooreImpl {


      public static class TokenizerMapper
           extends Mapper<Object, Text, Text, IntWritable>{
        private BoyerMoore boyerMoore;
        private static IntWritable offset;
        private Text offsetFound = new Text("offset");

        public void map(Object key, Text value, Context context
                        ) throws IOException, InterruptedException {
          StringTokenizer itr = new StringTokenizer(value.toString());
          while (itr.hasMoreTokens()) {
              String line = itr.nextToken();
              int offset1 = boyerMoore.search(line);
              if (line.length() != offset1) {
                  offset = new IntWritable(offset1);
                  context.write(offsetFound,offset);
              }
          }
        }
        @Override
        public final void setup(Context context) {
            if (boyerMoore == null)
                boyerMoore = new BoyerMoore(context.getConfiguration().get("pattern"));
        }
      }


      public static void main(String[] args) throws Exception {
        Configuration conf = new Configuration();
        conf.set("pattern","your_pattern_here");
        Job job = Job.getInstance(conf, "BoyerMoore");
        job.setJarByClass(BoyerMooreImpl.class);
        job.setMapperClass(TokenizerMapper.class);
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(IntWritable.class);
        FileInputFormat.addInputPath(job, new Path(args[0]));
        FileOutputFormat.setOutputPath(job, new Path(args[1]));
        System.exit(job.waitForCompletion(true) ? 0 : 1);
      }
}

Answer 2

我不知道这是否是运行并行算法的正确实现，但这是我想出来的，

import java.io.IOException;
import java.util.*;

import org.apache.hadoop.conf.*;
import org.apache.hadoop.fs.*;
import org.apache.hadoop.conf.*;
import org.apache.hadoop.io.*;
import org.apache.hadoop.mapreduce.*;
import org.apache.hadoop.mapreduce.lib.input.*;
import org.apache.hadoop.mapreduce.lib.output.*;
import org.apache.hadoop.util.*;

public class StringMatching extends Configured implements Tool {

  public static void main(String args[]) throws Exception {
      long start = System.currentTimeMillis();
      int res = ToolRunner.run(new StringMatching(), args);
      long end = System.currentTimeMillis();
      System.exit((int)(end-start));
  }

  public int run(String[] args) throws Exception {
    Path inputPath = new Path(args[0]);
    Path outputPath = new Path(args[1]);

    Configuration conf = getConf();
    Job job = new Job(conf, this.getClass().toString());

    FileInputFormat.setInputPaths(job, inputPath);
    FileOutputFormat.setOutputPath(job, outputPath);

    job.setJobName("StringMatching");
    job.setJarByClass(StringMatching.class);
    job.setInputFormatClass(TextInputFormat.class);
    job.setOutputFormatClass(TextOutputFormat.class);
    job.setMapOutputKeyClass(Text.class);
    job.setMapOutputValueClass(IntWritable.class);
    job.setOutputKeyClass(Text.class);
    job.setOutputValueClass(IntWritable.class);

    job.setMapperClass(Map.class);
    job.setCombinerClass(Reduce.class);
    job.setReducerClass(Reduce.class);

    return job.waitForCompletion(true) ? 0 : 1;
  }

  public static class Map extends Mapper<LongWritable, Text, Text, IntWritable> {
    private final static IntWritable one = new IntWritable(1);
    private Text word = new Text();

    @Override
    public void map(LongWritable key, Text value,
                    Mapper.Context context) throws IOException, InterruptedException {
      String line = value.toString();
      StringTokenizer tokenizer = new StringTokenizer(line);
      while (tokenizer.hasMoreTokens()) {
        word.set(tokenizer.nextToken());
        context.write(word, one);
      }
    }
  }

  public static class Reduce extends Reducer<Text, IntWritable, Text, IntWritable> {

    @Override
    public void reduce(Text key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException {
        BoyerMoore bm = new BoyerMoore(); 
        boolean flag = bm.findPattern(key.toString().trim().toLowerCase(), "abc");
        if(flag){
            context.write(key, new IntWritable(1));
        }else{
            context.write(key, new IntWritable(0));
        }
    }
  }

}

我正在使用 AWS（亚马逊网络服务），因此我可以 select 我希望我的程序同时运行来自控制台的节点数。所以我假设我使用的 map 和 reduce 方法应该足以运行并行使用 Boyer-Moore 字符串匹配算法。

如何用Hadoop实现字符串匹配算法？

How to implement string matching algorithm with Hadoop?

java

hadoop

string-matching

boyer-moore