係り受け解析して可視化するくんを作った

詳細はGithubのREADME.mdを見て頂ければと思いますが、標準入力で入力した文章を係り受け解析し、有向グラフとして可視化するくんを作りました。

fishの練習がてら言語処理100本ノック 2015でやった内容を使いまわしました。結果は以下のようになります。 （bashもあります）

f:id:cipepser:20170527215111p:plain

処理の流れ

  1. 標準入力をCabochaに渡し、係り受け解析をする
  2. 上記の結果をGolangでDOT言語フォーマットに変換
  3. 上記をGraphvizで可視化

感想

辞書にないような言葉（文章的な作品名など）だとうまくいかないですが、ちょっと遊ぶには楽しい感じです。これでbotとかにしてもいいかもですね。

GolangでHMAC-SHA256署名する

APIの認証でHMAC(Hash-based Message Authentication Code)を使用したいことがあります。 HMACはその名の通り、あるhash-basedなメッセージ認証符号で、メッセージと秘密鍵をもとに生成されます。 今回はハッシュ関数にSHA256を用いて、HMACしてみます。

実装

func MakeHMAC(msg, key string) string {
    mac := hmac.New(sha256.New, []byte(key))
    mac.Write([]byte(msg))
    return hex.EncodeToString(mac.Sum(nil))
}

References

GolangでMiller-Rabin素数判定法を実装してみる

背景

Wikipedia にも記載されていますが、 Miller-Rabin素数判定法は 与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種で、乱択アルゴリズムです。
フェルマーテストでは、以下のフェルマーの小定理を用いて 素数判定を行いますが、カーマイケル数と呼ばれる合成数を、誤って(素数と)判定してしまいます。 例えば、最小のカーマイケル数は561ですが、 561 = 3 \times 11 \times 17のため、素数ではありません。

フェルマーの小定理
p:素数
a:pと互いに素となる整数
に対して
a^{p-1} \equiv 1 \ mod \ p \tag{1}
が成り立つ。

フェルマーテストを改良したのがMiller-Rabin素数判定法です。 詳細はWikipediaを参照頂ければと思いますが、与えられた素数 pを奇素数(素数判定をしたいのは、大きい整数なので、奇素数を考えれば目的は十分に果たせます)と考え、 p-1 = 2^{s} \cdot d と表現します。ここで s は正整数で、 d は奇数です。すると式(1)は以下のように書けます。

a^{2^{s}d} \equiv 1 \ mod \ p \tag{2}

pが素数であれば、式(2)を満たします。左辺を \bigl( a^{d \cdot 2^{s-1}} \bigr)^{2}とみて、式(2)について単位元の平方根を考えます。
非自明な平方根は存在しない(証明もWikipediaにあります)ので以下の2式のみを考えればよいことになります。

a^{d} \equiv 1 \ mod \ p \tag{3}

a^{2^{r}d} \equiv -1 \ mod \ p \tag{4}

ここで、 0 \leq r \leq s - 1です。 上記は、自明な平方根 1または -1となった場合を考えて、 1となった場合は、さらに繰り返し(平方根が -1となるまで)平方根を考えていった結果を表しています。式(3)は -1にならず、平方根が取れなくなるまで取ったあとの結果になります。
あとはフェルマーテストと同様に考えて、与えられた数が素数でない(合成数である)のであれば、式(3)および式(4)を満たさないとして、素数判定を行います。 フェルマーテストと同様に偽陽性(素数と判定したのに実は合成数だった)の可能性は残りますが、フェルマーテストより確率は低いようです。

実装

gist1cd38a67c96df7966b9c468927dc2757

結果

今回は以下の4パターンを判定してみました。

結果は以下の通り、いずれも正しく判定できています。

