Golangでパーセントエンコーディング

Goには標準のurlパッケージにQueryEscape()関数が用意されているので、これを利用してパーセントエンコーディングができます。 しかし、単純にQueryEscape()を使うと、以下のように半角スペースが+と表示されてしまいます。

package main

import (
    "fmt"
    "net/url"
)

func main() {
    str := "パーセント エンコーディング"

    str = url.QueryEscape(str)

    fmt.Println(str)
    // %E3%83%91%E3%83%BC%E3%82%BB%E3%83%B3%E3%83%88+%E3%82%A8%E3%83%B3%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0

}

ASCIIコード表を見ると半角スペースには0x20が割り当てられているので、これを置換してあげればOKです。

package main

import (
    "fmt"
    "net/url"
    "regexp"
)

func main() {
    str := "パーセント エンコーディング"

    str = url.QueryEscape(str)
    str = regexp.MustCompile(`([^%])(\+)`).ReplaceAllString(str, "$1%20")

    fmt.Println(str)
    // %E3%83%91%E3%83%BC%E3%82%BB%E3%83%B3%E3%83%88%20%E3%82%A8%E3%83%B3%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0

}

References

パケットキャプチャを可視化する

パケットキャプチャを取得することは多いもののWiresharkでの解析ばかりなので、 Goで可視化してみることにしました。

実装

入力としてfile.pcapを受け取り、gopacketでキャプチャデータを解析しています。 可視化はGraphvizを用いました。

gistf0b03462dc06db3ce515c677b10b0d14

上記を実行するとdigraph.dotとしてDOTファイルが出力されるので、 これをGraphvizに渡せば完了です。

dot -T png ./digraph.dot -o ./digraph.png

結果

結果として2パターンをほど試してみました。 ホストPCの環境だと、絶えずいろいろな通信が発生しており、可視化するのが楽しいのです。しかし、アドレス逆引きされるとどのサービスを使っているのか一発でわかってしまうので例示は避けました

こちらはテスト用に適当なドメインpingしています。自ホストが10.0.2.15です。

f:id:cipepser:20170717232516p:plain

次の例では、ネットワーク初心者の新卒がDockerでネットワークの勉強をしてみたを参考に、検証環境を用意してみました。 OSPFの224.0.0.5があるので、動的に経路情報を渡している様子が見えますね。

f:id:cipepser:20170717232529p:plain

感想

自分で使ってみて思ったのは、変な通信がないか確認できるのがよいなということでした。同セグメントをグループ化するなどするともっと良さそうです。 フィルタやL4以上の情報(逆にL2も)も可視化できそうなので、これをもとにツール化したいところですが、future workということで。

References

Golangでローソク足チャートを描くパッケージを書いた

Golangでグラフを描くときには gonum plot が便利です。 これを使った例として、以前、棒グラフの記事も書きました。 その他の例としては、公式のwikiGo でグラフを plot するパッケージを試したが参考になります。
gonumのレポジトリを見ると 棒グラフや箱ひげ図、折れ線グラフなどが標準で実装されています。 (他にも関数などおもしろそうなものもあります)
ところがローソク足チャートは標準で実装されていないようです。 レポジトリのWikiを見ているとオリジナルのPoltterをカスタマイズするチュートリアルがあったので、 今回はローソク足チャートを実装してみました。

実装

実装はこちら。 gonumのPlotter定義にあるように Plot(draw.Canvas, *plot.Plot)を実装してあげる必要があります。
Plot(draw.Canvas, *plot.Plot)を実装した独自の型を、plot.New()で生成した*Plot型の変数に、Add()してあげれば、グラフが描けます。
今回はこのように実装しました。 流れは大まかに以下です。

  1. canvas(出力先画面)のサイズに応じた座標変換をplot.Transforms()で行う。
  2. ローソクの幅を決める
  3. データの最安値、最高値、始値終値をもとに箱とヒゲを描画する。

