Informacje wstępne

W trakcie lekcji poświęconych kompresjikompresjakompresji ustaliliśmy, że jej podstawą jest zmiana sposobu kodowania, czyli zmiana sposobu zapisu informacji.

Przykładowo, zapisanie liczb w systemie rzymskim w wielu przypadkach spowoduje zwiększenie liczby znaków potrzebnych do zapisu danej liczby. Liczba „2020”, mogłaby zostać zapisana jako: MMXX.
Natomiast liczba „8” zostałaby zapisana jako VIII.

W pierwszym przypadku nie ma różnicy, a w drugim przypadku liczba znaków jest już różna.

W zdecydowanej większości przypadków korzystanie z systemu rzymskiego spowoduje zwiększenie liczby wymaganych znaków. O ile liczba „2020” dała się w sposób bezstratny konwertować, o tyle już liczba 2222 w systemie rzymskim prezentuje się następująco: MMCCXXII, co jest już wyraźnie dłuższym zestawem znaków.

Przykładowe zadanie typu maturalnego

Zadanie 1

W pewnym zakładzie obliczeniowym są przechowywane dane zapisane w postaci łańcuchów znaków. Metoda ta nie jest optymalna, ale ze względu na specyfikę działania tego konkretnego zakładu – konieczna. Zakład chce jednak zmniejszyć objętość plików, które muszą przechowywać, ale sposób kompresji powinien być w dalszym ciągu łatwo dekodowalny przez człowieka.

Przykładowe dane wejściowe:

5000, 2424222, 400, 562, 1245,

Podpunkt 1

Napisz program, w wybranym języku programowania, pseudokodzie lub w postaci listy kroków, który na podstawie dostarczonego pliku utworzy pseudoskompresowane pliki tekstowe, w których znajdą się informacje na temat powtarzających się pojedynczych liczb.

Specyfikacja:

Dane:

• dane – ciąg znaków, zawierający w sumie 119749 różnych znaków i przecinki; są w nim zapisane liczby

Wynik:

Pseudozakodowany plik, w którym poszczególne powtarzające się liczby zostały zapisane jako: NxL, gdzie N to liczba powtórzeń danej cyfry, a L to cyfra. Między poszczególnymi liczbami powinny znajdować się również przecinki je oddzielające.

Poprawny wynik dla przykładowych danych wejściowych:

1x5 3x0, 1x2, 1x4 1x2, 1x4 3x2, 1x4 2x0, 1x5 1x6 1x2, 1x1 1x2 1x4 1x5,

Przedstawimy rozwiązanie w postaci pseudokodu. Załóżmy, że informacje z pliku zapisaliśmy w tablicy dwuwymiarowej. Pamiętaj jednak, że pisząc własny program, musisz zadbać o prawidłowe wczytanie danych z pliku.

Rozwiązanie:

W rozwiązaniu tym będziemy zliczać wystąpienia identycznych znaków występujących po sobie i po wystąpieniu innego znaku od razu będziemy dopisywać odpowiednie informacje do końca nowo utworzonego ciągu znaków.

wczytaj dane
znak := dane[0]
i := 0
licznik := 0
dla wszystkich znaków w dane:
    jeżeli dane[i] == znak:
        licznik := licznik+1
    w przeciwnym wypadku jeżeli czyJestCyfrą(znak):
		wyjsciowyCiagZnakow := wyjsciowyCiagZnakow + " " + licznik + "x" + znak
    	licznik := 1
        znak = dane[i]
    w przeciwnym wypadku: 
    	wyjsciowyCiagZnakow := wyjsciowyCiagZnakow + " " + licznik + "x" + znak
    	wyjsciowyCiagZnakow := wyjsciowyCiagZnakow + znak
        licznik := 1
    i := i + 1
zwroc wyjsciowyCiagZnakow

Podpunkt 2

Napisz program w wybranym języku programowania, pseudokodzie lub w postaci listy kroków, który przekoduje wynik z poprzedniego podpunktu tak, żeby odtworzyć dane wejściowe.

Specyfikacja:

Dane:

• wejsciowyCiagZnakow – ciąg znaków, w którym zakodowano n różnych liczb, w ten sposób, że np. liczba 100334440 zostałaby zakodowana jako: 1x1 2x0 2x3 3x4 1x0,.

Wynik:

Ciąg znaków utworzony na podstawie zakodowanej wersji, w postaci:
100334440, .....

Rozwiązanie:

W poprzednim podpunkcie zakodowaliśmy dane, w tym podpunkcie wykonujemy operację odwrotną.

wczytaj wejsciowyCiagZnakow
liczba := wejsciowyCiagZnakow[0]
i := 0
czyTrafionoNaX := fałsz
wyjsciowyCiagZnakow := ""
dla wszystkich znaków w wejsciowyCiagZnakow:
	jeżeli czyJestCyfrą(wejsciowyCiagZnakow[i]) i czyTrafionoNaX == fałsz:
    	liczba := liczba*10 + wejsciowyCiagZnakow[i]
    w przeciwnym wypadku, jeżeli wejsciowyCiagZnakow[i] == x:
    	czyTrafionoNaX := prawda
    w przeciwnym wypadku, jeżeli czyJestCyfrą(wejsciowyCiagZnakow[i]):
    	dla j = 0, 1, 2 ... liczba-1 wykonuj:
        	wyjsciowyCiagZnakow := wyjsciowyCiagZnakow + wejsciowyCiagZnakow[i-1]
    w przeciwnym wypadku:
    	wyjsciowyCiagZnakow := wejsciowyCiagZnakow[i]
zwroc wyjsciowyCiagZnakow := ""

Słownik