「言語処理100本ノック 2015」ではじめるPythonとNLPスキルのリハビリテーション（第1章）


http://www.cl.ecei.tohoku.ac.jp/nlp100/
がリニューアルされて、2015年版が公開されているようですね。

大好きなpython(2系)を使って取り組んでみました。
類似の記事がいっぱいあるのは知っていますが、（そして参照していますが）
http://qiita.com/tanaka0325/items/08831b96b684d7ecb2f7
自分の進捗メモ＋共有の意味も兼ねて公開です。
ご指摘などあれば、よろしくお願いいたします。


第2章以降も続けたいものです・・・「リハビリ」は続けてこそ意味がある！

# 第1章: 準備運動

## 00. 文字列の逆順
> 文字列"stressed"の文字を逆に（末尾から先頭に向かって）並べた文字列を得よ．

```py:愚直に
text = "stressed"
text_reverse = ""
n = len(text)
for i in xrange(n):
    text_reverse += text[n-i-1]
print text_reverse
#>>> desserts
```
添え字を使って愚直に末尾から先頭まで取得。text=""の時も動作します。


```py:改良版
text = "stressed"
n = len(text)
text_reverse_list = [text[n-i-1] for i in xrange(n)]
text_reverse = ''.join(text_reverse_list)

print text_reverse
#>>> desserts
```

追記：
文字列にforループで連結していくのは、実行速度、メモリの面でよくないそう。
なので「文字列のリストを作る→joinでつなげる」方法を参考にさせていただきました。

```py:スライス
text = "stressed"
text_reverse = text[::-1]
print text_reverse
#>>> desserts
```
スライスを使ってシンプルに。
文字列オブジェクト[開始インデックス:終了インデックス:ステップ]


## 01. 「パタトクカシーー」
> 「パタトクカシーー」という文字列の1,3,5,7文字目を取り出して連結した文字列を得よ．

```py:
text = u"パタトクカシーー"
text_concat = text[0] + text[2] + text[4] + text[6]
print text_concat
#>>> パトカー
```

文字列をunicodeで与えてしまってますが。

```py:
text = u"パタトクカシーー"
text_concat = text[::2]
print text_concat
#>>> パトカー
```
なるほど、スライスを使えば同じようにできるのか。


## 02. 「パトカー」＋「タクシー」＝「パタトクカシーー」
> 「パトカー」＋「タクシー」の文字を先頭から交互に連結して文字列「パタトクカシーー」を得よ．

```py:
text1 = u"パトカー"
text2 = u"タクシー"
text_concat = ""
m = len(text1)
n = len(text2)
for i in xrange(m):
    if i<n:
        text_concat += text1[i] + text2[i]
        if i == m-1:
            text_concat += text2[i+1:]
    else:
        text_concat += text1[i:]
        break

print text_concat
#>>> パタトクカシーー
```

2つの文字列を先頭から見ていきます。
この問題では直接問題にならないですが、
text1とtext2の長さが同じじゃない(m!=n)場合も考慮してみます。
このときは片方が終了したら、
もう片方はそれ以降の文字列を連結することにしました。


## 03. 円周率
> "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."という文を単語に分解し，各単語の（アルファベットの）文字数を先頭から出現順に並べたリストを作成せよ．

```py:
sentence = "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."

word_length = [len(x.strip(',.')) for x in sentence.split()]
print word_length
#>>> [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
```

- リスト内包表記

こんな感じでスマートにワンライナーできちゃうところもpythonいいですね。


## 04. 元素記号
> "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文字を取り出し，取り出した文字列から単語の位置（先頭から何番目の単語か）への連想配列（辞書型もしくはマップ型）を作成せよ．

```py:
sentence = "Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can."

word_list = [x.strip(',.') for x in sentence.split()]
word_dict = dict()
specified = [1, 5, 6, 7, 8, 9, 15, 16, 19]
for i, word in enumerate(word_list):
    if i in [x-1 for x in specified]:
        word_dict[word[:1]] = i+1
    else:
        word_dict[word[:2]] = i+1

print word_dict
#>>> {'Be': 4, 'C': 6, 'B': 5, 'Ca': 20, 'F': 9, 'S': 16, 'H': 1, 'K': 19, 'Al': 13, 'Mi': 12, 'Ne': 10, 'O': 8, 'Li': 3, 'P': 15, 'Si': 14, 'Ar': 18, 'Na': 11, 'N': 7, 'Cl': 17, 'He': 2}
print word_dict['Be']
#>>> 4
```

