読者です 読者をやめる 読者になる 読者になる

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

Golangのmath/bigでIntを直接入力したい

背景

Golangの基本型であるint64では 64 \times log_{10} 2 \approx 64 \times 0.3 = 19.2のため20桁程度(※)でoverflowを起こします。そのため、math/bigパッケージのNewIntを使おうとするとoverflowのコンパイルエラーになります。

※正確には、符号付き64bit整数の最大値9223372036854775807(ギリギリ19桁)を超えるとoverflowします。

例えば、20桁の数16329805957987392833で試してみると、以下のようにconstant 16329805957987392833 overflows int64コンパイルエラーとなります。

package main

import (
    "fmt"
    "math/big"
)

func main()  {
    n := big.NewInt(16329805957987392833) // constant 16329805957987392833 overflows int64
    fmt.Println(n)
}

int64の最大値を超えるような大きな数をbig.Int型として扱いたいときは以下のようにすれば直接入力可能です。

package main

import (
    "fmt"
    "math/big"
)

const (
    DECIMAL int = 10
)

func main()  {
    
    n, _ := new(big.Int).SetString("16329805957987392833", DECIMAL)
    fmt.Println(n)
    
}

使った素数について

素数生成機をお借りして10桁の素数を2つ(7508269669,2174909357)生成し、積を計算したのが16329805957987392833です。

Reference

DH鍵交換でもWiresharkでSSL/TLSを復号化したい

WiresharkでSSL通信の中身を覗いてみる を拝見し、実際に自分の手を動かしてみたのですが、記事内でも触れられているようにDiffie-Hellman(DH) key exchange (および楕円曲線を用いたECDH) では、実際に鍵を送り合うわけではなく、鍵を生成するためのパラメータだけがやり取りされるので、サーバの秘密鍵を持っていても復号できません。
今回はDH鍵交換(以下、DHE)でもWiresharkSSL/TLSを復号すべく試行錯誤したので、まとめます。

事前の設定内容

VirtualBoxで以下のゲストOSやApacheを立ち上げておきます。

$ cat /etc/redhat-release
CentOS Linux release 7.2.1511 (Core)

$ httpd -v
Server version: Apache/2.4.6 (CentOS)
Server built:   Nov 14 2016 18:04:44

$ rpm -aq | grep mod_ssl
mod_ssl-2.4.6-45.el7.centos.x86_64

$ openssl version
OpenSSL 1.0.1e-fips 11 Feb 2013

ホストOSとゲストOSのIPは、それぞれ以下のようにアサインしました。

ホストOS ゲストOS
192.168.10.100 192.168.10.104

オレオレ証明書CentOS に Apache HTTPD を導入して SSL を有効にする を参考に作成し、証明書と秘密鍵は以下の名前でssl.confに記載しています。

# サーバ証明書
SSLCertificateFile /etc/httpd/conf/server.crt
# サーバ秘密鍵
SSLCertificateKeyFile /etc/httpd/conf/server.key

(参考)DHEを無効にする

参考までにサーバ側とクライアント側でDHEを無効にすることでSSL/TLS通信を復号する方法も記載します。 この方法ではサーバの秘密鍵があれば、SSL/TLS通信を復号することができます。サーバの秘密鍵を外へ出したくないということであれば(むしろ出すべきでないと思いますが)、session keyのみをexportすることでも復号できます。 セッションキーをエクスポートし、秘密鍵を共有することなくWireshark でSSL/TLS 通信を複合 に両方のやり方がありますので、興味がある方はぜひ。

サーバ側でDHEを無効にする

WiresharkでSSL通信の中身を覗いてみる にも記載がありますが、ssl.confで以下のように設定すればOKです。

SSLCipherSuite kRSA

設定後はservice httpd restartApacheを再起動しておきます。 この状態でhttpsの通信を発生させ、Server Helloに含まれるcipher suiteを見ると Cipher Suite: TLS_RSA_WITH_AES_128_CBC_SHA (0x002f)となっており、DHEもECDHEも使われていないことがわかります。

f:id:cipepser:20170326204102p:plain

ssl.confの設定を戻すことをお忘れなく

クライアント側でDHEを無効にする(Firefox)

Firefoxを立ち上げ、アドレスバーにabout:configと打ち込みます。 dheで検索し、DHEおよびECDHEを含むcipher suitesを無効化(false)にします。 以下の太字の箇所が変更箇所です(一番上以外)。

f:id:cipepser:20170326202640p:plain

この状態でhttpsの通信を発生させ、Server Helloに含まれるcipher suiteを見ると Cipher Suite: TLS_RSA_WITH_AES_128_CBC_SHA (0x002f)となっており、サーバ側でDHEとECDHEを無効化したときと同じですね。

f:id:cipepser:20170326202929p:plain

Firefoxの設定を戻すことをお忘れなく

本題

さて、DHEを無効化せずにWiresharkで復号化したいですね。 復号化するにはサーバの秘密鍵ではなく、session keyを入手する必要があります。 まずはホストOSでsession keyをexport先を指定してFirefoxを起動します。 ここではpremaster.txtにexportさせます。
Firefoxは閉じた状態で実行しないと怒られます。

$ SLKEYLOGFILE=/YOURPATH/TO/premaster.txt "/Applications/Firefox.app/Contents/MacOS/firefox-bin"

上記を実行すると、いつも通りFirefoxが起動するので、httpsの通信を発生させます。 するとpremaster.txtには以下のようにsession keyが書き込まれているはずです。

$ cat premaster.txt
# SSL/TLS secrets log file, generated by NSS
CLIENT_RANDOM  xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

※実際にはxが16進数で表示されるはずです。

この時点では以下のように復号化できていないです。

f:id:cipepser:20170326212249p:plain

復号するためには、Wiresharkpremaster.txtからsession keyを読むように指定してあげます。 指定方法は、WiresharkPreferenceからProtocolsSSL(Pre)-Master-Secret log filenamepremaster.txtを指定します。
※特にサーバの秘密鍵などは指定する必要ありません。

f:id:cipepser:20170326213212p:plain

OKを押下すると以下のようにhttpのパケットが復号できます。

f:id:cipepser:20170326214605p:plain

このときのServer Helloに含まれるcipher suiteを見ると Cipher Suite: TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (0xc02f)となっており、ECDHEでも復号化できていることがわかります。

f:id:cipepser:20170326214620p:plain

References

2016年度に読んだ本まとめ

年度も変わったので2016年度の一年間で読んだ本をまとめました。
例によって小説とか漫画は数が多くなりすぎるので割愛です。

技術書

いい加減、GitHub触っておかないとな、と思ったので読みました。 今でもたまにコマンド忘れて、Referenceとして本棚から引っ張り出しています。
手元にあると、困ったとき便利。

CTFとは何か、というところからバイナリ解析の種々の分野について例題を追っていくような感じです。ここからさらに常設CTFなどを自分で解いていくのがよさげです。

2015年末くらいからGo言語やり始めていた折に本屋でちら見して、実際のコードが記載された上で議論していたのでよさそうと思い、購入。実際、自分で書いたコードを思い浮かべながら読むと、意識してなかったこと、すべきことが多数紹介されていて、とても勉強になりました。
しかも思いの外手軽に読めるのがよいです。kindle版が、技術書にありがちな固定レイアウトではなく、しっかりkindleフォーマットなのがポイント高いです。iPhoneでも文字が小さくない!
ただし、A Tour of Goくらいは一読している前提で話が進むのでGo言語初見だと厳しいような印象です。少し触ったあとがオススメです。

良くも悪くも広く浅くという印象でした。各種用語を掴んだ上で自分の手を動かすなり、別の書籍で調べていくのがよさそうです。ちなみに情報処理資格(基本情報、応用情報)よりは深いです。

マネジメントとか

ソフトウェアのプロジェクトを技術的なものではなく、社会学的なものとして捉えて、どういうマネジメントが失敗していくかというお話です。身に覚えのある筋の悪いルールなどもあって、職場で紹介してあげたくなります笑

Googleがどうやって成功してきたか、ひたすら書かれています。 以下の考え方、あんまり思ったことがなかったのでよかったです。

燃え尽き症候群の原因は働きすぎではなく、自分にとって本当に大切なことを諦めなければならなくなったときに起こる

データ分析は銀の弾丸ではないという話をデータサイズや分析結果など様々な観点から話されています。分析の心構え的な話でした。

さくっと読めるセキュリティインシデント事例集。詳細までは追わないもののざっくりとどんなことが起きていて、知っておくべきキーワード、考え方は抑えられそうです。高度情報処理のセキュリティ受ける人とか読んでおくと午後問題回答しやすいかもですね。

資格系

※リンクは最新版にしました。

