Advertisement
Guest User

123P

a guest
May 29th, 2013
194
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.75 KB | None | 0 0
  1. import java.io.BufferedOutputStream;
  2. import java.io.BufferedInputStream;
  3. import java.io.*;
  4. import java.util.*;
  5. import java.io.IOException;
  6.  
  7.  
  8. public class HuffmanCompress{
  9.  
  10. int freq[];
  11. PriorityQueue q;
  12. public HuffmanCompress()
  13. {
  14. }
  15.  
  16. /*
  17. * Method for compressing the input data.
  18. *
  19. */
  20.  
  21. public void compress (InputStream fileInputName, OutputStream fileOutputName) throws IOException {
  22. freq = new int[256];
  23. int nextbyte = 0; //Read the next character of InputStream
  24. while (nextbyte != -1) {
  25. //If not EOF
  26. nextbyte = fileInputName.read();
  27. freq[nextbyte]++; //Add frequency of nextbyte
  28. if (fileInputName.available() == 0) {
  29. break;
  30. }
  31. }
  32.  
  33. HuffmanTree finalTree = buildTree(freq);
  34. String[] prefix = new String[256];
  35. String pos = "";
  36. makeTable(finalTree, prefix, pos);
  37. writeTree(finalTree, fileOutputName);
  38.  
  39. }
  40.  
  41. private HuffmanTree buildTree(int[] freq) {
  42. q = new PriorityQueue();
  43.  
  44. for (int i = 0; i < freq.length; i++) {
  45. if (freq[i] > 0) {
  46. q.offer(new HuffmanLeaf(freq[i],(char)i)); //Require HuffmanLeaf class
  47. }
  48. }
  49. while (q.size() > 1) {
  50. HuffmanTree first = (HuffmanTree) q.poll(); //Require HuffmanTree
  51. HuffmanTree second = (HuffmanTree) q.poll(); //Require HuffmanTree
  52. q.offer(new HuffmanNode(first, second)); //Enqueue the combined tree
  53. }
  54. return (HuffmanTree)q.poll();
  55. }
  56.  
  57. private void makeTable(HuffmanTree tree, String[] prefix, String s) {
  58.  
  59. if (tree instanceof HuffmanLeaf) {
  60. HuffmanLeaf leaf = (HuffmanLeaf)tree;
  61. prefix[((HuffmanLeaf)tree).value] = s;
  62. System.out.println(((HuffmanLeaf)tree).value + " " + prefix[((HuffmanLeaf)tree).value]);
  63. }
  64. else {
  65. if (tree instanceof HuffmanNode) {
  66. HuffmanNode node = (HuffmanNode)tree;
  67. makeTable(((HuffmanNode) tree).left, prefix, s + '0');
  68. makeTable(((HuffmanNode) tree).right, prefix, s + '1');
  69. }
  70. }
  71.  
  72. }
  73.  
  74. private void writeTree(HuffmanTree tree, OutputStream fileOutputName) throws IOException{
  75. if (tree instanceof HuffmanLeaf) {
  76. WriteBuffer w = new WriteBuffer(fileOutputName);
  77. w.write(((HuffmanLeaf)tree).value, 8);
  78. }
  79. else if (tree instanceof HuffmanNode) {
  80. writeTree(((HuffmanNode)tree).left, fileOutputName);
  81. writeTree(((HuffmanNode)tree).right, fileOutputName);
  82. }
  83. }
  84.  
  85. public String decompress (InputStream fileInputName, OutputStream fileOutputName) {
  86. return null;
  87. }
  88.  
  89.  
  90.  
  91. public static void main (String[] args) {
  92. boolean compressed = args[0].indexOf('c') != -1;
  93. boolean decompressed = args[0].indexOf('d')!= -1;
  94. try{
  95. FileInputStream fin = new FileInputStream(args[1]);
  96. FileOutputStream fout = new FileOutputStream(args[2]);
  97. HuffmanCompress huffman = new HuffmanCompress();
  98. if(compressed){
  99. huffman.compress(fin,fout);
  100. }
  101. else if(decompressed){
  102. huffman.decompress(fin, fout);
  103. }
  104. }
  105. catch(FileNotFoundException e){
  106. System.out.println("File not found");
  107. }
  108. catch(IOException e){
  109. System.out.println("Fail");
  110. e.printStackTrace();
  111. }
  112. }
  113.  
  114. /**
  115. *A simple class for writing bitstreams to bytestreams
  116. **/
  117. class WriteBuffer{
  118.  
  119. int pos;//the number of bits in the buffer
  120. long buffer;
  121. OutputStream out;
  122.  
  123. WriteBuffer(OutputStream out){
  124. this.out = out;
  125. }
  126.  
  127. /**
  128. *Writes the n least significant bits of m to the buffer
  129. **/
  130. public void write(int n, int m) throws IOException{
  131. buffer = (buffer<<n) + m%(1<<n);
  132. pos = pos+n;
  133. while(pos>=8){
  134. out.write((int) (buffer>>(pos-8)));
  135. pos = pos-8;
  136. }
  137. }
  138.  
  139. /**
  140. *pads the final output with 0's and writes to
  141. *the output stream
  142. **/
  143. public void flush() throws IOException{
  144. write((8-pos%8)%8,0);
  145. }
  146. }
  147. }
  148.  
  149. =======================================================================================================
  150. import java.util.PriorityQueue;
  151.  
  152. public class Node implements Comparable<Node> {
  153.  
  154. Node right;
  155. Node left;
  156. Node parent;
  157. String text;
  158. int frequency;
  159.  
  160. public Node(String textIn, int frequencyIn){
  161. text = textIn;
  162. frequency = frequencyIn;
  163. }
  164.  
  165. public Node(int frequencyIn){
  166. text = "";
  167. frequency = frequencyIn;
  168. }
  169.  
  170. public int compareTo(Node n){
  171. if (frequency < n.frequency){
  172. return -1;
  173. }
  174. else if(frequency > n.frequency){
  175. return 1;
  176. }
  177. return 0;
  178. }
  179.  
  180. public static void printFromPreOrder(Node n, String dashes){
  181. // print the colon if leaf node
  182. if(n.text != ""){
  183. System.out.println(dashes + n.frequency + ":" + n.text);
  184. }
  185. else{
  186. System.out.println(dashes + n.frequency);
  187. }
  188.  
  189. //Start recursive on left child then right
  190. if(n.left != null){
  191. printFromPreOrder(n.left, dashes + "-");
  192. }
  193.  
  194. if(n.right != null){
  195. printFromPreOrder(n.right, dashes + "-");
  196. }
  197. }
  198.  
  199. //Returns root node to pass to printFromPreOrder
  200. public static Node createTree(int frequencies[], String text[]){
  201. PriorityQueue<Node> queue = new PriorityQueue<Node>();
  202. for (int i = 0; i < text.length; i++) {
  203. Node n = new Node(text[i], frequencies[i]);
  204. queue.add(n);
  205. }
  206. Node root = null;
  207. while (queue.size() > 1) {
  208. Node least1 = queue.poll();
  209. Node least2 = queue.poll();
  210. Node combined = new Node(least1.frequency + least2.frequency);
  211. combined.right = least1;
  212. combined.left = least2;
  213. least1.parent = combined;
  214. least2.parent = combined;
  215. queue.add(combined);
  216. // Keep track until we actually find the root
  217. root = combined;
  218. }
  219. return root;
  220. }
  221.  
  222. public static void main(String[] args) {
  223. int frequencies[] = {10, 15, 12, 3, 4, 13, 1};
  224. String text[] = {"a", "b", "c", "e", "nl", "sp", "t"};
  225. Node root = Node.createTree(frequencies, text);
  226. Node.printFromPreOrder(root, "");
  227. }
  228. }
  229. ====================================================================================================
  230.  
  231. public class HuffmanLeaf extends HuffmanTree {
  232. char value;
  233.  
  234. public HuffmanLeaf (int freq, char val) {
  235. super(freq);
  236. value = val;
  237. }
  238.  
  239. public int compareTo(Object o) {
  240. return 0;
  241. }
  242.  
  243.  
  244. }
  245. ====================================================================================================
  246. import java.util.Comparator;
  247.  
  248. abstract class HuffmanTree implements Comparable{
  249. int frequency; //Frequency of the tree
  250.  
  251. public HuffmanTree (int freq) {
  252. frequency = freq;
  253. }
  254.  
  255. public int compareTo (HuffmanTree tree) {
  256. return frequency - tree.frequency;
  257. }
  258.  
  259. }
  260. ====================================================================================================
  261.  
  262. class HuffmanNode extends HuffmanTree {
  263. HuffmanTree left;
  264. HuffmanTree right;
  265.  
  266. public HuffmanNode (HuffmanTree l, HuffmanTree r) {
  267. super (l.frequency + r.frequency);
  268. left = l;
  269. right = r;
  270. }
  271.  
  272. public int compareTo(Object o) {
  273. return left.frequency - right.frequency;
  274. }
  275. }
  276. ====================================================================================================
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement