رمزنگاری با درخت هافمن

[MiKDev]

سلام میکنم خدمت تمام اساتید بزرگوار
کد زیر به زبان جاوا هست و درخت هافمنه ، این درخت برای فشرده سازی به کار میره ولی میشه ازش برای رمز نگاری هم استفاده کرد چون فقط با دیکودر هر متن میشه اونو به حالت قبل برگردوند پیشنهاد شخصیم اینه اگر میخواین کسی به اطلاعاتتون دسترسی نداشته باشه و نتونه به راحتی دیکدش کنه قسمت دیکدر درخت هافمن رو جدا ذخیره کنید.
البته کاربرد های جالب دیگش اینه که میتونید با یه کیلاگر تلفیقش کنید و دنبال روش هایی بگردید که آنتی ویروس ها رو دور بزنه البته باید اول به فکر راهی باشید تا که آنتی ویروس متوجه شنود ورودی ها توسط کیلاگرتون نشه.
درکل کد های زیادی درمورد درخت هافمن تو اینترنت هست که اکثرا گنگ و غیر قابل استفاده هستن من قسمت درخت این کد رو کمی اصلاح کردم و با لینک لیست ترکیبش کردم وبقیه قسمت ها مثل تبدیل به هش و encoding رو براش نوشتم قسمت دیکدش رو هم بعدا بهش اضافه میکنم ولی تا اینجا کد زیر توانایی فشرده سازی متن تا۷۰ درصد ، جدا نگه داشتن دیکودر و تبدیل باینری استرینگ به عدد صحیح برای نمایش عددی رو داره و مشابهش و اختصاصی هست چون میخوام ازش تو کیلاگر استفاده کنم یکم با ترکیب با لیست پیوندی پیچیدش کردم ولی خیلی جای کار داره.

کد به زبان جاوا هست.
موفق و پیروز باشید
 

import java.util.*;
import java.util.Scanner;

class MyMain {

	public static void main(String[] args) {
		System.out.printf("Please Enter your String?\n");
		Scanner input = new Scanner(System.in);
		String Data = input.nextLine();
		CompressWithHuffman CWH = new CompressWithHuffman(Data);
	}
}
abstract class HuffmanTree implements Comparable<HuffmanTree> {
	public final int frequency; // the frequency of this tree

	public HuffmanTree(int freq) {
		frequency = freq;
	}

	// compares on the frequency
	public int compareTo(HuffmanTree tree) {
		return frequency - tree.frequency;
	}
}

class HuffmanLeaf extends HuffmanTree {
	public final char value; // the character this leaf represents

	public HuffmanLeaf(int freq, char val) {
		super(freq);
		value = val;
	}
}

class HuffmanNode extends HuffmanTree {
	public final HuffmanTree left, right; // subtrees

	public HuffmanNode(HuffmanTree l, HuffmanTree r) {
		super(l.frequency + r.frequency);
		left = l;
		right = r;
	}
}

class HuffmanCode {
	// input is an array of frequencies, indexed by character code
	public static HuffmanTree buildTree(list charFreqs) {
		PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();
		// initially, we have a forest of leaves
		// one for each non-empty character
		Node C = charFreqs.Start;
		while (C != null) {
			if (C.value > 0)
				trees.offer(new HuffmanLeaf(C.value, C.Data));
			C = C.next;
		}
		assert trees.size() > 0;
		// loop until there is only one tree left
		while (trees.size() > 1) {
			// two trees with least frequency
			HuffmanTree a = trees.poll();
			HuffmanTree b = trees.poll();

			// put into new node and re-insert into queue
			trees.offer(new HuffmanNode(a, );
		}
		return trees.poll();
	}

	public static void printCodes(HuffmanTree tree, StringBuffer prefix) {
		assert tree != null;
		if (tree instanceof HuffmanLeaf) {
			HuffmanLeaf leaf = (HuffmanLeaf) tree;

			// print out character, frequency, and code for this leaf (which is
			// just the prefix)
			System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix);

		} else if (tree instanceof HuffmanNode) {
			HuffmanNode node = (HuffmanNode) tree;

			// traverse left
			prefix.append('0');
			printCodes(node.left, prefix);
			prefix.deleteCharAt(prefix.length() - 1);

			// traverse right
			prefix.append('1');
			printCodes(node.right, prefix);
			prefix.deleteCharAt(prefix.length() - 1);
		}
	}
}

class Node {
	public char Data;
	public int DataValue;
	public int value;
	public Node next;

	public Node() {

	}

	public Node(char data) {
		this.Data = data;
		DataValue = (int) data;
		value = 1;
	}