$ go run MillerRabinPrimalityTest.go
------------Prime-------------
2 :  true
3 :  true
5 :  true
7 :  true
11 :  true
13 :  true
17 :  true
19 :  true
23 :  true
29 :  true
31 :  true
37 :  true
41 :  true
43 :  true
47 :  true
53 :  true
59 :  true
61 :  true
67 :  true
71 :  true
73 :  true
79 :  true
83 :  true
89 :  true
97 :  true
------------Composite-------------
9 :  false
15 :  false
21 :  false
25 :  false
27 :  false
33 :  false
35 :  false
39 :  false
45 :  false
49 :  false
51 :  false
55 :  false
57 :  false
63 :  false
65 :  false
69 :  false
75 :  false
77 :  false
81 :  false
85 :  false
87 :  false
91 :  false
93 :  false
95 :  false
99 :  false
16329805957987392833 :  false
75367631466941141791247084978233913478587466161271622771710895906453753967164967411257954571043148038883968051384064219878882200013408641715083492640764339527637873502061727098279950196988248939994544197535642414553039637030217247486372549770605212095298947963579455290328750806815560590656493190626063424483777638146122548073605596393468295558919015322872295712049815793564477203891171966598995001945926910413702372501638140065699147590309176011776418089018393636130620122226631715476290375904684033 :  true

今回は aをランダムに選ぶ回数kをk=20としましたが、精度を上げるにはこの値を増やすことが有効です。逆にk=1などとしてみると以下のように結構間違えます。もちろん乱択アルゴリズムなので何度もやるとミスがあったりなかったりですが。

$ go run MillerRabinPrimalityTest.go
------------Prime-------------
2 :  true
3 :  true
5 :  true
7 :  true
11 :  true
13 :  true
17 :  true
19 :  true
23 :  true
29 :  true
31 :  true
37 :  true
41 :  true
43 :  true
47 :  true
53 :  true
59 :  true
61 :  true
67 :  true
71 :  true
73 :  true
79 :  true
83 :  true
89 :  true
97 :  true
------------Composite-------------
9 :  false
15 :  false
21 :  false
25 :  false
27 :  true
33 :  false
35 :  false
39 :  true
45 :  false
49 :  false
51 :  false
55 :  false
57 :  false
63 :  false
65 :  false
69 :  false
75 :  false
77 :  false
81 :  false
85 :  false
87 :  false
91 :  true
93 :  false
95 :  false
99 :  false
16329805957987392833 :  false
75367631466941141791247084978233913478587466161271622771710895906453753967164967411257954571043148038883968051384064219878882200013408641715083492640764339527637873502061727098279950196988248939994544197535642414553039637030217247486372549770605212095298947963579455290328750806815560590656493190626063424483777638146122548073605596393468295558919015322872295712049815793564477203891171966598995001945926910413702372501638140065699147590309176011776418089018393636130620122226631715476290375904684033 :  true

Reference

Atomでconfig.fishをハイライトさせる

zshからfishに移行している最中にconfig.fishがAtomでハイライトされていなかったのでさせました。 単純に拡張子とscope nameを対応させるだけですが、fishを検索ワードにしてると意外と引っかからなかったのでメモ書きとしてまとめておきます。

事前準備(file-typesのインストール)

Atomを開き、cmd + ,でPreferenceを開きます。 Installからfile-typesパッケージを検索し、インストールします。

config.csonの編集

以下のように設定します。 恐らく$HOME/.atom/config.csonにあるかと思います。

"*":
  "file-types":
    fish: "source.shell"

上記編集後、保存すれば設定が反映されます。

Reference

GolangでCuckoo Hashingを実装してみた

2017/5/27 修正
int64型であるkeyを[]byte型へconvertする際にhasher.Write([]byte(string(key)))ではうまくいかないため以下のように修正しました。

b := make([]byte, 8)
binary.LittleEndian.PutUint64(b, uint64(key))

hasher.Write(b)

背景

