Implementation of PageRank and Huffman Algorithms
Sources (PageRank)
pgrk1475.java
/* NAME SURNAME cs610 1475 prp */
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class pgrk1475 {
private static final double D = 0.85;
private int n;
private List pages = new ArrayList<>();
private pgrk1475(String fileName) throws RuntimeException {
try {
Scanner scanner = new Scanner(new File(fileName));
String[] tokens = scanner.nextLine().split(" ");
n = Integer.parseInt(tokens[0]);
int m = Integer.parseInt(tokens[1]);
for (int i = 0; ireferencedBy = new HashSet<>();
Set references = new HashSet<>();
double rank;
}
public static void main(String[] args) {
int iterations = Integer.parseInt(args[0]);
int initialValue = Integer.parseInt(args[1]);
String filename = args[2];
pgrk1475 pageRank = new pgrk1475(filename);
pageRank.pagerank(iterations, initialValue);
}
}
Sources (Huffman)
ArchiveData.java
/* NAME SURNAME cs610 1475 prp */
import java.io.*;
import java.util.List;
public class ArchiveData {
private FreqDictionary dictionary;
private int dataSize;
private ListbinString;
public FreqDictionarygetDictionary() {
return dictionary;
}
public int getDataSize() {
return dataSize;
}
public ListgetBinString() {
return binString;
}
public ArchiveData(FreqDictionary dictionary, int dataSize, ListbinString) {
this.dictionary = dictionary;
this.dataSize = dataSize;
this.binString = binString;
}
public void writeToFile(String filename) {
try {
OutputStreamoutputStream = new FileOutputStream(new File(filename));
DataOutputStreamdataOutputStream = new DataOutputStream(outputStream);
dictionary.writeToFile(dataOutputStream);
dataOutputStream.writeInt(dataSize);
byte[] bytes = BinStringConverter.binStringToBytes(binString);
dataOutputStream.writeInt(bytes.length);
dataOutputStream.write(bytes);
dataOutputStream.flush();
dataOutputStream.close();
}
catch(IOExceptionioe) {
System.err.println("Error while writing into file " + filename);
}
}
public static ArchiveDatareadFromFile(String filename) {
try {
InputStreaminputStream = new FileInputStream(new File(filename));
DataInputStreamdataInputStream = new DataInputStream(inputStream);
FreqDictionaryfreqDictionary = FreqDictionary.readFromFile(dataInputStream);
int dataSize = dataInputStream.readInt();
int byteSize = dataInputStream.readInt();
byte[] bytes = new byte[byteSize];
dataInputStream.read(bytes);
dataInputStream.close();
return new ArchiveData(freqDictionary, dataSize, BinStringConverter.bytesToBitString(bytes));
}
catch(IOExceptionioe) {
System.err.println("Error while writing into file " + filename);
return null;
}
}
}
BinStringConverter.java
/* NAME SURNAME cs610 1475 prp */
import java.util.ArrayList;
import java.util.List;
public class BinStringConverter {
public static final int BATCH_SIZE = 8 * 10000;
public static byte[] binStringToBytes(ListbinString) {
if (binString.isEmpty()) {
return new byte[0];
}
int length = (BATCH_SIZE / 8) * (binString.size() - 1) + ((binString.get(binString.size()-1).length()) + 7)/8;
int remainder = (binString.get(binString.size()-1).length()) % 8;
if (remainder >0) {
StringBuilder builder = new StringBuilder();
for (int i = 0; ibytesToBitString(byte[] bytes) {
List result = new ArrayList<>();
StringBuilder builder = new StringBuilder();
for (byte b: bytes) {
builder.append(String.format("%8s",Integer.toBinaryString(Byte.toUnsignedInt(b))).replace(' ','0'));
if (builder.length() == BATCH_SIZE) {
result.add(builder.toString());
builder = new StringBuilder();
}
}
if (builder.length() >0) {
result.add(builder.toString());
}
return result;
}
}
CodeDictionary.java
/* NAME SURNAME cs610 1475 prp */
import java.util.ArrayList;
import java.util.List;
public class CodeDictionary {
private List entries = new ArrayList<>();
private String currState = "";
public void addCode(int b, String code) {
for (int i = 0; igetEntries() {
return entries;
}
public String getCode(int b) {
for (CodeDictionaryEntry entry : entries) {
if (entry.symbol == b) {
return entry.code;
}
}
return null;
}
static class CodeDictionaryEntry {
int symbol;
String code;
CodeDictionaryEntry(int symbol, String code) {
this.symbol = symbol;
this.code = code;
}
}
}
FreqDictionary.java
/* NAME SURNAME cs610 1475 prp */
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class FreqDictionary {
private List entries = new ArrayList<>();
public void addFreq(byte b) {
for (int i = 0; igetEntries() {
return entries;
}
static class FreqDictionaryEntry {
byte symbol;
int frequency;
FreqDictionaryEntry(byte symbol, int frequency) {
this.symbol = symbol;
this.frequency = frequency;
}
}
public void writeToFile(DataOutputStream dos) throws IOException {
dos.writeInt(entries.size());
for (FreqDictionaryEntry entry : entries) {
dos.writeByte(entry.symbol);
dos.writeInt(entry.frequency);
}
}
public static FreqDictionaryreadFromFile(DataInputStream dis) throws IOException {
int size = dis.readInt();
FreqDictionary dictionary = new FreqDictionary();
for (int i = 0; i list = dictionary.getEntries();
LinkedListfreqNodes = new LinkedList<>();
for (FreqDictionary.FreqDictionaryEntry entry : list) {
FreqNode node = new FreqNode(entry.symbol);
node.freq = entry.frequency;
freqNodes.addLast(node);
}
freqNodes.sort(Comparator.comparingLong(o ->o.freq));
if (freqNodes.isEmpty()) {
return new FreqTree(null);
}
while (freqNodes.size() >1) {
FreqNode first1 = freqNodes.removeFirst();
FreqNode first2 = freqNodes.removeFirst();
FreqNodenewNode = new FreqNode();
newNode.left = first1;
newNode.right = first2;
newNode.freq = first1.freq + first2.freq;
booleaninserted = false;
for (int i = 0; inewNode.freq) {
freqNodes.add(i, newNode);
inserted = true;
break;
}
}
if (!inserted) {
freqNodes.addLast(newNode);
}
}
FreqTree tree = new FreqTree(freqNodes.getFirst());
return tree;
}
public CodeDictionarygetCodeDictionary() {
CodeDictionary dictionary = new CodeDictionary();
if (root != null) {
getCodeDictionaryStep(dictionary, root, "");
}
return dictionary;
}
private void getCodeDictionaryStep(CodeDictionary dictionary, FreqNode node, String s) {
if (node.symbol != null) {
dictionary.addCode(node.symbol, s);
}
else {
getCodeDictionaryStep(dictionary, node.left, s + "0");
getCodeDictionaryStep(dictionary, node.right, s + "1");
}
}
private static class FreqNode {
Byte symbol;
FreqNode left;
FreqNode right;
long freq;
public FreqNode() {
this.symbol = null;
}
public FreqNode(byte symbol) {
this.symbol = symbol;
}
}
}
hdec1475.java
/* NAME SURNAME cs610 1475 prp */
import java.io.*;
import java.util.List;
public class hdec1475 {
public static void main(String[] args) {
String filename = args[0];
ArchiveDataarchiveData = ArchiveData.readFromFile(filename);
FreqDictionaryfreqDictionary = archiveData.getDictionary();
FreqTreefreqTree = FreqTree.createFreqTree(freqDictionary);
int dataSize = archiveData.getDataSize();
ListbinString = archiveData.getBinString();
try {
String decodedFilename = filename + ".dec";
File decFile = new File(decodedFilename);
OutputStreamos = new FileOutputStream(decFile);
DataOutputStream dos = new DataOutputStream(os);
dos.write(createBytes(freqTree, binString, dataSize));
dos.close();
} catch (IOExceptionioe) {
ioe.printStackTrace();
}
}
private static byte[] createBytes(FreqTree tree, List lines, int dataSize) {
if (lines.isEmpty()) {
return new byte[0];
}
int counter = 0;
byte[] result = new byte[dataSize];
booleanisOver = false;
int step = 0;
String line = lines.get(step);
while(true) {
for (int i = 0; i createString(CodeDictionary dictionary, byte[] bytes) {
List result = new ArrayList<>();
StringBuilder builder = new StringBuilder();
for (byte b : bytes) {
builder.append(dictionary.getCode(b));
if (builder.length() >= BinStringConverter.BATCH_SIZE) {
String line = builder.toString();
result.add(line.substring(0, BinStringConverter.BATCH_SIZE));
builder = new StringBuilder();
builder.append(line.substring(BinStringConverter.BATCH_SIZE));
}
}
if (builder.length() >0) {
result.add(builder.toString());
}
return result;
}
}