Archief - [PROG]C++ Bestanden Comprimeren

dieterm · 11 apr 2006

Hallo,

Ik heb eens zitten nadenken naar een mogelijke manier om bestanden te comprimeren, en ik heb iets gevonden, dat (op papier toch) werkt.
De methode gaat als volgt:

Ik heb een bestand dat ik omzet naar binair.

bv: een bestand “comprimeermij.txt” met daarin de tekst “Dit is een test”
Omgezet in binair geeft dit :
01000100 01101001 01110100 00100000 01101001 01110011 00100000 01100101 01100101 01101110 00100000 01110100 01100101 01110011 01110100

Nu wil ik het volgende doen:
Ik lees telkens twee bits in en tel hoeveel keer de combinatie 00, de combinatie 01, de combinatie 10 en de combinatie 11 voorkomt.

In mijn voorbeeld:
bits 00: 16
bits 01: 24
bits 10: 12
bits 11: 8

Vervolgens wil ik 2 omzettingstabellen maken, nl één voor de even paren en één voor de oneven paren.
(De reeks bits begint met een even paar, de volgende twee bits is een oneven paar, de twee daaropvolgende bits zijn terug een even paar, enz…)
Voor de Even paren geldt:
De combinatie die het meest voorkomt wordt vervangen door een 1
De combinatie die het 2de meeste voorkomt vervangen door 01
De combinatie die het 3de meeste voorkomt vervangen door 001
De combinatie die het 4de meeste voorkomt vervangen door 000

Dus in mijn voorbeeld zou dat betekenen:
00 > 01
01 > 1
10 > 001
11 > 000

Voor de Oneven paren geldt:
De combinatie die het meest voorkomt wordt vervangen door een 0
De combinatie die het 2de meeste voorkomt vervangen door 10
De combinatie die het 3de meeste voorkomt vervangen door 110
De combinatie die het 4de meeste voorkomt vervangen door 111

Dus in mijn voorbeeld zou dat betekenen:
00 > 10
01 > 0
10 > 110
11 > 111

Als resultaat krijg je dus (E=even, O=oneven):

E O E O E O E O E O E O
Oorspronkelijke data: 01 00 01 00 01 10 10 01 01 11 01 00 ...
Na omzetting: 1 10 1 10 1 110 001 0 1 111 1 10 ...

Na omzetting heb ik dus 3 bits minder, maar om het later opnieuw te kunnen omzetten moet ik nog 6 bits bijtellen om te weten welke de 1ste, 2de en 3de meest voorkomende combinaties waren ( de 4de ken je, als je de eerste 3 kent)
Dus in mijn voorbeeld zou ik nog de bits 01 00 10 moeten bijvoegen.

Als je tot hiertoe nog meebent, dan merk je dat ik na omzetting 21 + 6 = 27 bits nodig heb om iets van 24 bits om te zetten, wat dus groter is dan het oorspronkelijke bestand. Maar ik heb het uitgeprobeerd met de tekst
"Dit is een testDit is een testDit is een testDit is een test" en dan heb ik een compressie van 2.5%" (niet veel ik weet het maar het is al iets

)

Zou iemand mij op weg kunnen helpen om dit te schrijven in C/C++ ?

killgore · 11 apr 2006

waarom het wiel opnieuw uitvinden?

Krueger · 11 apr 2006

killgore zei:
waarom het wiel opnieuw uitvinden?

Een vierkant wiel dan nog wel, want het na comprimeren heb je blijkbaar meer bits.
Beter zou zijn om de e door een 1 voor te stellen, de t door 01 etc. Daarna kan je eventueel nog eens runlength codering toepassen.
Een aanrader voor jou zijn zijn eens te zoeken op huffman codering en een huffman boom. Dat doet ongeveer wat jij wil, maar beter

dieterm · 11 apr 2006

Ik heb nog maar een jaartje ervaring in C en ik vond dit wel iets leuk om nog wat bij te leren.
Ik weet niet of deze methode wordt toegepast in compressie-programma's, maar ik vond het toch goed van mij (niet stoeferig bedoeld) dat ik dit zelf gevonden heb.
Ik zou het dan ook tof vinden om mijn methode eens in de praktijk aan het werk te krijgen, maar spijtig genoeg heb ik nog niet genoeg ervaring om dit te maken.
Vandaar dat ik jullie hulp vraag

killgore · 11 apr 2006

Veel compressie gebeurt adhv "geavanceerde" algebra, ik zou idd krueger zen raad volgen en op bestaande methodes zoeken, minder tijdverlies

.

Dat zelf vinden is idd een prestatie

, maar veel zijde er nie mee he

Krueger · 11 apr 2006

killgore zei:
Veel compressie gebeurt adhv "geavanceerde" algebra, ik zou idd krueger zen raad volgen en op bestaande methodes zoeken, minder tijdverlies .

Dat zelf vinden is idd een prestatie , maar veel zijde er nie mee he

