Pythonでハフマン符号化を実装してみた
何番煎じ?と言いたくなるぐらいPythonでやってみた例はたくさんあるけど 勉強に車輪の再発明をするのもよいと思いやってみる。
ハフマン符号 (Huffman encoding)
ハフマン符号はデータを圧縮するための方法の一つ。 HTTP/2とかPNGとかでもつかわれている有名な方法です。 出現の頻度が大きいデータは小さいビット数で表し、 頻度が小さいデータは大きいビット数で表すことでデータを圧縮します。
例としてAABCCDEEE
という文字列をハフマン符号化してみます。
文字の出現回数を求める
まず、この文字列中の文字ごとの出現回数を求めます。
文字 | 回数 |
---|---|
A | 2 |
B | 1 |
C | 2 |
D | 1 |
E | 3 |
ハフマン木を作る
ハフマン木 (Huffman tree)を作ります。 ハフマン木は文字を葉(Node)として使い、 ハフマン木を作るために上で求めた各文字の出現回数を使います。
- 葉の中から出現した回数が一番少ないものと2 番目に少ないものを選ぶ。
- 1で選んだ2つを子として持つ新たな節点を作り、1で選んだ2つの文字の回数を足した値を格納する。
- これを最後の1つになるまで繰り返す。
この例では出現した回数が1番少ないのはBとDの1回です。 なので、BとDを選びます。
文字 | 回数 |
---|---|
B | 1 |
D | 1 |
次に、この2つを子に持ち、2つの回数の合計を持つ、木を作ります。 こんな感じです。
表で表すと、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)はさっき作った木を子として使います。 これを最後まで繰り返して、ハフマン木を作っていきます。
ハフマン木が完成したら左側の節点には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
うまくインポートできなかった原因
ハマった
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回目 | 合計 |
---|---|---|
1 | 1 | 2 |
1 | 2 | 3 |
2 | 1 | 3 |
2 | 2 | 4 |
つまり、どちらに掛けても変わらない。
結果: どっちも一緒
で多分・・合ってるとおもう
間違ってたらコメントで教えてくれ〜〜〜〜
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");
という風にできる。
これはすごく、すごく便利である。
今まで頑張って正規表現使ってやっていたがもうそんなことをしなくていいのは良い
kiloを読む
kiloという1000行ほど(コメント除く)のテキストエディタがあるらしい。 私はコードを読むのがとても苦手なので読んでみようと思う
こんな記事もあるので今回はなんとなく理解できそうな希ガス
C言語1000行以下のエディタ「Kilo」を理解する (1) シンプルな内部構造 | マイナビニュース
あと、今日は暑すぎる。もう9月終わるのに.