"Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can."という文を単語に分解し，1, 5, 6, 7, 8, 9, 15, 16, 19番目の単語は先頭の1文字，それ以外の単語は先頭に2文字を取り出し，取り出した文字列から単語の位置（先頭から何番目の単語か）への連想配列（辞書型もしくはマップ型）を作成せよ．

gist9992125ab064053287a0dd4dd4ae4c0a

マグネシウム......

05. n-gram

与えられたシーケンス（文字列やリストなど）からn-gramを作る関数を作成せよ．この関数を用い，"I am an NLPer"という文から単語bi-gram，文字bi-gramを得よ．

gistcbc1ee78191bf3f77d7a49df56d45a19

結構めんどくさかったものの、文字列はruneとして扱って、最後表示するときだけstringにするほうがバグの混入も減りそうな気がしました。

06. 集合

"paraparaparadise"と"paragraph"に含まれる文字bi-gramの集合を，それぞれ, XとYとして求め，XとYの和集合，積集合，差集合を求めよ．さらに，'se'というbi-gramがXおよびYに含まれるかどうかを調べよ．

giste1d1767b1727a65b3d4b1702cfab0dbc

sliceに対してappendだけじゃなくてremoveも欲しくなりました。

07. テンプレートによる文生成

引数x, y, zを受け取り「x時のyはz」という文字列を返す関数を実装せよ．さらに，x=12, y="気温", z=22.4として，実行結果を確認せよ．

gist916d6c7abb3721d8c4df8e285afc51b2

08. 暗号文

与えられた文字列の各文字を，以下の仕様で変換する関数cipherを実装せよ．

英小文字ならば(219 - 文字コード)の文字に置換その他の文字はそのまま出力この関数を用い，英語のメッセージを暗号化・復号化せよ．

gist89bee82fa497b427b37eef97744b58ce

09. Typoglycemia

スペースで区切られた単語列に対して，各単語の先頭と末尾の文字は残し，それ以外の文字の順序をランダムに並び替えるプログラムを作成せよ．ただし，長さが４以下の単語は並び替えないこととする．適当な英語の文（例えば"I couldn't believe that I could actually understand what I was reading : the phenomenal power of the human mind ."）を与え，その実行結果を確認せよ．

gist72bf7cadaab3f3219dab0349223925ad

部分配列取り出すとき、a[0:3]のようにしたときa[0], a[1], a[2]が取り出されてa[3]は含まれないのをいつも勘違いするので気をつけていきたいです。

Reference

2016-12-25

Golomb-coded setについて調べてみた

Oku KazuhoさんのHTTP/2の課題と将来を拝見していたらGolomb-coded setなるものが登場したのでいろいろ調べたメモです。

BloomFilterについてもそのうち記事にするかもしれないです。
~~むしろBloomFilterを先に書くべきでは。~~

前提、やりたいこと

やりたいことの例としてhttp2のcache-aware server pushを考える。
clientからserverへリクエストするとき、htmlよりcssを先にpushするといったような優先度付けをしたい。
一方で、既にclientでcacheしていたら、改めてserverからpushするのは無駄。
そこでclientからのリクエスト中のcookieにcache済みのjsやcssといったasset情報埋め込んでserverに教えてあげる。

とはいえ、そのままassetごとにpath/file名とか書くと無駄が大きいし、file名は変わらないけど中身が変わっていたりすると区別ができなくてつらい。
→ハッシュして送る。

ここで偽陽性はある程度許容する。
やりたいことは、すでにcache済みだったら送らない(≒送る数を減らしたい)なので、確実にcacheされてないと言えるなら送る。
(偽陽性で、cache済みと判断したけど実はcacheされてないやつはclientが改めてGETする)
→BloomFilterのような確率的データ構造が適している。

BloomFilterの空間効率性

A. PaghらによるとBloomFilterにデータを格納するために必要なbit数は以下。

BloomFilterで使うbit数: $N log_2 \frac{1}{p} \times log_2 e$

確率的データ構造に使うbit数(理論値): $N log_2 \frac{1}{p}$

$N: 貯めておく要素数$
$p: 偽陽性確率$

$log_2 e ≒ 1.44$ なので44%程度、BloomFilterは理論値より空間効率が悪い。

挿入するデータの分布に適した方法でデータを格納すれば理論値に近づく。
→Golomb-coded setは、ハッシュ値の均一性を利用し、幾何分布のときにHuffman符号と同じ効率になるGolomb符号により理論値に近づける。

Golomb-coded set

※例は以下の参考文献のなぞり。

Golomb-coded sets: smaller than Bloom filters

変数はさっきと一緒。

$N: 貯めておく要素数$
$P: 偽陽性確率$

例題として以下のフォネティックコード( $N = 26$ )を考える。

['alpha', 'bravo', 'charlie', 'delta', 'echo', 'foxtrot', 'golf', 'hotel', 'india', 'juliet', 'kilo', 'lima', 'mike', 'november', 'oscar', 'papa', 'quebec', 'romeo', 'sierra', 'tango', 'uniform', 'victor', 'whiskey', 'xray', 'yankee', 'zulu']

許容する偽陽性確率を $P = \frac{1}{64}$ とする。

要素は適当なハッシュ取ってから $mod (N \times \frac{1}{P} (= 1664)$ する。

※cache-aware server pushで使う場面では、sha-2にするというようなセキュリティ性は担保しなくてよく、均一性と速度のほうが重要なのでMD5やsha-1で十分。

→ $[0, (N \times \frac{1}{P} ) ] = [0, 1664$ ]でハッシュ値が分布する。
ここで $N(= 26)$ 要素をハッシュ計算してからソートする。
十分に均一なハッシュならソート後の要素列のi番目とi+1番目の差は $\frac{1}{P} (=64)$ くらいになる(ことが多いと期待される)。
→ $\frac{1}{P} (=64)$ で割ると、商は0 or 1になることが多い。
→これ幾何分布となるのでGolomb符号使うと効率がよい。

符号化は以下の表のように行う。

商	符号化
0	0
1	10
2	110
3	1110
4	11110

余りはそのまま2進数でくっつける。
例) 68 / 64 = 1 ... 4 → 68 = 0b(10 100)
※10と100の間のblankは便宜的に入れてるだけ。

これでフォネティックコードを符号化すると以下になる(197 bits)。

11001011 10101001 00100000 11110111 10000000 01100110 00111010 00000110 00011111 00100000 01100101 00011001 10001010 10110001 00000011 00101101 01100010 01001100 01010000 00110011 00011110 01100110 10101110 10011000 00011

それぞれデータの格納に必要なbit数は以下のようになるので、BloomFilterより理論値に近くなっていることがわかる。

理論値: 156 bits  
BloomFilter: 225 bits (最適なハッシュ関数の数で同じ偽陽性確率を許容する場合)  
Golomb-coded set: 197 bits

参考

2016-12-23

「トランプを3枚出してその積を103で割った余りの値の元素をいかに早く言うか」をGolangとMySQLで実装する

背景

こちらのツイートが流れてきたのでgolangで実装してみました。

「トランプを3枚出してその積を103で割った余りの値の元素をいかに早く言うか」

環境

CentOS Linux release 7.2.1511 (Core)

mysql Ver 14.14 Distrib 5.7.17, for Linux (x86_64) using EditLine wrapper

go version go1.6.3 linux/amd64

事前準備

環境変数

mysql用のdriverをgo getするためにも必要なのでGOPATHを設定します。

$ export GOPATH=<path>

またMySQLに接続するためのパスワードを環境変数から取得するため、設定します。

$ export MYSQL_PASSWD=<password>

MySQLのインストール

GoでMySQLに接続するにある go-sql-driver/mysql のインストール を行います。

$ go get github.com/go-sql-driver/mysql

データベースの構築

今回はgolangでMySQLを叩いてみたかったので、データベースを構築しておきます。

データベース名: div3element

テーブル名: element

テーブルの構成は以下です。

mysql> show columns from element;
+--------+-------------+------+-----+---------+-------+
| Field  | Type        | Null | Key | Default | Extra |
+--------+-------------+------+-----+---------+-------+
| n      | int(11)     | NO   | PRI | NULL    |       |
| symbol | varchar(2)  | YES  |     | NULL    |       |
| name   | varchar(10) | YES  |     | NULL    |       |
+--------+-------------+------+-----+---------+-------+

nを原子番号として元素記号(symbol)、元素名(name)を引けるようにしています。

構築用のsqlはこちら

実装

gist30613d82a059a6a51c518d0d4026c452

コードはgithubにもあげています。

使い方

コンパイルしてから、以下のように標準入力から3つの数字を入力すると、原子番号と元素名を返します。

$ ./main 12 13 11
Answer: 68, エルビウム

感想

MySQLとの連携もできたので個人的には満足しています。

