Bezkomputera
1
2
3
4
5

Lekcja 2: Kompresja tekstu

Grades 6-8 | Grades 9-12

Przegląd

W pewnym momencie docieramy do fizycznego limitu prędkości, z jaką możemy przesyłać bity, i jeżeli chcemy przesyłać dużą ilość informacji szybciej, musimy znaleźć sposób reprezentowania tej samej informacji za pomocą mniejszej ilości bitów - musimy skompresować dane. W tej lekcji uczniowie wykorzystają Widget Kompresji Tekstu do skompresowania segmentów tekstu w języku angielskim poprzez wyszukiwanie wzorców i zastępowanie większych fragmentów symbolami.

Cel

Podstawową zasadą przyświecającą kompresji jest opracowanie metody lub protokołu używania mniejszej ilości bitów do przedstawienia oryginalnej informacji. Sposób, w jaki przedstawiamy skompresowane dane w ramach tej lekcji, przy pomocy "słownika" powtórzonych wzorców, jest podobny do schematu kompresji LZW, należy natomiast zauważyć, że LZW jest nieco inny od tego, co robią na tej lekcji uczniowie. Uczniowie wynajdują tutaj swój własny sposób. LZW wykorzystuje się nie tylko do tekstu (pliki zip), ale również do formatu plików obrazkowych GIF.

Agenda

Pierwsze kroki (5-7 min)

Aktywność (45 min)

Podsumowanie (10 min)

Wersja rozszerzona

Cele

Uczniowie będą w stanie:

  • Współpracować z rówieśnikami, aby znaleźć rozwiązanie zadania polegającego na kompresji tekstu używając "Widgetu kompresji tekstu (planu kompresji bezstratnej).
  • Wyjaśniać powody, dla których kompresja w ilości optymalnej nie jest możliwa lub jest "trudna" do określenia.
  • Wyjaśniać czynniki, które sprawiają, że kompresja stanowi wyzwanie.
  • Opisać cel i uzasadnienie dla kompresji bezstratnej.

Przygotowanie

  • Przetestuj widget kompresji tekstu
  • Przejrzyj wskazówki dydaktyczne, aby zdecydować, z których opcji chcesz skorzystać

Odnośniki

Uwaga! Zrób kopię wszelkich dokumentów, które planujesz udostępnić uczniom.

Dla Teacher

Dla Students

Słownictwo

  • Kompresja bezstratna - algorytm kompresji danych, który pozwala na perfekcyjne odtworzenie oryginalnych danych ze skompresowanych danych.

Wsparcie

Zgłoś błąd

Poradnik dydaktyczny

Pierwsze kroki (5-7 min)

Rozgrzewka: Abbr In Ur Txt Msgs (5-7 min)

Discussion Goal

W ramach rozgrzewki przed podjęciem rozważań na temat kompresji tekstu nawiąż do sposobów, w jakie większość osób już dokonuje kompresji tekstu w swoim życiu, poprzez stosowanie skrótów i akronimów; większość z nich ma już w tym zakresie pewne doświadczenie dzięki sms-om.

Motywuj do wymyślania dlaczego ktoś mógłby chcieć dokonywać kompresji tekstu.

Podpowiedź:

  • "Gdy wysyłasz sms-a do kolegi, czy poprawnie literujesz każde słowo?"
    • Czy stosujesz skróty powszechnie stosowanych słów? Wymień ich jak najwięcej.
    • Napisz kilka przykładów rzeczy, które można zobaczyć w sms-ach, które nie są zapisane poprawnym językiem angielskim.

Daj uczniom chwilę, na ich napisanie i pokazanie sąsiadowi?

  • "Dlaczego posługujesz się takimi skrótami? Jaka płynie z tego korzyść?"
    • Możliwe odpowiedzi:
      • aby oszczędzać znaki/ uderzenia w klawisze
      • aby ukryć coś przed rodzicami/ nauczycielami
      • aby wydawać się fajnym, inteligentnym, zabawnym
      • aby "mówić kodem”
      • aby przekazać tę samą myśl zajmując mniej miejsca

O co tutaj chodzi? - Kompresja: te same dane, mniej bitów

  • Dzisiejsze zajęcia poświęcone są kompresji
  • Gdy tworzysz skróty lub używasz zakodowanego języka, aby skracać tekst oryginalny, dokonujesz "kompresji tekstu". Komputery też to robią, aby oszczędzać czas i miejsce.
  • Sztuka i wiedza dotycząca kompresji polega na wymyśleniu jak przedstawić TE SAME DANE przy pomocy MNIEJSZEJ ILOŚCI BITÓW.
  • Dlaczego to jest ważne? Jednym z powodów jest ograniczona ilość miejsca do przechowywania, a poza tym zawsze preferuje się użycie mniejszej ilości bitów, jeśli jest taka możliwość. Natomiast dużo bardziej przekonywującą przyczyną jest górna granica prędkości, z jaką bity mogą być przesyłane w Internecie.
  • A co jeśli musimy szybciej przesłać dużą ilość tekstu w Internecie, ale osiągnęliśmy fizyczny limit prędkości, z jaką możemy przesyłać bity? Mamy jedną jedyną opcję - znaleźć sposób, aby oddać te same informacje przy pomocy mniejszej ilości bitów: nazywamy to kompresją.

