introduction

Au lycée, le programme d'études a été révisé et le sujet «Information» a également changé de manière significative. Le plus grand changement est d'apprendre la programmation à l'école secondaire. À cet égard, le ministère de l'Éducation, de la Culture, des Sports, de la Science et de la Technologie a publié gratuitement du matériel pédagogique pour la formation des enseignants. Dans cet article, j'aimerais écrire des informations supplémentaires liées à la programmation à apprendre au lycée dans le futur.

Divers articles ont déjà été écrits par nos ingénieurs ancêtres, veuillez donc consulter les liens ci-dessous. Informations sur le prochain cours d'orientation pédagogique 2020 Le Python du ministère de l'Éducation n'est pas Python [Enseignant à plein temps de la matière "Information" et rêve futur "Statut actuel de l'ingénieur / programmeur informatique"](https://qiita.com/woadachi/items/fdcb67bed4d496d5823e "Professeur à temps plein de la matière" Information "et rêve futur" Ingénieur informatique " ・ Statut actuel du "programmeur" ")

Matériel pédagogique

[Matériel pédagogique pour la formation des enseignants du Département de l’information du lycée "Information I" (partie principale): Ministère de l’éducation, de la culture, des sports, des sciences et de la technologie](https://www.mext.go.jp/a_menu/shotou/zyouhou/detail/1416756.htm "Département d’information du lycée Matériel pédagogique "Information I" pour la formation des enseignants (partie principale): Ministère de l'éducation, de la culture, des sports, des sciences et de la technologie ") Chapitre 2 Conception de la communication et de l'information (PDF: 6892 Ko) PDF

environnement

Dans la nouvelle directive, "Information I" ajoute principalement le domaine de la programmation, et "Information II" ajoute principalement le domaine de la science des données. Compte tenu de cela, il existe de nombreuses explications par code en python, donc cet article utilise également python. De plus, on suppose que Google Colab, qui facilite la création d'un environnement, est utilisé.

ipython
Colaboratory - Google Colab

Aperçu

Cette fois, nous nous concentrerons sur le «Chapitre 2 Communication et conception de l'information» du matériel de formation des enseignants «Information I». Conformément à la politique implicite d'Information I, lors de la programmation avec python, nous vérifierons et compléterons les éléments qui ne sont pas écrits dans le matériel pédagogique. Plus précisément, aux pages 61 à 63 du matériel pédagogique "Chapitre 2 Communication et conception de l'information"

(9) Méthode de compression de fichier-Huffman

Si vous vérifiez l'endroit, vous pouvez voir l'explication de l'algorithme de la méthode Huffman, mais le ** code de programmation essentiel ** n'est pas répertorié. Je voudrais donc implémenter du code python.

Autres références, etc.

Encodage Huffman avec Python3 J'ai essayé d'implémenter l'encodage Huffman en Python [Code Huffman-Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6% E5% 8F% B7 "Code Huffman-Wikipedia")

Méthode Huffman (chaîne de caractères: à propos de l'intelligence)

Étape 1

Commentaire

Disposer les personnages par ordre d'apparition

la mise en oeuvre

Utilisons le type de dictionnaire python et organisons-les par ordre du nombre d'occurrences.


from collections import Counter
target_string = 'intelligence'

print('{0}Vérifiez le nombre d'occurrences du personnage' .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)

Résultat de sortie

Vérifiez le nombre d'occurrences du caractère intelligent
{'i': 2, 'n': 2, 't': 1, 'e': 3, 'l': 2, 'g': 1, 'c': 1}

Étape 2

Commentaire

Connectez deux personnages avec le moins d'apparitions et écrivez-y le nombre total d'apparitions. Puisque le caractère sélectionné a déjà été ajouté au total, sélectionnez les deux caractères avec le moins d'apparitions parmi le total des 5 autres caractères et le nombre total d'apparitions du caractère ②, entrez le total, et tous les caractères sont reliés par la même procédure. Continuez jusqu'à ce que le total soit l'intelligence (12).

la mise en oeuvre

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:
    #Trier les nœuds par ordre décroissant
    nodes = sorted(nodes, key=lambda x: x.count, reverse=True)

    #Nombre de créations de succursales
    trial_count += 1

    #Extraire les nœuds avec le plus petit nombre d'occurrences
    left = nodes.pop()
    #Extraire le nœud avec le deuxième plus petit nombre d'occurrences
    right = nodes.pop()

    #Ajouter le nombre d'occurrences de gauche et de droite aux nœuds
    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("Nombre d'exécutions:", trial_count)
    print(left.key_char, right.key_char,  count)
    print("---------------")

Résultat de sortie

Nombre d'exécutions: 1
c g 2
---------------
Nombre d'exécutions: 2
t cg 3
---------------
Nombre d'exécutions: 3
l n 4
---------------
Nombre d'exécutions: 4
i tcg 5
---------------
Nombre d'exécutions: 5
e ln 7
---------------
Nombre d'exécutions: 6
itcg eln 12
---------------

Étape 3

Commentaire

Mettez 0 à gauche et 1 à droite de toutes les pièces connectées. Prenez les 0 et 1 dans la partie épissée par le haut et attribuez la chaîne de bits compressée à chaque caractère.

la mise en oeuvre

#Obtenez le résultat de la compression
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)

Résultat de sortie

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

Taux de compression

Commentaire

Si «intelligence» est représentée par une chaîne de bits compressée utilisant le code Huffman créé, ce sera 33 bits. Si un caractère de «intelligence» était représenté par 3 bits, il était de 36 bits, ce qui signifie qu'il a été compressé à environ 92%.

la mise en oeuvre

print(target_string,'Comparaison du taux de compression')
bitlength = len(str(bin(len(dict_target_string) - 1))) - 2
before_size = target_len * bitlength
print('Taille avant compression')
print(target_len,'*',bitlength ,'=', before_size, 'bits')

encode_bits_string = ''
for v in list_target_string:
    encode_bits_string += encode_dict[v]
print('Chaîne de bits après compression')
print(encode_bits_string)
print('Taille après compression')
print(len(encode_bits_string),'bits')

Résultat de sortie

comparaison du taux de compression de l'intelligence
Taille avant compression
12 * 3 = 36 bits
Chaîne de bits après compression
001110101011011000011110111011010
Taille après compression
33 bits

Comparaison / correction des résultats de mise en œuvre avec le matériel pédagogique

L'explication du matériel pédagogique est la suivante.

Comparons-le avec le résultat de sortie implémenté ici.

Vérifiez le nombre d'occurrences du caractère intelligent
{'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'}

**···cette? ** ** ** Le résultat de sortie est différent. ** ** Puisque la méthode de génération des branches et la méthode d'allocation des branches à gauche et à droite ne sont expliquées que pour la logique, en ignorant la mise en œuvre, cela ne donne pas le résultat selon le matériel pédagogique. Les points suivants doivent être notés.

--Lors de l'organisation des caractères par le nombre d'occurrences, il est nécessaire de les organiser de manière stable. --Sélectionnez deux éléments qui apparaissent moins fréquemment, mais sélectionnez les éléments qui ont le même nombre d'alphabets autant que possible. (La priorité est donnée au même nombre de caractères concaténés dans le premier alphabet que dans le second)

Quant à la manière de spécifier la gauche et la droite de la branche, celle avec le plus petit nombre d'alphabets connectés est attribuée à la gauche, celle qui n'est pas affectée à la droite est affectée à la droite, et sinon, celle acquise en premier est affectée à la droite et la seconde. Celui acquis est à gauche.

Par conséquent, mettez en œuvre selon cette condition.

Étape 2'

la mise en oeuvre


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:
    #Trier les nœuds par ordre décroissant
    nodes = sorted(nodes, key=lambda x: x.count, reverse=True)

    #Nombre de créations de succursales
    trial_count += 1

    #Extraire les nœuds avec le plus petit nombre d'occurrences
    first = nodes.pop()
    #Extraire le nœud avec le deuxième plus petit nombre d'occurrences
    second = nodes.pop()

    #temp_nodes
    temp_nodes = []

    #Déterminez si les première et deuxième jointures alphabétiques sont identiques
    if (len(first.key_char) != len(second.key_char)):
        print('Le nombre de combinaisons d'alphabet pour le premier et le second est différent')

        #Lorsqu'il y a encore un ou plusieurs nœuds, récupérez le troisième nœud et les suivants
        while len(nodes) >= 1:
            overthird = nodes.pop()
            if (second.count == overthird.count):
                print('Le nombre d'occurrences du deuxième et du troisième match')
                if (len(first.key_char) == len(overthird.key_char)):
                    print('Le nombre de combinaisons alphabétiques du premier et du troisième match')
                    nodes.append(second)
                    second = overthird
                    break
                else:
                  temp_nodes.append(overthird)
            else:
                nodes.append(overthird)
                break
    
    #Retourner ce qui a été sauté
    nodes += temp_nodes

    #Ajouter le nombre d'occurrences du premier et du second aux nœuds
    count = first.count + second.count

    print("Nombre d'exécutions:", 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("---------------")

~~ Il est devenu un traitement inutilement redondant. Pour putain de code à la fois ~~

Résultat de sortie

Nombre d'exécutions: 1
g c 2
---------------
Nombre d'exécutions: 2
l t 3
---------------
Nombre d'exécutions: 3
i n 4
---------------
Le nombre de combinaisons d'alphabet pour le premier et le second est différent
Le nombre d'occurrences du deuxième et du troisième match
Le nombre de combinaisons alphabétiques du premier et du troisième match
Nombre d'exécutions: 4
lt gc 5
---------------
Le nombre de combinaisons d'alphabet pour le premier et le second est différent
Nombre d'exécutions: 5
e in 7
---------------
Le nombre de combinaisons d'alphabet pour le premier et le second est différent
Nombre d'exécutions: 6
ein ltgc 12
---------------

Résultat de la correction

Résultat de la nouvelle exécution de l'étape 3

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

C'était en accord avec l'explication du matériel didactique. Au fait, si vous comparez le taux de compression,

comparaison du taux de compression de l'intelligence
Taille avant compression
12 * 3 = 36 bits
Chaîne de bits après compression
010011101001001000101100001111100
Taille après compression
33 bits

Code source

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

[Informations sur les lignes directrices d'apprentissage du lycée I] Matériel pédagogique pour la formation des enseignants: mise en œuvre de la méthode Huffman par python

introduction

Matériel pédagogique

environnement

Aperçu

Autres références, etc.

Méthode Huffman (chaîne de caractères: à propos de l'intelligence)

Étape 1

Commentaire

la mise en oeuvre

Résultat de sortie

Étape 2

Commentaire

la mise en oeuvre

Résultat de sortie

Étape 3

Commentaire

la mise en oeuvre

Résultat de sortie

Taux de compression

Commentaire

la mise en oeuvre

Résultat de sortie

Comparaison / correction des résultats de mise en œuvre avec le matériel pédagogique

Étape 2'

la mise en oeuvre

Résultat de sortie

Résultat de la correction

Code source