トランプ想定なので1-13以外の数字が来た場合の処理とか追加したほうがよかったかもなぁと思っています。

余談ですが、このゲーム、名前付いてるんでしょうか。名前があれば本記事のタイトルも悩まなくよかったんですが......。

Reference

2016-12-11

SECCON 2016 WriteUp

はじめに

SECCON2016に参加しました。

初CTFです。

開催されていることに当日気がついた程度の情弱ですが、とりあえず手を動かしてみたかったのでチャレンジしてみました。

結果1問解答でした。せっかくなのでwriteup残します。

Vigenère

問題

k: ????????????

p: SECCON{???????????????????????????????????}

c: LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ

k=key, p=plain, c=cipher, md5(p)=f528a6ab914c1ecf856a1d93103948fe

解答

Vigenère暗号です。

問題文にもWikipediaのリンク付きです。

ただオリジナルがアルファベット26文字に対して{,}の2文字が追加の28文字版です。

ASCIIコード見ながらAが0になるように65文字シフトさせます。

ただし、{と}はASCIIコードの123と125でZの次じゃないので、それぞれ[と\に置換して順番を揃えます。

pのSECCON{を対応表からkがk: VIGENE??????だとわかります。それならあと2文字も暗号名から推測してk: VIGENERE????でしょうか。この時点でとりあえず復号してみます。

c = 'LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ'
c = c.replace('{', '[')
c = c.replace('}', '\\')

p = len(c)*[0]

k = 'VIGENERE'
shift = 0 # len(k)ずつずらす

for i in range(len(k)):
    p[i] = (ord(c[i + shift]) - ord(k[i])) % 28
    p[i] = chr(p[i] + 65)

print p

ここまでで p: SECCON{A????BCDEDEFG????KLMNOPQR????VWXYYZ} とわかります。

いい感じにアルファベット順ですね。

残り4文字はcipherとかcryptとかかなぁと思ったものの文字数が合わないものの最初はCでいってみるかと思いやってみると p: SECCON{AB???BCDEDEFGH???KLMNOPQRS???VWXYYZ} となりました。

最初の???をBABとなれば綺麗かなぁと思って暗号文cを見ながら対応表を見て、k = 'VIGENERECODE'となったので良さそうです。あとは上記のコードそのままkだけ変えて終わりです。

p: SECCON{ABABABCDEDEFGHIJJKLMNOPQRSTTUVWXYYZ}

感想

Vigenèreはわりとすぐにできたのでもう1問!!と思ってVoIPやってみたのですが、何をしていいやらとなったので他の方のwriteup見て研鑽が必要です。

でもいろいろ記事ばっかり読んでいて自分で手を動かさないとwriteup読んでも楽しさが欠けるのでこれから数こなしていきたいです。

最後に。参加されたみなさん、お疲れ様でした。

運営の方、ありがとうございました。

2016-11-05

Golangのdeferの処理順序

背景

Jxckさんのgihyo連載でGoを触っていて、以下の記載を読んで、エラー処理でlog.Fatalとかしていたら実行されないのでどういう仕組なのか遊んだメモです。

先の例ではfile.Close()の関数呼び出しをdeferの後ろに記述すると，この処理がmain()を抜ける直前に必ず実行されるようになります。

処理順序

Golang の defer 文と panic/recover 機構についてにてdeferが記述されたstatementが関数を抜ける直前に実行されることがわかります。

(Jxckさんの記事では「必ず」じゃなくて「直前」ってほうが言いたいことだったんですね......)

上記に加えて複数defer付けたらどうなるのか試してみました。

gist7b299b8f60a9ac6a3296f9d8f09fbfa5

実行結果です。

[vagrant@localhost gihyotest]$ go run defer.go
execute this statement firstly
execute this statement secondly
execute this statement thirdly

後入れ先出しになっていることがわかります。

記事を書いてからReference見てたら Goブログでそのまんま同じことやっていますし、以下のように記載されていました。

Deferred function calls are executed in Last In First Out order after the surrounding function returns.

参考

2016-08-15

Googleクラウド自然言語APIをPostmanで遊ぶ

背景

Googleクラウド自然言語APIを使ってみたを拝読しました。自分でも試したいと思いつつもGoogle Cloud Platform(GCP)を使ったことがなかったので、せっかくの機会なので触ってみることにしました。

GCPのプロジェクト作成

CCPにログイン後、ホーム画面から「プロジェクトを作成」を押下します。

f:id:cipepser:20160815152042p:plain

「プロジェクト名」を入力し、「作成」を押下します。

ここでは「NLPtrial」としました。

(少し時間が掛かるようです) f:id:cipepser:20160815152047p:plain

認証情報の作成とAPIキーの取得

プロジェクトの作成が完了すると左上の方に作成したプロジェクト名が表示されているはずです。

この状態で「Google Cloud Natural Language API」で検索すると自然言語 APIが出てきます。

f:id:cipepser:20160815152050p:plain

有効にします。

f:id:cipepser:20160815152054p:plain

APIを有効にしたらAPIを使用するための認証情報を作成します。

今回は「APIキー」で「サーバーキー」を使用します。

(このあたりは初めて触ったのでもっと適切な設定がある気がします。。。)

f:id:cipepser:20160815152100p:plain f:id:cipepser:20160815152102p:plain f:id:cipepser:20160815152107p:plain

名前を適当に入力します。ここでは「nlp」としました。

IPアドレスは未入力で作成しました。 f:id:cipepser:20160815152114p:plain

APIキーが作成されます。

(画像では消していますが、赤枠のところに現れます)

APIを叩く際に利用するのでコピーしておきましょう。

f:id:cipepser:20160815152118p:plain

一覧でも見れます。 f:id:cipepser:20160815152121p:plain

APIを叩く前に

前ステップで取得したAPIキーを使用してAPIを叩くにあたって認証情報をどうやって送ればいいのか確認しておきます。

Setting up API keys

によると

The application passes this key into all API requests as a key=API_key parameter.

とのことです。

Best practices for securely using API keys には

Restrict your API keys to be used by only the IP addresses, referrer URLs, and mobile apps that need them:

の記述があるのですが、Refferヘッダから第三者に参照されてしまったりしないのか不安です。URLにパラメータ直書きで問題ないのでしょうか。

セキュリティ上よろしくないというようなことでしたご指摘ください。

APIを叩く

いよいよAPIを叩きます。

Entities(固有表現抽出)のAPI仕様は公式ドキュメントに記載があります。Typeについてはこちらから。

gist9a8307d8b14251d45999da818b2b084e

上記のような仕様に従ったjsonを以下にPOSTすればよいそうです。

https://language.googleapis.com/v1beta1/documents:analyzeEntities

手軽にやるために今回はPostmanを利用します。

リクエストを「POST」とし、上のURLに先ほど作成したAPIキーをパラメータとして渡してあげます。

あとはBodyにjsonを入れてSendするだけです。

f:id:cipepser:20160815152126p:plain

文章は何もおもいつかなかったので山月記の書き出しを拝借します。

隴西の李徴は博学才穎、天宝の末年、若くして名を虎榜に連ね、ついで江南尉に補せられたが、性、狷介、自ら恃むところ頗る厚く、賤吏に甘んずるを潔しとしなかった。

結果です。

gistb77a1571570c7bc080bfc3d6c89cf344

李徴はPERSONと出ていますし、URLも返ってきていますね。

各単語のbeginOffsetがわかるので、その単語が文章の何文字目か分かるようになっています。

一方で、隴西のように地名がPERSONとなってしまっていたり、

江南尉もORGANIZATIONとなっています。また天宝や狷介は結果も返ってきません。

感想

Googleクラウド自然言語APIを使ってみたでも言及されていますが、wikipediaから引っ張ってくるだけですし、今はちょっと微妙で、今後の発展次第ではもっとおもしろいことできそうかなーという感想です。

自然言語 APIというよりその前段階の認証の記事みたいになってしまったもののGCPに触れてよかったです。

繰り返しになりますが、認証のkeyの渡し方で問題があればご指摘ください。

背景

選択ソート

挿入ソート

感想

Reference

Golangで言語処理100本ノック2015 第1章: 準備運動

00. 文字列の逆順

01. 「パタトクカシーー」

02. 「パトカー」＋「タクシー」＝「パタトクカシーー」

03. 円周率

04. 元素記号

05. n-gram

06. 集合

07. テンプレートによる文生成

08. 暗号文

09. Typoglycemia

Reference

前提、やりたいこと

BloomFilterの空間効率性

Golomb-coded set

参考

背景

環境

事前準備

MySQLのインストール

データベースの構築

実装

使い方

感想

Reference

はじめに

Vigenère

問題

解答

感想

背景

処理順序

参考

背景

GCPのプロジェクト作成

認証情報の作成とAPIキーの取得

APIを叩く前に

APIを叩く

感想

参考