両方やっておけば合格余裕と思います。自分個人としては計算問題をしっかり理解できたので、計算が安定感ある得点源になりました。

先にある程度問題を解いていたのもあると思いますが、本気でやれば数時間で終わります。無理なくやれば1週間程度でしょうか。問題こなしてから本書を読むと知識が整理されるので教科書としてとても助かりました。

その他

上のGitHub実践入門読んで、GitHubの草も残しておこうと思ったので残します。 Go言語触り始めたあたりから草多めになりました。

f:id:cipepser:20170401001153p:plain

Golangで棒グラフを描く

背景

言語処理100本ノック 2015をやっている最中に、棒グラフで表示する問題(Q37)に遭遇しました。簡単に検索したところ、意外と日本語記事が少なかったので、Gonum Plotを色々触ってみたメモを残しておきます。

packageのインストール

Gonum Plotにもありますが、go getしておきます。

# go get github.com/gonum/plot/...

何もエラーが出ず、プロンプトが表示されれば問題ありません。 ここでhgが足りないエラーがでる場合は、mercurialをインストールしましょう。

# brew install mercurial

棒グラフの作成

各設定事項はコメントで記載しました。 その他にももろもろ設定できますので、Gonum Plotをご覧ください。

gist9515002d792508b91e54766930751e37

棒グラフの出力

上記を実行すると、グラフがディレクトリに.pngで出力されます。 f:id:cipepser:20170324010640p:plain

Reference

Golangで言語処理100本ノック2015 第3章: 正規表現

言語処理100本ノック 2015の第3章: 正規表現の10問です。

20. JSONデータの読み込み

Wikipedia記事のJSONファイルを読み込み,「イギリス」に関する記事本文を表示せよ.問題21-29では,ここで抽出した記事本文に対して実行せよ.

gist1c2eef5c84cb1bb2f2ffc568d5d60d31

Goでjsonを触ったことがなかったので勉強がてら。 結果の表示は長すぎるので割愛します。

21. カテゴリ名を含む行を抽出

記事中でカテゴリ名を宣言している行を抽出せよ.

gistd85ddaaaeedb8accc0431d2ea8458fb5

Q20で抜き出した結果をtxtに格納しています。 本問題は実質、L45-48のみです。

# go run q21.go
[[Category:イギリス|*]]
[[Category:英連邦王国|*]]
[[Category:G8加盟国]]
[[Category:欧州連合加盟国]]
[[Category:海洋国家]]
[[Category:君主国]]
[[Category:島国|くれいとふりてん]]
[[Category:1801年に設立された州・地域]]

22. カテゴリ名の抽出

記事のカテゴリ名を(行単位ではなく名前で)抽出せよ.

gistd36f7ebc49991afa58cb42101c9265b5

# go run q22.go
イギリス|*
英連邦王国|*
G8加盟国
欧州連合加盟国
海洋国家
君主国
島国|くれいとふりてん
1801年に設立された州・地域

正規表現のところをCategory:.*]としました。 あとは表示する箇所を*のところだけにしています。

23. セクション構造