word_dictにi+1を入れて、問題で与えられた「番目」との整合性をとってます。
そうか、解き終わって気づいたけど、「原子番号、つまり陽子の数」が得られてるのか。
「すいへー、りーべー、ぼくのふね」って懐かしい。

・・・と思いきや、マグネシウムは'Mg'では？

```py:
'Mi': 12
```


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


```py:
def n_gram(sentence_str, n, type):
    result = set()
    if type == 'word':
        words = [x.strip(',.') for x in sentence_str.split()]
    elif type == 'letter':
        words = sentence_str
    m = len(words)
    for i in xrange(m-n+1):
        result.add(tuple(words[i:i+n]))
    return result

# 頻度情報も欲しい場合
from collections import defaultdict
def n_gram_freq(sentence_str, n, type):
    result = defaultdict(int)
    if type == 'word':
        words = [x.strip(',.') for x in sentence_str.split()]
    elif type == 'letter':
        words = sentence_str
    m = len(words)
    for i in xrange(m-n+1):
        result[tuple(words[i:i+n])] += 1
    return result


sentence_str = "I am an NLPer"
#sentence_list = ['I', 'am', 'an', 'NLPer']

print n_gram(sentence_str, 2, 'word')
#>>> set([('am', 'an'), ('an', 'NLPer'), ('I', 'am')])
print n_gram(sentence_str, 2, 'letter')
#>>> set([('N', 'L'), ('m', ' '), ('e', 'r'), ('a', 'n'), ('I', ' '), ('n', ' '), ('L', 'P'), (' ', 'N'), (' ', 'a'), ('a', 'm'), ('P', 'e')])


print n_gram_freq(sentence_str, 2, 'word')
#>>> defaultdict(<type 'int'>, {('am', 'an'): 1, ('an', 'NLPer'): 1, ('I', 'am'): 1})
print n_gram_freq(sentence_str, 2, 'letter')
#>>>defaultdict(<type 'int'>, {('N', 'L'): 1, ('m', ' '): 1, ('e', 'r'): 1, ('a', 'n'): 1, ('I', ' '): 1, ('n', ' '): 1, ('L', 'P'): 1, (' ', 'N'): 1, (' ', 'a'): 2, ('a', 'm'): 1, ('P', 'e'): 1})
```

文字列を引数としておきます。
別の引数typeで、単語n-gram・文字n-gramを選択できるようにします。


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

```py:
str_x = "paraparaparadise"
str_y = "paragraph"

X = n_gram(str_x, 2, 'letter')
Y = n_gram(str_y, 2, 'letter')

print X.union(Y) # 和集合。X | Y と同義
#>>>set([('g', 'r'), ('p', 'h'), ('p', 'a'), ('s', 'e'), ('a', 'p'), ('a', 'g'), ('a', 'd'), ('i', 's'), ('r', 'a'), ('a', 'r'), ('d', 'i')])

print X.intersection(Y) # 積集合。X & Y と同義
#>>>set([('a', 'p'), ('r', 'a'), ('p', 'a'), ('a', 'r')])

print X.difference(Y) # 差集合。X - Y と同義
#>>>set([('a', 'd'), ('s', 'e'), ('d', 'i'), ('i', 's')])

tuple('se') in X
#>>> True
tuple('se') in Y
#>>> False
```

前問で定義した関数を使います。
関数の定義上、与えられた'se'はtupleに変換して、条件判定しています。


## 07. テンプレートによる文生成
> 引数x, y, zを受け取り「x時のyはz」という文字列を返す関数を実装せよ．さらに，x=12, y="気温", z=22.4として，実行結果を確認せよ．

