PB161 Jazyk C++ - 6. cvicení

Bentleyho kódování

Úvod:

Bentleyho kódování je slovníková komprese, která je velice úcinná u bezného textu s castým opakováním stejných slov. Prestoze je tento algoritmus velice jednoduchý, pro potrebu naseho príkladu ho trochu upravíme. Toto kódování se dá predvést napríklad na následujícím príklade:

Puvodní zpráva: KAZDY STUDENT BDI KAZDY DEN CELY DEN
Slovník: KAZDY STUDENT BDI DEN CELY
Zakódovaná zpráva: 1 KAZDY 2 STUDENT 3 BDI 1 4 DEN 5 CELY 4

Jak lze videt, algoritmus pridá do slovníku kazdé dosud neznámé slovo. Na výstup se pak posílá "index slova ve slovníku [bílé místo] slovo samotné" (v prípade ze dané slovo se vyskytlo poprvé), nebo pouze "index slova " (v prípade ze slovo jiz ve slovníku existovalo). Index je rostoucí, pocínaje jednickou, a zvysující se vzdy o 1. Ve skutecnosti se samozrejme slovník optimalizuje tak, ze slova s nejcastejsím výskytem mají nejnizsí indexy, a slova s nejméne castým výskytem indexy nejvyssí. My si vsak pro jednoduchost zavedeme pravidlo, ze se do slovníku budou slova pridávat dle jejich prvního výskytu (tudíz presne jak v ukázkovém príklade), nikoliv dle cetnosti jejich výskytu.
Dekódování textu probíhá samozrejme presne opacným zpusobem. Program jako první prvek na vstupu ocekává císlici 1, následovanou prvním slovem pridávaným do slovníku. Dále vzdy dvojici "nový_index bílý_znak nové_ slovo", nebo jen "existující_ index". Na výstup se posílá dekódovaný text.

Zadání:

Vytvorte program, který bude ze standardního vstupu císt text, a na standardní výstup bude posílat text zakódovaný zjednoduseným Bentleyho kódováním, a opacne.

Pozadavky:

• Program nazvete bentley.
• Pri spustení programu pouze jeho názvem, tudíz príkazem bentley, bude program kódovat (komprimovat) text na standardním vstupu, a posílat jej na standardní výstup. Pri pustení programu s volbou -d, tudíz príkazem bentley -d, bude program dekódovat (dekomprimovat) text na standardním vstupu, a posílat jej na standarní výstup. Výstup programu se bude rídit algoritmem popsaným v Úvodu. Pokud bude program spusten s nesprávnými volbami ci parametry, vypiste na standardní výstup správné pouzití programu a skoncete.
• Program pracuje do té doby, dokud nenacte znak konce souboru (v Unixu pri ctení z klávesnice tento stav zpusobíte klávesovou kombinací Ctrl+D na zacátku rádku; ve Windows zkratkou Ctrl+Z na zacátku rádku).
• Pri kompresi textu nacítáte slova oddelená bílým místem. Nemusíte zachovávat formátování (pocty mezer, tabelátory, konce rádku). Pokud se rozhodnete nezachovávat formátování, tak císla a slova posílané na výstup oddelujte jednou mezerou.
• Pri dekompresi textu predpokládejte, ze vstupní text je korektní a splnuje syntaxi (císlování zacíná jednickou; císlování slov se korektne zvysuje vzdy o 1; slova jsou oddelena bílým místem; tam kde program ocekává císlo opravdu bude císlo). Nemusíte zachovávat formátování (pocty mezer, tabelátory, konce rádku). Pokud se rozhodnete nezachovávat formátování, tak slova posílané na výstup oddelujte jednou mezerou.
• V nasem algoritmu nebudeme rozlisovat písmena a interpunkcní znaménka. Pokud tedy vstupní text bude obsahovat interpuncní znaménka, budeme je povazovat za soucást slova, ke kterému priléhají. Potom tedy napríklad takovýto vstupní text:
Prvni text, druhy text, treti text.
Zakódujeme jako:
1 Prvni 2 text, 3 druhy 2 4 treti 5 text.
• Podle Konvence 11 slusný program vypisuje výzvu k zadávání dat. Vypisujte ji vsak nikoli do proudu cout, ale do cerr. Jinak se stává soucástí zakódovaného textu.
• Pokud zvládnete osetrit, aby program nehavaroval pri nekorektních vstupních datech, a vsechny takovéto vstupy ohlásil, dostanete dva bonusové body navíc. Nekorektními vstupními daty je mysleno nedodrzení syntaxe vstupního textu (dle popisu v Úvodu) pri dekompresi textu. (Napríklad na vstupu je text na míste, kde by správne melo být císlo). Dobre si promyslete, jaké vsechny prípady mohou nastat, aby byla syntaxe porusena. Nemusíte ale osetrovat prípad, ze se na vstupu vyskytne jako index slova císlo delsí nez odpovídá long int.
  Zároven musíte na standardní chybový výstup poslat hlásku o chybe programu spolu s posledním korektne nacteným vstupem a vstupem, který zpusobil chybu. Na standardní chybový výstup se posílá text príkazem cerr<< (místo cout<<).