Przejście:

Spójrzmy na przykład wiadomości tekstowej, która została w inteligentny sposób skompresowana.

Aktywność (45 min)

Odkoduj ten "Sekretny tekst" (10-15 min)

  • Rozdaj lub pokaż "Przewodnik po zajęciach: Dekoduj tę wiadomość - Przewodnik po zajęciach
  • Połącz uczniów w parę z partnerem lub niech pracują samodzielnie.
  • Zadanie: Jak wyglądał tekst oryginału?
  • Daj uczniom parę minut na odkodowanie tekstu. Tekstem powinien być krótki wierszyk (zobacz podsumowanie zajęć poniżej)
{Przewodnik po zajęciach dla ucznia) Podsumowanie zajęć
Rozdaj lub pokaż "Przewodnik po zajęciach": decode-this-message (Pokaż lub sam narysuj) Podsumowanie zajęć: activity-recap-decode-this-message
Dekoduj tę wiadomość - Przewodnik po zajęciach Podsumowanie zajęć - Odszyfruj tę wiadomość - Podsumowanie zajęć

Podsumowanie: Ile z tego zostało skompresowane?

W celu udzielenia odpowiedzi musimy porównać liczbę znaków w tekście oryginału wiersza do liczby znaków potrzebnych do przedstawienia skompresowanej wersji.

Podzielmy to na mniejsze części.

  • Pokaż albo Zademonstrujsamodzielnie pojęcia z: Podsumowanie zajęć - Odszyfruj tę wiadomość - Podsumowanie zajęć (pokazane w powyższej tabeli)

  • Ważna uwaga:

    • Skompresowany wiersz nie jest tylko tą częścią: Jeśli miałbyś to wysłać komuś w Internecie, ta osoba nie byłaby w stanie tego odkodować.
    • W pełni skompresowany tekst obejmuje ZARÓWNO skompresowany tekst i klucz do jego rozwiązania.
    • W związku z powyższym musisz znać łączną liczbę znaków w wiadomości plus łączną liczbę znaków w kluczu, aby zobaczyć, ile zostało skompresowane z porównaniu do oryginału.

Przejście

Teraz Wy wypróbujecie swoich sił w kompresowaniu pewnych rzeczy na własną rękę.

Użyj widgetu do kompresowania tekstu

Content Corner

W filmie wideo wyjaśniono pewne ogólne rzeczy dotyczące kompresji - różnicę pomiędzy kompresją bezstratną a kompresją stratną. Dzisiejsza lekcja poświęcona jest kompresji bezstratnej kompresją stratną zajmiemy się na jednych lub dwóch zajęciach, gdy poznamy już kodowanie obrazu.

Teaching Tip

Wybór nauczyciela czy pokazać film wideo całej klasie czy pozwolić uczniom obejrzeć do w "Studio kodowania". Każda opcja niesie ze sobą zarówno korzyści, jak i niedogodności.

Opcja do rozważenia: Zapoznaj uczniów z narzędziem kompresji tekstu PRZED pokazaniem filmu wideo. Możecie stwierdzić, że uczniowie łatwiej przyswajają sobie pewne informacje z filmu wideo, jeśli najpierw próbowali użyć narzędzia.

**Komunikacja i współpraca" W celu wypracowania komunikacji i współpracy pomiędzy uczniami, uwzględnij w zajęciach jeden z poniższych scenariusz:

  • Niech uczniowie, którym został przydzielony ten sam wiersz porównają wyniki albo posadź ich w tym samym obszarze pokoju.
  • Zrób małe, przyjazne zawody - nie dopuszczając przy tym do tego, aby w konkurencję wlała się "niezdrowa" konkurencja - w tym, która para jest w stanie skompresować wiersz w największym zakresie. Użyj wiersza, którego żaden uczeń jeszcze nie kompresował.
  • W przypadku każdego wiersza niech grupa, która to wymyśli będzie uznana/ grupy które to wymyślą będą uznane za najlepsze w klasie i zapisz to na tablicy lub gdzieś, gdzie ludzie będą mogli to zobaczyć.
    • Niech cel klasy w zakresie uzyskania jak największej procentowej kompresji czterech wierszy będzie najwyższy z możliwych.
    • Grupy, które uzyskają największą kompresję w ujęciu procentowym, mogą zostać poproszone o udostępnienie swojej strategii klasie.

