Wonder Code

プログラミングとか、PCについてが多いかな

Pythonでハフマン符号化を実装してみた

何番煎じ?と言いたくなるぐらいPythonでやってみた例はたくさんあるけど 勉強に車輪の再発明をするのもよいと思いやってみる。

ハフマン符号 (Huffman encoding)

ハフマン符号はデータを圧縮するための方法の一つ。 HTTP/2とかPNGとかでもつかわれている有名な方法です。 出現の頻度が大きいデータは小さいビット数で表し、 頻度が小さいデータは大きいビット数で表すことでデータを圧縮します。

ハフマン符号 - Wikipedia

例としてAABCCDEEEという文字列をハフマン符号化してみます。

文字の出現回数を求める

まず、この文字列中の文字ごとの出現回数を求めます。

文字 回数
A 2
B 1
C 2
D 1
E 3

ハフマン木を作る

ハフマン木 (Huffman tree)を作ります。 ハフマン木は文字を葉(Node)として使い、 ハフマン木を作るために上で求めた各文字の出現回数を使います。

  1. 葉の中から出現した回数が一番少ないものと2 番目に少ないものを選ぶ。
  2. 1で選んだ2つを子として持つ新たな節点を作り、1で選んだ2つの文字の回数を足した値を格納する。
  3. これを最後の1つになるまで繰り返す。

この例では出現した回数が1番少ないのはBとDの1回です。 なので、BとDを選びます。

文字 回数
B 1
D 1

次に、この2つを子に持ち、2つの回数の合計を持つ、木を作ります。 こんな感じです。 f:id:k_yuya:20180717232703p:plain

表で表すと、BとDが合体したので下のようになります。

文字 回数
A 2
B+D 2
C 2
E 3

次は、また最初に戻り、上の表(BとDが合体した表)の中から出現した回数が、 一番少ないものと2 番目に少ないものを選びます。 しかし、今回は一番少ない回数である2回出現したものが3つある(B+D, C, A)ため、Aと(B+D)を選んでみます。

文字 回数
A 2
B+D 2

そして、この2つを子に持つ木を作ります。 (B+D)はさっき作った木を子として使います。 f:id:k_yuya:20180718224227p:plain これを最後まで繰り返して、ハフマン木を作っていきます。

ハフマン木が完成したら左側の節点には0を、右側の節点には1を割り当てます。 すると、各文字が下の表のように表せます。これが各文字の圧縮結果になります。

文字 圧縮結果 圧縮後のサイズ
A 01 2ビット
B 101 3ビット
C 00 2ビット
D 100 3ビット
E 11 2ビット

このように出現頻度の大きいデータほどは少ないビット数で表すことができます。(今回はデータの種類が少なかったので、わかりにくかったですが・・・)

最後にHuffman符号化のPythonのコードです。

class Huffman:
    def __init__(self):
        self.tree = None
        self.pattern = None
        self.encode_dict = {}
        self.decode_dict = {}

    def encode(self, data):
        unique_data = set(data)
        nodes = []

        for v in unique_data:
            node_obj = Node(value=v, count=data.count(v))
            nodes.append(node_obj)
        temp = []
        while len(nodes) >= 2:
            for v in range(2):
                elem = min(nodes, key=lambda x: x.count)
                temp.append(elem)
                nodes.remove(elem)
            n = Node(value=None, count=temp[0].count+temp[1].count, left=temp[0], right=temp[1])
            temp = []
            nodes.append(n)
        self.tree = nodes[0]
        self.recursive_code(self.tree, "")
        s = ""
        for v in data:
            s += self.encode_dict[v]
        return s

    def recursive_code(self, node, s): #圧縮結果を取得する
        if not isinstance(node, Node):
            return
        if node.value:
            self.encode_dict[node.value] = s
            self.decode_dict[s] = node.value
            return
        self.recursive_code(node.right, s+"1")
        self.recursive_code(node.left, s+"0")
    def decode(self, data):
        assert(self.decode_dict)
        result = ""
        s = ""
        for bit in data:
            s += bit
            if s in self.decode_dict:
                result += self.decode_dict[s]
                s = ""
        return result