BloomFilterを実装した後に、やろうやろうと思っていたCuckoo Hashingを実装してみました。
Cuckoo Hashing自体の説明は @_krzさんの記事がわかりやすいです。絵を交えられているのでイメージもつきやすいです。
メリットとしてはlookupが定数時間(2回比較するだけ)で完了することが挙げられます。
またアルゴリズム自体がわかりやすいです。2つのテーブルを用意しておき、挿入したいkeyのハッシュ値を計算し、ハッシュ値をindexとみて、テーブルが空いていれば挿入。すでに埋まっていれば、keyと既に入っていた値を交換して、もう一つのテーブルで同様の操作を繰り返すという流れになっています。カッコーの托卵のようですね。

デメリットは、ハッシュの衝突が起こった場合やループが無限ループに入る恐れがあります。今回の実装でもMAXLOOPを設定することで無限ループを防いでいます。 また、こちらによるとテーブルの半分が埋まった段階で性能が落ちてしまうそうです。

実装

gistaaf77c63f3668efdd44e2f4ae9642f76

今回は0を空とする実装にしましたが、実際には0を挿入したい場合も多いと思うので、その場合はうまくゼロ値を使うなどするのがよいと思います。

References

Golangで有向グラフをかく

背景

言語処理100本ノック 2015をやっている最中に、有向グラフで表示する問題(Q44)に遭遇しました。 gographvizでDOT言語のdotファイルを作成し、graphvizで可視化したのでまとめます。

動作環境

# sw_vers
ProductName:    Mac OS X
ProductVersion: 10.11.6
BuildVersion:   15G31

# go version
go version go1.8 darwin/amd64

# dot -V
dot - graphviz version 2.40.1 (20161225.0304)

インストール

graphvizのインストール

# brew install graphviz

gographviz packageのインストール

# go get github.com/awalterschulze/gographviz

有向グラフの作成

設定値などはGraphvizとdot言語でグラフを描く方法のまとめを参考にさせて頂きました。

gist4c915c1e14aae064a92cc30fbcb5eac7

dotファイル上で、Attributionにダブルクオーテーションが必要な場合は、エスケープしないとsyntaxエラーになるので注意してください。
また、今回のように事前のテストができる場合は問題ないですが、Attrを動的に設定するような場合は、以下のようにエラーチェックをしたほうがよいでしょう。

// 例) colorschemeを設定する場合
if _, err := gographviz.NewAttr("colorscheme"); err != nil {
    panic(err)
}
nodeAttrs["colorscheme"] = "rdylgn11" // 問題ないことを確認してからmapに格納する

出力のdotファイルは以下のようになります。

gistc0bdfb47ec6948b6bed5cd51ad92f05c

有向グラフの出力

噂のGraphvizを使ってみるにもありますが、上記で出力したdotファイルをもとに、pngファイルとして結果を出力させるには以下のようにします。

# dot -T png diGraph.dot -o diGraph.png

結果です。いい感じですね。

f:id:cipepser:20170422201356p:plain

Reference

Golangで言語処理100本ノック2015 第4章: 形態素解析

言語処理100本ノック 2015の第4章: 形態素解析の10問です。

前処理

mecabの処理は先に済ませておきます。

# mecab neko.txt -o neko.txt.mecab

30. 形態素解析結果の読み込み

形態素解析結果（neko.txt.mecab）を読み込むプログラムを実装せよ．ただし，各形態素は表層形（surface），基本形（base），品詞（pos），品詞細分類1（pos1）をキーとするマッピング型に格納し，1文を形態素（マッピング型）のリストとして表現せよ．第4章の残りの問題では，ここで作ったプログラムを活用せよ．

gistc6be3f30935d9f1032cb8dd29b3a6f8e

# go run q30.go
[map[base:　 pos:記号 pos1:空白 surface:　] map[pos:名詞 pos1:代名詞 surface:吾輩 base:吾輩] map[pos1:係助詞 surface:は base:は pos:助詞] map[base:猫 pos:名詞 pos1:一般 surface:猫] map[pos:助動詞 pos1:* surface:で base:だ] map[pos1:* surface:ある base:ある pos:助動詞] map[surface:。 base:。 pos:記号 pos1:句点]]