```py:
from string import Template

def generate_sentence(x,y,z):
    t = Template("${x_tmpl}時の${y_tmpl}は${z_tmpl}")
    return t.safe_substitute(x_tmpl=x, y_tmpl=y, z_tmpl=z)

def generate_sentence_incomplete(x,y,z):
    t = Template("${x_tmpl}時の${y_tmpl}は${z_tmpl}")
    return t.safe_substitute(x_tmpl=x, y_tmpl=y)

x, y, z =12, "気温", 22.4
print generate_sentence(x,y,z)
#>>> 12時の気温は22.4
print generate_sentence_incomplete(x,y,z)
#>>> 12時の気温は${z_tmpl}
```

Template.safe_substitute()を使ったので、
http://docs.python.jp/2/library/string.html#string.Template.safe_substitute
> substitute() と同じですが、プレースホルダに対応するものを mapping や kws から見つけられなかった場合に、 KeyError 例外を送出する代わりにもとのプレースホルダがそのまま入ります。


## 08. 暗号文
> 与えられた文字列の各文字を，以下の仕様で変換する関数cipherを実装せよ．
> 英小文字ならば(219 - 文字コード)の文字に置換
> その他の文字はそのまま出力
> この関数を用い，英語のメッセージを暗号化・復号化せよ．


```py:

def cipher(input_str):
    result = ""
    for letter in input_str:
        # 英小文字ならば
        if letter.isalpha() and letter.islower():
            result += chr(219-ord(letter))
        else:
            result += letter
    return result

english_message = "This is a pen."

# 暗号化
print cipher(english_message)
#>>> Tsrh rh z kvm.

# 復号化
print cipher(cipher(english_message))
#>>> This is a pen.
```

この題材は知りませんでしたが、アトバシュ暗号と言うそうですね。
http://www.mitsubishielectric.co.jp/security/learn/info/misty/stage1.html

> 旧約聖書の中にも暗号が使われていました。その一つがヘブライ語の換字式暗号アトバシュ。この暗号は、文字に番号をつけて、最初からの順番と末尾からの順番を入れ替えて作ります。アルファベット26文字を暗号にする場合には、AをZに、BをYに、というように順番を置き替えて作ります。

そういうわけなので、暗号化と復号化を同じ関数で実現できる
（同じ関数を2回適用することで、元の文字列が得られる）んですね。

使った組み込み関数はこちら。

```py:組み込み関数
str.isalpha()
str.islower()
ord()
chr()
unichr()

# http://docs.python.jp/2.6/library/functions.html#ord
# http://docs.python.jp/2.6/library/functions.html#chr
# http://docs.python.jp/2.6/library/functions.html#unichr
```

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

```py:
import random

def random_shuffled_str(input_str):
    input_list = list(input_str)
    random.shuffle(input_list)
    result = ''.join(input_list)
    return result

def typoglycemia(sentence):
    str_list = sentence.split()
    result_list = [x[0]+ random_shuffled_str(x[1:-1]) +x[-1] if len(x) > 4 else x for x in str_list]
    return ' '.join(result_list)

message = "I couldn't believe that I could actually understand what I was reading : the phenomenal power of the human mind ."

print typoglycemia(message)
#>>> I cunl'dot beveile that I cloud aallucty unsrndtead what I was rdaineg : the phaenmneol pweor of the huamn mind .

print typoglycemia(message)
#>>> I cu'dolnt bivelee that I cloud aculltay udetnnasrd what I was ridneag : the pheonaenml peowr of the hamun mind .

```

リストの内包表記でelseを使いたいとき、

```py:
if len(x) > 4 else x
```
ってこの位置に持ってくるんだ・・・。
そして、random.shuffle。

- 引数で与えたリスト（など）を直接変更する。
 - ので変更された結果をリスト内包表記の中で得られるように関数を定義した。

http://docs.python.jp/2/library/random.html

>random.shuffle(x[, random])
>シーケンス x を直接変更によって混ぜます。オプションの引数 random は、値域が [0.0, 1.0) のランダムな浮動小数点数を返すような引数を持たない関数です; 標準では、この関数は random() です。

> かなり小さい len(x) であっても、 x の順列はほとんどの乱数生成器の周期よりも大きくなるので注意してください; このことは長いシーケンスに対してはほとんどの順列は生成されないことを意味します。