Jak działa kodowanie PackBits i его zastosowanie w kompresji danych

Kodowanie PackBits jest jednym z podstawowych przykładów kompresji danych opartych na długości ciągów powtarzających się elementów, znane także jako kodowanie długości ciągów (RLE, Run-Length Encoding). Choć na pierwszy rzut oka wydaje się to skuteczną metodą kompresji, w praktyce nie jest idealne dla wszystkich rodzajów danych. Istnieją przypadki, w których takie podejście okazuje się mniej efektywne niż przechowywanie surowych danych w niezmienionej formie. Przykładowo, ciąg znaków "ABC" w tej metodzie będzie zapisany jako 1A1B1C, co podwaja rozmiar danych.

Jest to zbliżone do formatu MacPaint, ale pojawia się tu pytanie: jak odróżnić, kiedy liczba oznacza powtórzenie, a kiedy jest częścią literału? Aby rozwiązać ten problem, w systemie PackBits liczby są reprezentowane przez liczby całkowite jedno-bajtowe (signed 1-byte integers). Zasada jest prosta: liczba z zakresu 0–127 oznacza, że po niej następuje n + 1 literalnych bajtów, natomiast liczba z zakresu od -1 do -127 wskazuje, że następny bajt ma się powtarzać 1 - n razy. Z kolei liczba -128 nie jest używana. Dzięki temu systemowi kodowanie literali i powtórzeń może być rozróżniane bez ryzyka niejednoznaczności.

PackBits jest wykorzystywane w wielu popularnych formatach plików, w tym w MacPaint, gdzie kompresja tekstów osiąga średni rozmiar 10 KB. Zaletą tej metody jest to, że działa na poziomie wiersza, co oznacza, że dane w pliku są kompresowane w sposób niezależny dla każdego wiersza. Przykładem może być obraz, którego każdy wiersz zawiera do 576 pikseli (72 bajty), co jest mniejsze niż 128, a zatem nie ma ryzyka przekroczenia limitu rozmiaru ciągu.

PackBits może wydawać się nieco bardziej skomplikowane, ale jego mechanizm jest bardzo prosty. Pierwszym krokiem jest znalezienie ciągów powtarzających się znaków, co można zrobić przy pomocy funkcji take_same(). Ta funkcja, analizując dane wejściowe, znajduje sekwencje powtarzających się bajtów i liczy ich długość. Następnie, w zależności od tego, czy znaleziono ciąg powtórzeń, czy literał, dane są dodawane do kodowanego strumienia w odpowiedni sposób. Kodowanie w tym przypadku może wyglądać jak poniżej:

1. Jeśli znaleziono ciąg powtórzeń, zapisuje się liczbę powtórzeń oraz bajt.

2. Jeśli znaleziono ciąg literali, zapisuje się liczbę literali oraz same literali w formie niezmienionej.

Ta procedura jest wykonywana na każdym wierszu, co zapewnia efektywność i minimalizuje ryzyko błędów w procesie kompresji. Warto zauważyć, że kodowanie PackBits nie ma mechanizmu obsługi pojedynczych powtórzeń (np. "repeat once"), co oznacza, że takie przypadki będą traktowane jako literały.

PackBits jest stosunkowo prostym, ale wydajnym rozwiązaniem dla niektórych typów plików graficznych i innych zastosowań, gdzie dominują powtarzające się dane. W jego obrębie kodowanie długości ciągów powtarzających się elementów jest realizowane w sposób optymalny, a rozmiar pliku może być znacznie zmniejszony bez utraty jakości danych.

Co istotne, oprócz samego sposobu kodowania PackBits, warto pamiętać o jego zastosowaniach. Dzięki temu algorytmowi możliwe jest szybkie kompresowanie danych, które charakteryzują się dużą liczbą powtórzeń. W wielu przypadkach, zwłaszcza w grafice rastrowej, gdzie jedne kolory dominują przez szereg pikseli, metoda ta jest niezwykle skuteczna. Jednakże dla danych bardziej zróżnicowanych, takich jak obrazy z dużą liczbą różnorodnych kolorów, efektywność PackBits może znacząco spadać, co warto mieć na uwadze przy wyborze techniki kompresji.

Jak stworzyć prosty rozpoznawacz cyfr ręcznych przy użyciu Pygame i algorytmu KNN?

Po uruchomieniu tego kodu, nasza aplikacja będzie gotowa do dalszych interakcji. W kolejnym kroku musimy stworzyć pętlę główną programu, która będzie odpowiedzialna za renderowanie obrazu na ekranie oraz obsługę zdarzeń, takich jak naciskanie klawiszy czy kliknięcia myszką.

Pętla główna zaczyna się od stałego wyświetlania tablicy pikseli reprezentujących cyfry na ekranie. Kod:

python
Copy code
while True:

    pygame.surfarray.blit_array(screen, digit_pixels)
    pygame.display.flip()