陽線と陰線は、始値終値から計算できるので、Plot()ではなく、 コンストラクタに委任し、各ローソクにColorフィールドとして持たせることにしました。
それ以外にも軸の表示とか、データをどうやってもたせるのがいいのかとか 実装する箇所は意外と細かく広範囲に渡るので詳しくは実装をご参照ください。

使い方

インストー

go get github.com/cipepser/plot

描画

実行例は以下です。 描画したいデータはdataに格納してください。

gist31d1820b58d1a4c7cf8d9d2e0013e515

結果

グラフは実行したディレクトリにimg.pngとして出力されます。

f:id:cipepser:20170709160604p:plain

References

Golangで長いステートメントを次の行へ継続する

文字列の結合をしていると以下のように長くなることがあります。 改行したくなります。

str := stmt1 + stmt2 + stmt3 + stmt4 + stmt5 + stmt6 + stmt7 + stmt8 + stmt9 + stmt10

少しググった限りだと文字列に改行が含まれ複数行になる場合の記事ばかりが見つかったので、備忘録として残しておきます。 複数行に渡る記述は以下のようにすればOKです。

str := stmt1 +
       stmt2 +
       stmt3 +
       stmt4 +
       stmt5 +
       stmt6 +
       stmt7 +
       stmt8 +
       stmt9 +
       stmt10

+を行頭にもってくるとコンパイルエラーになるので注意です。

Reference

Golangで言語処理100本ノック2015 第5章: 係り受け解析

言語処理100本ノック 2015の第5章: 係り受け解析の10問です。

前処理

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

# cabocha -f1 neko.txt -o neko.txt.cabocha

