entry
Di vê gotarê de ez ê li ser algorîtmaya navdar a Huffman, û hem jî serîlêdana wê di berhevkirina daneyan de biaxivim.
Wekî encamek, em ê arşîvek hêsan binivîsin. Jixwe ev yek hatiye nîqaşkirin , lê bêyî pêkanîna pratîk. Materyalên teorîkî yên posta heyî ji dersên zanistiya kompîturê ya dibistanê û pirtûka Robert Laforet "Strukturên Daneyê û Algorîtmayên li Java"yê hatine girtin. Ji ber vê yekê, her tişt qut dibe!
Çend raman
Di pelek nivîsê ya birêkûpêk de, karakterek bi 8 bit (enkodkirina ASCII) an jî 16 (kodkirina Unicode) tê kod kirin. Piştre em ê kodkirina ASCII-ê bifikirin. Mînakî, rêza s1 = "SUSIE DIBÊJE EV EASYn" bigire. Di rêzê de bi tevahî 22 tîp hene, bi xwezayî, di nav wan de cîh û karaktera rêza nû - 'n'. Pela ku vê rêzê dihewîne dê giraniya wê 22*8 = 176 bit. Pirs tavilê derdikeve holê: ma maqûl e ku meriv hemî 8 bit bikar bîne ji bo şîfrekirina 1 karakterê? Em hemî tîpên ASCII bikar nakin. Heger wan bikira jî, maqûltir e ku herfa herî berbelav - S - koda herî kurt were dayîn, û ji bo tîpa herî kêm - T (an U, an 'n') - kodek dirêjtir were dayîn. Ya ku algorîtmaya Huffman jê pêk tê ev e: Pêdivî ye ku vebijarka kodkirina çêtirîn a ku tê de pel dê xwedan giraniya hindiktirîn be bibînin. Pir normal e ku dirêjahiya kodê ji bo sembolên cihêreng cûda dibe - ev e ya ku algorîtma li ser bingeha wê ye.
Kodkirin
Çima kodek nadin karaktera 'S', mînakî, 1 bit dirêj: 0 an 1. Bila ew bibe 1. Paşê karaktera duyemîn a herî gelemperî - ' ' (valahî) - 0 bide. Bifikirin ku we dest bi deşîfrekirina peyama xwe kir - rêzika kodkirî s1 - û hûn dibînin ku kod bi 1-ê dest pê dike. Ji ber vê yekê, hûn çi dikin: ev karaktera S ye, an karakterek din e, mînak A? Ji ber vê yekê, qaîdeyek girîng derdikeve holê:
Divê herdu kod ne pêşgira yekî din be
Ev qaîdeyek di algorîtmayê de sereke ye. Ji ber vê yekê, çêkirina kodek bi tabloyek frekansê dest pê dike, ku frekansa (hejmara bûyeran) ya her sembolê destnîşan dike:
Divê karakterên ku herî zêde çêdibin herî kêm werin kod kirin derîmkan hejmara bits. Ez ê mînakek yek ji tabloyên kodê yên gengaz bidim:
Ji ber vê yekê peyama kodkirî dê bi vî rengî xuya bike:
10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110
Min koda her karakterê bi valahiyek veqetand. Ev ê di pelek bi rastî pêçandî de nebe!
Pirs derdikeve holê: vî xortê ciwan çawa kodek çêkir ku tabloyek kodan çêbike? Ev dê li jêr were nîqaş kirin.
Çêkirina dara Huffman
Li vir darên lêgerînê yên binary têne alîkariyê. Xem neke, hûn ê ne hewce ne ku hûn li vir metodên lêgerîn, têxin an jêbirin. Li vir avahiya darê di java de ye:
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;
}
...
}
Ev ne koda tevahî ye, koda tevahî dê li jêr be.
Li vir algorîtmaya avakirina darê ye:
- Ji bo her karakterek ji peyamê (xêza s1) objeyek Node biafirînin. Di rewşa me de dê 9 nod (Tiştên Node) hebin. Her girêk ji du qadên daneyê pêk tê: sembol û frekansa
- Ji bo her Nodek Tiştek Darê (BinaryTree) biafirînin. Girik dibe koka darê.
- Van daran têxe rêza pêşîn. Frekansa hindiktir, pêşanî bilindtir e. Ji ber vê yekê, dema derxistinê, dervoya bi frekansa herî kêm her gav tê hilbijartin.
Dûv re hûn hewce ne ku van çerxa jêrîn bikin:
- Du daran ji rêza pêşîn derxînin û wan bikin zarokên girêka nû (girêka ku nû hatî afirandin bêyî tîp). Frekansa girêka nû bi kombûna frekansên du darên dûv re wekhev e.
- Ji bo vê girêk, darek bi kok li vê girêkê biafirînin. Vê darê dîsa têxin rêza pêşîn. (Ji ber ku dara xwedan frekansek nû ye, ew ê bi îhtîmalek mezin li cîhek nû di rêzê de xuya bibe)
- Gavên 1 û 2 bidomînin heya ku tenê darek di rêzê de bimîne - dara Huffman
Vê algorîtmayê li ser xeta s1 binihêrin:
Li vir nîşana "lf" (xetxwarin) tê wateya rêzek nû, "sp" (valahî) valahiyek e.
Paşê çi heye?
Me darek Huffman girt. OK. Û bi wê re çi bikin? Ew ê wê belaş jî negirin. Û paşê, hûn hewce ne ku hemî rêyên gengaz ji kokê heya pelên darê bişopînin. Werin em razî bin ku 0 an ango 1 nîşan bidin ger ew ber bi zaroka çepê ve were û XNUMX jî heke ew ber bi yê rastê ve were destnîşan kirin. Bi awayekî hişk, di vê nîşankirinê de, koda sembolê rêyek e ku ji koka darê heya pelê ku vê sembolê vedihewîne ye.
Bi vî rengî tabloya kodan derket holê. Bala xwe bidinê ku heke em vê tabloyê bifikirin, em dikarin li ser "giraniya" her sembolê encam bidin - ev dirêjahiya koda wê ye. Dûv re, di forma pêçandî de, pelê orîjînal dê giran bibe: 2 * 3 + 2 * 4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 bit . Di destpêkê de giraniya wê 176 bit bû. Di encamê de, me ew bi qasî 176/65 = 2.7 carî kêm kir! Lê ev utopyayek e. Ev qasekî wisa ne mimkûn e ku were bidestxistin. Çima? Ev dê hinekî paşê bê nîqaşkirin.
Deşîfrekirin
Welê, dibe ku tiştê herî hêsan mayî deşîfrekirin e. Ez difikirim ku gelek ji we texmîn kirine ku em nekarin bi hêsanî pelek pêçandî bêyî îşaretek ka ew çawa hatî kod kirin biafirînin - em ê nikaribin wê deşîfre bikin! Erê, erê, ji min re zehmet bû ku ez vê yekê fêhm bikim, lê ez ê neçar bim ku pelek nivîsê table.txt bi tabloyek berhevkirinê biafirînim:
01110
00
A010
E1111
I110
S10
T0110
U01111
Y1110
Têketina tabloyê bi forma 'sembol' 'koda karakterê'. Çima 01110 bê sembol e? Bi rastî, ew bi sembolek e, tenê ew amûrên javayê yên ku ez dema ku pelek derdixim bikar tînim, karaktera xêza nû - 'n' - di xetek nû de tê veguheztin (çiqas gêj dibe bila bibe). Ji ber vê yekê, xêza vala ya li jor karaktera koda 01110-ê ye. Ji bo koda 00, karakter li destpêka rêzê cîhek e. Ez ê tavilê bibêjim ku ji bo hevsengiya Xanî ya me, ev rêbaza hilanîna tabloyek dikare îdîa bike ku ya herî bêaqil e. Lê fêmkirin û bicihanîn hêsan e. Ez ê kêfxweş bibim ku di şîroveyan de di derbarê xweşbîniyê de pêşniyarên we bibihîzim.
Hebûna vê tabloyê deşîfrekirina wê pir hêsan dike. Werin em bînin bîra xwe dema ku em kodkirinê diafirînin me çi qaîdeyek şopandiye:
Divê herdu kod ne pêşgira yekî din be
Li vir roleke hêsanker dilîze. Em li pey hev bit bi bît dixwînin û, gava ku rêzika encam d, ku ji bitikên xwendinê pêk tê, bi şîfreya ku bi karaktera karakterê re têkildar e li hev dike, em tavilê dizanin ku karaktera karakterê (û tenê ew!) hatiye kodkirin. Dûv re, em karakterê di rêza dekodkirinê de dinivîsin (xêza ku peyama dekodkirî vedihewîne), rêza d-yê ji nû ve vedike, û dûv re pelê kodkirî dixwîne.
Реализация
Wext e ku ez koda xwe şermezar bikim û arşîvanek binivîsim. Ka em jê re bibêjin Kompresor.
Ji nû ve dest pê bikin. Berî her tiştî, em çîna Node dinivîsin:
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;
}
}
Niha dara:
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;
}
}
Rêza pêşîn:
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;//возвращаем удаленный элемент(элемент с наименьшей частотой)
}
}
Çîna ku dara Huffman diafirîne:
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;
}
}
Dersa ku tê de şîfre/dekod dike:
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("========================================================");
}
}
Çînek ku nivîsandina pelê hêsantir dike:
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();
}
}
Dersek ku xwendina ji pelek hêsantir dike:
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();
}
}
Belê, û çîna sereke:
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());
}
}
Divê hûn bi xwe pelê readme.txt binivîsin :)
encamê
Ez texmîn dikim ku tenê min dixwest ez bibêjim ev e. Ger we tiştek heye ku hûn di derbarê bêkêmasiya min de di baştirkirina kod, algorîtma, an bi gelemperî xweşbîniyek de bibêjin, wê hingê xwe binivîsin. Ger min tiştek rave nekiribe, ji kerema xwe re jî binivîse. Ez dixwazim ji we re di şîroveyan de bibihîzim!
PS
Erê, erê, ez hîna li vir im, ji ber ku min ji bîr nekiriye hevberê. Ji bo string s1, tabloya kodkirinê 48 byte giran e - ji pelê çavkaniyê pir mezintir e, û me sifirên zêde ji bîr nekir (hejmara sifirên lê zêdekirî 7 e) => Rêjeya berhevkirinê dê ji yekê kêmtir be: 176/ (65 + 48*8 + 7) = 0.38. Ger we jî vê yekê ferq kir, wê hingê ne tenê rûyê we xweş e. Erê, ev pêkanîn dê ji bo pelên piçûk pir bêkêmasî be. Lê pelên mezin çi dibe? Mezinahiya pelan ji mezinahiya tabloya kodkirinê pir mezintir e. Li vir e ku algorîtma wekî ku divê dixebite! Ji bo nimûne, ji bo Arşîv jimareyek rastîn (ne îdealîzekirî) 1.46- hema hema yek û nîv carî çêdike! Û erê, diviyabû ku pel bi Îngilîzî be.
Source: www.habr.com