Einführung

In der High School wurden die Richtlinien für Lernrichtlinien überarbeitet, und auch das Thema "Informationen" wurde erheblich geändert. Die größte Veränderung besteht darin, Programmieren von der High School zu lernen. In diesem Zusammenhang hat das Ministerium für Bildung, Kultur, Sport, Wissenschaft und Technologie kostenlos Unterrichtsmaterialien für die Lehrerausbildung veröffentlicht. In diesem Artikel möchte ich zusätzliche Informationen zum Programmieren schreiben, die in Zukunft an der High School gelernt werden sollen.

Verschiedene Artikel wurden bereits von unseren Ahneningenieuren verfasst. Bitte überprüfen Sie die unten stehenden Links. [Entschlüsselung des 2020 Next Learning Guidance-Kurses "Information"](https://qiita.com/woadachi/items/75cc334b10e22e4c5cad "Entschlüsselung des 2020 Next Learning Guidance-Kurses" Information ") Der Python des Bildungsministeriums ist kein Python [Vollzeitlehrer des Fachs "Information" und Zukunftstraum "Aktueller Status des IT-Ingenieurs / Programmierers"](https://qiita.com/woadachi/items/fdcb67bed4d496d5823e "Vollzeitlehrer des Fachs" Information "und zukünftiger Traum" IT-Ingenieur " ・ Aktueller Status von "Programmierer" ")

Lehrmaterial

[Lehrmaterial für die Lehrerinformation der High School "Information I" (Hauptteil): Ministerium für Bildung, Kultur, Sport, Wissenschaft und Technologie](https://www.mext.go.jp/a_menu/shotou/zyouhou/detail/1416756.htm "Informationsabteilung der High School Unterrichtsmaterialien "Information I" für die Lehrerausbildung (Hauptteil): Ministerium für Bildung, Kultur, Sport, Wissenschaft und Technologie ") Kapitel 2 Kommunikations- und Informationsdesign (PDF: 6892 KB) PDF

Umgebung

In der neuen Richtlinie fügt "Information I" hauptsächlich den Bereich der Programmierung hinzu, und "Information II" fügt hauptsächlich den Bereich der Datenwissenschaft hinzu. In Anbetracht dessen gibt es in Python viele Erklärungen nach Code, sodass in diesem Artikel auch Python verwendet wird. Darüber hinaus wird davon ausgegangen, dass Google Colab verwendet wird, mit dem sich eine Umgebung einfach erstellen lässt.

ipython
Colaboratory - Google Colab

Überblick

Dieses Mal werden wir "Information I" für Materialien zur Lehrerausbildung verwenden, "Kapitel 2 Kommunikation und Informationsdesign". In Übereinstimmung mit der impliziten Richtlinie von Information I werden wir beim Programmieren mit Python die Elemente überprüfen und ergänzen, die nicht in den Lehrmaterialien geschrieben sind. Insbesondere auf den Seiten 61-63 des Lehrmaterials "Kapitel 2 Kommunikations- und Informationsdesign".

(9) Dateikomprimierungs-Huffman-Methode

Wenn Sie den Ort überprüfen, sehen Sie die Erklärung des Huffman-Methodenalgorithmus, aber der ** wesentliche Programmiercode ** ist nicht aufgeführt. Also möchte ich Python-Code implementieren.

Andere Referenzen usw.

Huffman-Codierung mit Python3 Ich habe versucht, die Huffman-Codierung in Python zu implementieren [Huffman Code-Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6% E5% 8F% B7 "Huffman Code-Wikipedia")

Huffman-Methode (Zeichenkette: über Intelligenz)

Schritt 1

Kommentar

Ordnen Sie die Zeichen in der Reihenfolge ihres Auftretens an

Implementierung

Verwenden wir den Python-Wörterbuchtyp und ordnen Sie sie in der Reihenfolge der Anzahl der Vorkommen an.


from collections import Counter
target_string = 'intelligence'

print('{0}Überprüfen Sie die Anzahl der Vorkommen des Zeichens' .format(target_string))
list_target_string = list(target_string)
counter_target_string = Counter(target_string)
dict_target_string = dict(counter_target_string)
print(dict_target_string)

Ausgabeergebnis

Überprüfen Sie die Anzahl der Vorkommen des Intelligenzzeichens
{'i': 2, 'n': 2, 't': 1, 'e': 3, 'l': 2, 'g': 1, 'c': 1}

Schritt 2

Kommentar

Verbinden Sie zwei Zeichen mit der geringsten Anzahl von Auftritten und schreiben Sie die Gesamtzahl der Auftritte darauf. Da das ausgewählte Zeichen bereits zur Gesamtsumme hinzugefügt wurde, wählen Sie die beiden Zeichen mit der geringsten Anzahl von Erscheinungen aus der Summe der anderen 5 Zeichen und der Gesamtzahl der Erscheinungen des Zeichens ② aus, geben Sie die Gesamtsumme ein, und alle Zeichen werden nach demselben Verfahren verbunden. Fahren Sie fort, bis die Summe Intelligenz ist (12).

Implementierung

class Node:
    def __init__(self, key_char=None, count=None, left=None, right=None):
        self.key_char = key_char
        self.left = left
        self.right = right
        self.count = count

nodes = []

for k, v in dict_target_string.items():
    node_obj = Node(key_char = k, count = v)
    nodes.append(node_obj)

trial_count = 0
while len(nodes) >= 2:
    #Sortieren Sie die Knoten in absteigender Reihenfolge
    nodes = sorted(nodes, key=lambda x: x.count, reverse=True)

    #Anzahl der Zweigkreationen
    trial_count += 1

    #Extrahieren Sie die Knoten mit der geringsten Anzahl von Vorkommen
    left = nodes.pop()
    #Extrahieren Sie den Knoten mit der zweitkleinsten Anzahl von Vorkommen
    right = nodes.pop()

    #Fügen Sie die Anzahl der Vorkommen von links und rechts zu Knoten hinzu
    count = left.count + right.count
    append_node = Node(key_char = left.key_char + right.key_char, count = count, left = left, right = right)
    nodes.append(append_node)

    print("Anzahl der Durchsetzungsmaßnahmen:", trial_count)
    print(left.key_char, right.key_char,  count)
    print("---------------")

Ausgabeergebnis

Anzahl der Durchsetzungsmaßnahmen: 1
c g 2
---------------
Anzahl der Durchsetzungsmaßnahmen: 2
t cg 3
---------------
Anzahl der Durchsetzungsmaßnahmen: 3
l n 4
---------------
Anzahl der Durchsetzungsmaßnahmen: 4
i tcg 5
---------------
Anzahl der Durchsetzungsmaßnahmen: 5
e ln 7
---------------
Anzahl der Durchsetzungsmaßnahmen: 6
itcg eln 12
---------------

Schritt 3

Kommentar

Setzen Sie 0 links und 1 rechts von allen angeschlossenen Teilen. Nehmen Sie die Nullen und Einsen im gespleißten Teil von oben auf und weisen Sie jedem Zeichen die komprimierte Bitfolge zu.

Implementierung

#Holen Sie sich das Komprimierungsergebnis
def recursive_code(node, s, temp_encode_dict):
    if len(node.key_char) == 1:
        temp_encode_dict[node.key_char] = s
        return
    recursive_code(node.left, s + "0", temp_encode_dict)
    recursive_code(node.right, s + "1", temp_encode_dict)

encode_dict = {}
tree = nodes[0]
recursive_code(tree, "", encode_dict)
print(encode_dict)

Ausgabeergebnis

{'i': '00', 't': '010', 'c': '0110', 'g': '0111', 'e': '10', 'l': '110', 'n': '111'}

Kompressionsrate

Kommentar

Wenn "Intelligenz" durch eine komprimierte Bitfolge unter Verwendung des erstellten Huffman-Codes dargestellt wird, sind es 33 Bits. Wenn ein Zeichen von "Intelligenz" durch 3 Bits dargestellt wurde, waren es 36 Bits, was bedeutet, dass es auf etwa 92% komprimiert wurde.

Implementierung

print(target_string,'Vergleich der Kompressionsrate')
bitlength = len(str(bin(len(dict_target_string) - 1))) - 2
before_size = target_len * bitlength
print('Größe vor der Komprimierung')
print(target_len,'*',bitlength ,'=', before_size, 'bits')

encode_bits_string = ''
for v in list_target_string:
    encode_bits_string += encode_dict[v]
print('Bitfolge nach der Komprimierung')
print(encode_bits_string)
print('Größe nach Komprimierung')
print(len(encode_bits_string),'bits')

Ausgabeergebnis

Vergleich des Intelligenzkomprimierungsverhältnisses
Größe vor der Komprimierung
12 * 3 = 36 bits
Bitfolge nach der Komprimierung
001110101011011000011110111011010
Größe nach Komprimierung
33 bits

Vergleich / Korrektur der Umsetzungsergebnisse mit Lehrmaterialien

Die Erklärung der Unterrichtsmaterialien lautet wie folgt.

Vergleichen wir es mit dem hier implementierten Ausgabeergebnis.

Überprüfen Sie die Anzahl der Vorkommen des Intelligenzzeichens
{'i': 2, 'n': 2, 't': 1, 'e': 3, 'l': 2, 'g': 1, 'c': 1}

{'i': '00', 't': '010', 'c': '0110', 'g': '0111', 'e': '10', 'l': '110', 'n': '111'}

**···Das? ** **. ** Das Ausgabeergebnis ist unterschiedlich. ** **. Dies ergibt nicht die in den Lehrmaterialien gezeigten Ergebnisse, da die Methode zum Generieren von Zweigen und die Methode zum Zuweisen von Zweigen nach links und rechts nur durch Ignorieren der Implementierung erläutert werden. Die folgenden Punkte sollten beachtet werden.

Wenn Zeichen nach der Anzahl der Vorkommen angeordnet werden, müssen sie stabil angeordnet werden. --Wählen Sie zwei Elemente aus, die weniger häufig vorkommen, wählen Sie jedoch Elemente mit der gleichen Anzahl von Alphabeten so weit wie möglich aus. (Vorrang hat die gleiche Anzahl verketteter Zeichen im ersten Alphabet wie im zweiten) ――Bei der Angabe der linken und rechten Seite des Zweigs wird links diejenige mit der geringeren Anzahl verbundener Alphabete zugewiesen, diejenige, die nicht rechts zugeordnet ist, wird rechts zugewiesen, andernfalls wird die erste erfasste rechts und die zweite zugewiesen Der erworbene ist auf der linken Seite.

Implementieren Sie daher gemäß dieser Bedingung.

Schritt 2'

Implementierung


class Node:
    def __init__(self, key_char=None, count=None, left=None, right=None):
        self.key_char = key_char
        self.left = left
        self.right = right
        self.count = count

nodes = []
encode_dict = {}

for k, v in dict_target_string.items():
    node_obj = Node(key_char = k, count = v)
    nodes.append(node_obj)

trial_count = 0
while len(nodes) >= 2:
    #Sortieren Sie die Knoten in absteigender Reihenfolge
    nodes = sorted(nodes, key=lambda x: x.count, reverse=True)

    #Anzahl der Zweigkreationen
    trial_count += 1

    #Extrahieren Sie die Knoten mit der geringsten Anzahl von Vorkommen
    first = nodes.pop()
    #Extrahieren Sie den Knoten mit der zweitkleinsten Anzahl von Vorkommen
    second = nodes.pop()

    #temp_nodes
    temp_nodes = []

    #Stellen Sie fest, ob die erste und die zweite alphabetische Verknüpfung identisch sind
    if (len(first.key_char) != len(second.key_char)):
        print('Die Anzahl der Alphabetkombinationen für die erste und zweite ist unterschiedlich')

        #Wenn sich noch ein oder mehrere Knoten befinden, rufen Sie den dritten und die nachfolgenden Knoten ab
        while len(nodes) >= 1:
            overthird = nodes.pop()
            if (second.count == overthird.count):
                print('Die Anzahl der Vorkommen der zweiten und dritten Übereinstimmung')
                if (len(first.key_char) == len(overthird.key_char)):
                    print('Die Anzahl der alphabetischen Kombinationen der ersten und dritten Übereinstimmung')
                    nodes.append(second)
                    second = overthird
                    break
                else:
                  temp_nodes.append(overthird)
            else:
                nodes.append(overthird)
                break
    
    #Geben Sie zurück, was geknallt wurde
    nodes += temp_nodes

    #Fügen Sie die Anzahl der Vorkommen des ersten und zweiten Knotens hinzu
    count = first.count + second.count

    print("Anzahl der Durchsetzungsmaßnahmen:", trial_count)

    if len(first.key_char) < len(second.key_char): 
        append_node = Node(key_char = first.key_char + second.key_char, count = count, left = first, right = second)
    else:
        append_node = Node(key_char = second.key_char + first.key_char, count = count, left = second, right = first) 

    print(append_node.left.key_char, append_node.right.key_char,  count)

    nodes.insert(0, append_node)
    print("---------------")

~~ Es wurde ein verschwenderischer und überflüssiger Prozess. Um sofort Code zu ficken ~~

Ausgabeergebnis

Anzahl der Durchsetzungsmaßnahmen: 1
g c 2
---------------
Anzahl der Durchsetzungsmaßnahmen: 2
l t 3
---------------
Anzahl der Durchsetzungsmaßnahmen: 3
i n 4
---------------
Die Anzahl der Alphabetkombinationen für die erste und zweite ist unterschiedlich
Die Anzahl der Vorkommen der zweiten und dritten Übereinstimmung
Die Anzahl der alphabetischen Kombinationen der ersten und dritten Übereinstimmung
Anzahl der Durchsetzungsmaßnahmen: 4
lt gc 5
---------------
Die Anzahl der Alphabetkombinationen für die erste und zweite ist unterschiedlich
Anzahl der Durchsetzungsmaßnahmen: 5
e in 7
---------------
Die Anzahl der Alphabetkombinationen für die erste und zweite ist unterschiedlich
Anzahl der Durchsetzungsmaßnahmen: 6
ein ltgc 12
---------------

Korrekturergebnis

Ergebnis der erneuten Ausführung von Schritt 3

{'e': '00', 'i': '010', 'n': '011', 'l': '100', 't': '101', 'g': '110', 'c': '111'}

Es stimmte mit der Erklärung der Unterrichtsmaterialien überein. Übrigens, wenn Sie das Kompressionsverhältnis vergleichen,

Vergleich des Intelligenzkomprimierungsverhältnisses
Größe vor der Komprimierung
12 * 3 = 36 bits
Bitfolge nach der Komprimierung
010011101001001000101100001111100
Größe nach Komprimierung
33 bits

Quellcode

https://gist.github.com/ereyester/68ef4653890f0823e81e99dc00d73a07

[Informationen zu Richtlinien für das Lernen an Gymnasien I] Unterrichtsmaterialien für die Lehrerausbildung: Implementierung der Huffman-Methode durch Python

Einführung

Lehrmaterial

Umgebung

Überblick

Andere Referenzen usw.

Huffman-Methode (Zeichenkette: über Intelligenz)

Schritt 1

Kommentar

Implementierung

Ausgabeergebnis

Schritt 2

Kommentar

Implementierung

Ausgabeergebnis

Schritt 3

Kommentar

Implementierung

Ausgabeergebnis

Kompressionsrate

Kommentar

Implementierung

Ausgabeergebnis

Vergleich / Korrektur der Umsetzungsergebnisse mit Lehrmaterialien

Schritt 2'

Implementierung

Ausgabeergebnis

Korrekturergebnis

Quellcode