داخلہ
اس مضمون میں میں مشہور ہف مین الگورتھم کے ساتھ ساتھ ڈیٹا کمپریشن میں اس کے اطلاق کے بارے میں بات کروں گا۔
نتیجے کے طور پر، ہم ایک سادہ آرکائیور لکھیں گے. اس پر پہلے ہی بات ہو چکی ہے۔ لیکن عملی نفاذ کے بغیر۔ موجودہ پوسٹ کا نظریاتی مواد اسکول کے کمپیوٹر سائنس کے اسباق اور رابرٹ لافورٹ کی کتاب "جاوا میں ڈیٹا سٹرکچرز اینڈ الگورتھم" سے لیا گیا ہے۔ تو، سب کچھ کٹ گیا ہے!
چند خیالات
ایک باقاعدہ ٹیکسٹ فائل میں، ایک کریکٹر کو 8 بٹس (ASCII انکوڈنگ) یا 16 (یونیکوڈ انکوڈنگ) کے ساتھ انکوڈ کیا جاتا ہے۔ اگلا ہم ASCII انکوڈنگ پر غور کریں گے۔ مثال کے طور پر، s1 = "SUSIE SAYS IT IS EASYn" لائن لیں۔ لائن میں کل 22 حروف ہیں، قدرتی طور پر، خالی جگہوں اور نئے لائن کریکٹر - 'n' سمیت۔ اس لائن پر مشتمل فائل کا وزن 22*8 = 176 بٹس ہوگا۔ سوال فوری طور پر پیدا ہوتا ہے: کیا 8 کریکٹر کو انکوڈ کرنے کے لیے تمام 1 بٹس کا استعمال کرنا عقلی ہے؟ ہم تمام ASCII حروف استعمال نہیں کرتے ہیں۔ یہاں تک کہ اگر انہوں نے ایسا کیا ہے، تو یہ زیادہ معقول ہوگا کہ سب سے عام خط - S - کو مختصر ترین ممکنہ کوڈ دیا جائے، اور نایاب خط - T (یا U، یا 'n') - کے لیے ایک طویل کوڈ دیا جائے۔ یہ وہی ہے جو Huffman الگورتھم پر مشتمل ہے: یہ ضروری ہے کہ بہترین انکوڈنگ آپشن تلاش کیا جائے جس میں فائل کا وزن کم سے کم ہو۔ یہ بالکل عام بات ہے کہ کوڈ کی لمبائی مختلف علامتوں کے لیے مختلف ہوگی - یہ وہی ہے جس پر الگورتھم مبنی ہے۔
کوڈنگ
حرف 'S' کو ایک کوڈ کیوں نہیں دیتے، مثال کے طور پر، 1 بٹ لمبا: 0 یا 1۔ اسے 1 رہنے دیں۔ پھر دوسرا سب سے عام کریکٹر - ' ' (space) - 0 دیں۔ تصور کریں کہ آپ نے اپنے پیغام کو ڈی کوڈ کرنا شروع کر دیا ہے۔ انکوڈ شدہ سٹرنگ s1 - اور آپ دیکھتے ہیں کہ کوڈ 1 سے شروع ہوتا ہے۔ تو، آپ کیا کرتے ہیں: کیا یہ S حرف ہے، یا یہ کوئی دوسرا کریکٹر ہے، مثال کے طور پر A؟ لہذا، ایک اہم اصول پیدا ہوتا ہے:
کوئی بھی کوڈ دوسرے کا سابقہ نہیں ہونا چاہئے۔
یہ اصول الگورتھم میں کلیدی حیثیت رکھتا ہے۔ لہذا، ایک کوڈ بنانا فریکوئنسی ٹیبل سے شروع ہوتا ہے، جو ہر علامت کی تعدد (واقعات کی تعداد) کی نشاندہی کرتا ہے:
سب سے زیادہ واقعات والے حروف کو کم سے کم انکوڈ کیا جانا چاہئے۔ ممکن بٹس کی تعداد میں ممکنہ کوڈ ٹیبلز میں سے ایک کی مثال دوں گا۔
تو انکوڈ شدہ پیغام اس طرح نظر آئے گا:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
میں نے ہر کردار کے کوڈ کو اسپیس کے ساتھ الگ کیا۔ یہ واقعی کمپریسڈ فائل میں نہیں ہوگا!
سوال یہ پیدا ہوتا ہے کہ اس نوجوان نے کوڈ کا ٹیبل بنانے کا کوڈ کیسے بنایا؟ اس پر ذیل میں بات کی جائے گی۔
ایک Huffman درخت کی تعمیر
یہ وہ جگہ ہے جہاں بائنری تلاش کے درخت بچاؤ کے لئے آتے ہیں۔ پریشان نہ ہوں، آپ کو یہاں تلاش کرنے، داخل کرنے یا حذف کرنے کے طریقوں کی ضرورت نہیں ہوگی۔ جاوا میں درخت کی ساخت یہ ہے:
public class Node {
private int frequence;
private char letter;
private Node leftChild;
private Node rightChild;
...
}
class BinaryTree {
private Node root;
public BinaryTree() {
root = new Node();
}
public BinaryTree(Node root) {
this.root = root;
}
...
}
یہ مکمل کوڈ نہیں ہے، مکمل کوڈ نیچے دیا جائے گا۔
درخت کی تعمیر کا الگورتھم یہ ہے:
- پیغام (لائن s1) سے ہر کردار کے لیے نوڈ آبجیکٹ بنائیں۔ ہمارے معاملے میں 9 نوڈس (نوڈ آبجیکٹ) ہوں گے۔ ہر نوڈ دو ڈیٹا فیلڈز پر مشتمل ہوتا ہے: علامت اور تعدد
- ہر نوڈ کے لیے ٹری آبجیکٹ (BinaryTree) بنائیں۔ نوڈ درخت کی جڑ بن جاتا ہے.
- ان درختوں کو ترجیحی قطار میں داخل کریں۔ فریکوئنسی جتنی کم ہوگی، ترجیح اتنی ہی زیادہ ہوگی۔ اس طرح، نکالتے وقت، سب سے کم تعدد کے ساتھ ڈیرو کو ہمیشہ منتخب کیا جاتا ہے۔
اگلا آپ کو درج ذیل چکر لگانے کی ضرورت ہے:
- ترجیحی قطار سے دو درختوں کو ہٹا دیں اور انہیں نئے نوڈ کے بچے بنائیں (بغیر خط کے نئے بنائے گئے نوڈ)۔ نئے نوڈ کی فریکوئنسی دو نسلی درختوں کی تعدد کے مجموعے کے برابر ہے۔
- اس نوڈ کے لیے، اس نوڈ پر جڑ کے ساتھ ایک درخت بنائیں۔ اس درخت کو دوبارہ ترجیحی قطار میں داخل کریں۔ (چونکہ درخت کی ایک نئی تعدد ہے، اس لیے یہ قطار میں کسی نئی جگہ پر ظاہر ہو گا)
- مرحلہ 1 اور 2 کو جاری رکھیں جب تک کہ قطار میں صرف ایک درخت باقی نہ رہ جائے - ہفمین درخت
لائن s1 پر اس الگورتھم پر غور کریں:
یہاں علامت "lf" (linefeed) کا مطلب ایک نئی لائن ہے، "sp" (space) ایک اسپیس ہے۔
اس کے بعد کیا ہے؟
ہمیں ہف مین کا درخت ملا۔ ٹھیک ہے. اور اس کے ساتھ کیا کرنا ہے؟ وہ اسے مفت میں بھی نہیں لیں گے۔ اور پھر، آپ کو جڑ سے درخت کے پتوں تک تمام ممکنہ راستے تلاش کرنے کی ضرورت ہے۔ آئیے ایک کنارے 0 کو ظاہر کرنے پر اتفاق کرتے ہیں اگر یہ بائیں بچے کی طرف جاتا ہے اور 1 اگر یہ دائیں طرف لے جاتا ہے۔ سخت الفاظ میں، اس اشارے میں، علامت کا کوڈ درخت کی جڑ سے پتی تک کا راستہ ہے جس میں یہ علامت ہے۔
کوڈز کا ٹیبل اس طرح نکلا۔ نوٹ کریں کہ اگر ہم اس جدول پر غور کریں تو ہم ہر علامت کے "وزن" کے بارے میں نتیجہ اخذ کر سکتے ہیں - یہ اس کے کوڈ کی لمبائی ہے۔ پھر، کمپریسڈ شکل میں، اصل فائل کا وزن ہوگا: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 بٹس . پہلے اس کا وزن 176 بٹ تھا۔ اس کے نتیجے میں، ہم نے اسے 176/65 = 2.7 گنا تک کم کیا! لیکن یہ یوٹوپیا ہے۔ اس طرح کا گتانک حاصل کرنے کا امکان نہیں ہے۔ کیوں؟ اس پر تھوڑی دیر بعد بات کی جائے گی۔
ضابطہ کشائی
ٹھیک ہے، شاید سب سے آسان چیز ڈی کوڈنگ ہے۔ مجھے لگتا ہے کہ آپ میں سے بہت سے لوگوں نے اندازہ لگایا ہے کہ ہم صرف ایک کمپریسڈ فائل کو بغیر کسی اشارے کے نہیں بنا سکتے کہ اسے کیسے انکوڈ کیا گیا تھا - ہم اسے ڈی کوڈ کرنے کے قابل نہیں ہوں گے! ہاں، ہاں، میرے لیے اس کا ادراک کرنا مشکل تھا، لیکن مجھے کمپریشن ٹیبل کے ساتھ ایک ٹیکسٹ فائل table.txt بنانا پڑے گا:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
'علامت' 'کریکٹر کوڈ' کی شکل میں ٹیبل کا اندراج۔ 01110 بغیر علامت کے کیوں ہے؟ درحقیقت، یہ ایک علامت کے ساتھ ہے، یہ صرف یہ ہے کہ جاوا ٹولز جو میں فائل میں آؤٹ پٹ کرتے وقت استعمال کرتا ہوں، نیو لائن کریکٹر - 'n' - کو ایک نئی لائن میں تبدیل کر دیا جاتا ہے (چاہے یہ کتنا ہی احمقانہ لگے)۔ اس لیے، سب سے اوپر خالی لائن کوڈ 01110 کے لیے کریکٹر ہے۔ کوڈ 00 کے لیے، کریکٹر لائن کے شروع میں ایک اسپیس ہے۔ میں فوراً کہوں گا کہ ہمارے خان کوفیشنٹ کے لیے، میز کو ذخیرہ کرنے کا یہ طریقہ انتہائی غیر معقول ہونے کا دعویٰ کر سکتا ہے۔ لیکن اسے سمجھنا اور لاگو کرنا آسان ہے۔ مجھے اصلاح کے حوالے سے تبصروں میں آپ کی تجاویز سن کر خوشی ہوگی۔
یہ ٹیبل رکھنے سے اسے ڈی کوڈ کرنا بہت آسان ہو جاتا ہے۔ آئیے یاد رکھیں کہ انکوڈنگ بناتے وقت ہم نے کس اصول کی پیروی کی:
کوئی بھی کوڈ دوسرے کا سابقہ نہیں ہونا چاہئے۔
یہ وہ جگہ ہے جہاں یہ سہولت کاری کا کردار ادا کرتا ہے۔ ہم ترتیب وار تھوڑا سا پڑھتے ہیں اور جیسے ہی نتیجے میں آنے والی سٹرنگ d، پڑھنے والے بٹس پر مشتمل ہوتی ہے، کیریکٹر کیریکٹر سے مماثل انکوڈنگ سے میل کھاتی ہے، ہم فوراً جان جاتے ہیں کہ کریکٹر کیریکٹر (اور صرف یہ!) انکوڈ کیا گیا تھا۔ اگلا، ہم ڈیکوڈنگ لائن (ڈی کوڈ شدہ پیغام پر مشتمل لائن) میں کریکٹر لکھتے ہیں، لائن ڈی کو دوبارہ ترتیب دیتے ہیں، اور پھر انکوڈ شدہ فائل کو پڑھتے ہیں۔
Реализация
یہ میرے کوڈ کی تذلیل کرنے اور آرکائیور لکھنے کا وقت ہے۔ آئیے اسے کمپریسر کہتے ہیں۔
پھر سے شروع. سب سے پہلے، ہم نوڈ کلاس لکھتے ہیں:
public class Node {
private int frequence;//частота
private char letter;//буква
private Node leftChild;//левый потомок
private Node rightChild;//правый потомок
public Node(char letter, int frequence) { //собственно, конструктор
this.letter = letter;
this.frequence = frequence;
}
public Node() {}//перегрузка конструтора для безымянных узлов(см. выше в разделе о построении дерева Хаффмана)
public void addChild(Node newNode) {//добавить потомка
if (leftChild == null)//если левый пустой=> правый тоже=> добавляем в левый
leftChild = newNode;
else {
if (leftChild.getFrequence() <= newNode.getFrequence()) //в общем, левым потомком
rightChild = newNode;//станет тот, у кого меньше частота
else {
rightChild = leftChild;
leftChild = newNode;
}
}
frequence += newNode.getFrequence();//итоговая частота
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public int getFrequence() {
return frequence;
}
public char getLetter() {
return letter;
}
public boolean isLeaf() {//проверка на лист
return leftChild == null && rightChild == null;
}
}
اب درخت:
class BinaryTree {
private Node root;
public BinaryTree() {
root = new Node();
}
public BinaryTree(Node root) {
this.root = root;
}
public int getFrequence() {
return root.getFrequence();
}
public Node getRoot() {
return root;
}
}
ترجیحی قطار:
import java.util.ArrayList;//да-да, очередь будет на базе списка
class PriorityQueue {
private ArrayList<BinaryTree> data;//список очереди
private int nElems;//кол-во элементов в очереди
public PriorityQueue() {
data = new ArrayList<BinaryTree>();
nElems = 0;
}
public void insert(BinaryTree newTree) {//вставка
if (nElems == 0)
data.add(newTree);
else {
for (int i = 0; i < nElems; i++) {
if (data.get(i).getFrequence() > newTree.getFrequence()) {//если частота вставляемого дерева меньше
data.add(i, newTree);//чем част. текущего, то cдвигаем все деревья на позициях справа на 1 ячейку
break;//затем ставим новое дерево на позицию текущего
}
if (i == nElems - 1)
data.add(newTree);
}
}
nElems++;//увеличиваем кол-во элементов на 1
}
public BinaryTree remove() {//удаление из очереди
BinaryTree tmp = data.get(0);//копируем удаляемый элемент
data.remove(0);//собственно, удаляем
nElems--;//уменьшаем кол-во элементов на 1
return tmp;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
وہ کلاس جو ہف مین ٹری کو تخلیق کرتی ہے:
public class HuffmanTree {
private final byte ENCODING_TABLE_SIZE = 127;//длина кодировочной таблицы
private String myString;//сообщение
private BinaryTree huffmanTree;//дерево Хаффмана
private int[] freqArray;//частотная таблица
private String[] encodingArray;//кодировочная таблица
//----------------constructor----------------------
public HuffmanTree(String newString) {
myString = newString;
freqArray = new int[ENCODING_TABLE_SIZE];
fillFrequenceArray();
huffmanTree = getHuffmanTree();
encodingArray = new String[ENCODING_TABLE_SIZE];
fillEncodingArray(huffmanTree.getRoot(), "", "");
}
//--------------------frequence array------------------------
private void fillFrequenceArray() {
for (int i = 0; i < myString.length(); i++) {
freqArray[(int)myString.charAt(i)]++;
}
}
public int[] getFrequenceArray() {
return freqArray;
}
//------------------------huffman tree creation------------------
private BinaryTree getHuffmanTree() {
PriorityQueue pq = new PriorityQueue();
//алгоритм описан выше
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) {//если символ существует в строке
Node newNode = new Node((char) i, freqArray[i]);//то создать для него Node
BinaryTree newTree = new BinaryTree(newNode);//а для Node создать BinaryTree
pq.insert(newTree);//вставить в очередь
}
}
while (true) {
BinaryTree tree1 = pq.remove();//извлечь из очереди первое дерево.
try {
BinaryTree tree2 = pq.remove();//извлечь из очереди второе дерево
Node newNode = new Node();//создать новый Node
newNode.addChild(tree1.getRoot());//сделать его потомками два извлеченных дерева
newNode.addChild(tree2.getRoot());
pq.insert(new BinaryTree(newNode);
} catch (IndexOutOfBoundsException e) {//осталось одно дерево в очереди
return tree1;
}
}
}
public BinaryTree getTree() {
return huffmanTree;
}
//-------------------encoding array------------------
void fillEncodingArray(Node node, String codeBefore, String direction) {//заполнить кодировочную таблицу
if (node.isLeaf()) {
encodingArray[(int)node.getLetter()] = codeBefore + direction;
} else {
fillEncodingArray(node.getLeftChild(), codeBefore + direction, "0");
fillEncodingArray(node.getRightChild(), codeBefore + direction, "1");
}
}
String[] getEncodingArray() {
return encodingArray;
}
public void displayEncodingArray() {//для отладки
fillEncodingArray(huffmanTree.getRoot(), "", "");
System.out.println("======================Encoding table====================");
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) {
System.out.print((char)i + " ");
System.out.println(encodingArray[i]);
}
}
System.out.println("========================================================");
}
//-----------------------------------------------------
String getOriginalString() {
return myString;
}
}
کلاس جس میں انکوڈز/ڈی کوڈز شامل ہیں:
public class HuffmanOperator {
private final byte ENCODING_TABLE_SIZE = 127;//длина таблицы
private HuffmanTree mainHuffmanTree;//дерево Хаффмана (используется только для сжатия)
private String myString;//исходное сообщение
private int[] freqArray;//частотаная таблица
private String[] encodingArray;//кодировочная таблица
private double ratio;//коэффициент сжатия
public HuffmanOperator(HuffmanTree MainHuffmanTree) {//for compress
this.mainHuffmanTree = MainHuffmanTree;
myString = mainHuffmanTree.getOriginalString();
encodingArray = mainHuffmanTree.getEncodingArray();
freqArray = mainHuffmanTree.getFrequenceArray();
}
public HuffmanOperator() {}//for extract;
//---------------------------------------compression-----------------------------------------------------------
private String getCompressedString() {
String compressed = "";
String intermidiate = "";//промежуточная строка(без добавочных нулей)
//System.out.println("=============================Compression=======================");
//displayEncodingArray();
for (int i = 0; i < myString.length(); i++) {
intermidiate += encodingArray[myString.charAt(i)];
}
//Мы не можем писать бит в файл. Поэтому нужно сделать длину сообщения кратной 8=>
//нужно добавить нули в конец(можно 1, нет разницы)
byte counter = 0;//количество добавленных в конец нулей (байта в полне хватит: 0<=counter<8<127)
for (int length = intermidiate.length(), delta = 8 - length % 8;
counter < delta ; counter++) {//delta - количество добавленных нулей
intermidiate += "0";
}
//склеить кол-во добавочных нулей в бинарном предаствлении и промежуточную строку
compressed = String.format("%8s", Integer.toBinaryString(counter & 0xff)).replace(" ", "0") + intermidiate;
//идеализированный коэффициент
setCompressionRatio();
//System.out.println("===============================================================");
return compressed;
}
private void setCompressionRatio() {//посчитать идеализированный коэффициент
double sumA = 0, sumB = 0;//A-the original sum
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
if (freqArray[i] != 0) {
sumA += 8 * freqArray[i];
sumB += encodingArray[i].length() * freqArray[i];
}
}
ratio = sumA / sumB;
}
public byte[] getBytedMsg() {//final compression
StringBuilder compressedString = new StringBuilder(getCompressedString());
byte[] compressedBytes = new byte[compressedString.length() / 8];
for (int i = 0; i < compressedBytes.length; i++) {
compressedBytes[i] = (byte) Integer.parseInt(compressedString.substring(i * 8, (i + 1) * 8), 2);
}
return compressedBytes;
}
//---------------------------------------end of compression----------------------------------------------------------------
//------------------------------------------------------------extract-----------------------------------------------------
public String extract(String compressed, String[] newEncodingArray) {
String decompressed = "";
String current = "";
String delta = "";
encodingArray = newEncodingArray;
//displayEncodingArray();
//получить кол-во вставленных нулей
for (int i = 0; i < 8; i++)
delta += compressed.charAt(i);
int ADDED_ZEROES = Integer.parseInt(delta, 2);
for (int i = 8, l = compressed.length() - ADDED_ZEROES; i < l; i++) {
//i = 8, т.к. первым байтом у нас идет кол-во вставленных нулей
current += compressed.charAt(i);
for (int j = 0; j < ENCODING_TABLE_SIZE; j++) {
if (current.equals(encodingArray[j])) {//если совпало
decompressed += (char)j;//то добавляем элемент
current = "";//и обнуляем текущую строку
}
}
}
return decompressed;
}
public String getEncodingTable() {
String enc = "";
for (int i = 0; i < encodingArray.length; i++) {
if (freqArray[i] != 0)
enc += (char)i + encodingArray[i] + 'n';
}
return enc;
}
public double getCompressionRatio() {
return ratio;
}
public void displayEncodingArray() {//для отладки
System.out.println("======================Encoding table====================");
for (int i = 0; i < ENCODING_TABLE_SIZE; i++) {
//if (freqArray[i] != 0) {
System.out.print((char)i + " ");
System.out.println(encodingArray[i]);
//}
}
System.out.println("========================================================");
}
}
ایک کلاس جو فائل میں لکھنا آسان بناتی ہے:
import java.io.File;
import java.io.PrintWriter;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.Closeable;
public class FileOutputHelper implements Closeable {
private File outputFile;
private FileOutputStream fileOutputStream;
public FileOutputHelper(File file) throws FileNotFoundException {
outputFile = file;
fileOutputStream = new FileOutputStream(outputFile);
}
public void writeByte(byte msg) throws IOException {
fileOutputStream.write(msg);
}
public void writeBytes(byte[] msg) throws IOException {
fileOutputStream.write(msg);
}
public void writeString(String msg) {
try (PrintWriter pw = new PrintWriter(outputFile)) {
pw.write(msg);
} catch (FileNotFoundException e) {
System.out.println("Неверный путь, или такого файла не существует!");
}
}
@Override
public void close() throws IOException {
fileOutputStream.close();
}
public void finalize() throws IOException {
close();
}
}
ایک کلاس جو فائل سے پڑھنا آسان بناتی ہے:
import java.io.FileInputStream;
import java.io.EOFException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.Closeable;
import java.io.File;
import java.io.IOException;
public class FileInputHelper implements Closeable {
private FileInputStream fileInputStream;
private BufferedReader fileBufferedReader;
public FileInputHelper(File file) throws IOException {
fileInputStream = new FileInputStream(file);
fileBufferedReader = new BufferedReader(new InputStreamReader(fileInputStream));
}
public byte readByte() throws IOException {
int cur = fileInputStream.read();
if (cur == -1)//если закончился файл
throw new EOFException();
return (byte)cur;
}
public String readLine() throws IOException {
return fileBufferedReader.readLine();
}
@Override
public void close() throws IOException{
fileInputStream.close();
}
}
ٹھیک ہے، اور اہم کلاس:
import java.io.File;
import java.nio.charset.MalformedInputException;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.NoSuchFileException;
import java.nio.file.Paths;
import java.util.List;
import java.io.EOFException;
public class Main {
private static final byte ENCODING_TABLE_SIZE = 127;
public static void main(String[] args) throws IOException {
try {//указываем инструкцию с помощью аргументов командной строки
if (args[0].equals("--compress") || args[0].equals("-c"))
compress(args[1]);
else if ((args[0].equals("--extract") || args[0].equals("-x"))
&& (args[2].equals("--table") || args[2].equals("-t"))) {
extract(args[1], args[3]);
}
else
throw new IllegalArgumentException();
} catch (ArrayIndexOutOfBoundsException | IllegalArgumentException e) {
System.out.println("Неверный формат ввода аргументов ");
System.out.println("Читайте Readme.txt");
e.printStackTrace();
}
}
public static void compress(String stringPath) throws IOException {
List<String> stringList;
File inputFile = new File(stringPath);
String s = "";
File compressedFile, table;
try {
stringList = Files.readAllLines(Paths.get(inputFile.getAbsolutePath()));
} catch (NoSuchFileException e) {
System.out.println("Неверный путь, или такого файла не существует!");
return;
} catch (MalformedInputException e) {
System.out.println("Текущая кодировка файла не поддерживается");
return;
}
for (String item : stringList) {
s += item;
s += 'n';
}
HuffmanOperator operator = new HuffmanOperator(new HuffmanTree(s));
compressedFile = new File(inputFile.getAbsolutePath() + ".cpr");
compressedFile.createNewFile();
try (FileOutputHelper fo = new FileOutputHelper(compressedFile)) {
fo.writeBytes(operator.getBytedMsg());
}
//create file with encoding table:
table = new File(inputFile.getAbsolutePath() + ".table.txt");
table.createNewFile();
try (FileOutputHelper fo = new FileOutputHelper(table)) {
fo.writeString(operator.getEncodingTable());
}
System.out.println("Путь к сжатому файлу: " + compressedFile.getAbsolutePath());
System.out.println("Путь к кодировочной таблице " + table.getAbsolutePath());
System.out.println("Без таблицы файл будет невозможно извлечь!");
double idealRatio = Math.round(operator.getCompressionRatio() * 100) / (double) 100;//идеализированный коэффициент
double realRatio = Math.round((double) inputFile.length()
/ ((double) compressedFile.length() + (double) table.length()) * 100) / (double)100;//настоящий коэффициент
System.out.println("Идеализированный коэффициент сжатия равен " + idealRatio);
System.out.println("Коэффициент сжатия с учетом кодировочной таблицы " + realRatio);
}
public static void extract(String filePath, String tablePath) throws FileNotFoundException, IOException {
HuffmanOperator operator = new HuffmanOperator();
File compressedFile = new File(filePath),
tableFile = new File(tablePath),
extractedFile = new File(filePath + ".xtr");
String compressed = "";
String[] encodingArray = new String[ENCODING_TABLE_SIZE];
//read compressed file
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!check here:
try (FileInputHelper fi = new FileInputHelper(compressedFile)) {
byte b;
while (true) {
b = fi.readByte();//method returns EOFException
compressed += String.format("%8s", Integer.toBinaryString(b & 0xff)).replace(" ", "0");
}
} catch (EOFException e) {
}
//--------------------
//read encoding table:
try (FileInputHelper fi = new FileInputHelper(tableFile)) {
fi.readLine();//skip first empty string
encodingArray[(byte)'n'] = fi.readLine();//read code for 'n'
while (true) {
String s = fi.readLine();
if (s == null)
throw new EOFException();
encodingArray[(byte)s.charAt(0)] = s.substring(1, s.length());
}
} catch (EOFException ignore) {}
extractedFile.createNewFile();
//extract:
try (FileOutputHelper fo = new FileOutputHelper(extractedFile)) {
fo.writeString(operator.extract(compressed, encodingArray));
}
System.out.println("Путь к распакованному файлу " + extractedFile.getAbsolutePath());
}
}
آپ کو readme.txt فائل خود لکھنی ہوگی :)
حاصل يہ ہوا
مجھے لگتا ہے کہ میں صرف اتنا ہی کہنا چاہتا تھا۔ اگر آپ کو کوڈ، الگورتھم، یا عمومی طور پر کسی اصلاح میں میری نااہلی کے بارے میں کچھ کہنا ہے، تو بلا جھجھک لکھیں۔ اگر میں نے کچھ وضاحت نہیں کی ہے تو براہ کرم بھی لکھ دیں۔ میں تبصرے میں آپ سے سننا پسند کروں گا!
PS
ہاں، ہاں، میں اب بھی یہاں ہوں، کیونکہ میں گتانک کے بارے میں نہیں بھولا تھا۔ سٹرنگ s1 کے لیے، انکوڈنگ ٹیبل کا وزن 48 بائٹس ہے - جو سورس فائل سے بہت بڑا ہے، اور ہم اضافی زیرو کے بارے میں نہیں بھولے (شامل زیرو کی تعداد 7 ہے) => کمپریشن کا تناسب ایک سے کم ہوگا: 176/ (65 + 48*8 + 7) = 0.38۔ اگر آپ نے بھی یہ دیکھا ہے، تو یہ صرف آپ کا چہرہ ہی نہیں ہے جو بہت اچھا ہے۔ ہاں، یہ نفاذ چھوٹی فائلوں کے لیے انتہائی غیر موثر ہو گا۔ لیکن بڑی فائلوں کا کیا ہوتا ہے؟ فائل کے سائز انکوڈنگ ٹیبل کے سائز سے بہت بڑے ہیں۔ یہ وہ جگہ ہے جہاں الگورتھم کام کرتا ہے جیسا کہ اسے کرنا چاہئے! مثال کے طور پر، کے لیے آرکائیور 1.46 کا ایک حقیقی (مثالی نہیں) گتانک تیار کرتا ہے - تقریبا ڈیڑھ گنا! اور ہاں، فائل انگریزی میں ہونی تھی۔
ماخذ: www.habr.com