Eigenlijk niet hé. Blijkbaar wil hij gewoon c/c++ in de vingers krijgen, en dat aan de hand van zo een programma. Dus het doel heiligt de middelen hé. (Helaas zit mijn c++ nogal ver om te helpen)

BuiZe · 11 apr 2006

Uw voorstel lijkt redelijk op huffman-encodering, dat ook een korte code aan het meest voorkomend teken toekent, en de langste code aan het minst voorkomend teken. Je kan http://www.cis.ksu.edu/~rhowell/viewer/huffman.html eens uitproberen met "hottentottententententoonstelling" als praktisch voorbeeld.

Als je jezelf wil verdiepen in encodering en compressie begin je best met de basisbegrippen zoals de definitie van informatie en dergelijke op te zoeken. Als het in de praktijk moet gebruikt worden, kijk je best naar een library zoals zlib of lzo

edit: posts van mijn voorgangers te vluchtig gelezen, huffman werd blijkbaar reeds aangehaald.

killgore · 11 apr 2006

Krueger zei:
Eigenlijk niet hé. Blijkbaar wil hij gewoon c/c++ in de vingers krijgen, en dat aan de hand van zo een programma. Dus het doel heiligt de middelen hé. (Helaas zit mijn c++ nogal ver om te helpen)

ik vind da ge dan beter iets nuttig kunt doen en een bestaand CONCEPT (dus geen bestaande code/tutos volgen) gaan incoden. Ge kunt natuurlijk uw eigen zaken waarmee ge iets zijt gaan incoden ook, ma das zo onnuttig.

Zo leerde het concept tenminste (waarmee ge mssch nog iets zijt

) en leerde goed coden.

Mjah, ieder zen eigen manier om te leren

.

dieterm · 11 apr 2006

Een concrete vraag dan maar:
Ik kan momenteel in een lus steeds één char inlezen uit het bestand.
Vervolgens wil ik telkens twee bits inlezen en bij de overeenkomende teller één bij optellen.
bitpairs[0] telt het bitpaar 00
bitpairs[1] telt het bitpaar 01
bitpairs[2] telt het bitpaar 10
bitpairs[3] telt het bitpaar 11

Code:

#include <iostream>
#include <fstream>

using namespace std;

// Global structures
struct bitpair {
	long pair_count;
	// hier moeten nog dingen bijkomen later
};

// Global variables
bitpair bitpairs[4] = {0}; // only need 00, 01, 10, 11

// Function declarations
void analyse_file(char *filename);

int main(int argc, char *argv[]) 
{
	cout << "----------------------" << endl
		 << "| Compressie-methode |" << endl 
		 << "----------------------" << endl;

	if(argc>0) 
	{
		for(int i=0; i < argc; i++) 
		{
			if(!strcmp(argv[i],"-f")) 
			{
				analyse_file(argv[++i]);
			}
		}
	} 
	else 
	{
		cout << "Geen argumenten meegegeven!";
	}

	getchar();
	
	return 0;
}

void analyse_file(char *filename) 
{
	long file_length;
	char masker = 3, index;
	char buffer;
	ifstream file;
	
	file.open(filename, ios::binary);
	
	cout << "Open bestand: " << filename << endl;
	
	if(!file.is_open()) {
		cerr << "Fout: Kan het bestand niet openen";
		exit(1);
	}

	// get length of file:
	file.seekg (0, ios::end); // goto end of file
	file_length = file.tellg();
	file.seekg (0, ios::beg); // goto beginning of file

	cout << "total_length (file_length * 8): " << (file_length * 8) << endl;

	while(file >> buffer)
	{
		cout << buffer << endl; // toon karakter op scherm

		for(int pos=0; pos<4; pos++)
		{
			index = (buffer & masker);
			buffer <<= 2;
			bitpairs[(int)index].pair_count++;
		}
	}

	cout << "Bitpair 00: " << bitpairs[0].pair_count << endl;
	cout << "Bitpair 01: " << bitpairs[1].pair_count << endl;
	cout << "Bitpair 10: " << bitpairs[2].pair_count << endl;
	cout << "Bitpair 11: " << bitpairs[3].pair_count << endl;

	file.close();
}

De output van dit programma is:

----------------------
| Compressie-methode |
----------------------
Open bestand: comprimeermij.txt
total_length (file_length * 8): 480
Bitpair 00: 160
Bitpair 01: 20
Bitpair 10: 4
Bitpair 11: 8

Blijkbaar klopt er iets niet want normaal zou de som van die bitpair's samen de helft van 480 moeten zijn.
Ik denk dat ik iets fout doe bij het binair inlezen van de twee bits.
Kan iemand mijn fout vinden?
Alvast bedankt

dieterm · 12 apr 2006

Ik heb de fout ondertussen gevonden

Archief - [PROG]C++ Bestanden Comprimeren

dieterm

Legacy Member

killgore

Legacy Member

Krueger

Legacy Member

dieterm

Legacy Member

killgore

Legacy Member

Krueger

Legacy Member

BuiZe

Legacy Member

killgore

Legacy Member

dieterm

Legacy Member

dieterm

Legacy Member