Umożliwia nam to ciągłe rysowanie i odświeżanie obrazu. Następnie, obsługujemy różne zdarzenia, które mogą wystąpić, w tym naciskanie klawiszy. Klawisz "c" jest używany do klasyfikacji wprowadzonej cyfry. Proces klasyfikacji wymaga przekształcenia danych wejściowych — obrazek przedstawiający cyfrę jest konwertowany z formatu wielowymiarowego na jednowymiarowy wektor. Wartości pikseli są przekształcane na odpowiednią skalę, a następnie klasa KNN (k najbliższych sąsiadów) dokonuje rozpoznania.

Kod do klasyfikacji:

python
Copy code
if key_name == "c":  # klasyfikacja cyfry

    pixels = digit_pixels.transpose((1, 0, 2))[:, :, 0].flatten() * P_TO_D

    classified_digit = digits_knn.classify(K, Digit("", pixels))
    print(f"Classified as {classified_digit}")

Kolejny klawisz — "e" — umożliwia wyczyszczenie matrycy, czyli usunięcie rysunku, a klawisz "p" służy do przewidywania tego, jak powinna wyglądać narysowana cyfra. W tym przypadku proces jest podobny do klasyfikacji, ale zamiast klasyfikować obrazek, używamy algorytmu KNN do przewidywania, jak ten obrazek może wyglądać na podstawie innych podobnych w zbiorze uczącym.

Kod przewidywania:

python
Copy code
elif key_name == "p":  # przewidywanie cyfry

    pixels = digit_pixels.transpose((1, 0, 2))[:, :, 0].flatten() * P_TO_D
    predicted_pixels = digits_knn.predict_array(K, Digit("", pixels), "pixels")
    predicted_pixels = predicted_pixels.reshape((PIXEL_HEIGHT, PIXEL_WIDTH)).transpose((1, 0)) * D_TO_P
    digit_pixels = np.stack((predicted_pixels, predicted_pixels, predicted_pixels), axis=2)

Program rozpoznawania cyfr obsługuje również kliknięcia myszką — każdy klik na ekranie rysuje biały punkt na matrycy. Program kończy działanie, kiedy użytkownik zamknie okno.

python
Copy code
elif event.type == pygame.MOUSEBUTTONDOWN or (event.type == pygame.MOUSEMOTION and pygame.mouse.get_pressed()[0]):

    x, y = event.pos
    if x < PIXEL_WIDTH and y < PIXEL_HEIGHT:
        digit_pixels[x][y] = WHITE

Choć nasz program jest stosunkowo krótki (około 50 linii kodu), potrafi poprawnie rozpoznać większość rysunków cyfr, co świadczy o efektywności i prostocie algorytmu KNN. Mimo że algorytm ten jest prosty, działa zaskakująco dobrze i daje możliwość łatwego prototypowania rozpoznawania obrazów.

Algorytm KNN, pomimo swojej prostoty, znajduje szerokie zastosowanie w różnych dziedzinach, takich jak analiza tekstu, przewidywanie wyników finansowych, czy nawet medycyna. W badaniach dotyczących długości pobytu pacjentów w szpitalu w czasie pandemii COVID-19, KNN wykazał się podobną skutecznością co bardziej zaawansowane metody, takie jak regresja logistyczna czy lasy losowe. Co więcej, KNN jest stosunkowo łatwy do zaimplementowania i nie wymaga skomplikowanego strojenia parametrów, co czyni go idealnym narzędziem w przypadku, gdy zależy nam na prostocie i szybkości.

Należy jednak pamiętać, że algorytm KNN nie sprawdza się w przypadku danych hałaśliwych lub zbyt dużych zbiorów, w których czas obliczeń staje się nieakceptowalnie długi. W takich przypadkach warto rozważyć inne algorytmy, takie jak SVM (maszyny wektorów nośnych) czy sieci neuronowe, które lepiej radzą sobie z dużymi i złożonymi zbiorami danych.

Jak działa NanoBASIC: Zrozumienie podstaw i składni

NanoBASIC, uproszczona wersja języka BASIC, ma na celu nauczenie podstaw programowania i rozwiązywania problemów poprzez proste skrypty. Składa się z prostych poleceń, które pozwalają na manipulowanie danymi, wykonywanie obliczeń matematycznych oraz sterowanie przebiegiem programu. Choć język ten jest ograniczony, to jednak stanowi doskonałą okazję do zrozumienia fundamentów programowania, które pozostają niezmienne niezależnie od używanego języka.

Jednym z kluczowych elementów NanoBASIC jest polecenie PRINT, które służy do wyświetlania informacji na ekranie. Może ono wyświetlać zarówno literały tekstowe, jak i wynik obliczeń. W NanoBASIC wystarczy użyć prostych instrukcji, aby np. wyświetlić ciąg tekstowy, jak:

arduino
Copy code
10 PRINT "What a nice program"

20 PRINT "Who said sit down?"
30 PRINT "6734 spells HELP upside down sorta"

Programy w tym języku mogą również wyświetlać wyniki działań matematycznych, takich jak dodawanie, mnożenie, czy inne operacje arytmetyczne. Na przykład:

