GolangでS式の簡易パーサを書いてみた
言語処理100本ノック 2015のQ59でS式の解析の問題に出会ったので、パーサの自作なるものにチャレンジしたく、書いてみました。
前提
タスク
以下のS式を多分木にパースします。
(a(b(d(i)(j))(e)(f(k)))(c(g)(h(l(n))(m))))
わかりやすいように改行を入れると以下のようになります。
(a (b (d (i) (j) ) (e) (f (k) ) ) (c (g) (h (l (n) ) (m) ) ) )
木にすると以下なイメージです。
実装
Tree
まず、多分木を以下のように定義します。
type Tree struct { Parent *Tree Child []*Tree Value string }
root node
root nodeは親を持たないので、便宜的に自分自身を親として、コンストラクタを書きます。
func NewTree() *Tree { t := &Tree{} t.Parent = t return t }
実装
パーサの実装は以下です。
gistb526d47b5f834803b8d69ce4ccecbc63
Install
githubにあげてあるので以下でInstallできます。
# go get github.com/cipepser/goSExpression-sample/gose
Usage
以下のようにParse()
でパースできます。
s := `(a(b(d(i)(j))(e)(f(k)))(c(g)(h(l(n))(m))))` t, err := gose.Parse(s) if err != nil { log.Fatal(err) }
結果の表示は簡易的ですが、以下のようにWalk()
でできるようにしました。
// t.Walk() I am ' a ' my parent is ' a ' ------- I am ' b ' my parent is ' a ' ------- I am ' d ' my parent is ' b ' ------- I am ' i ' my parent is ' d ' ------- I am ' j ' my parent is ' d ' ------- I am ' e ' my parent is ' b ' ------- I am ' f ' my parent is ' b ' ------- I am ' k ' my parent is ' f ' ------- I am ' c ' my parent is ' a ' ------- I am ' g ' my parent is ' c ' ------- I am ' h ' my parent is ' c ' ------- I am ' l ' my parent is ' h ' ------- I am ' n ' my parent is ' l ' ------- I am ' m ' my parent is ' h ' -------
Reference
Golangでjsonをbsonに変換する
Go言語でMongoDBを扱っているとjsonをbsonに変換したくなります。 APIのレスポンスがjsonで返ってきて、それをMongoDBに格納したいときなどですね。
Go言語でMongoDBを触るためのdriverには、mgoがあります。
変換もmgoからできるのでgo get
しておきます。
go get gopkg.in/mgo.v2
あとはUnmarshalJSON()
を適用してあげればOKです。
逆にbsonをjsonにしてあげたいときはMarshalJSON()
を使います。
それぞれ実装例は以下です。
gist2bd83a17dba79bec793e5f07296e7b6e
References
xmlからGo strcutを生成する
ツール紹介です。 Web APIのレスポンスはだいたいjsonで返ってくるので、go structを自動生成してくれる JSON-to-Goが便利でよく使っているのですが、今回はxmlで同じことをしたいと思い、chidleyというツールを触ってみたので、使い方をまとめます。
インストール
いつものごとく、go get
しましょう。
# go get github.com/gnewton/chidley
使い方
READMEにもありますが、同じサンプル(test.xmlとします)を借ります。
<people> <person> <name>bill</name> <age>37</age> <married>true</married> </person> <person> <name>sarah</name> <age>24</age> <married>false</married> </person> </people>
-G
オプションを付けることでxmlからGo structが生成されます。
# chidley -G test.xml type ChiChidleyRoot314159 struct { ChiPeople *ChiPeople `xml:" people,omitempty" json:"people,omitempty"` } type ChiAge struct { Text string `xml:",chardata" json:",omitempty"` } type ChiMarried struct { Text string `xml:",chardata" json:",omitempty"` } type ChiName struct { Text string `xml:",chardata" json:",omitempty"` } type ChiPeople struct { ChiPerson []*ChiPerson `xml:" person,omitempty" json:"person,omitempty"` } type ChiPerson struct { ChiAge *ChiAge `xml:" age,omitempty" json:"age,omitempty"` ChiMarried *ChiMarried `xml:" married,omitempty" json:"married,omitempty"` ChiName *ChiName `xml:" name,omitempty" json:"name,omitempty"` }
型付きでコンバート
上記のようにデフォルトではint
型やbool
型もすべてstring
型として解釈されます。-t
オプションで型まで含めたコンバートを行ってくれます。
# chidley -G -t test.xml type ChiChidleyRoot314159 struct { ChiPeople *ChiPeople `xml:" people,omitempty" json:"people,omitempty"` } type ChiAge struct { Text int8 `xml:",chardata" json:",omitempty"` } type ChiMarried struct { Text bool `xml:",chardata" json:",omitempty"` } type ChiName struct { Text string `xml:",chardata" json:",omitempty"` } type ChiPeople struct { ChiPerson []*ChiPerson `xml:" person,omitempty" json:"person,omitempty"` } type ChiPerson struct { ChiAge *ChiAge `xml:" age,omitempty" json:"age,omitempty"` ChiMarried *ChiMarried `xml:" married,omitempty" json:"married,omitempty"` ChiName *ChiName `xml:" name,omitempty" json:"name,omitempty"` }
age
の24
,37
がint8
型として解釈されていますが、chidleyでは以下のように記載されているとおり、できるだけ小さい型に合わせようとします。
今回は-128
〜127
の範囲に収まっているために、int8
型となります。
chidley tries to fit the smallest Go type. For example, if all instances of a tag contain a number, and all instances are -128 to 127, then it will use an int8 in the Go struct.
接頭辞を変更する
上記の結果をみるとわかるように型の接頭辞にChi
がつきます。これを変更するには-e
オプションを用います。
ただし、xmlのデコーダなど外部からも参照できるように大文字から始める必要があるので注意してください。
# chidley -G -e "Prefix" test.xml type PrefixChidleyRoot314159 struct { PrefixPeople *PrefixPeople `xml:" people,omitempty" json:"people,omitempty"` } type PrefixAge struct { Text string `xml:",chardata" json:",omitempty"` } type PrefixMarried struct { Text string `xml:",chardata" json:",omitempty"` } type PrefixName struct { Text string `xml:",chardata" json:",omitempty"` } type PrefixPeople struct { PrefixPerson []*PrefixPerson `xml:" person,omitempty" json:"person,omitempty"` } type PrefixPerson struct { PrefixAge *PrefixAge `xml:" age,omitempty" json:"age,omitempty"` PrefixMarried *PrefixMarried `xml:" married,omitempty" json:"married,omitempty"` PrefixName *PrefixName `xml:" name,omitempty" json:"name,omitempty"` }
ちなみに""
を指定してあげることで接頭辞をなしにすることもできます。
chidley -G -e "" test.xml type ChidleyRoot314159 struct { People *People `xml:" people,omitempty" json:"people,omitempty"` } type Age struct { Text string `xml:",chardata" json:",omitempty"` } type Married struct { Text string `xml:",chardata" json:",omitempty"` } type Name struct { Text string `xml:",chardata" json:",omitempty"` } type People struct { Person []*Person `xml:" person,omitempty" json:"person,omitempty"` } type Person struct { Age *Age `xml:" age,omitempty" json:"age,omitempty"` Married *Married `xml:" married,omitempty" json:"married,omitempty"` Name *Name `xml:" name,omitempty" json:"name,omitempty"` }
他にも色々なオプションがありますが、自分が使いそうなところを中心にまとめました。
Reference
GolangでHopscotch Hashingを実装してみた
※2017/8/13 タイトルにtypoがあったので修正しました。 [前]GolfingでHopscotch Hashingを実装してみた [後]GolangでHopscotch Hashingを実装してみた
前回のCuckoo Hashingの実装記事から少し間が空きましたが、今回はHopscotch Hashingを実装してみようと思います。
Hopscotch Hashingとは
テーブルのハッシュ衝突を解決する目的で、Mauriceらによって導入された手法です。 論文はこちら。
Hopscotch Hashingでは、各bucketにitemとbitmapを持ちます。
今回の実装では、以下のようにしています。
H
はビットマップの大きさです。
type bucket struct { item int64 bitmap [H]bool } type Hopscotch []bucket
item
は、Insert
、Lookup
、Delete
したい要素そのものです。
bitmap
は、ハッシュ値が衝突した場合に、そのbucketから見てからH-1
番目までに、その要素が存在するかを表します。
図にすると以下のようなイメージです。
itema
とitemb
が同じハッシュ値を持っていることを保証します。
この構造を維持することで、Lookup
はbitmap
が1
になっているところのitem
のみをチェックすればよいので、
計算量がO(H)
となります。
Delete
もLookup
して対象となるitem
があれば、それを削除し、対応するbitmap
を0
としてあげればよいので簡単です。
問題はInsert
ですが、次節に記載します。
Insertのアルゴリズム
Hopscotch Hashingでは、ハッシュ衝突後に、空いているbucketを線形探索で探し、その空きbucketを順々に最初のハッシュ値のindexからH-1
番目以内まで持ってくるということをします。
言葉だけではわかりづらいので図にすると以下のようになります。
空きbucketが見つからない場合は、サイズを大きくしてテーブルを作り直してあげる必要があります。 今回の実装では2倍ずつ増やすことにしました。
実装
以上を実装したものが以下になります。
gisteb0ae2b452b62984e8b54c6298321238
テストも含めて、githubにあげてあります。
実行
テーブルサイズを10、bitmap
のサイズを2として、1から10までを挿入してみます。
gist806d61d8cd2522a4a797838694069293
実行結果
----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true false]} 2 | {0 [false false]} 3 | {0 [false false]} 4 | {0 [false false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {0 [false false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true false]} 2 | {0 [false false]} 3 | {0 [false false]} 4 | {2 [true false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {0 [false false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true false]} 2 | {3 [true false]} 3 | {0 [false false]} 4 | {2 [true false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {0 [false false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true false]} 2 | {3 [true false]} 3 | {0 [false false]} 4 | {2 [true true]} 5 | {4 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {0 [false false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true false]} 2 | {3 [true false]} 3 | {0 [false false]} 4 | {2 [true true]} 5 | {4 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true true]} 2 | {6 [false true]} 3 | {3 [false false]} 4 | {2 [true true]} 5 | {4 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true true]} 2 | {6 [false true]} 3 | {3 [false false]} 4 | {2 [true true]} 5 | {4 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {7 [true false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {6 [true false]} 2 | {0 [false false]} 3 | {0 [false false]} 4 | {2 [true false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {0 [false false]} 10 | {0 [false false]} 11 | {1 [true true]} 12 | {8 [false true]} 13 | {3 [false false]} 14 | {4 [true false]} 15 | {0 [false false]} 16 | {0 [false false]} 17 | {0 [false false]} 18 | {0 [false false]} 19 | {7 [true false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {6 [true false]} 2 | {0 [false false]} 3 | {0 [false false]} 4 | {2 [true false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {0 [false false]} 10 | {0 [false false]} 11 | {1 [true true]} 12 | {8 [false true]} 13 | {3 [false false]} 14 | {4 [true true]} 15 | {9 [false false]} 16 | {0 [false false]} 17 | {0 [false false]} 18 | {0 [false false]} 19 | {7 [true false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {6 [true false]} 2 | {0 [false false]} 3 | {0 [false false]} 4 | {2 [true false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {0 [false false]} 10 | {0 [false false]} 11 | {1 [true true]} 12 | {8 [false true]} 13 | {3 [false false]} 14 | {4 [true true]} 15 | {9 [false true]} 16 | {10 [false false]} 17 | {0 [false false]} 18 | {0 [false false]} 19 | {7 [true false]}
item
として8を挿入しようとしたときにテーブルの作り直しが起こっています。
感想
Insert
の実装が思いの外、苦戦しました。添字のミスがないように一つ一つ確かめながら実装したので身には付いたかなと思います。
テーブルの作り直しもバグが入りがちで、ループになったり、挿入がされていなかったりで理解してから実装までが大変でした。
References
Golangでパーセントエンコーディングをデコードする
前回の記事でGo言語でパーセントエンコーディングを行ったので、今回はデコード編です。
とはいえ、標準でデコードするQueryUnescape()
関数が用意されているので、そちらを使うのみです。
前回のように半角スペースの置換を気にする必要はありません。
ドキュメントにも以下のように記載されています。
func QueryUnescape
converting %AB into the byte 0xAB and ‘+’ into ‘ ’ (space).
実装は以下です。
package main import ( "fmt" "net/url" "regexp" ) func main() { str := "パーセント エンコーディング" // encode str = url.QueryEscape(str) str = regexp.MustCompile(`([^%])(\+)`).ReplaceAllString(str, "$1%20") // decode str, _ = url.QueryUnescape(str) fmt.Println(str) // パーセント エンコーディング }
References
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
です。
次の例では、ネットワーク初心者の新卒がDockerでネットワークの勉強をしてみたを参考に、検証環境を用意してみました。
OSPFの224.0.0.5
があるので、動的に経路情報を渡している様子が見えますね。
感想
自分で使ってみて思ったのは、変な通信がないか確認できるのがよいなということでした。同セグメントをグループ化するなどするともっと良さそうです。 フィルタやL4以上の情報(逆にL2も)も可視化できそうなので、これをもとにツール化したいところですが、future workということで。