001: /*
002: * HuffmanCoder.java
003: *
004: *
005: * Copyright (c) 2003 Rimfaxe ApS (www.rimfaxe.com).
006: * All rights reserved.
007: *
008: * This package is written by Lars Andersen <lars@rimfaxe.com>
009: * and licensed by Rimfaxe ApS.
010: *
011: * Redistribution and use in source and binary forms, with or without
012: * modification, are permitted provided that the following conditions
013: * are met:
014: *
015: * 1. Redistributions of source code must retain the above copyright
016: * notice, this list of conditions and the following disclaimer.
017: *
018: * 2. Redistributions in binary form must reproduce the above copyright
019: * notice, this list of conditions and the following disclaimer in
020: * the documentation and/or other materials provided with the
021: * distribution.
022: *
023: * 3. The end-user documentation included with the redistribution, if
024: * any, must include the following acknowlegement:
025: * "This product includes software developed by Rimfaxe ApS
026: (www.rimfaxe.com)"
027: * Alternately, this acknowlegement may appear in the software itself,
028: * if and wherever such third-party acknowlegements normally appear.
029: *
030: * 4. The names "Rimfaxe", "Rimfaxe Software", "Lars Andersen" and
031: * "Rimfaxe WebServer" must not be used to endorse or promote products
032: * derived from this software without prior written permission. For written
033: * permission, please contact info@rimfaxe.com
034: *
035: * 5. Products derived from this software may not be called "Rimfaxe"
036: * nor may "Rimfaxe" appear in their names without prior written
037: * permission of the Rimfaxe ApS.
038: *
039: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
040: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
041: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
042: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
043: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
044: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
045: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
046: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
047: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
048: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
049: * SUCH DAMAGE.
050: *
051: */
052:
053: package com.rimfaxe.util;
054:
055: import java.util.*;
056:
057: /**
058: *
059: * @author Lars Andersen
060: */
061: public class HuffmanCoder extends Object {
062: private HashMap _inverseMap = null;
063: private String[] _code = null;
064:
065: private final static String[] map = { "A", "B", "C", "D", "E", "F",
066: "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R",
067: "S", "T", "U", "V", "W", "X", "Y", "Z", "a", "b", "c", "d",
068: "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p",
069: "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "0", "1",
070: "2", "3", "4", "5", "6", "7", "8", "9", "+", "/",
071:
072: ":A", ":B", ":C", ":D", ":E", ":F", ":G", ":H", ":I", ":J",
073: ":K", ":L", ":M", ":N", ":O", ":P", ":Q", ":R", ":S", ":T",
074: ":U", ":V", ":W", ":X", ":Y", ":Z", ":a", ":b", ":c", ":d",
075: ":e", ":f", ":g", ":h", ":i", ":j", ":k", ":l", ":m", ":n",
076: ":o", ":p", ":q", ":r", ":s", ":t", ":u", ":v", ":w", ":x",
077: ":y", ":z", ":0", ":1", ":2", ":3", ":4", ":5", ":6", ":7",
078: ":8", ":9", ":+", ":/",
079:
080: ";A", ";B", ";C", ";D", ";E", ";F", ";G", ";H", ";I", ";J",
081: ";K", ";L", ";M", ";N", ";O", ";P", ";Q", ";R", ";S", ";T",
082: ";U", ";V", ";W", ";X", ";Y", ";Z", ";a", ";b", ";c", ";d",
083: ";e", ";f", ";g", ";h", ";i", ";j", ";k", ";l", ";m", ";n",
084: ";o", ";p", ";q", ";r", ";s", ";t", ";u", ";v", ";w", ";x",
085: ";y", ";z", ";0", ";1", ";2", ";3", ";4", ";5", ";6", ";7",
086: ";8", ";9", ";+", ";/",
087:
088: "-A", "-B", "-C", "-D", "-E", "-F", "-G", "-H", "-I", "-J",
089: "-K", "-L", "-M", "-N", "-O", "-P", "-Q", "-R", "-S", "-T",
090: "-U", "-V", "-W", "-X", "-Y", "-Z", "-a", "-b", "-c", "-d",
091: "-e", "-f", "-g", "-h", "-i", "-j", "-k", "-l", "-m", "-n",
092: "-o", "-p", "-q", "-r", "-s", "-t", "-u", "-v", "-w", "-x",
093: "-y", "-z", "-0", "-1", "-2", "-3", "-4", "-5", "-6", "-7",
094: "-8", "-9", "-+", "-/" };
095:
096: class Ranking implements Comparable {
097: private int _value;
098: private long _frequency;
099:
100: public Ranking(int value, long frequency) {
101: _value = value;
102: _frequency = frequency;
103: }
104:
105: public int compareTo(Object o) {
106: Ranking other = (Ranking) o;
107: if (other.getFrequency() < _frequency) {
108: return -1;
109: } else if (other.getFrequency() == _frequency) {
110: return 0;
111: } else {
112: return 1;
113: }
114: }
115:
116: public int getValue() {
117: return _value;
118: }
119:
120: public long getFrequency() {
121: return _frequency;
122: }
123: }
124:
125: /** Creates new HuffmanCoder */
126: public HuffmanCoder() {
127: }
128:
129: public String getMapping() {
130: StringBuffer res = new StringBuffer();
131:
132: Set set = _inverseMap.keySet();
133: Iterator iter = set.iterator();
134: while (iter.hasNext()) {
135: String key = "" + iter.next();
136: res.append("" + key + "," + _inverseMap.get(key) + ",");
137: }
138: return "" + res;
139: }
140:
141: public void createMap(String mapping) {
142: _inverseMap = new HashMap();
143: StringTokenizer tkz = new StringTokenizer(mapping.trim(), ",",
144: false);
145:
146: while (tkz.hasMoreTokens()) {
147: String key = tkz.nextToken();
148: Integer val = new Integer(tkz.nextToken());
149: _inverseMap.put(key, val);
150: }
151: }
152:
153: public byte[] decodeHuffman(String stream, String mapping) {
154: createMap(mapping);
155: int index = 0;
156: int streamLength = stream.length();
157: ArrayList list = new ArrayList();
158: while (index < streamLength) {
159: char indexChar = stream.charAt(index);
160: String code = null;
161: if (indexChar == ':' || indexChar == ';'
162: || indexChar == '-') {
163: code = stream.substring(index, index + 2);
164: index += 2;
165: } else {
166: code = stream.substring(index, index + 1);
167: index += 1;
168: }
169: Integer value = (Integer) _inverseMap.get(code);
170: list.add(value);
171: }
172: byte buffer[] = new byte[list.size()];
173: Iterator iter = list.iterator();
174: index = 0;
175: while (iter.hasNext()) {
176: buffer[index++] = ((Integer) iter.next()).byteValue();
177: }
178: return buffer;
179: }
180:
181: public byte[] decodeHuffman(String stream, boolean std) {
182: buildInverseMap();
183: int index = 0;
184: int streamLength = stream.length();
185: ArrayList list = new ArrayList();
186: while (index < streamLength) {
187: char indexChar = stream.charAt(index);
188: String code = null;
189: if (indexChar == ':' || indexChar == ';'
190: || indexChar == '-') {
191: code = stream.substring(index, index + 2);
192: index += 2;
193: } else {
194: code = stream.substring(index, index + 1);
195: index += 1;
196: }
197: Integer value = (Integer) _inverseMap.get(code);
198: list.add(value);
199: }
200: byte buffer[] = new byte[list.size()];
201: Iterator iter = list.iterator();
202: index = 0;
203: while (iter.hasNext()) {
204: buffer[index++] = ((Integer) iter.next()).byteValue();
205: }
206: return buffer;
207: }
208:
209: public String encodeHuffman(byte[] buffer) {
210: StringBuffer encodedString = new StringBuffer();
211:
212: int readBytes = buffer.length;
213: long[] freqCount = new long[256];
214:
215: for (int i = 0; i < readBytes; i++) {
216: freqCount[(0x000000ff & buffer[i])]++;
217: }
218:
219: ArrayList list = new ArrayList();
220: for (int i = 0; i < 256; i++) {
221: list.add(new Ranking(i, freqCount[i]));
222: }
223: Collections.sort(list);
224: Iterator iter = list.iterator();
225: _code = new String[256];
226: int index = 0;
227: _inverseMap = new HashMap();
228: while (iter.hasNext()) {
229: Ranking rank = (Ranking) iter.next();
230: _code[rank.getValue()] = map[index];
231: _inverseMap.put(map[index], new Integer(rank.getValue()));
232: index++;
233: }
234:
235: int totalChars = 0;
236: for (int i = 0; i < readBytes; i++) {
237: String codeValue = _code[buffer[i] & 0xff];
238: totalChars += codeValue.length();
239: encodedString.append(_code[buffer[i] & 0xff]);
240: }
241:
242: return "" + encodedString;
243: }
244:
245: public String encodeHuffman(byte[] buffer, boolean std) {
246: StringBuffer encodedString = new StringBuffer();
247:
248: int readBytes = buffer.length;
249:
250: ArrayList list = new ArrayList();
251: for (int i = 0; i < 256; i++) {
252: list.add(new Ranking(i, i));
253: }
254: //Collections.sort(list);
255: Iterator iter = list.iterator();
256: _code = new String[256];
257: int index = 0;
258: _inverseMap = new HashMap();
259: while (iter.hasNext()) {
260: Ranking rank = (Ranking) iter.next();
261: _code[rank.getValue()] = map[index];
262: _inverseMap.put(map[index], new Integer(rank.getValue()));
263: index++;
264: }
265:
266: int totalChars = 0;
267: for (int i = 0; i < readBytes; i++) {
268: String codeValue = _code[buffer[i] & 0xff];
269: totalChars += codeValue.length();
270: encodedString.append(_code[buffer[i] & 0xff]);
271: }
272:
273: return "" + encodedString;
274: }
275:
276: public void buildInverseMap() {
277: ArrayList list = new ArrayList();
278: for (int i = 0; i < 256; i++) {
279: list.add(new Ranking(i, i));
280: }
281:
282: Iterator iter = list.iterator();
283: _code = new String[256];
284: int index = 0;
285: _inverseMap = new HashMap();
286: while (iter.hasNext()) {
287: Ranking rank = (Ranking) iter.next();
288: _code[rank.getValue()] = map[index];
289: _inverseMap.put(map[index], new Integer(rank.getValue()));
290: index++;
291: }
292: }
293:
294: }
|