	public Node(Node node) {
		Data = node.Data;
		DataValue = node.DataValue;
		value = node.value;
		next = null;
	}
}

class list {
	public Node Start;
	public int size;

	//
	public list() {

	}

	//
	public list(String Str) {
		char[] D;
		D = StringProssesing(Str);
		for (int i = 0; i < D.length; i++) {
			// System.out.printf("%c",D[i]);
			AddChar(D[i]);
		}
		accSort();
	}

	//
	public boolean Empty() {
		if (Start == null) {
			return true;
		}
		return false;
	}

	//
	private static char[] StringProssesing(String text) {
		char[] data = new char[text.length()];
		for (int i = 0; i < text.length(); i++) {
			data[i] = text.charAt(i);
		}
		return data;
	}

	//
	private boolean AddChar(char data) {
		Node p = new Node(data);
		Node C = Start, s = null;
		while (C != null && C.DataValue < p.DataValue) {
			s = C;
			C = C.next;
		}
		p.next = C;
		if (C != null && C.DataValue == p.DataValue) {
			C.value++;
		} else if (s == null) {
			Start = p;
		} else {
			s.next = p;
		}
		size++;
		// System.out.printf("your list Updated successfully:IAE\n");
		return true;
	}

	//
	public void listPrint() {
		if (this.Empty()) {
			System.out.printf("\nyour list is Empty\n");
		} else {
			Node C = Start;
			while (C != null) {
				System.out.printf("%c\t%d\t%d\n", C.Data, C.DataValue, C.value);
				C = C.next;
			}
			System.out.println();
		}
	}

	//
	private void accSort() {
		boolean flag = true;
		while (flag) {
			Node C = Start, s = null;
			flag = false;
			while (C.next != null) {
				s = C;
				C = C.next;
				if (C.next != null && C.value < C.next.value) {
					Node temp = new Node(C);
					s.next = C.next;
					C = C.next;
					if (C.next != null) {
						temp.next = C.next;
						C.next = temp;
					} else
						C.next = temp;
					flag = true;
				}
			}
		}
	}
}

class Encodelist {
	class BuiltTreeLeaf {
		public char Data;
		public StringBuffer leafCode;
		String lf;
		BuiltTreeLeaf next;

		public BuiltTreeLeaf(char data, StringBuffer prefix) {
			Data = data;
			leafCode = new StringBuffer(prefix);
			lf = new String(prefix);
		}
	}

	BuiltTreeLeaf Start;

	public boolean Add(char data, StringBuffer prefix) {
		BuiltTreeLeaf p = new BuiltTreeLeaf(data, prefix);
		BuiltTreeLeaf C = Start, s = null;
		while (C != null) {
			s = C;
			C = C.next;
		}
		p.next = C;
		if (s == null) {
			Start = p;
		} else {
			s.next = p;
		}
		// System.out.printf("your list Updated successfully:IAE\n");
		return true;
	}

	public String FindItem(char item) {
		BuiltTreeLeaf t = Start;
		while (t != null) {
			if (t.Data == item)
				return t.leafCode.toString();
			t = t.next;
		}
		return t.leafCode.toString();
	}

	public boolean AddCodes(HuffmanTree tree, StringBuffer prefix) {
		assert tree != null;
		if (tree instanceof HuffmanLeaf) {
			HuffmanLeaf leaf = (HuffmanLeaf) tree;

			// print out character, frequency, and code for this leaf (which is
			// just the prefix)
			// System.out.println(leaf.value + "\t" + leaf.frequency + "\t" +
			// prefix);
			this.Add(leaf.value, prefix);

		} else if (tree instanceof HuffmanNode) {
			HuffmanNode node = (HuffmanNode) tree;

			// traverse left
			prefix.append('0');
			AddCodes(node.left, prefix);
			prefix.deleteCharAt(prefix.length() - 1);

			// traverse right
			prefix.append('1');
			AddCodes(node.right, prefix);
			prefix.deleteCharAt(prefix.length() - 1);
		}
		return true;
	}

	public void listPrint() {
		BuiltTreeLeaf C = Start;
		while (C != null) {
			System.out.println(C.Data + "\t" + C.leafCode.toString() + "\t" + C.lf);
			C = C.next;
		}
		System.out.println();

	}
}

class EncodeString {
	char[] str;
	String temp = "";
	Encodelist ls;

	public EncodeString(String Str, Encodelist els) {
		str = StringProssesing(Str);
		ls = els;
		Convert();
	}

	public String getHash() {
		return temp;
	}

