如何用Hadoop实现字符串匹配算法? [英] How to implement string matching algorithm with Hadoop?

查看:488
本文介绍了如何用Hadoop实现字符串匹配算法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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



到目前为止,我看到的所有示例程序都是字数统计的例子,而我找不到任何字符串匹配的示例程序。

我尝试寻找一些教程,教导如何使用Java编写Hadoop应用程序,但找不到任何。你可以向我推荐一些教程,在这里我可以学习如何使用Java编写Hadoop应用程序。



预先致谢

解决方案

我没有测试下面的代码,但是这应该让你开始。
我已经使用了BoyerMoore实现此处



下面的代码是做什么的:



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



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

这里不需要减速器。如果在不同的映射器中多次发现模式,那么输出将会有多个偏移量(每个映射器1个)。

  package hadoop。 boyermoore; 

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

导入org.apache.hadoop.conf.Configuration;
导入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);


$ b @Override
public final void setup(Context context){
if(boyerMoore == null)
boyerMoore = new BoyerMoore(context.getConfiguration()。get(pattern));



$ b 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);
}
}


I want to implement a string matching(Boyer-Moore) algorithm using Hadoop. I just started using Hadoop so I have no idea how to write a Hadoop program in Java.

All the sample programs that I have seen so far are word counting examples and I couldn't find any sample programs for string matching.

I tried searching for some tutorials that teaches how to write Hadoop applications using Java but couldn't find any. Can you suggest me some tutorials where I can learn how to write Hadoop applications using Java.

Thanks in advance.

解决方案

I haven't tested the below code, But this should get you started. I have used the BoyerMoore implementation available here

What the below code is doing:

The goal is to search for a pattern in an input document. The BoyerMoore class is initialized in the setup method using the pattern set in the configuration.

The mapper receives each line at a time and it uses the BoyerMoore instance to find the pattern. If match is found, the we write it using context.

There is no need of a reducer here. If the pattern is found multiple times in different mapper then the output will have multiple offsets(1 per mapper).

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);
      }
}

这篇关于如何用Hadoop实现字符串匹配算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