BDPA_Assign2_WJIN.md
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 withequals
. Here I proposed the method of comparing pairs by calculating asum
value(sum of two id) and adifference
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();
}