記事中に含まれるセクション名とそのレベル(例えば"== セクション名 ==“なら1)を表示せよ.

gist4db740893310296693544caa501a9727

# go run q23.go
国名 1
歴史 1
地理 1
気候 2
政治 1
外交と軍事 1
地方行政区分 1
主要都市 2
科学技術 1
経済 1
鉱業 2
農業 2
貿易 2
通貨 2
企業 2
交通 1
道路 2
鉄道 2
海運 2
航空 2
通信 1
国民 1
言語 2
宗教 2
 婚姻  2
教育 2
文化 1
食文化 2
文学 2
 哲学  2
音楽 2
イギリスのポピュラー音楽 3
映画 2
コメディ 2
国花 2
世界遺産 2
祝祭日 2
スポーツ 1
サッカー 2
競馬 2
モータースポーツ 2
脚注 1
関連項目 1
外部リンク 1

(?m)がないと^が否定として認識されるところでハマりました。。。

24. ファイル参照の抽出

記事から参照されているメディアファイルをすべて抜き出せ.

gist6feafca211c2f0c574b60770553f1a71

# go run q24.go
Royal Coat of Arms of the United Kingdom.svg
Battle of Waterloo 1815.PNG
The British Empire.png
Uk topo en.jpg
BenNevis2005.jpg
Elizabeth II greets NASA GSFC employees, May 8, 2007 edit.jpg
Palace of Westminster, London - Feb 2007.jpg
David Cameron and Barack Obama at the G20 Summit in Toronto.jpg
Soldiers Trooping the Colour, 16th June 2007.jpg
Scotland Parliament Holyrood.jpg
London.bankofengland.arp.jpg
City of London skyline from London City Hall - Oct 2008.jpg
Oil platform in the North SeaPros.jpg
Eurostar at St Pancras Jan 2008.jpg
Heathrow T5.jpg
Anglospeak.svg
CHANDOS3.jpg
The Fabs.JPG
PalaceOfWestminsterAtNight.jpg
Westminster Abbey - West Door.jpg
Edinburgh Cockburn St dsc06789.jpg
Canterbury Cathedral - Portal Nave Cross-spire.jpeg
Kew Gardens Palm House, London - July 2009.jpg
2005-06-27 - United Kingdom - England - London - Greenwich.jpg
Stonehenge2007 07 30.jpg
Yard2.jpg
Durham Kathedrale Nahaufnahme.jpg
Roman Baths in Bath Spa, England - July 2006.jpg
Fountains Abbey view02 2005-08-27.jpg
Blenheim Palace IMG 3673.JPG
Liverpool Pier Head by night.jpg
Hadrian's Wall view near Greenhead.jpg
London Tower (1).JPG
Wembley Stadium, illuminated.jpg

.*でマッチさせようとすると最後の|まで引っかかってしまうので.*?としています。
Fileファイルでわかれてるがめんどくさかったですね。。。

25. テンプレートの抽出

記事中に含まれる「基礎情報」テンプレートのフィールド名と値を抽出し,辞書オブジェクトとして格納せよ.

gistb73da44413a4ccb5c9e32bd95a7ae4a4

# go run q25.go
イギリス
------------------
{{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>
*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}([[スコットランド・ゲール語]])<br/>
*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}([[ウェールズ語]])<br/>
*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}([[アイルランド語]])<br/>
*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}([[コーンウォール語]])<br/>
*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}([[スコットランド語]])<br/>
**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}(アルスター・スコットランド語)</ref>
------------------
現在の国号「'''グレートブリテン及び北アイルランド連合王国'''」に変更

最初に基本情報を抜き出し、そこから|で区切られるテンプレートを抽出しました。 公式国名があるせいで、改行区切りではないので、\s\Sを用いて改行を含む抽出をしつつ、|を区切りとしています。 ただし単純に\n|を終端として持ってくると偶数回目が抜き出せなくなるので、\n|をダブらせるように前処理を入れています。 同様に最後の注記も抜き出せなくなるので終端処理を入れています。

課題では辞書オブジェクト(Map)に格納するところまでですが、テストとして略名と、ハマりどころの公式国名、偶数番目、最後のテンプレートもちゃんと取れているかの確認用に確立形態4注記を表示させてみました。

26. 強調マークアップの除去

25の処理時に,テンプレートの値からMediaWikiの強調マークアップ(弱い強調,強調,強い強調のすべて)を除去してテキストに変換せよ(参考: マークアップ早見表).

gist8fb6214399e84001eecfcd72acddd3c1

# go run q26.go
現在の国号「グレートブリテン及び北アイルランド連合王国」に変更

Q25を元に、ReplaceAllString'{2,5}をマッチさせています。 確認用には確立形態4を表示。

27. 内部リンクの除去

26の処理に加えて,テンプレートの値からMediaWikiの内部リンクマークアップを除去し,テキストに変換せよ(参考: マークアップ早見表).

gist0531301d5d7252c813b3f8bc12bd074d