	boolean Convert() {
		int i = 0;
		boolean flag = true;
		while (flag) {
			temp += ls.FindItem(str[i]);
			i++;
			if (i == str.length - 1)
				flag = false;
		}
		return true;
	}

	private static char[] StringProssesing(String text) {
		char[] data = new char[text.length()];
		for (int i = 0; i < text.length(); i++) {
			data[i] = text.charAt(i);
		}
		return data;
	}

	public static int[] Compress(String str) {
		int[] result;
		if (str.length() % 8 != 0) {
			int a = (str.length() / 8) + 1;
			int b = 8 - (str.length() % 8);
			String t = "";
			for (int i = 0; i < b; i++) {
				t += "0";
			}
			str += t;
		}
		result = new int[str.length() / 8];
		for (int i = 0; i < result.length; i++) {
			String temp = "";
			for (int j = i * 8; j < (i * 8) + 8; j++) {
				temp += str.charAt(j);
			}
			result[i] = binaryToInteger(temp);
		}
		return result;
	}

	private static int binaryToInteger(String binary) {
		char[] numbers = binary.toCharArray();
		int result = 0;
		for (int i = numbers.length - 1; i >= 0; i--)
			if (numbers[i] == '1')
				result += Math.pow(2, (numbers.length - i - 1));
		return result;
	}

}

class CompressWithHuffman {
	public CompressWithHuffman(String Data) {
		list ls = new list(Data);
		HuffmanTree HF = HuffmanCode.buildTree(ls);
		Encodelist els = new Encodelist();
		StringBuffer pre = new StringBuffer();
		els.AddCodes(HF, pre);
		EncodeString ES = new EncodeString(Data, els);
		int[] a = EncodeString.Compress(ES.getHash());
		System.out.printf(Data.length() + "\t" + a.length + "\n");
		for (int i = 0; i < a.length; i++)
			System.out.printf(a[i] + " ");
	}

}

[EvilEye]

درخت هافمن تا جایی می‌دونم که برای فشرده سازی کاربرد داره

[0r0b4s]

در در 26 خرداد 1395 در 09:45، MiKDev گفته است :

سلام میکنم خدمت تمام اساتید بزرگوار
کد زیر به زبان جاوا هست و درخت هافمنه ، این درخت برای فشرده سازی به کار میره ولی میشه ازش برای رمز نگاری هم استفاده کرد چون فقط با دیکودر هر متن میشه اونو به حالت قبل برگردوند پیشنهاد شخصیم اینه اگر میخواین کسی به اطلاعاتتون دسترسی نداشته باشه و نتونه به راحتی دیکدش کنه قسمت دیکدر درخت هافمن رو جدا ذخیره کنید.
البته کاربرد های جالب دیگش اینه که میتونید با یه کیلاگر تلفیقش کنید و دنبال روش هایی بگردید که آنتی ویروس ها رو دور بزنه البته باید اول به فکر راهی باشید تا که آنتی ویروس متوجه شنود ورودی ها توسط کیلاگرتون نشه.
درکل کد های زیادی درمورد درخت هافمن تو اینترنت هست که اکثرا گنگ و غیر قابل استفاده هستن من قسمت درخت این کد رو کمی اصلاح کردم و با لینک لیست ترکیبش کردم وبقیه قسمت ها مثل تبدیل به هش و encoding رو براش نوشتم قسمت دیکدش رو هم بعدا بهش اضافه میکنم ولی تا اینجا کد زیر توانایی فشرده سازی متن تا۷۰ درصد ، جدا نگه داشتن دیکودر و تبدیل باینری استرینگ به عدد صحیح برای نمایش عددی رو داره و مشابهش و اختصاصی هست چون میخوام ازش تو کیلاگر استفاده کنم یکم با ترکیب با لیست پیوندی پیچیدش کردم ولی خیلی جای کار داره.

کد به زبان جاوا هست.
موفق و پیروز باشید
 

import java.util.*;
import java.util.Scanner;

class MyMain {

	public static void main(String[] args) {
		System.out.printf("Please Enter your String?\n");
		Scanner input = new Scanner(System.in);
		String Data = input.nextLine();
		CompressWithHuffman CWH = new CompressWithHuffman(Data);
	}
}
abstract class HuffmanTree implements Comparable<HuffmanTree> {
	public final int frequency; // the frequency of this tree

	public HuffmanTree(int freq) {
		frequency = freq;
	}

	// compares on the frequency
	public int compareTo(HuffmanTree tree) {
		return frequency - tree.frequency;
	}
}

class HuffmanLeaf extends HuffmanTree {
	public final char value; // the character this leaf represents

	public HuffmanLeaf(int freq, char val) {
		super(freq);
		value = val;
	}
}