40. 係り受け解析結果の読み込み(形態素

形態素を表すクラスMorphを実装せよ.このクラスは表層形(surface),基本形(base),品詞(pos),品詞細分類1(pos1)をメンバ変数に持つこととする.さらに,CaboChaの解析結果(neko.txt.cabocha)を読み込み,各文をMorphオブジェクトのリストとして表現し,3文目の形態素列を表示せよ.

gista80e31cd3ff1e50d1b23de09cebe9133

# go run q40.go
[{名前 名前 名詞 一般} {は は 助詞 係助詞} {まだ まだ 副詞 助詞類接続} {無い 無い 形容詞 自立} {。 。 記号 句点}]

第4章の使い回して、形態素をclassとして用意して、格納する感じです。

41. 係り受け解析結果の読み込み(文節・係り受け

40に加えて,文節を表すクラスChunkを実装せよ.このクラスは形態素(Morphオブジェクト)のリスト(morphs),係り先文節インデックス番号(dst),係り元文節インデックス番号のリスト(srcs)をメンバ変数に持つこととする.さらに,入力テキストのCaboChaの解析結果を読み込み,1文をChunkオブジェクトのリストとして表現し,8文目の文節の文字列と係り先を表示せよ.第5章の残りの問題では,ここで作ったプログラムを活用せよ.

gistf3c8acd821ce16bf25ae0031b8224ffa

# go run q41.go
この ---> 書生 という の は
書生 という の は ---> 話 で ある 。
時々 ---> 捕え て
我々 を ---> 捕え て
捕え て ---> 煮 て
煮 て ---> 食う という
食う という ---> 話 で ある 。
話 で ある 。

dstsrcsが何を表しているのか掴むまで、しばらくCabochaの出力とにらめっこしました。 index out of rangeを避けるためにも、一文を格納してからsrcsを得る方式に変えました。

42. 係り元と係り先の文節の表示

係り元の文節と係り先の文節のテキストをタブ区切り形式ですべて抽出せよ.ただし,句読点などの記号は出力しないようにせよ.

gist36ba96af65a7eabb0ae0f4e290a1d117

# go run q42.go
吾輩は   猫である
名前は   無い
まだ  無い
どこで   生れたか
生れたか    つかぬ
とんと   つかぬ
見当が   つかぬ
何でも   薄暗い
薄暗い   所で
じめじめした  所で
所で  泣いて
ニャーニャー  泣いて
泣いて   記憶している
いた事だけは  記憶している
吾輩は   見た
ここで   始めて
始めて   人間という
人間という ものを
ものを   見た

(4文まで表示)

基本的にはQ41の出力を調整したのみです。

43. 名詞を含む文節が動詞を含む文節に係るものを抽出

名詞を含む文節が,動詞を含む文節に係るとき,これらをタブ区切り形式で抽出せよ.ただし,句読点などの記号は出力しないようにせよ.

gist4552848a0d983d80938af931546e5ff5

# go run q43.go
どこで   生れたか
見当が   つかぬ
所で  泣いて
ニャーニャー  泣いて
いた事だけは  記憶している
吾輩は   見た
ここで   始めて
ものを   見た

(4文まで表示)

Q42の出力条件をflgで検査しています。

44. 係り受け木の可視化

与えられた文の係り受け木を有向グラフとして可視化せよ.可視化には,係り受け木をDOT言語に変換し,Graphvizを用いるとよい.また,Pythonから有向グラフを直接的に可視化するには,pydotを使うとよい.

gist5a8a6d53415949ce6a47706e80b5f141

# go run q44.go
# dot -T png ../data/q44_diGraph.dot -o ../data/q44.png
# open ../data/q44.png

f:id:cipepser:20170422214431p:plain

例として10文目を表示させました。 Golangで有向グラフを書く方法については、以前記事にまとめました。

45. 動詞の格パターンの抽出

今回用いている文章をコーパスと見なし,日本語の述語が取りうる格を調査したい. 動詞を述語,動詞に係っている文節の助詞を格と考え,述語と格をタブ区切り形式で出力せよ. ただし,出力は以下の仕様を満たすようにせよ.

  • 動詞を含む文節において,最左の動詞の基本形を述語とする
  • 述語に係る助詞を格とする
  • 述語に係る助詞(文節)が複数あるときは,すべての助詞をスペース区切りで辞書順に並べる 「吾輩はここで始めて人間というものを見た」という例文(neko.txt.cabochaの8文目)を考える. この文は「始める」と「見る」の2つの動詞を含み,「始める」に係る文節は「ここで」,「見る」に係る文節は「吾輩は」と「ものを」と解析された場合は,次のような出力になるはずである.
始める  で
見る    は を

このプログラムの出力をファイルに保存し,以下の事項をUNIXコマンドを用いて確認せよ.

  • コーパス中で頻出する述語と格パターンの組み合わせ
  • 「する」「見る」「与える」という動詞の格パターン(コーパス中で出現頻度の高い順に並べよ)

gist8d36953a713c4ebed4998b88b1d66fa0

# go run q45.go
# cat ../data/q45.out.txt | sort | uniq -c | sort -nr | head -10
 565 云う と
 460 する を
 249 思う と
 204 ある が
 194 なる に
 178 する に
 173 見る て
 128 する と
 118 する が
  94 見る を

# cat ../data/q45.out.txt | awk '$1=="する"{print $0}' | sort | uniq -c | sort -nr | head -10
 460 する を
 178 する に
 128 する と
 118 する が
  93 する て を
  63 する は
  63 する て
  59 する を に
  56 する が を
  51 する から

# cat ../data/q45.out.txt | awk '$1=="見る"{print $0}' | sort | uniq -c | sort -nr | head -10
 173 見る て
  94 見る を
  21 見る て て
  20 見る から
  16 見る て を
  14 見る と
  12 見る で
  11 見る から て
  11 見る は て
   8 見る に

# cat ../data/q45.out.txt | awk '$1=="与える"{print $0}' | sort | uniq -c | sort -nr | head -10
   3 与える  に を
   1 与える  けれども に は を
   1 与える  じゃあ か と は て を
   1 与える  として を か
   1 与える  たり て に を
   1 与える  で だけ に を
   1 与える  に は に対して のみ は も
   1 与える  て が は は と て に を
   1 与える  は て に を に
   1 与える  は て に を

結果は例として上位10個を表示しています。 最初の助詞に対してはスペースを付与しないこと、動詞に係っている形態素がありつつも助詞を含まない場合を除く処理があることの2つのためコードが長くなってしまいました。

46. 動詞の格フレーム情報の抽出

45のプログラムを改変し,述語と格パターンに続けて項(述語に係っている文節そのもの)をタブ区切り形式で出力せよ.45の仕様に加えて,以下の仕様を満たすようにせよ.

  • 項は述語に係っている文節の単語列とする(末尾の助詞を取り除く必要はない)
  • 述語に係る文節が複数あるときは,助詞と同一の基準・順序でスペース区切りで並べる

「吾輩はここで始めて人間というものを見た」という例文(neko.txt.cabochaの8文目)を考える. この文は「始める」と「見る」の2つの動詞を含み,「始める」に係る文節は「ここで」,「見る」に係る文節は「吾輩は」と「ものを」と解析された場合は,次のような出力になるはずである.

始める  で      ここで
見る    は を   吾輩は ものを

gist57d3ba0bf021ed599905416f5bfe654d

# go run q46.go
# cat ../data/q46.out.txt | head -10
生れる   で どこで
つく  か が 生れたか 見当が
泣く  で 所で
する  て だけ は  泣いて いた事だけ いた事だけは
いる  て だけ は  泣いて いた事だけ いた事だけは
始める   で ここで
見る  は を 吾輩は ものを
聞く  で あとで
捕える   を 我々を
煮る  て 捕えて

実行結果は最初の10個のみを表示しています。 問題文中の例も含まれていますね。 実装については、Q45に対して、L.141-169を追加したのみです。

47. 機能動詞構文のマイニング

動詞のヲ格にサ変接続名詞が入っている場合のみに着目したい.46のプログラムを以下の仕様を満たすように改変せよ.

  • 「サ変接続名詞+を(助詞)」で構成される文節が動詞に係る場合のみを対象とする
  • 述語は「サ変接続名詞+を+動詞の基本形」とし,文節中に複数の動詞があるときは,最左の動詞を用いる
  • 述語に係る助詞(文節)が複数あるときは,すべての助詞をスペース区切りで辞書順に並べる
  • 述語に係る文節が複数ある場合は,すべての項をスペース区切りで並べる(助詞の並び順と揃えよ) 例えば「別段くるにも及ばんさと、主人は手紙に返事をする。」という文から,以下の出力が得られるはずである.
返事をする      と に は        及ばんさと 手紙に 主人は

このプログラムの出力をファイルに保存し,以下の事項をUNIXコマンドを用いて確認せよ.

  • コーパス中で頻出する述語(サ変接続名詞+を+動詞)
  • コーパス中で頻出する述語と助詞パターン

gist15c366015aa0acde42de2429e5527498

# go run q47.go
# cat ../data/q47.out.txt | head -10
決心をする と      こうと
返報をする んで   偸んで
昼寝をする が      彼が
迫害を加える    て         追い廻して
生活をする  が を         我等猫族が  愛を
投書をする て へ      やって  ほととぎすへ
話をする    に      時に
昼寝をする て      出て
欠伸をする から て て         なったから   して  押し出して
報道をする を      報道を

# cat ../data/q47.out.txt | awk '{print $1}' | sort | uniq -c | sort -nr | head -10
  26 返事をする
  19 挨拶をする
  12 話をする
   8 質問をする
   7 喧嘩をする
   6 真似をする
   5 質問をかける
   5 相談をする
   5 注意をする
   5 昼寝をする

# cat ../data/q47.out.txt | awk 'BEGIN {FS="\t"} {print $1,$2}' | sort | uniq -c | sort -nr | head -10
   6 返事をする と
   4 挨拶をする と
   3 質問をかける と は
   3 挨拶をする から
   2 同情を表する と は て
   2 返事をする は と
   2 挨拶をする と も
   2 講義をする で
   2 覚悟をする と
   2 喧嘩をする  と

“述語に係る助詞(文節)が複数ある"とあるので助詞を全部出力していたら、同一分節中に複数の助詞がある場合に出力が想定通りにならず、苦労しました。 問題中の例題だと以下のように、終助詞"さ"と格助詞"と"が別々になってしまいました。しかも最初に助詞を見つけたところではなく、文節ごと出力させるために最後まで確認しないといけないのが面倒でした。

返事をする さ と は に 及ばんさ 及ばんさと 主人は 手紙に

しかし、仕様の例外処理でどんどんコードが汚くなっていきますね。。。

48. 名詞から根へのパスの抽出

文中のすべての名詞を含む文節に対し,その文節から構文木の根に至るパスを抽出せよ. ただし,構文木上のパスは以下の仕様を満たすものとする.

  • 各文節は(表層形の)形態素列で表現する
  • パスの開始文節から終了文節に至るまで,各文節の表現を"->“で連結する

「吾輩はここで始めて人間というものを見た」という文(neko.txt.cabochaの8文目)から,次のような出力が得られるはずである.

吾輩は -> 見た
ここで -> 始めて -> 人間という -> ものを -> 見た
人間という -> ものを -> 見た
ものを -> 見た

gist951151b7941178023b359176f4cb5953

# go run q48.go > ../data/q48.out.txt
# cat ../data/q48.out.txt | head -10
一
吾輩は -> 猫である
猫である
名前は -> 無い
どこで -> 生れたか -> つかぬ
見当が -> つかぬ
何でも -> 薄暗い -> 所で -> 泣いて -> 記憶している
所で -> 泣いて -> 記憶している
ニャーニャー -> 泣いて -> 記憶している
いた事だけは -> 記憶している

名詞を含む文節を探し、そこから再帰的にルートまで向かう形にしたのでコードがすっきりしました。

49. 名詞間の係り受けパスの抽出

文中のすべての名詞句のペアを結ぶ最短係り受けパスを抽出せよ.ただし,名詞句ペアの文節番号がiとj(i<j)のとき,係り受けパスは以下の仕様を満たすものとする.

  • 問題48と同様に,パスは開始文節から終了文節に至るまでの各文節の表現(表層形の形態素列)を"->“で連結して表現する
  • 文節iとjに含まれる名詞句はそれぞれ,XとYに置換する

また,係り受けパスの形状は,以下の2通りが考えられる.

  • 文節iから構文木の根に至る経路上に文節jが存在する場合: 文節iから文節jのパスを表示
  • 上記以外で,文節iと文節jから構文木の根に至る経路上で共通の文節kで交わる場合: 文節iから文節kに至る直前のパスと文節jから文節kに至る直前までのパス,文節kの内容を"|“で連結して表示

例えば,「吾輩はここで始めて人間というものを見た。」という文(neko.txt.cabochaの8文目)から,次のような出力が得られるはずである.

Xは | Yで -> 始めて -> 人間という -> ものを | 見た
Xは | Yという -> ものを | 見た
Xは | Yを | 見た
Xで -> 始めて -> Y
Xで -> 始めて -> 人間という -> Y
Xという -> Y

gistd4f8192b24df8751246341e8bc354380

# go run q49.go > ../data/q49.out.txt
# cat ../data/q49.out.txt | head -18
Xは -> Y
Xで -> 生れたか | Yが | つかぬ
Xでも -> 薄暗い -> 所で -> 泣いて | Y -> 泣いて | 泣いて
Xでも -> 薄暗い -> 所で -> 泣いて | Yだけは | 記憶している
Xで -> 泣いて | Y -> 泣いて | 泣いて
Xで -> 泣いて | Yだけは | 記憶している
X -> 泣いて | Yだけは | 記憶している
Xでも -> 薄暗い -> Y
Xでも -> 薄暗い -> 所で -> 泣いて -> Y
Xで -> 泣いて -> Y
X -> 泣いて -> Y
Xだけは -> Y
Xは | Yで -> 始めて -> 人間という -> ものを | 見た
Xは | Yという -> ものを | 見た
Xは | Yを | 見た
Xで -> 始めて -> Y
Xで -> 始めて -> 人間という -> Y
Xという -> Y

例題の結果を含めるために18行目まで出力しました。
問題文の意味を理解するのに苦労しましたが、以下の2つは別の問題と考えたほうがわかりやすいです。

  • 文節iから構文木の根に至る経路上に文節jが存在する場合: 文節iから文節jのパスを表示
  • 上記以外で,文節iと文節jから構文木の根に至る経路上で共通の文節kで交わる場合: 文節iから文節kに至る直前のパスと文節jから文節kに至る直前までのパス,文節kの内容を"|“で連結して表示

今回は上記をそれぞれ、directNounPairs()indirectNounPairs()として別々に実装しました。こうすると問題文中のYの処理が異なるところの処理をわけて考えやすいです。

実装の方針は言語処理100本ノック 2015年版 (46~49)を参考にさせて頂きました。

感想

やっと折り返しまできました。しかし一問一問が重たくなってきたのと、NLPの単語を知らなすぎて調べたりしないといけないので時間がかかるようになってきました。それでもQ45のような可視化をするとやっぱり楽しくなってきますね。残りもコツコツがんばります。

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

Reference

mycliの選択候補のカラーを変更する

mycliではSyntax Colorsにあるようにカラーテーマを設定できますが、選択候補はカラーテーマによって変更されないので以下のように見づらくなってしまいます。

f:id:cipepser:20170617215850p:plain

解決するためには、~/.myclircのCompletion menusを編集すればカラーを自由に設定することができます。 以下は自分の設定例です。

# Completion menus.
Token.Menu.Completions.Completion.Current = 'bg:#686868 #d8d8d8'
Token.Menu.Completions.Completion = 'bg:#2d2d2d #d8d8d8'

変更後は以下のようになりました。
※テーマもsyntax_style = monokaiとしています。

f:id:cipepser:20170617220058p:plain

Reference

GolangでBucketized Cuckoo Hashingを実装してみた

先日、Cuckoo Hashingの記事を書いたところ、以下のご指摘を頂いたのでBucketized版も実装してみました。

Erlingssonらの論文にも述べられていますが、挿入した要素がテーブルサイズの50%に達すると性能が低下するそうです。 前回も述べましたが、挿入時のハッシュの衝突によって要素の追い出しが起きてしまうためですね。そこで、挿入できる数をひとつでなく複数個にする(本記事ではこれをbucketと呼ぶことにします)ことで、衝突しても用意したbucketの大きさだけそのまま挿入できるようにしたものがBucketized Cuckoo Hashingです。

Fotakisらによるとひとつのbucketに4つの要素まで詰め込めるようにした場合では97%まで空間効率を上げることができるそうです。 この論文中ではBucketized Cuckoo Hashingはd-ary Cuckoo Hashingと呼ばれており、d=4の場合で97%と述べられています。

実装

gist0b30182c97fa91f73174ebcf3baf7645

上記では結果が見やすいようにd=2としています。

ベンチマーク

せっかくなのでbucketized CuckooHashingを通常のCuckooHashingと比較してみます。 ここでは一様乱数で発生させた要素を挿入し、挿入時間を測定します。 測定内容を実環境の問題と合わせて考えるべきですが、実環境の問題はどんなのがあるんでしょうか…

挿入する要素数をテーブルサイズ×bucketサイズで除した値を充填率とし、充填率が大きくなったときに挿入時間がどのように変化するか測定します。
今回は限られたメモリ上でbucketizedするかしないかを決定することを想定し、テーブルサイズとbucketのサイズを以下とします。

[Normal CuckooHashing]
N       int64 = 100000 // テーブルの大きさ

[Bucketized CuckooHashing]
N       int64 = 25000 // テーブルの大きさ
BCKSIZE int   = 4     // bucketのサイズ

ベンチマークコードはGithubにあります。 ベンチマーク結果は以下です。

f:id:cipepser:20170527161928p:plain

全体としてbucketizedしたほうが挿入時間が小さくなっていることがわかります。

References