LZ77 - Algorithmus - Auflösung
Las ich zu diesem Algorithmus... Und ich codiert eine Klasse zu komprimieren, habe ich nicht codiert, das Dekomprimieren Klasse noch...
Was denkst du über den code?
Ich glaube, ich habe ein problema... Meine Kodifizierung ist : "position | Länge", aber ich glaube, dass diese Methode halten Sie mich auf Probleme, wenn Sie krank Dekomprimieren, weil ich nicht weiß, ob die Zahl der Positionen und die Länge sind 2, 3, 4-stellig... :S
einige Ratschläge angenommen... 😀
Irgendwelche Vorschläge angenommen werden.
Main-Datei:
#include <iostream>
#include "Compressor.h"
int main() {
Compressor c( "/home/facu/text.txt", 3);
std::cout << c.get_TEXT_FILE() << std::endl;
std::cout << c.get_TEXT_ENCONDED() << std::endl;
c.save_file_encoded();
return 0;
}
header-Datei :
#ifndef _Compressor_H_
#define _Compressor_H_
#include <utility>
#include <string>
typedef unsigned int T_UI;
class Compressor
{
public:
//Constructor
Compressor( const std::string &PATH, const T_UI minbytes = 3 );
/** GET BUFFERS **/
std::string get_TEXT_FILE() const;
std::string get_TEXT_ENCONDED() const;
/** END GET BUFFERS **/
void save_file_encoded();
private:
/** BUFFERS **/
std::string TEXT_FILE; //contains the text from an archive
std::string TEXT_ENCODED; //contains the text encoded
std::string W_buffer; //contains the string to analyze
std::string W_inspection; //contains the string where will search matches
/** END BUFFERS **/
T_UI size_of_minbytes;
T_UI size_w_insp; //The size of window inspection
T_UI actual_byte;
std::pair< T_UI, T_UI> v_codes; //Values to code text
//Utilitaries functions
void change_size_insp(){ size_w_insp = TEXT_FILE.length() ; }
bool inspection_empty() const;
std::string convert_pair() const;
//Encode algorythm
void lz77_encode();
};
#endif
Umsetzung Datei :
#include <iostream>
#include <fstream>
using std::ifstream;
using std::ofstream;
#include <string>
#include <cstdlib>
#include <sstream>
#include "Compressor.h"
Compressor::Compressor(const std::string& PATH, const T_UI minbytes)
{
std::string buffer = "";
TEXT_FILE = "";
ifstream input_text( PATH.c_str(), std::ios::in );
if( !input_text )
{
std::cerr << "Can't open the text file";
std::exit( 1 );
}
while( !input_text.eof() )
{
std::getline( input_text, buffer );
TEXT_FILE += buffer;
TEXT_FILE += "\n";
buffer.clear();
}
input_text.close();
change_size_insp();
size_of_minbytes = minbytes;
TEXT_ENCODED = "";
W_buffer = "";
W_inspection = "";
v_codes.first = 0;
v_codes.second = 0;
actual_byte = 0;
lz77_encode();
}
std::string Compressor::get_TEXT_FILE() const
{
return TEXT_FILE;
}
std::string Compressor::get_TEXT_ENCONDED() const
{
return TEXT_ENCODED;
}
bool Compressor::inspection_empty() const
{
return ( size_w_insp != 0 );
}
std::string Compressor::convert_pair() const
{
std::stringstream out;
out << v_codes.first;
out << "|";
out << v_codes.second;
return out.str();
}
void Compressor::save_file_encoded()
{
std::string path("/home/facu/encoded.txt");
ofstream out_txt( path.c_str(),std::ios::out );
out_txt << TEXT_ENCODED << "\n";
out_txt.close();
}
void Compressor::lz77_encode()
{
while( inspection_empty() )
{
W_buffer = TEXT_FILE.substr( actual_byte, 1);
if( W_inspection.find( W_buffer ) == W_inspection.npos )
{
//Cant find any byte from buffer
TEXT_ENCODED += W_buffer;
W_inspection += W_buffer;
W_buffer.clear();
++actual_byte;
--size_w_insp;
}
else
{
//We founded any byte from buffer in inspection
v_codes.first = W_inspection.find( W_buffer );
v_codes.second = 1;
while( W_inspection.find( W_buffer ) != W_inspection.npos )
{
++actual_byte;
--size_w_insp;
v_codes.second++;
W_inspection += TEXT_FILE[actual_byte - 1];
W_buffer += TEXT_FILE[actual_byte];
}
++actual_byte;
--size_w_insp;
if( v_codes.second > size_of_minbytes )
TEXT_ENCODED += convert_pair();
else
TEXT_ENCODED += W_buffer;
W_buffer.clear();
}
}
}
Danke!
Im coding die descompressing Klasse 🙂
- Was ist eine Codierung wie " position|Länge|' - machen, oder die Länge einer festen Breite Feld?
- Yup, ich dachte, dass... also ich glaube der beste Weg ist die Verwendung von "Datei zufällig" mit den Strukturen in der Datei...
Du musst angemeldet sein, um einen Kommentar abzugeben.
Generell empfehle ich, das schreiben der Dekompressor zuerst, und dann schreiben Sie den Kompressor, um es anzupassen.
Empfehle ich immer einen Kompressor und entsprechende Entpacker arbeiten mit einer festen Größe kopieren Sie die Dateien zuerst, und erst danach-wenn notwendig-optimieren Sie produzieren/konsumieren, variable-size-Elemente kopieren.
Viele LZ77-algorithmen verwenden eine Feste Größe in der komprimierten Datei zu repräsentieren sowohl die position und Länge;
oft eine hex-Ziffer für die Länge, und 3 hex-Ziffern für die position, insgesamt 2 bytes.
Den "|" zwischen die position und die Kopie, die Länge ist unnötig.
Wenn Sie wirklich versuchen, zu implementieren, die original LZ77-Algorithmus,
Ihre Kompressions-Algorithmus muss immer wieder den festen Länge kopieren-Länge (auch wenn es null ist), wird die fixe Länge, position (wenn die Länge null ist, könnte man genauso gut kleben null hier auch), und eine Feste Länge literalen Wert.
Einige LZ77-wie Datei-Formate sind unterteilt in "Elemente", die entweder eine Feste Länge auf und kopieren-Länge,position-pair-Mädchen oder sonst eine oder mehrere Literale Werte.
Wenn Sie diesen Weg gehen, der Kompressor muss irgendwie erstmal sagen die decompressor, ob die kommende Element repräsentiert literal value(s) - oder eine Kopie-Länge, position paar.
Eine von vielen Möglichkeiten, dies zu tun ist, um die Reservierung eine Besondere Stellung "0" - Wert, der anstatt der angibt, eine position in der Ausgabe dekomprimiert Streams wie alle anderen Werte der position, stattdessen zeigt die nächsten paar literal-Werte in die input-komprimierte Datei.
Fast alle LZ77-algorithmen speichern "offset" rückwärts von der aktuellen Position in den Text, anstatt ein "- position" vorn aus dem Anfang des Klartext.
Zum Beispiel, "1" steht für den in jüngster Zeit entschlüsselten Klartext-byte, nicht der erste-dekodierter Klartext-byte.
Wie ist es möglich, für die decoder zu sagen, wo das eine ganze Zahl endet und der nächste beginnt, wenn die komprimierte Datei enthält eine Reihe von Ganzzahlen?
Es gibt 3 beliebte Antworten:
http://en.wikibooks.org/wiki/Data_Compression
Jacob Ziv und Abraham Lempel; A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, 23(3), S. 337-343, Mai 1977.