# go run q27.go
1801年
244,820
1兆5478億<ref name="imf-statistics-gdp">[http://www.imf.org/external/pubs/ft/weo/2012/02/weodata/weorept.aspx?pr.x=70&pr.y=13&sy=2010&ey=2012&scsm=1&ssd=1&sort=country&ds=.&br=1&c=112&s=NGDP%2CNGDPD%2CPPPGDP%2CPPPPC&grp=0&a= IMF>Data and Statistics>World Economic Outlook Databases>By Countrise>United Kingdom]</ref>
2兆3162億<ref name="imf-statistics-gdp" />
イングランド王国/スコットランド王国<br />(両国とも連合法 (1707年)まで)
グレートブリテン及びアイルランド連合王国建国<br />(連合法 (1800年))
女王陛下万歳
ロンドン
246
1.3%
2兆4337億<ref name="imf-statistics-gdp" />
±0
.uk / .gb<ref>使用は.ukに比べ圧倒的少数。</ref>
44
(イギリスの国章)
{{lang|fr|Dieu et mon droit}}<br/>(フランス語:神と私の権利)
6
建国
1927年
{{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>
*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}(スコットランド・ゲール語)<br/>
*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}(ウェールズ語)<br/>
*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}(アイルランド語)<br/>
*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}(コーンウォール語)<br/>
*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}(スコットランド語)<br/>
**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}(アルスター・スコットランド語)</ref>
ロンドン
デーヴィッド・キャメロン
927年/843年
GB / GBR
1707年
Flag of the United Kingdom.svg
22
63,181,775<ref>[http://esa.un.org/unpd/wpp/Excel-Data/population.htm United Nations Department of Economic and Social Affairs>Population Division>Data>Population>Total Population]</ref>
2012
グレートブリテン王国建国<br />(連合法 (1707年))
2011
1 E7
36,727<ref name="imf-statistics-gdp" />
ファイル:Royal Coat of Arms of the United Kingdom.svg|85px
Location_UK_EU_Europe_001.svg
イギリスの君主
76
1 E11
+1
<references />
2012
5
2012
イギリス
グレートブリテン及び北アイルランド連合王国
英語(事実上)
エリザベス2世
イギリスの首相
現在の国号「グレートブリテン及び北アイルランド連合王国」に変更
スターリング・ポンド (&pound;)
GBP

ルールは単純なのですが、意外と時間かかりました。 グループ文字列の概念をここで知ったのでFindAllStringSubmatch()も使ってみました。

28. MediaWikiマークアップの除去

27の処理に加えて,テンプレートの値からMediaWikiマークアップを可能な限り除去し,国の基本情報を整形せよ.

gistb0ae0915872317ffa62cedb2c505d854

# go run q28.go
1 E7
1兆5478億<ref name="imf-statistics-gdp">
スターリング・ポンド (&pound;)
GBP
1.3%
244,820
2兆3162億<ref name="imf-statistics-gdp" />
36,727<ref name="imf-statistics-gdp" />
ロンドン
2011
63,181,775<ref>
グレートブリテン及びアイルランド連合王国建国<br />(連合法 (1800年))
1927年
<references />
イギリスの君主
Flag of the United Kingdom.svg
(イギリスの国章)
エリザベス2世
{{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>
*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}(スコットランド・ゲール語)<br/>
*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}(ウェールズ語)<br/>
*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}(アイルランド語)<br/>
*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}(コーンウォール語)<br/>
*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}(スコットランド語)<br/>
**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}(アルスター・スコットランド語)</ref>
1801年
+1
246
Location_UK_EU_Europe_001.svg
英語(事実上)
ロンドン
5
2012
1707年
現在の国号「グレートブリテン及び北アイルランド連合王国」に変更
グレートブリテン及び北アイルランド連合王国
GB / GBR
±0
イギリスの首相
76
1 E11
2012
2兆4337億<ref name="imf-statistics-gdp" />
建国
イングランド王国/スコットランド王国<br />(両国とも連合法 (1707年)まで)
{{lang|fr|Dieu et mon droit}}<br/>(フランス語:神と私の権利)
グレートブリテン王国建国<br />(連合法 (1707年))
.uk / .gb<ref>使用は.ukに比べ圧倒的少数。</ref>
44
927年/843年
ファイル:Royal Coat of Arms of the United Kingdom.svg|85px
女王陛下万歳
デーヴィッド・キャメロン
22
2012
6
イギリス

外部リンクとコメントアウトを消しました。

29. 国旗画像のURLを取得する

テンプレートの内容を利用し,国旗画像のURLを取得せよ.(ヒント: MediaWiki APIimageinfoを呼び出して,ファイル参照をURLに変換すればよい)

gist84f53bc3fb6df3029aff323f42cb6c5d

# go run q29.go
https://upload.wikimedia.org/wikipedia/en/a/ae/Flag_of_the_United_Kingdom.svg

API client書いたことがなかったので書いてみましたが、もっとちゃんと書けそうな気がしています。どういうことに気をつけて書くべきなのかも経験不足なので、今後の課題ですね。

感想