Uczniowie mogą być niechętni udostępnianiu jeśli będą mieli poczucie, że nie uzyskali najlepszych wyników, ale powinni zobaczyć pracę innych i oferować rady i strategie.

Wideo: Kompresja tekstu z Aloe Blacc - Wideo

  • Film wideo wyjaśnia zagadnienie kompresji
  • Demonstruje użycie "Narzędzia kompresji tekstu".
  • UWAGA: To wideo pojawia się automatycznie, gdy uczniowie wchodzą na etap kompresji tekstu w "Studio kodowania".
  • Podziel uczniów na grupy liczące 2 osoby
  • Przydziel każdej parze jeden z podanych wierszy i daj im zadanie, jako parze, skompresowanie ich wiersza w największym możliwym stopniu.
  • Podaj lub zapisz proste instrukcje na tablicy tak, aby uczniowie mogli je śledzić.
    • Wyzwanie: Skompresujcie swój wiersz w największym możliwym stopniu.
    • Porównaj z innymi grupami, aby przekonać się, czy poszło im lepiej.
    • Spróbujcie wypracować strategię ogólną, która doprowadzi do dobrej kompresji.

  • Po jakimś czasie niech pary, które opracowywały ten sam wiersz, porównają swoje schematy. Ich zadaniem, jako grupy, było uzyskanie największego stopnia kompresji tego wiersza dla klasy.
  • Opcjonalnie: możesz wydać Text Compression (optional) - Activity Guide, w której również wyjaśnia się instrukcje i daje uczniom zadania. To może się dobrze sprawdzać jako zajęcia pozalekcyjne lub sprawdzian.

Podsumowanie (10 min)

Omów właściwości i wyzwania wiążące się z kompresją

Poproś grupy, aby zrobiły przerwę w celu omówienia pytań pod koniec ćwiczenia.

Podpowiedzi:

  • "Co sprawia, że kompresja jest trudna?"

    • Stymuluj odpowiedzi. Niektóre z tych kwestii powinny wypłynąć same: Możesz rozpocząć na wiele różnych sposobów. Wybory dokonane wcześniej wpływają na wybory dokonywane później. Gdy znajdziesz już zbiór wzorców, inne wyłaniają się same.
    • Pojawia się jednak punkt krytyczny: być może czynisz postępy w zakresie kompresji, ale w pewnym momencie szalka przechyli się na Twoją niekorzyść i słownik zacznie się tak rozrastać, że zanikną wynikające z tego korzyści. Wówczas możesz zacząć rozpatrywać słownik ponownie, aby wykręcić z niego niektóre bity.

  • "Czy wydaje nam się, że taki zakres kompresji, który znaleźliśmy, jest najlepszy? Czy jest sposób na to, aby się dowiedzieć, jaka kompresja jest najlepsza?"

    • Prawdopodobnie nie wiemy, co jest najlepsze.
    • Jest tyle możliwości, trudno to stwierdzić. Okazuje się, że jedynym sposobem na zagwarantowanie idealnej kompresji jest brutalna siła. Oznacz to wypróbowanie każdego możliwego zestawu zastąpień. Nawet w przypadku niewielkich tekstów będzie on zbyt długi. "Najlepszy" stanowi jedynie najlepszy, jak dotychczas odkryliśmy.

  • "Jest jednak proces, który osoba może przejść, aby znaleźć najlepszą (lub całkiem dobrą) kompresję na potrzeby fragmentu tekstu?"

    • Tak, ale to jest niedokładne - pozostaw to jako nierozstrzygniętą kwestię.

Wersja rozszerzona

Realny świat: Kompresja zip

  • Poeksperymentuj z zipem używając plików tekstowych o różnej treści. Czy wyniki w przypadku małych plików są równie dobre, jak w przypadku dużych plików? (na komputerach Macs, w programie Finder znajdź "uzyskaj informację" dla pliku, aby zobaczyć rzeczywistą liczbę bitów w pliku, ponieważ ekran w programie Finder pokaże 4KB w przypadku dowolnego pliku, który jest od tego mniejszy.)
    • Ostrzeżenie: wyniki mogą się różnić. Zip sprawdza się bardzo dobrze w przypadku tekstu, ale może nie kompresować zbyt dobrze innych plików, ponieważ są one już skompresowane albo nie mają wbudowanych wzorców tego samego rodzaju, jak dokumenty tekstowe.

Wyzwanie: Zbadaj algorytm LZW

  • podstawą kompresji .zip jest Metoda kompresji LZW

  • Wprawdzie pomysł leżący u podstaw narzędzia kompresji tekstu jest podobny do algorytmu LZW (zip), śledzenie ścieżki kompresji i dekompresji może stanowić pewne wyzwanie. Zdobywanie dalszej wiedzy na temat LZW oraz tego co dzieje się w toku tego algorytmu byłoby wspaniałym rozszerzeniem projektu dla pewnych osób.

