Matura 2016 (maj). Zadanie 1. Kompresja

Matura 2016 (maj). Zadanie 1. Kompresja

Rozważmy algorytm kompresji, który zlicza liczbę kolejnych wystąpień tego samego znaku, a następnie zamiast całej grupy identycznych znaków podaje ten znak tylko jeden raz, poprzedzając go liczbą jego kolejnych wystąpień. Liczba kolejnych wystąpień każdego znaku nie przekracza 9, więc do zapisania tej liczby wystarczy jeden znak.

Przykład:

tekst źródłowy tekst skompresowany rozmiar tekstu w liczbie znaków
źródłowego skompresowanego
 FFFYYYYYYYYYFFFHAAAAA  3F9Y3F1H5A  21 10

Zadanie 1.

Skompresuj powyższym algorytmem tekst podany w tabeli, oblicz rozmiar tekstu przed kompresją i po kompresji.

tekst źródłowy tekst skompresowany rozmiar tekstu w liczbie znaków
źródłowego skompresowanego
***##!!* 3*2#2!1* 8 8

Zadanie 2.

Ile powinna wynosić minimalna liczba kolejnych znaków w grupie, aby jej kompresja była opłacalna?

Rozwiązanie:

W tekście musi występować powyżej dwa takie same znaki lub minimum dwa razy występować trzy takie same znaki.

Zadanie 3.

Czy opisana metoda kompresji jest stratna, czy – bezstratna?

Rozwiązanie:

Opisana kompresja jest bezstratna, ponieważ tekst, który został skompresowany, możliwe jest przywrócić tekst źródłowy bez jakiejkolwiek straty.

Zadanie 4.

Napisz (w postaci listy kroków, schematu blokowego, pseudokodu lub w wybranym języku programowania) algorytm obliczający rozmiar skompresowanego tekstu.

Specyfikacja:

Dane:

n – dodatnia liczba całkowita, długość kompresowanego tekstu
T[1..n] – tablica zawierająca tekst do skompresowania; T[i] – i-ty znak w tekście

Wynik:

b – rozmiar skompresowanego tekstu T

Algorytm:

#include <iostream>
using namespace std;
int main()
{
 string tekst = "***##!!*";
 string nowy = "";
 int dl = tekst.length();
 int ile=1;
 char szyfr = tekst[0];
 for (int i=1; i<dl; i++){
   if(szyfr==tekst[i])
     ile++;
   else {
     nowy+=(48+ile);
   nowy+=szyfr;
   ile=1;
   szyfr = tekst[i];
   }
 }
 nowy+=(48+ile);
 nowy+=szyfr;
 cout << nowy.length();
 return 0;
}

Leave a Reply

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>