mecabの結果は形態素ごとに一行で出力されるのでReadLine()で読み取っています。 例として「　吾輩は猫である。」を表示させています。

31. 動詞

動詞の表層形をすべて抽出せよ．

gist0230b9eddcac1d6541935856342866ba

# go run q31.go
[生れ つか し] [死な 得 られ]

Q30をそのまま利用すれば余裕です。結果が長くなるので最初と最後の3つだけ標準出力させました。

32. 動詞の原形

動詞の原形をすべて抽出せよ．

gist015db5a66878a77df992821b075ab8b5

# go run q32.go
[生れる つく する] [死ぬ 得る られる]

Q31とほぼ同じです。

33. サ変名詞

サ変接続の名詞をすべて抽出せよ．

gistc2c9fe26605d803583db6ee4b26f6f00

# go run q33.go
[見当 記憶 話] [抵抗 見当 判然]

こちらもQ31とほぼ同じです。

34. 「AのB」

2つの名詞が「の」で連結されている名詞句を抽出せよ．

gist120cb467e3a271b9bfbd55af9ca1b868

$ go run q34.go
[彼の掌 掌の上 書生の顔] [水の中 座敷の上 不可思議の太平]

「の」が出てきた前後が名詞になるものを抜き出しています。 気をつけるのはindex out of rangeのruntime errorを出さないことでしょうか。

35. 名詞の連接

名詞の連接（連続して出現する名詞）を最長一致で抽出せよ．

gistf15b4cadbae765b94f4abf99b771ae39

# go run q35.go
[吾輩 猫 名前] [太平 太平 南無阿弥陀仏南無阿弥陀仏]

名詞が続く間はループ回しています。 標準出力させながらコード書いてましたが、意外なもの(非自立や接尾の名詞)が出力され、間違っているのでは？と微妙にハマりました。そもそも国語力というか日本語の弱さが問題です。。。

36. 単語の出現頻度

文章中に出現する単語とその出現頻度を求め，出現頻度の高い順に並べよ．

gistc5f254f78da7fd7774c6513726607a71

# go run q36.go
の 9194
。 7486
て 6848
、 6772
は 6420
に 6243
を 6071
だ 5975
と 5508
が 5337

mapは順序を保存してくれないので、擬似的なTreeMapとしてsortedMap型を用意しました。ほぼこちらを参考にしました。
上位10個を抜き出してみましたが、固有名詞がないですね。。。

37. 頻度上位10語

出現頻度が高い10語とその出現頻度をグラフ（例えば棒グラフなど）で表示せよ．

gist5f74bc0a182cfa616d5f270037ac4d17

実行結果

f:id:cipepser:20170325103521p:plain

gonum/plotが日本語サポートしていないのでX軸にどの単語だが、表示されないのが微妙ですね。。。出力しているのはQ36と同じですが。 棒グラフの書き方は以前記事にまとめました。

38. ヒストグラム

単語の出現頻度のヒストグラム（横軸に出現頻度，縦軸に出現頻度をとる単語の種類数を棒グラフで表したもの）を描け．

gistc2bdc1b97162a49e390991bd454d45c5

実行結果

f:id:cipepser:20170325125720p:plain

英語だとちゃんと軸名が表示されます笑 題意の単語が何を指しているのか戸惑って、問題文理解するのに時間掛かりました。。。

39. Zipfの法則

単語の出現頻度順位を横軸，その出現頻度を縦軸として，両対数グラフをプロットせよ．

gista037ce443bd2066f6061ce91a8167630

実行結果

f:id:cipepser:20170325172053p:plain

Q38を流用するとすぐですね。

感想

言語処理をやったことがなかったので、そもそもの用語を知らなくて戸惑うことが多かったです。このまま5章の係り受け解析も頑張ります。

いつも通りコードはGithubにも置いてあります。

Reference