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:

Linia 1. 5000 przecinek 2424222 przecinek 400 przecinek 562 przecinek 1245 przecinek.

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.

Linia 1. wczytaj dane. Linia 2. znak dwukropek znak równości dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 3. i dwukropek znak równości 0. Linia 4. licznik dwukropek znak równości 0. Linia 5. dla wszystkich znaków w dane dwukropek. Linia 6. jeżeli dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości znak dwukropek. Linia 7. licznik dwukropek znak równości licznik plus 1. Linia 8. w przeciwnym wypadku jeżeli czyJestCyfrą otwórz nawias okrągły znak zamknij nawias okrągły dwukropek. Linia 9. wyjsciowyCiagZnakow dwukropek znak równości wyjsciowyCiagZnakow plus cudzysłów cudzysłów plus licznik plus cudzysłów x cudzysłów plus znak. Linia 10. licznik dwukropek znak równości 1. Linia 11. znak znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 12. w przeciwnym wypadku dwukropek. Linia 13. wyjsciowyCiagZnakow dwukropek znak równości wyjsciowyCiagZnakow plus cudzysłów cudzysłów plus licznik plus cudzysłów x cudzysłów plus znak. Linia 14. wyjsciowyCiagZnakow dwukropek znak równości wyjsciowyCiagZnakow plus znak. Linia 15. licznik dwukropek znak równości 1. Linia 16. i dwukropek znak równości i plus 1. Linia 17. 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ą.

Linia 1. wczytaj wejsciowyCiagZnakow. Linia 2. liczba dwukropek znak równości wejsciowyCiagZnakow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 3. i dwukropek znak równości 0. Linia 4. czyTrafionoNaX dwukropek znak równości fałsz. Linia 5. wyjsciowyCiagZnakow dwukropek znak równości cudzysłów cudzysłów. Linia 6. dla wszystkich znaków w wejsciowyCiagZnakow dwukropek. Linia 7. jeżeli czyJestCyfrą otwórz nawias okrągły wejsciowyCiagZnakow otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły i czyTrafionoNaX znak równości znak równości fałsz dwukropek. Linia 8. liczba dwukropek znak równości liczba asterysk 10 plus wejsciowyCiagZnakow otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 9. w przeciwnym wypadku przecinek jeżeli wejsciowyCiagZnakow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości x dwukropek. Linia 10. czyTrafionoNaX dwukropek znak równości prawda. Linia 11. w przeciwnym wypadku przecinek jeżeli czyJestCyfrą otwórz nawias okrągły wejsciowyCiagZnakow otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły dwukropek. Linia 12. dla j znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka liczba minus 1 wykonuj dwukropek. Linia 13. wyjsciowyCiagZnakow dwukropek znak równości wyjsciowyCiagZnakow plus wejsciowyCiagZnakow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy. Linia 14. w przeciwnym wypadku dwukropek. Linia 15. wyjsciowyCiagZnakow dwukropek znak równości wejsciowyCiagZnakow otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 16. zwroc wyjsciowyCiagZnakow dwukropek znak równości cudzysłów cudzysłów.

Słownik

kod
kod

ciąg jednoznacznie identyfikowalnych kombinacji znaków i symboli, dzięki którym możemy odczytać informację w sposób jednoznaczny

kompresja
kompresja

proces polegający na zmianie sposobu zapisu informacji w ten sposób, aby zmniejszyć redundancję oraz objętość zbioru

plik
plik

uporządkowany zbiór danych o skończonej długości stanowiący dla użytkownika systemu operacyjnego całość;  może również posiadać atrybuty lub inne cechy, takie jak uprawnienia, czy nazwa, które dodatkowo go charakteryzują; możliwy zestaw cech i atrybutów zależy od konkretnego systemu