言語処理100本ノック with Python（第2章・前編）


# はじめに

自然言語処理と Python のトレーニングのため，東北大学の乾・岡崎研究室 Web ページにて公開されている[言語処理100本ノック](http://www.cl.ecei.tohoku.ac.jp/nlp100/)に挑戦していきます．その中で実装したコードや，抑えておくべきテクニック等々をメモしていく予定です．コードについては[GitHub](https://github.com/gamma1129/nlp100)でも公開していきます．

[第1章](http://qiita.com/gamma1129/items/37bf660cf4e4b21d4267)の続きです．
ここだけは Python だけではなく， UNIX コマンドの説明もちょいちょい挟めれば良いかなと思っています． 
UNIX コマンドの細かいオプションなどについては `man` コマンドや，[ITpro さんのウェブサイト](http://itpro.nikkeibp.co.jp)などで確認するとちゃんと勉強になると思います！


# 第2章: UNIXコマンドの基礎
> hightemp.txtは，日本の最高気温の記録を「都道府県」「地点」「℃」「日」のタブ区切り形式で格納したファイルである．以下の処理を行うプログラムを作成し，hightemp.txtを入力ファイルとして実行せよ．さらに，同様の処理をUNIXコマンドでも実行し，プログラムの実行結果を確認せよ．

## 10. 行数のカウント
> 行数をカウントせよ．確認にはwcコマンドを用いよ．

### Python での回答

```python:10.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 10.py

import sys

f = open(sys.argv[1])
lines = f.readlines()
print(len(lines))

f.close()
```

#### python 回答へのコメント
問題文にて「hightemp.txt を入力ファイルとして〜」って書いてあるので， `sys.argv` を利用してコマンドライン引数を取れるように設計しました．
実行時には `$ python 10.py high temp.txt` としているので，この場合 `sys.argv[0] == "10.py"`，`sys.argv[1] == "hightemp.txt"` という文字列を格納していることになります．

ファイルの読み込みに関しては，

1. `f = open(ファイル名)`
2. `hoge = f.read() / f.readline() / f.readlines()`
3.  `f.close()`

という流れで行っていきます．
2\. で出てきた3種類の関数はそれぞれ以下のような動作をしてくれます．必要に応じて使い分けてください．

* `read()`
    * 指定されたファイルを文字列として一括で読み込む．
* `readline()`
    * 指定されたファイルを1行ずつ読み込む．なのでループ回すごとに `readline()` が実行されるようにコードを書く必要がある．これ以外の `read() / readlines()` は一括読み込みなので，大規模ファイルや条件に合致したら終了する場合などはこちらがおすすめ．
* `readlines()`
    * 指定されたファイルを1行ごとの文字列のリストとして一括で読み込む．今回は行数が知りたかったので，このリストの長さを求めることで算出（`len()`）．

#### `with` を利用したパターン
ファイルの読み込み（書き込み）については，前述のように `close()` を伴う書き方の他に，`with` を利用する書き方があります．`with` を利用するとよくある `close()` のつけ忘れや，例外処理のし忘れなどを防げるためにこちらの方が推奨されているようです．
試しに `10.py` を `with` を使って書き換えたものが以下のプログラムになります．

```python:with構文を利用した場合
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# 10.py

import sys

with open(sys.argv[1]) as f:
    lines = f.readlines()

print(len(lines))

```

以降，原則的にファイルの読み書きは `with` を使っていきます．`with` じゃ書けない場合（あるのかな？）のみレガシーな書き方でプログラミングします．

### UNIX での回答

```bash
$ wc -l hightemp.txt
      24 hightemp.txt
```

#### UNIX 回答へのコメント
`wc` コマンドを使うとファイルの行数，単語数，バイト数を表示してくれる．
オプションを指定しなければ以下のように順番に出力してくれる．

```bash
$ wc hightemp.txt 
      24      98     813 hightemp.txt
```

オプションは `-l` で行数，`-w` で単語数，`-c` でバイト数．


## 11. タブをスペースに置換
> タブ1文字につきスペース1文字に置換せよ．確認にはsedコマンド，trコマンド，もしくはexpandコマンドを用いよ．

### Python での回答
```python:11.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 11.py

import sys

with open(sys.argv[1]) as f:
    str = f.read()

print(str.replace("\t", " "))

```

#### Python 回答へのコメント
行に着目した先ほどは異なり，今回は文字を一括で置換したいだけなのでシンプルに `read()` を使用．
前章でも出てきた `replace()` 関数でタブ文字（`\t`）をスペースで置換しています．
~~出力結果の最後に余計な改行が残ってしまうのがちょっと嫌だけど，まあその辺はご愛嬌…？~~
`print()` ではデフォルトで最後に改行が入ってしまいます．これを回避するには，Python 2 であれば `print "hogehoge", ` といったように末尾にカンマを付記すれば大丈夫です．Python 3 であれば `print("hogehoge", end="")` といったように，`end` で末尾に追加される文字を指定できるので `""` を指定してあげれば大丈夫です．

### UNIX での回答

```bash
// sed version（環境に依存するので注意）
$ sed -e s/$'\t'/" "/g hightemp.txt
// tr version
$ cat hightemp.txt | tr "\t" " "
// expand version
$ expand -t 1 hightemp.txt

//結果は同じ
高知県 江川崎 41 2013-08-12
埼玉県 熊谷 40.9 2007-08-16
岐阜県 多治見 40.9 2007-08-16
（中略...）
山梨県 大月 39.9 1990-07-19
山形県 鶴岡 39.9 1978-08-03
愛知県 名古屋 39.9 1942-08-02

```

#### UNIX 回答へのコメント
`sed` はさまざまな文字編集をこなせる便利なコマンドですが，今回のように限られた用途（文字置換）ならそれ用のコマンド（`tr`）を利用するほうが賢いのでは． 
`expand` は逆に用途が限定されすぎているので，なかなか触れる機会はないかも？

* `sed` 
 * `-e` とオプション指定して，その後に行いたい処理を記述するとその結果を標準出力に出力してくれる．記法は独特かもしれないけど，Vim ユーザであれば見覚えのある書き方かもしれない．
 * 結構環境に依存するらしく，動いてくれる書き方を探すのに結構骨が折れた...注意！
* `tr`
 * 文字置換コマンド．文字置換だけでなく，オプションで大文字を小文字にしたりとかもできて地味に汎用性は高そう．
* `expand` 
 * タブをスペースに変換してくれる．オプション `-t` でタブ幅の指定が可能．

## 12. 1列目をcol1.txtに，2列目をcol2.txtに保存
> 各行の1列目だけを抜き出したものをcol1.txtに，2列目だけを抜き出したものをcol2.txtとしてファイルに保存せよ．確認にはcutコマンドを用いよ．

### Python での回答

```python:12.py
#! /usr/bin/env python
# -*- coding:utf-8 -*-
# 12.py

import sys


def write_col(source_lines, colunm_number, filename):
    col = []
    for line in source_lines:
        col.append(line.split()[colunm_number] + "\n")
    with open(filename, "w") as writer:
        writer.writelines(col)


with open(sys.argv[1]) as f:
    lines = f.readlines()

write_col(lines, 0, "col1.txt")
write_col(lines, 1, "col2.txt")


```

#### Python 回答へのコメント
似たような処理を行うので関数化しました．第1引数で受け取った `list` の，第2引数で指定した行を，第3引数の文字列をファイル名として書き込みます．`append()` する際に改行文字を追加して体裁を整えています．

目新しい技術は使っていないのでコメントはこれくらいになりますが，プログラムによってアルゴリズムがバラバラなのが我ながら恥ずかしい…
詳しくは後述しますが，反省も兼ねてそのまま掲載．

### UNIX での回答

```bash
$ cut -f 1 hightemp.txt
高知県
埼玉県
岐阜県
（中略...）
山梨県
山形県
愛知県
$ cut -f 2 hightemp.txt
江川崎
熊谷
多治見
（中略...）
大月
鶴岡
名古屋

```

#### UNIX 回答へのコメント

やっている内容は Python と同じく，`-f` でフィールド（行）を指定しています．Python では zero-based（0行目，1行目...）だったのに対して UNIX コマンドでは one-based（1行目，2行目...）となっている点に注意．

## 13. col1.txtとcol2.txtをマージ

> 12で作ったcol1.txtとcol2.txtを結合し，元のファイルの1列目と2列目をタブ区切りで並べたテキストファイルを作成せよ．確認にはpasteコマンドを用いよ．

### Python での回答

```python:13.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 13.py

with open("col1.txt") as f1, open("col2.txt") as f2:
    lines1, lines2 = f1.readlines(), f2.readlines()

with open("merge.txt", "w") as writer:
    for col1, col2 in zip(lines1, lines2):
        writer.write("\t".join([col1.rstrip(), col2]))

```

#### Python 回答へのコメント

Python にも慣れてきたので，前半の読み込み部はちょっとこなれた感じで書いてみました．こういう書き方ができるのは強い．
後半の書き込み部は，第1章の復習を兼ねて `zip()` を利用した書き方にしてみました．12.とは逆に今回は `col1, col2` の末尾に両方共改行文字が残っているので，`col1` の末尾の改行文字を `rstrip()` で除いています．

復習ついでに内包記法で書き直したものがこちら．

```python:内包記法で書き直した場合
# カッコ内であればコード中に改行してもちゃんと解釈してくれる
with open("merge.txt", "w") as writer:
    writer.write(
        "\n".join(
            ["\t".join([col1.rstrip(), col2.rstrip()])
                for col1, col2 in zip(lines1, lines2)]
        )
    )
    
```

#### 実行時間の比較

様々な記法が出てきたので，`timeit` を利用して各手法の実行時間を計測・比較してみました．

```python:timeitを利用した実行時間計測プログラム
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 13_timeit.py

import timeit

# 前処理; col1,col2.txt を読み込む
s0 = """
with open("col1.txt") as f1, open("col2.txt") as f2:
    lines1, lines2 = f1.readlines(), f2.readlines()
"""

# naive な実装; 文字列を足し合わせる
s1 = """
merged_txt = ""
for i in xrange(len(lines1)):
    merged_txt = merged_txt + lines1[i].rstrip() + "\t" + lines2[i]

with open("merge.txt", "w") as writer:
    writer.write(merged_txt)
"""

# zip を利用した実装
s2 = """
with open("merge.txt", "w") as writer:
    for col1, col2 in zip(lines1, lines2):
        writer.write("\t".join([col1.rstrip(), col2]))
"""

# 内包記法(connotation)による実装
# "\\n" と書かないと SyntaxError になる…何で？
s3 = """
with open("merge.txt", "w") as writer:
    writer.write(
        "\\n".join(
            ["\t".join([col1.rstrip(), col2.rstrip()])
                for col1, col2 in zip(lines1, lines2)]
        )
    )
"""

print("naive:", timeit.repeat(stmt=s1, setup=s0, number=100000))
print("zip:", timeit.repeat(stmt=s2, setup=s0, number=100000))
print("connotation:", timeit.repeat(stmt=s3, setup=s0, number=100000))

```
3種類の手法で3回（デフォルト），ループを100000周回した際の計算時間（秒）です．
[公式ドキュメント](http://docs.python.jp/2/library/timeit.html)によれば実行時間は平均や最大値ではなく，最小値で評価すべきとのこと．


```bash:実行結果
$ python 13_timeit.py
('naive:', [32.61601686477661, 47.96871089935303, 33.15881299972534])
('zip:', [49.846755027770996, 45.05450105667114, 58.70397615432739])
('connotation:', [46.472286224365234, 52.708040952682495, 46.71139121055603])
```
結果，実行時間だけで言えば単純に文字列を足し合わせた方式が一番優秀でした．順番を入れ替えても同じく．
一般的に内包記法では高速化が期待できるらしいのですが，高速化できる/できないの境界って一体何なのでしょう．

### UNIX での回答

```bash
$ paste col1.txt col2.txt 
高知県	江川崎
埼玉県	熊谷
岐阜県	多治見
（中略...）
山梨県	大月
山形県	鶴岡
愛知県	名古屋

```

#### UNIX 回答へのコメント
`paste` コマンドはファイルを水平方向に連結してくれる．
区切り文字はタブがデフォルトだけど，`-d` オプションで指定可能．
## 14. 先頭からN行を出力

> 自然数Nをコマンドライン引数などの手段で受け取り，入力のうち先頭のN行だけを表示せよ．確認にはheadコマンドを用いよ．

### Python での回答
```python:14.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 14.py

# Usage: python 14.py [filename] [number of lines]

import sys

with open(sys.argv[1]) as f:
    lines = f.readlines()

for line in lines[:int(sys.argv[2])]:
    print line,

```

#### Python 回答へのコメント

最初は `xrange()` を使った以下のような実装にしていたのですが，

```python:xrange()を利用した実装
# 前略

for i in xrange(int(sys.argv[2])):
    print lines[i],

```
こうするとファイルの行数を超える数を指定したときに `IndexError` が出てしまうので，スライスを使った実装のほうが賢いかなーと思います．
そもそも入力値のチェックをしてない・エラー処理を書いてないってのが問題だとは思いますが…
出力に関しては以前 11. でご説明したように，`print` 文の末尾に `,`  を付記することで余計な改行を除きました．

### UNIX での回答

```bash
$ head -3 hightemp.txt
高知県	江川崎	41	2013-08-12
埼玉県	熊谷	40.9	2007-08-16
岐阜県	多治見	40.9	2007-08-16 

```

#### UNIX 回答へのコメント
こちらもシンプルに，オプションで行数を指定できます．

## 15. 末尾のN行を出力

> 自然数Nをコマンドライン引数などの手段で受け取り，入力のうち末尾のN行だけを表示せよ．確認にはtailコマンドを用いよ．

### Python での回答
```python:15.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 15.py

import sys

with open(sys.argv[1]) as f:
    lines = f.readlines()

for line in lines[len(lines) - int(sys.argv[2]):]:
    print line,

```

#### Python 回答へのコメント
ひとつ前の 14. とほぼ同じです．スライスの指定がわずかに複雑にはなっていますが．

### UNIX での回答

```bash
$ tail -3 hightemp.txt

山梨県	大月	39.9	1990-07-19
山形県	鶴岡	39.9	1978-08-03
愛知県	名古屋	39.9	1942-08-02
```

#### UNIX 回答へのコメント
`head` とほぼ同様．


# おわりに
長くなってしまったので2章に関する記事を分割しました．
第2章・後編に続きます．