• Dalsí 2 body navíc dostanete, pokud dokázete zachovat formátování vstupního textu. Výstupní text bude tedy obsahovat presne stejné pocty mezer, tabelátory a konce rádku a se stejným umístením jako text vstupní. Nevznikne nám tudíz jeden dlouhý rádek obsahující proud slov oddelených mezerou, ale opravdu soubor se shodným formátováním.
  Budete pro to ovsem zrejme potrebovat pár metod z deváté prednásky pracující se vstupním proudem, konkrétne asi:
  cin.get() (0 az 3 parametry (kam, délka, koncový_znak)) - dovolí Vám nacíst jeden znak ze vstupního bufferu
  cin.unget() - vrátí poslední prectený znak zpet do vstupního bufferu

#include<iostream>
#include<string>
#include<map>
using namespace std;

long int index=1;
string retazec;
//==================KOMPRIMOVAT=================================================
void komprimovat(void)
{
map<string,int> kompresia;
map<string,int>::iterator p;

 for(;;)                                     // hlavny cyklus kompresie
 {
  if (!(cin>>retazec)) break;
  p=kompresia.find(retazec);
  if (p==kompresia.end())                     // retazec este nepozna  
   {
	  kompresia.insert(make_pair(retazec,index));
	  cout<<index<<' '<<retazec<<' ';
	  index++;
	 }
	else                                        // retazec uz pozna 
	 {
	  cout<<p->second<<' ';
	 } 
 }
	
}
//==================DEKOMPRIMOVAT===============================================
void dekomprimovat(void)
{
map<int,string> dekompresia;
map<int,string>::iterator p;

 for(;;)                                     // hlavny cyklus dekompresie
 {
  if (!(cin>>index)) break;
  p=dekompresia.find(index);
  if (p==dekompresia.end())                     // retazec este nepozna  
   {
		cin>>retazec;
	  dekompresia.insert(make_pair(index,retazec));
	  cout<<retazec<<' ';
	 }
	else                                        // retazec uz pozna 
	 {
	  cout<<p->second<<' ';
	 } 
 }	
}
//==================MAIN========================================================
int main(int argc,char *argv[])
{
 if(argc==2)
  {
	 if (argv[1][0]=='-' && argv[1][1]=='d') dekomprimovat();
		
	  else{cout<<"Zadali ste nespravny parameter!!\n";
		     cout<<"Spravny tvar pre dekomprimaciu je: bentley -d\n";
		     cout<<"             pre komprimaciu bez parametra\n";
				}
  }
 else komprimovat();
	
cout<<endl;	 
return 0;		 
}