序盤はさくさく進んだので余裕かと思いましたが、後半でかなり手こずりしました。正規表現むずい。
今回もコードはGithubにも置いてあります。

Reference

tracerouteで * (アスタリスク)になる理由

背景

「ネットワークがつながらない!」といったトラブルシューティングをしていると、 tracerouteの結果が、以下のように経路の途中で*になる事象によく遭遇します。
今回はIPヘッダやパケットを見比べながら、なぜ*になるのかを見ていきます。

$ traceroute 8.8.8.8
traceroute to 8.8.8.8 (8.8.8.8), 64 hops max, 52 byte packets
 1  192.168.43.1 (192.168.43.1)  823.037 ms *  3.936 ms
 2  * * *
 3  osk004bb01.iij.net (202.32.116.5)  476.654 ms  132.676 ms  120.725 ms
 4  osk004ix50.iij.net (58.138.107.218)  119.609 ms
    osk004ix50.iij.net (58.138.107.166)  133.204 ms
    osk004ix51.iij.net (58.138.107.222)  117.566 ms
 5  72.14.210.182 (72.14.210.182)  126.614 ms
    210.130.133.86 (210.130.133.86)  115.229 ms  118.843 ms
 6  108.170.243.36 (108.170.243.36)  119.670 ms
    108.170.243.68 (108.170.243.68)  134.219 ms
    108.170.243.132 (108.170.243.132)  135.462 ms
 7  209.85.255.163 (209.85.255.163)  141.621 ms
    216.239.41.199 (216.239.41.199)  132.251 ms  138.545 ms
 8  66.249.95.77 (66.249.95.77)  165.501 ms
    108.170.235.231 (108.170.235.231)  155.299 ms
    66.249.95.77 (66.249.95.77)  172.740 ms
 9  216.239.43.101 (216.239.43.101)  153.654 ms
    72.14.235.77 (72.14.235.77)  175.888 ms
    64.233.175.209 (64.233.175.209)  156.037 ms
10  * * *
11  * * *
12  * * *
13  * * *
14  * * *
15  * * *
16  * * *
17  * * *
18  google-public-dns-a.google.com (8.8.8.8)  159.839 ms  156.416 ms  166.939 ms

※プロバイダによっては*にならない場合もあるようです。 今回はDMMのSIMカードからテザリングしています。
ちなみに8.8.8.8GoogleのパブリックDNSIPアドレスです。覚えやすいですね。

前提知識

IPヘッダのProtocolナンバー

RFC791でIPヘッダのフォーマットは以下のように定められています。

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version|  IHL  |Type of Service|          Total Length         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         Identification        |Flags|      Fragment Offset    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Time to Live |    Protocol   |         Header Checksum       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Source Address                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Destination Address                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Options                    |    Padding    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

上記のProtocolフィールドが1となるものがICMPとなります。
※ProtocolナンバーはRFC790 で規定されています。 TCPUDP(User Datagram)もそれぞれ617がアサインされています。

ping実行時のパケットをWiresharkで見てみると以下のようにICMP(1)となっていることがわかります。

f:id:cipepser:20170305172120p:plain

tracerouteの仕組み

tracerouteは、冒頭のコマンド結果のように、宛先までのホップ情報を教えてくれる便利なコマンドです。
tracerouteは上記のIPヘッダにあるTime to Live(TTL)を利用して実装されています。
TTLはパケットの寿命みたいなものです。誤ったルーティングが設定されたネットワークでは、度々ループが発生します。この時、ネットワークに入ってきたパケットがいつまでもループし続けると、ネットワークの帯域を逼迫させ、通信ができなくなります。それを避けるための方法として、ルータはパケットをフォワードする際にTTLを1ずつデクリメントします。TTLが0になったパケットを受信したルータは、そのパケットをフォワードせず、破棄します。これによってネットワークが輻輳まみれになることを防ぎます。
そしてTTLが0になったときtracerouteの発行元に対して、TTLが0になったことを通知(Time Exceeded Message)します。

※これらはRFC792で以下のように規定されています。

If the gateway processing a datagram finds the time to live field is zero it must discard the datagram. The gateway may also notify the source host via the time exceeded message.

この通知には破棄したルータのIPアドレスが含まれています。 tracerouteではTTLを1つずつインクリメントし、応答があったTime Exceeded Messageに含まれるIPアドレスを表示することで実装されています。

本題