class HuffmanNode extends HuffmanTree {
	public final HuffmanTree left, right; // subtrees

	public HuffmanNode(HuffmanTree l, HuffmanTree r) {
		super(l.frequency + r.frequency);
		left = l;
		right = r;
	}
}

class HuffmanCode {
	// input is an array of frequencies, indexed by character code
	public static HuffmanTree buildTree(list charFreqs) {
		PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();
		// initially, we have a forest of leaves
		// one for each non-empty character
		Node C = charFreqs.Start;
		while (C != null) {
			if (C.value > 0)
				trees.offer(new HuffmanLeaf(C.value, C.Data));
			C = C.next;
		}
		assert trees.size() > 0;
		// loop until there is only one tree left
		while (trees.size() > 1) {
			// two trees with least frequency
			HuffmanTree a = trees.poll();
			HuffmanTree b = trees.poll();

			// put into new node and re-insert into queue
			trees.offer(new HuffmanNode(a, );
		}
		return trees.poll();
	}

	public static void printCodes(HuffmanTree tree, StringBuffer prefix) {
		assert tree != null;
		if (tree instanceof HuffmanLeaf) {
			HuffmanLeaf leaf = (HuffmanLeaf) tree;

			// print out character, frequency, and code for this leaf (which is
			// just the prefix)
			System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix);

		} else if (tree instanceof HuffmanNode) {
			HuffmanNode node = (HuffmanNode) tree;

			// traverse left
			prefix.append('0');
			printCodes(node.left, prefix);
			prefix.deleteCharAt(prefix.length() - 1);

			// traverse right
			prefix.append('1');
			printCodes(node.right, prefix);
			prefix.deleteCharAt(prefix.length() - 1);
		}
	}
}

class Node {
	public char Data;
	public int DataValue;
	public int value;
	public Node next;

	public Node() {

	}

	public Node(char data) {
		this.Data = data;
		DataValue = (int) data;
		value = 1;
	}

	public Node(Node node) {
		Data = node.Data;
		DataValue = node.DataValue;
		value = node.value;
		next = null;
	}
}

class list {
	public Node Start;
	public int size;

	//
	public list() {

	}

	//
	public list(String Str) {
		char[] D;
		D = StringProssesing(Str);
		for (int i = 0; i < D.length; i++) {
			// System.out.printf("%c",D[i]);
			AddChar(D[i]);
		}
		accSort();
	}

	//
	public boolean Empty() {
		if (Start == null) {
			return true;
		}
		return false;
	}

	//
	private static char[] StringProssesing(String text) {
		char[] data = new char[text.length()];
		for (int i = 0; i < text.length(); i++) {
			data[i] = text.charAt(i);
		}
		return data;
	}

	//
	private boolean AddChar(char data) {
		Node p = new Node(data);
		Node C = Start, s = null;
		while (C != null && C.DataValue < p.DataValue) {
			s = C;
			C = C.next;
		}
		p.next = C;
		if (C != null && C.DataValue == p.DataValue) {
			C.value++;
		} else if (s == null) {
			Start = p;
		} else {
			s.next = p;
		}
		size++;
		// System.out.printf("your list Updated successfully:IAE\n");
		return true;
	}

	//
	public void listPrint() {
		if (this.Empty()) {
			System.out.printf("\nyour list is Empty\n");
		} else {
			Node C = Start;
			while (C != null) {
				System.out.printf("%c\t%d\t%d\n", C.Data, C.DataValue, C.value);
				C = C.next;
			}
			System.out.println();
		}
	}

	//
	private void accSort() {
		boolean flag = true;
		while (flag) {
			Node C = Start, s = null;
			flag = false;
			while (C.next != null) {
				s = C;
				C = C.next;
				if (C.next != null && C.value < C.next.value) {
					Node temp = new Node(C);
					s.next = C.next;
					C = C.next;
					if (C.next != null) {
						temp.next = C.next;
						C.next = temp;
					} else
						C.next = temp;
					flag = true;
				}
			}
		}
	}
}

class Encodelist {
	class BuiltTreeLeaf {
		public char Data;
		public StringBuffer leafCode;
		String lf;
		BuiltTreeLeaf next;

		public BuiltTreeLeaf(char data, StringBuffer prefix) {
			Data = data;
			leafCode = new StringBuffer(prefix);
			lf = new String(prefix);
		}
	}

	BuiltTreeLeaf Start;

	public boolean Add(char data, StringBuffer prefix) {
		BuiltTreeLeaf p = new BuiltTreeLeaf(data, prefix);
		BuiltTreeLeaf C = Start, s = null;
		while (C != null) {
			s = C;
			C = C.next;
		}
		p.next = C;
		if (s == null) {
			Start = p;
		} else {
			s.next = p;
		}
		// System.out.printf("your list Updated successfully:IAE\n");
		return true;
	}