arduino
Copy code
30 PRINT "2 plus 2 is", 2 + 2, "and 3 times 5 is", 3 * 5

Wynik tego polecenia to:

csharp
Copy code
2 plus 2 is 4 and 3 times 5 is 15

Warto zauważyć, że między wyrażeniami dodawane są tabulatory, które mogą wyglądać różnie w zależności od ustawień konsoli.

Instrukcje warunkowe i wyrażenia logiczne w NanoBASIC

Podobnie jak w innych językach programowania, NanoBASIC obsługuje instrukcje warunkowe. Jednak są one bardzo uproszczone w porównaniu do standardowych rozwiązań. Instrukcja IF sprawdza warunek, a jeśli jest on prawdziwy, wykonuje przypisaną akcję. W NanoBASIC IF nie obsługuje operatorów logicznych jak AND czy OR i nie posiada klauzuli ELSE. Przykładowo, aby sprawdzić, czy liczba jest mniejsza od 10, i w zależności od tego wyświetlić komunikat, użyjemy takiego zapisu:

vbnet
Copy code
500 IF N < 10 THEN PRINT "Small Number"

700 IF V >= 34 THEN GOTO 20

Wyrażenia logiczne w NanoBASIC różnią się od tych w bardziej zaawansowanych językach programowania, np. operator nierówności to <> lub ><, a porównanie równości wykonuje się za pomocą znaku =, a nie ==.

Skok do etykiety: GOTO, GOSUB i RETURN

NanoBASIC korzysta z instrukcji sterujących takich jak GOTO, GOSUB oraz RETURN. Instrukcja GOTO przerywa bieżący ciąg wykonywania programu i natychmiast przenosi do wskazanej linii kodu. Z kolei GOSUB umożliwia przejście do określonej linii, a potem po wykonaniu kodu powrót do miejsca, z którego zostało wywołane. Kluczową różnicą jest to, że po zakończeniu GOSUB należy użyć instrukcji RETURN, aby wrócić do miejsca wywołania. Na przykład:

pgsql
Copy code
10 GOTO 50
20 LET A = 10
40 RETURN
50 LET A = 5
60 GOSUB 20 REM RETURN returns to here; we expect A to be 10
70 PRINT A

W tym przypadku program wyświetli 10, ponieważ po wykonaniu GOSUB zmienna A została ustawiona na wartość 10.

Styl programowania w NanoBASIC

NanoBASIC nie posiada zaawansowanych narzędzi do organizowania kodu, dlatego warto wprowadzać odpowiednie komentarze, które pomogą w zrozumieniu struktury programu. Dobrą praktyką jest także pisanie słów kluczowych w języku BASIC wielkimi literami, co zwiększa czytelność. Z racji, że NanoBASIC nie oferuje złożonych mechanizmów kontrolujących przepływ programu, takich jak pętle FOR, często korzysta się z instrukcji GOTO, co może prowadzić do tzw. "spaghetti code". Choć to rozwiązanie jest prymitywne, jest ono typowe dla starszych wersji języka BASIC, a także dla niektórych języków maszynowych i assemblera.

Przykład programu: Liczby Fibonacciego

Aby lepiej zrozumieć działanie NanoBASIC, warto przyjrzeć się przykładowi programu, który wypisuje liczby Fibonacciego mniejsze niż 100. Sekwencja Fibonacciego to ciąg liczb, w którym każda liczba (oprócz pierwszych dwóch) jest sumą dwóch poprzednich. Program w NanoBASIC, który generuje te liczby, wygląda następująco:

vbnet
Copy code
REM Printing the Fibonacci numbers less than 100

REM A is the last number
10 LET A = 0
REM B is the next number
11 LET B = 1
20 PRINT A
21 PRINT B
REM C is last + next
30 LET C = A + B
31 LET A = B
32 LET B = C
40 IF B < 100 THEN GOTO 21

Zrozumienie składni języka

Aby jeszcze głębiej zrozumieć działanie NanoBASIC, warto przyjrzeć się składni, która opiera się na tzw. formie Backusa-Naur’a (BNF). Jest to metoda formalnego opisania gramatyki języka programowania. Dzięki tej gramatyce możemy określić, jakie konstrukcje są poprawne, a które nie. Dla przykładu:

go
Copy code
<expression> ::= <letter> | <digit>

<letter> ::= 'A' | 'B'
<digit> ::= '1' | '2'

Gramatyka pozwala na generowanie poprawnych łańcuchów znaków, a także sprawdzanie, czy dany ciąg tekstowy spełnia zasady języka.

Rozważania na temat przyszłości

Mimo że NanoBASIC jest celowo uproszczony, jego projekt oparty na rzeczywistej wersji Tiny BASIC czyni go interesującym przykładem języka, który może pomóc w nauce podstaw programowania. Choć brak zaawansowanych funkcji programistycznych, takich jak pętle FOR czy strukturalne instrukcje sterujące, może ograniczać możliwości, to i tak pozostaje użyteczny w nauce podstawowych zasad działania komputerów.