前置きが長くなりましたが、いよいよ本題に入っていきます。
tracerouteは、WindowsではICMPを用いていますが、LinuxではUDPでポート番号33434 〜33534が使われます。tracerouteをFWで通す要件がある場合は、実装する際に注意が必要です。
今回はICMPのTTLをマニュアルで設定することで、tracerouteの仕組みを擬似的に再現し、*の正体を探ります。 そのためtraceroute-Iオプションを付けてICMPでのtraceroute結果を得ておきます。

$ traceroute -I 8.8.8.8
traceroute to 8.8.8.8 (8.8.8.8), 64 hops max, 72 byte packets
 1  * * *
 2  * * *
 3  osk009nasgw111.iij.net (202.32.116.105)  132.515 ms  122.689 ms  119.731 ms
 4  osk004bb01.iij.net (202.32.116.5)  117.981 ms  114.951 ms  121.114 ms
 5  osk004ix51.iij.net (58.138.107.222)  123.171 ms  118.085 ms  122.172 ms
 6  72.14.210.182 (72.14.210.182)  117.047 ms  122.246 ms  123.139 ms
 7  108.170.243.66 (108.170.243.66)  117.916 ms  498.344 ms  149.948 ms
 8  209.85.255.163 (209.85.255.163)  116.059 ms  132.291 ms  121.649 ms
 9  72.14.233.211 (72.14.233.211)  159.789 ms  163.511 ms  173.399 ms
10  72.14.235.77 (72.14.235.77)  154.462 ms  153.933 ms  170.539 ms
11  * * *
12  * * *
13  * * *
14  * * *
15  * * *
16  * * *
17  * * *
18  * * *
19  google-public-dns-a.google.com (8.8.8.8)  168.872 ms  150.776 ms  161.775 ms

この時の通信の様子をWiresharkで見てみると以下のようになります。 TTLを1から順に増やしつつ、それぞれ3回送っていることがわかります。

f:id:cipepser:20170305211345p:plain f:id:cipepser:20170305211351p:plain f:id:cipepser:20170305211358p:plain

勘の良い方はすでにお気づきかと思いますが、 tracerouteの結果が*ではないものはTime Exceeded Messageを返しています。 逆に言えば、*になっている箇所は応答がありません。

さらに詳しく見るためにTTLを設定したpingを打ってみましょう。 -mオプションでpingTTLを設定できます。 長いですが、以下結果です。
192.168.43.11は自ホストのアドレスです。

$ ping -m 1 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 2 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 3 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
36 bytes from osk009nasgw111.iij.net (202.32.116.105): Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  00 5400 248e   0 0000  01  01 9958 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 4 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
76 bytes from osk004bb01.iij.net (202.32.116.5): Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  00 5400 80d2   0 0000  01  01 3d14 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 5 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
36 bytes from osk004ix51.iij.net (58.138.107.222): Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  00 5400 1fb3   0 0000  01  01 9e33 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 6 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
36 bytes from 72.14.210.182: Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  00 5400 3fb3   0 0000  01  01 7e33 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 7 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
36 bytes from 108.170.243.66: Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  80 5400 acc6   0 0000  01  01 10a0 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 8 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
148 bytes from 209.85.255.163: Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  80 5400 5d6e   0 0000  01  01 5ff8 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 9 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
148 bytes from 72.14.233.211: Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  80 5400 13e9   0 0000  02  01 a87d 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 10 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
36 bytes from 72.14.235.77: Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  80 5400 6b01   0 0000  01  01 5265 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 11 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 12 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 13 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 14 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 15 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 16 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 17 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 18 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 19 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
64 bytes from 8.8.8.8: icmp_seq=0 ttl=46 time=166.696 ms

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 1 packets received, 0.0% packet loss
round-trip min/avg/max/stddev = 166.696/166.696/166.696/0.000 ms

確かにtracerouteの結果が*ではないものはTime Exceeded Messageを返していることがわかります。 しかもその応答をTTL=0となったホップが返しているので、送信元アドレス(=tracerouteで表示するアドレス)もわかりました。
逆に*になっている箇所はpacket lossで応答なしのため、表示することができず、代替手段として*を表示するしかないようですね。
またTTL=19の最終の宛先では、通常のping応答と同様のメッセージが返ってきているので、これを自分でtracerouteを実装するとしたら、「応答があったこと」を条件にループ止めるなどで実装できそうですね。

結論

tracerouteの結果、経路の途中で*になるのは、そのホップが応答を返さないとき(フォワードのみする)。

Reference