	public String FindItem(char item) {
		BuiltTreeLeaf t = Start;
		while (t != null) {
			if (t.Data == item)
				return t.leafCode.toString();
			t = t.next;
		}
		return t.leafCode.toString();
	}

	public boolean AddCodes(HuffmanTree tree, StringBuffer prefix) {
		assert tree != null;
		if (tree instanceof HuffmanLeaf) {
			HuffmanLeaf leaf = (HuffmanLeaf) tree;

			// print out character, frequency, and code for this leaf (which is
			// just the prefix)
			// System.out.println(leaf.value + "\t" + leaf.frequency + "\t" +
			// prefix);
			this.Add(leaf.value, prefix);

		} else if (tree instanceof HuffmanNode) {
			HuffmanNode node = (HuffmanNode) tree;

			// traverse left
			prefix.append('0');
			AddCodes(node.left, prefix);
			prefix.deleteCharAt(prefix.length() - 1);

			// traverse right
			prefix.append('1');
			AddCodes(node.right, prefix);
			prefix.deleteCharAt(prefix.length() - 1);
		}
		return true;
	}

	public void listPrint() {
		BuiltTreeLeaf C = Start;
		while (C != null) {
			System.out.println(C.Data + "\t" + C.leafCode.toString() + "\t" + C.lf);
			C = C.next;
		}
		System.out.println();

	}
}

class EncodeString {
	char[] str;
	String temp = "";
	Encodelist ls;

	public EncodeString(String Str, Encodelist els) {
		str = StringProssesing(Str);
		ls = els;
		Convert();
	}

	public String getHash() {
		return temp;
	}

	boolean Convert() {
		int i = 0;
		boolean flag = true;
		while (flag) {
			temp += ls.FindItem(str[i]);
			i++;
			if (i == str.length - 1)
				flag = false;
		}
		return true;
	}

	private static char[] StringProssesing(String text) {
		char[] data = new char[text.length()];
		for (int i = 0; i < text.length(); i++) {
			data[i] = text.charAt(i);
		}
		return data;
	}

	public static int[] Compress(String str) {
		int[] result;
		if (str.length() % 8 != 0) {
			int a = (str.length() / 8) + 1;
			int b = 8 - (str.length() % 8);
			String t = "";
			for (int i = 0; i < b; i++) {
				t += "0";
			}
			str += t;
		}
		result = new int[str.length() / 8];
		for (int i = 0; i < result.length; i++) {
			String temp = "";
			for (int j = i * 8; j < (i * 8) + 8; j++) {
				temp += str.charAt(j);
			}
			result[i] = binaryToInteger(temp);
		}
		return result;
	}

	private static int binaryToInteger(String binary) {
		char[] numbers = binary.toCharArray();
		int result = 0;
		for (int i = numbers.length - 1; i >= 0; i--)
			if (numbers[i] == '1')
				result += Math.pow(2, (numbers.length - i - 1));
		return result;
	}

}

class CompressWithHuffman {
	public CompressWithHuffman(String Data) {
		list ls = new list(Data);
		HuffmanTree HF = HuffmanCode.buildTree(ls);
		Encodelist els = new Encodelist();
		StringBuffer pre = new StringBuffer();
		els.AddCodes(HF, pre);
		EncodeString ES = new EncodeString(Data, els);
		int[] a = EncodeString.Compress(ES.getHash());
		System.out.printf(Data.length() + "\t" + a.length + "\n");
		for (int i = 0; i < a.length; i++)
			System.out.printf(a[i] + " ");
	}

}

سلام 

دوست عزیز کد خوبی هست اما نگاهی که بنده کردم نمیشه براین پایه یک فودر مناسب نوشت یا عمل جایگزینی رو انجام داد چون این کلاسهایی که تعریف شده فقط عمل فشرده سازی باینری رو انجام میدن نه عمل معکوس رو 

واینکه این اصلا برا هدر های فایل ایجاد شده چیزی رو مد نظر قرار نداده که در قسمت فود کردن بسیار هائزاهمیت میباشدو انتی ها 85درصد ازهمون فودر برنامه میفهمند که این فایل یک رنسام هست یا سالمه باز اینجا میگم 

بنده جاوا کار نیستم ولی دوسش دارم و نمیگم که کد اشتباه یا بد هست.

این فایلم برا افرادی که میخان هافمن رو در کمترین زمان درک کنن

دانلود

ch10.pdf