Dostosowanie standardów

Zobacz pełne dostosowanie kursu

Standardy Informatyki CSTA dla K-12 (2011)

CL - Współpraca
  • CL.L2:3 - Współpracuj z rówieśnikami, specjalistami oraz innymi osobami stosującymi praktyki współpracy takie jak programowanie w parach, praca w zespołach projektowych i udział w zajęciach aktywnej nauki w grupie.
CPP - Praktyki komputacyjne i programowanie
  • CPP.L2:4 - Wykazuj zrozumienie dla algorytmów i ich praktycznego zastosowania.
CT - Myślenie komputacyjne
  • CT.L2:9 - Wchodź w interakcje z modelami i symulacjami dla konkretnych treści (np. ekosystemów, epidemii, dynamiki molekularnej), aby wspierać naukę i badania.
  • CT.L3B:8 - Użyj modeli i symulacji, aby pomóc w sformułowaniu, doskonaleniu i badaniu hipotez naukowych.
  • CT.L3B:9 - Analizuj dane i identyfikuj wzorce przez modelowanie i symulację.

Zasady informatyki

2.1 - A variety of abstractions built upon binary sequences can be used to represent all digital data.
2.1.1 - Opisz szereg abstrakcji używanych do przedstawiania danych. [P3]
  • 2.1.1A - Dane cyfrowe są reprezentowane przez wyodrębnione na różnych poziomach elementy.
  • 2.1.1B - Na poziomie niższym, dane cyfrowe są reprezentowane przez bity.
  • 2.1.1C - Na wyższym poziomie są grupowane, aby reprezentować wyodrębnione mniejsze elementy, między innymi, liczby, znaki i kolor.
2.2 - Multiple levels of abstraction are used to write programs or create other computational artifacts
2.2.1 - Przy pisaniu programu lub tworzeniu innych rekwizytów komputacyjnych rozwijaj wymiar abstrakcyjny. [P2]
  • 2.2.1B - Wyodrębnianie (abstrahowanie) prowadzi do wyłonienia wspólnych cech z konkretnych przykładów w celu generalizacji pojęć.
3.1 - People use computer programs to process information to gain insight and knowledge.
3.1.1 - Używaj komputerów do przetwarzania informacji, wynajduj wzorce i testuj hipotezy na temat informacji przetwarzanych cyfrowo, aby uzyskać wgląd i wiedzę. [P4]
  • 3.1.1A - Komputerów używa się w sposób iteratywny i interaktywny przy przetwarzaniu informacji cyfrowych, aby uzyskać wgląd i wiedzę.
  • 3.1.1D - Wgląd i wiedzę można uzyskać przekładając i przekształcając cyfrowo przedstawione informacje.
  • 3.1.1E - Przy przekształcaniu danych z użyciem narzędzi informatycznych mogą się wyłonić wzorce.
3.1.2 - Współpracuj przy przetwarzaniu informacji, aby uzyskać wgląd i wiedzę. [P6]
  • 3.1.2A - Współpraca stanowi ważny element rozwiązywania zadań kształtowanych przez dane.
  • 3.1.2B - Współpraca ułatwia rozwiązywanie zadań informatycznych dzięki stosowaniu różnych perspektyw, doświadczeń i zestawów umiejętności.
  • 3.1.2C - Komunikacja pomiędzy uczestnikami pracującymi nad rozwiązaniem zadań kształtowanych przez dane prowadzi do postania lepszego, dogłębnego rozeznania i wiedzy.
  • 3.1.2D - Współpraca w zakresie opracowywania hipotez i pytań oraz w zakresie testowania hipotez i udzielania odpowiedzi na pytania, na temat danych pomaga uczestnikom w uzyskaniu rozeznania i wiedzy.
3.1.3 - Wyjaśnij wgląd i wiedzę uzyskaną z danych przetwarzanych cyfrowo używając odpowiednich wizualizacji, notatek oraz precyzyjnego języka. [P]
  • 3.1.3A - Narzędzia do wizualizacji oraz oprogramowanie są w stanie przekazywać informacje na temat danych.
  • 3.1.3E - Interaktywność przy pomocy danych stanowi aspekt komunikacji.
3.3 - There are trade offs when representing information as digital data.
3.3.1 - Analizuj, w jaki sposób przedstawienie danych, przechowywanie, ochrona i transmisja danych łączy się z manipulacją komputacyjną informacjami. [P4]
  • 3.3.1A - Przedstawienia danych cyfrowych obejmują kompromisy dotyczące obaw związanych z przechowywaniem, bezpieczeństwem i prywatnością.