class Node: #葉を表すクラス
    def __init__(self, value=None, count=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
        self.count = count

h = Huffman()
x = h.encode("AABCCDEEE")
print(x, len(x))
d = h.decode(x)
print("decoded:", d)

ECMAScript Module (ESM)がimportしようとしたらハマった

久々にブログ書く

下のようなコードをECMAScript Module(ES Module、ESMともいう)をimportしようとしたらハマってしまったので書いておく。

//hello.mjs
function hello() {
    console.log("Hello");
}

export { hello }
<!DOCTYPE html>

<!-- hello.html -->

<html lang="ja">
    <head>
        <meta charset="utf-8">
        <script type="module">
            import { hello } from './hello.mjs'
        </script>
    </head>
    <body>
    </body>
</html>

TL;DR

うまくインポートできなかった原因

  1. ローカルから(Webサーバなしで)Moduleを読み込もうとしてた
  2. .mjs(Moduleの拡張子)のMedia TypeがPythonのhttp.serverでサポートされてなかった

ハマった

hello.htmlをChromeで開くと

Access to Script at 'file:///C:/Users/username/Programming/jsworks/es_module/hello.mjs' from origin 'null' has been blocked by CORS policy: 
Invalid response. Origin 'null' is therefore not allowed access.

というエラー。 調べてみるとどうもAccess Originがnullになっているために読み込んでいないようでした。  同じオリジンからでないと読み込まないようなので pythonを使ってWebサーバを立ち上げてAccess Originを同じlocalhost:8000にしてもう一度やってみました。

しかし、これが別のエラーの原因になろうとは、まだ知る由もなかった

気を取り直して、Webサーバー起動して、localhost:8000/hello.htmlを開いてみると また別のエラーが出ていました。

Failed to load module script: The server responded with a non-JavaScript MIME type of "application/octet-stream". 
Strict MIME type checking is enforced for module scripts per HTML spec.

これもググってみたら、どうもModuleのMIME Typeにはjavascriptという文字列が含まれていないといけないようなのですが、 Pythonのhttp.serverのMIME typeの一覧には、まだ.mjsがなく、その代わりにapplication/octet-streamを送ってしまうためエラーになるようです。 そこで一時的に.mjsを.jsに変更したらきちんと動きました。

ちなみに、http.serverのmimetypeの対応づけはmimetypesというPythonの標準ライブラリを使っているようで、 その中にまだ.mjsがないために発生するエラーのようです。(Python3.7.0時点) もうすでにpull reqは出ているようなので()3.8では直っていると思われます。

終わりに

こんな感じでハマってしまいましたが、JavaScriptには言語にモジュールの仕組みがなかったので(Node.jsのCJSなどもありますが、あれはNode.jsの仕様なのでカウントしない)もっと流行ってほしいです。

ネットで見かけた確率の問題に答える

https://story.hyuki.net/20161023173434/

数学ガールとかの著者の方がtwitterでつぶやいてた問題。 面白そう。少し考えてみる (あってるかどうかは不明)

表に1と書いてあり、裏に2と書いてあるコインが一枚ある。このコインを二回投げて、出た数二つを合計する。合計が偶数か奇数か、どちらに掛けたほうが当たるだろうか。
たかしくんはこう考えた。一回投げて出るのは偶数か奇数のどちらかだ。二回投げたときには「両方とも偶数」か「両方とも奇数」か「偶数と奇数」かの三種類になる。このうち合計が奇数になるのは「偶数と奇数」の一種類しかない。だから、合計が偶数になる方に掛けたほうが当たる。
たかしくんの考えをどう思う?
ただし、コインには偏りがないとする。


偶数と奇数のどちらの方の合計になる確率が高いかっていう問題だとおもう。

表で考えると出てくる通りは下で全部。 偶数が2通り(2, 4) 奇数も2通り(3,3)、

1回目2回目合計
112
123
213
224

つまり、どちらに掛けても変わらない。

結果: どっちも一緒

で多分・・合ってるとおもう

間違ってたらコメントで教えてくれ〜〜〜〜

orelangをPythonで実装してみた

http://qiita.com/shuetsu@github/items/ac21e597265d6bb906dc

いろんな人がいろんな言語で実装してた。 Python版が載ってなかったので参戦。

一応、引き算にも対応した。

class Engine:
    def __init__(self):
        self.operators = {}
        self.variables = {}
        
        self.operators["+"] = AddOperator()
        self.operators["-"] = SubOperator()
        self.operators["*"] = MultiplyOperator()
        self.operators["="] = EqualOperator()
        self.operators["set"] = SetOperator()
        self.operators["get"] = GetOperator()
        self.operators["until"] = UntilOperator()
        self.operators["step"] = StepOperator()

    def eval(self, script):
        return self._get_expression(script).eval(self)
    
    def _get_expression(self, script):
        if isinstance(script, list):
            script_list = script
            return CallOperator(self.operators[script_list[0]], script_list[1:])
        else:
            return ImmediateValue(script)


class CallOperator:
    def __init__(self, operator, args):
        self.operator = operator
        self.args = args
    
    def eval(self, engine):
        return self.operator.call(engine, self.args)


class ImmediateValue:
    def __init__(self, value):
        self.value = value
        
    def eval(self, engine):
        return self.value


class SubOperator:
    def call(self, engine, args):
        retval = engine.eval(args[0])
        for arg in args[1:]:
            v = engine.eval(arg)
            retval -= v
        return retval
        

class AddOperator:
    def call(self, engine, args):
        retval = 0
        for arg in args:
            v = engine.eval(arg)
            retval += v
        return retval


class MultiplyOperator:
    def call(self, engine, args):
        retval = 1
        for arg in args:
            v = engine.eval(arg)
            retval *= v
        return retval


class EqualOperator:
    def call(self, engine, args):
        return engine.eval(args[0]) == engine.eval(args[1])
    
    
class SetOperator:
    def call(self, engine, args):
        value = engine.eval(args[1])
        engine.variables[str(engine.eval(args[0]))] = value
        return value
    
    
class GetOperator:
    def call(self, engine, args):
        return engine.variables[engine.eval(args[0])]
    

class UntilOperator:
    def call(self, engine, args):
        retval = None
        while not engine.eval(args[0]):
            retval = engine.eval(args[1])
        return retval
    
    
class StepOperator:
    def call(self, engine, args):
        retval = None
        for arg in args:
            retval = engine.eval(arg)
        return retval

言語を作るのは、どうやるのか想像がしにくかったので面白かった

Stack Overflowの通知アプリをWebExtensionsでやろうとしたらできなかった

Stack Overflowの通知アプリをWebExtensionsで作ろうとしたらAPIがなくてできなかった

自分の質問に回答がついたとか、誰かがコメントしたとか、そういうのがトゥルテンって通知センターとかに出るようにしたいと思ってトライした。

inboxの内容をとるAPIはあるけど、1度通知されたinboxの内容の状態を既読にするAPIがなかった。 だから、inboxの内容が何回も通知される

トゥルテン、トゥルテン、トゥルテン、トゥルテンと延々となり続けるというなんともうざいアプリができた。

KiYugadgeter/StackNoisyOverflow: Stack Overflow Notification WebExtensions (WIP)

トゥルテン・・・

DOMParserが便利すぎる

なんかDOMParserというのを見つけた

標準であるやつで、HTMLとかXMLとかSVGとかの文字列をParseしてDOMにしてくれるらしい。 返ってくるのはDOMなのでgetElementByIdとかが使えるようだ

var parser = new DOMParser();
var dom = parser.parseFromString(xml_string, "application/xml");
dom.getElementsByTagName("TagName");

という風にできる。

これはすごく、すごく便利である。

今まで頑張って正規表現使ってやっていたがもうそんなことをしなくていいのは良い

DOMParser - Web API インターフェイス | MDN

kiloを読む

kiloという1000行ほど(コメント除く)のテキストエディタがあるらしい。 私はコードを読むのがとても苦手なので読んでみようと思う

こんな記事もあるので今回はなんとなく理解できそうな希ガス

C言語1000行以下のエディタ「Kilo」を理解する (1) シンプルな内部構造 | マイナビニュース

あと、今日は暑すぎる。もう9月終わるのに.