如何在Hadoop中实现字符串匹配算法?

2020年8月29日 13点热度 0条评论

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

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

我尝试搜索一些教程,这些教程教如何使用Java编写Hadoop应用程序,但找不到任何内容。您能为我推荐一些教程,在那里我可以学习如何使用Java编写Hadoop应用程序。

提前致谢。

解决方案如下:

我尚未测试以下代码,但这应该可以帮助您入门。
我已经使用了可用的boytMoore实现here

下面的代码在做什么:

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

映射器一次接收每一行,并使用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);
      }
}