Skip to content
Snippets Groups Projects
Select Git revision
  • ff15a9c49163ae3ea2ddd886ee626c998fa3a572
  • master default
2 results

BDPA_Assign2_WJIN.md

Blame
  • user avatar
    Wen Yao Jin authored
    a90b4bc4
    History

    Assignment 2 for BDPA

    by Wenyao JIN

    Preprocessing the input

    1. Remake the stopwords file

    By slightly modifying the wordcount code from the previous assignment, we can output a stopwords file.

    • take all three input files as before
    • use space or -- as tokenizer
    • filter out all characters besides letters and numbers
    • transform all words to lower case
    • output is only count larger than 4000
    
          public void map(LongWritable key, Text value, Context context)
                  throws IOException, InterruptedException {
             for (String token: value.toString().split("\\s+|-{2,}+")) {
            	 word.set(token.replaceAll("[^A-Za-z0-9]+", "").toLowerCase());
                context.write(word, ONE);
             }
          }
          

    The stop word file can be found here.

    2. Count word frequency of pg100.txt

    By using again the wordcount algorithm, we recount the word frequency for pg100.txt to be used later for word sorting. This time capital cases are kept to be taken acount in the similarity comparison. The output file can be found here.

    3. Output lines

    In this step, several tasks should be done:

    • Store all stopwords in a set
    • Store all word frequency in a hashmap
    • For each line:
      • keep counting line number with a counter
      • skip empty lines
      • separate words
      • filter special characters
      • take out words that are stopwords
      • wipe out duplicates
      • sort them by their pre-calculated frequency
      • output words with their line number as key

    For this step, all task are done within the mapper. The tokenizer is space or -- as before. A set container is used to avoid duplicates. Java's build-in sort function is applied with a costumed compare function incorporating the word frequency. StringUtils's join function serves to join words together with a comma. The counter reveals a total of 124787 lines.

          public void map(LongWritable key, Text value, Context context)
                  throws IOException, InterruptedException {
        	 Counter counter = context.getCounter(DocLineCounter.NUM);
        	 counter.increment(1);
        	 Set<String> wordSet = new HashSet<String>();
        	 if (value.toString().isEmpty()){
        		 return;
        	 }
             for (String token: value.toString().split("\\s+|-{2,}+")) {
            	 String s = token.replaceAll("[^A-Za-z0-9]+", "");
            	 if (stopWords.contains(s)||(s.isEmpty())){
            		 continue;
            	 }else if(!wordFreq.containsKey(s)){
            		 System.out.println("WARN: HASHTABLE DON'T HAVE WORD:");
            		 System.out.println(s);	 
            	 }
            	 wordSet.add(s);
             }
             List<String> wordList = new ArrayList<String>(wordSet);
             
             Collections.sort(wordList, new Comparator<String>() {
            	 @Override
            	 public int compare(String s1, String s2)
            	 {
            		 return  wordFreq.get(s1).compareTo(wordFreq.get(s2));
            	 }
             });
             words.set(StringUtils.join(wordList,","));
             context.write(new LongWritable(counter.getValue()), words);
          }

    The output file can be found here. The total line number is output to HDFS as instructed, you can also find the file here.


    Set similarity joins

    0. Primary implementation

    In this part, we need compare pairwise similarity. Before we do our implementations of two approaches, several basic modules need to be done.

    Key Pair

    In this mapreduce program, keys emitted from mappers will be pairs of keys. Thus, an implementation of new class key pair (in our case a pair of longwritables) is needed.

    Several remarks and intuition here:

    • LongPair need to implement WritableComparable interface in order to permit shuffle and order
    • Override function equals : We should see that order within the pairs should not be taken into account when checking two pairs are equal or not (For example : (A,B) should equal (B,A)). So our function should inverse one pair to verify inequality before yield no.
    • Override function compareTo : The compare function has not much importance, but its difficulty lies in the necessity of coherence with equals. Here I proposed the method of comparing pairs by calculating a sum value(sum of two id) and a difference value(absolute difference of two id). We can check that 2 pairs can be equal if and only if pairwise difference of this two values are both zero.
    class LongPair implements WritableComparable<LongPair> {
    
        private LongWritable first;
        private LongWritable second;
        
        public LongPair() {
            this.set(new LongWritable(0), new LongWritable(0));
        }
        
        public LongPair(LongWritable first, LongWritable second) {
            this.set(first, second);
        }
        
        public LongPair(Long first, Long second) {
            this.set(new LongWritable(first), new LongWritable(second));
        }
    
        public LongPair(String first, String second) {
            this.set(new LongWritable( new Long(first)), new LongWritable( new Long(second)));
        }
    
        public LongWritable getFirst() {
            return first;
        }
    
        public LongWritable getSecond() {
            return second;
        }
    
        public void set(LongWritable first, LongWritable second) {
            this.first = first;
            this.second = second;
        }    
        
        public void setFirst(LongWritable first){
            this.first = first;
        }
        
        public void setFirst(Long first){
            this.first = new LongWritable(first);
        }
        
        public void setSecond(LongWritable second){
            this.second = second;
        }
        
        public void setSecond(Long second){
            this.second = new LongWritable(second);
        }
        
        public long getSum(){
        	return this.first.get()+this.second.get();
        }
        
        public long getDiff(){
        	return Math.abs(this.first.get()-this.second.get());
        }
        
        public LongPair inverse(){
        	return new LongPair(second, first);
        }
    
        @Override
        public boolean equals(Object o) {
            if (o instanceof LongPair) {
                LongPair p1 = (LongPair) o;
                boolean b1 = first.equals(p1.first) && second.equals(p1.second);
                LongPair p2 = p1.inverse();
                boolean b2 = first.equals(p2.first) && second.equals(p2.second);
                return b1 || b2;
            }
            return false;
        }
        
        @Override
        public int compareTo(LongPair other) {
        	long cmp = this.getSum()-other.getSum();
        	long cmp_alter = this.getDiff() - other.getDiff();
        	if(cmp<0){
        		return 1;
        	}else if(cmp>0){
        		return -1;
        	}else if(cmp_alter<0){
        		return 1;
        	}else if(cmp_alter>0){
        		return -1;
        	}
        	return 0;
        }
        
    
        @Override
        public void readFields(DataInput in) throws IOException {
            first.readFields(in);
            second.readFields(in);
        }
    
        @Override
        public void write(DataOutput out) throws IOException {
            first.write(out);
            second.write(out);
        }
    
        @Override
        public String toString() {
            return first.toString() + "," + second.toString();
        }
    Similarity

    To compute the similarity of two strings as instructed, we used a Set to store words. The advantage of set is its automatical ignorance of duplicates which enable quick calculation of union and intersection operations.

    	   public double similarity(String t1, String t2) {
    
    		   Set<String> s1 = text2Set(t1);
    		   Set<String> s2 = text2Set(t2);
    		   
    		   Set<String> union = new HashSet<String>(s1);
    		   union.addAll(s2);
    		   
    		   Set<String> intersection = new HashSet<String>(s1);
    		   intersection.retainAll(s2);
    		   
    		   if (union.size()==0){
    			   return 0;
    		   }
    		   
    		   return intersection.size()/union.size();
    	    }

    1. Naive approach