【第2章】言語処理100本ノックでPythonに入門

この記事は拙著言語処理100本ノックでPythonに入門の続きです。
100本ノック第2章に取り組みながらPython（とUnixコマンド）の基礎を学びたい方向けです。

12番くらいまでできればほぼPythonの基礎はほぼOKです。

あとは少し細かい知識を地道に身に着けていく感じになると思います。
まずは問題文で指示されたファイルを適当な方法でダウンロードします。

$ wget https://nlp100.github.io/data/popular-names.txt

問題文の補足

自然言語処理においては、巨大なテキストファイルを1行ずつ処理したいという場面が多く、この章の問題もそうなっています。

1行が1データになっていて、列が項目に分けられているような構造を表現する形式にはTSV (Tab-Separated Values)やCSV (Comma-Separated Values) などがよく用いられます。この章で扱うファイルはタブ区切りなのでTSVですね。

（紛らわしいのですが、このような形式をまとめてCSV (Character-Separated Values) と呼ぶこともあります。）

解答例の方針

この章の問題はpandasや標準ライブラリのcsvを使って解くこともできますが、そこまで必要性を感じられないので最も素朴な方法を解説していきます。ちなみに、解答例のコーディングスタイルはPEP8に従っているつもりです。例えば変数名・関数名はsnake_caseにする、インデントは半角スペース4つにする等です。

Unixコマンドについて

オプション・パイプ・リダイレクト・lessに馴染みが無い人はこちらのQiita記事の1・3節を読んでおいてください。そして$ less popular-names.txtでダウンロードしたファイルの中身を確認してみましょう。

コマンド名については問題文で指定されるので、知らなくても--helpを駆使すれば使えると思います。ただ、この章で登場するUnixのコマンドのほとんどはよく使うものなので、できれば覚えておきましょう。

ファイル読み込み

Cではファイルポインタを駆使していましたが、Pythonではファイルオブジェクトという便利なデータ型を使います。ファイルオブジェクトはイテラブルなので、テキストファイルを1行ずつ読みたいときは次のように書きます。

with open('popular-names.txt') as f:
    for line in f:
        print(line, end='')

with構文は、f = open('popular-names.txt')の実行と、ブロックを抜けるときのf.close()を勝手にやってくれる優れものです。公式ドキュメントでも良い習慣であるとされているので、ぜひ使いましょう。

for文の各ループではlineに各行の内容が代入されています。

ファイルを一度に複数個使うときはwith open('test1') as f1, open('test2') as f2のようにカンマを使います。

標準入力を一行ずつ読みたいときはsys.stdinを使います。これもファイルオブジェクトです。この章の問題は全て上の方法でできるのですが、標準入力を使う方が何かと便利です。

import sys

for line in sys.stdin:
    print(line, end='')

（標準入力は最初からopen()されているのでwithは不要、と考えてください。）

（一部Unixコマンドは標準入力もファイル名も受け付ける仕様になってますが、Pythonでそこまでやるのはやや面倒です→参考記事）

10. 行数のカウント

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

Pythonスクリプトを保存してpopular-names.txtを標準入力から受け取って実行してみましょう。

以下、解答例です。

q10.py

import sys

i = 0
for line in sys.stdin:
    i += 1
print(i)

$ python q10.py < popular-names.txt

2780

PythonではCのi++は使えないので累算代入演算子+=を使いましょう。

（f.read().splitlines(), f.readlines(), list(f)はファイルサイズが大きいときや、複雑な処理をしたいときに困るので避けてます）

少しエレガントな方法にも触れておきます。sys.stdinはイテラブルであること、Pythonのforブロックはスコープを形成しないことを利用します。

import sys


i = 0
for i, _ in enumerate(sys.stdin, start=1):
    pass

print(i)

ループ回数を数える組み込み関数enumerate()が活躍します。使わない戻り値を_で受けるのはPythonの慣習みたいなものです。pass文は何もしたくないけど文法上何かを書く必要があるときに使います。

確認はwcコマンド(word count)を使います。普通に使うといろいろ出てくるのでオプション-l, --linesを指定します。

$ wc -l popular-names.txt

2780 popular-names.txt

11. タブをスペースに置換

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

str.replace(old, new)を使ってみましょう。このメソッドは文字列中の部分文字列oldをnewに置換して返します。タブ文字はCと同じように\tとします。

以下、解答例です。

q11.py

import sys


for line in sys.stdin:
    print(line.replace('\t', ' '), end='')

行数が多いので結果の確認はpython q11.py < popular-names.txt | less等でやりましょう。

Unixコマンドは3つ挙げられてますがsed -e 's/\t/ /g' popular-names.txtが一番ポピュラーですね。Twitterでも自分の誤字をリプでこのように修正する人をたまに見かけます。sedはStream EDitor の略で多機能なコマンドです。

個人的にはs/\t/ /gの部分が面倒なのでtr '\t' ' ' < popular-names.txtを使いますかね...

とはいえsedは知っておくべきコマンドで、sed -n 10pで10行目を抽出、sed -n 10,20pで10～20行目を抽出、みたいなこともできるので便利です。

ファイル書き込み

次の問題ではファイル書き込みについて学びます。テキストファイルを書き込みモードで開くときはopen(filename, 'w)を使います。

with open('test', 'w') as fo:
    # fo.write('hoge')
    print('hoge', file=fo)

書き込むときはwrite()メソッドを使っても良いですが、改行を付け忘れたりする等やや不便なので、print()のオプション引数fileを使うのが良いと思います。

12. 1列目をcol1.txtに，2列目をcol2.txtに保存

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

以下、解答例です。

q12.py

import sys


with open('col1.txt', 'w') as fo1,\
     open('col2.txt', 'w') as fo2:
    for line in sys.stdin:
        cols = line.rstrip('\n').split('\t')
        print(cols[0], file=fo1)
        print(cols[1], file=fo2)

2つのopen()は1行にまとめて書いても良かったのですが、バックスラッシュ\を使うことで改行しても文が継続していると見なされます。

popular-names.txtの読み込みにもopen()を使っても良いのですが、with文が更に長くなることをきらって標準入力から読み込む方式にしてます。

line.rstrip('\n').split('\t')の部分ですがこれはメソッドチェインと呼ばれるもので、左からメソッドが順々に実行されます。この問題ではrstrip()しなくても結果は変わりませんが、cols[-1]に改行文字が含まれてしまうのを防ぐためのものです。テキストを読み込むときに習慣のように行う処理です。

Unixコマンドはcutにオプション-f, --fieldsを指定すればOKです。コマンドを2回実行しても良いですが&&で一気にいけます。

!cut -f1 popular-names.txt > col1.txt && cut -f2 popular-names.txt > col2.txt

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

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

これは簡単ですね。以下、解答例です。

q13.py

with open('col1.txt') as fi1,\
     open('col2.txt') as fi2:
    for col1, col2 in zip(fi1, fi2):
        col1 = col1.rstrip()
        col2 = col2.rstrip()
        print(f'{col1}\t{col2}')

Writing q13.py

組み込み関数zip()の出番です。rstrip()は引数を省略すると末尾のあらゆる改行文字・空白文字を除去します。

（入力ファイルが3つ以上になることを考えると、zip()の戻り値を1つの変数で受け取ってjoin()する方式が良いでしょう。さらに挙動をpasteコマンドに近づけようとすると大変です。こちらの記事をお読みください。）

Unixコマンドはpaste col1.txt col2.txtでOKです。

14. 先頭からN行を出力

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

コマンドライン引数はsys.argvで取得できますが、argparseを使う方が何かと便利です。使い方は、公式の素晴らしいチュートリアルの最初から「短いオプション」までを読んでください...

ファイルオブジェクトはシーケンス型ではないのでスライスが使えません。他の方法で行数を数えましょう。

以下、解答例です。

q14.py

import argparse
import sys


def arg_lines():
    parser = argparse.ArgumentParser()
    parser.add_argument('-n', '--lines', default=1, type=int)
    args = parser.parse_args()
    return args.lines


def head(N):
    for i, line in enumerate(sys.stdin):
        if i < N:
            print(line, end='')
        else:
            break


if __name__ == '__main__':
    head(arg_lines())

$ python q14.py -n 10 < popular-names.txt

次の問題で使いまわすため、argparse部分を単独で関数化してます。if __name__ == '__main__':でメインの処理がimport時に勝手に実行されるのを防いでいます。

(うるさいことを言うと、if __name__ == '__main__':以下に長々と処理を書くのは良くありません。変数が全てグローバルになるからです。Pythonはグローバル変数のアクセスが遅いのでパフォーマンスが下がるというデメリットも生じます。実は今まで関数化せずにベタ書きしてたコードも関数化することでほんのわずかに速くなります。）

breakはforブロックの中で使う制御文で、ただちにfor文を抜けます。continue（ただちに次のループに移動する）と併せて覚えておきましょう。

head()関数はもう少しエレガントに書けます。

import sys
from itertools import islice

def head(N):
    for line in islice(sys.stdin, N):
        print(line, end='')

Unixコマンドはhead -n 5 popular-names.txt等で良いです。オプションを省略するとデフォルトの値(おそらく10)で実行されます。

11番の解説時、行数が長いのでパイプでlessに渡す等してくださいと書きましたが、最初の方だけ確認したいときはheadで十分でしたね。

パイプでこれらのコマンドを渡すと終了時にBroken Pipe Errorと出ると思います。
これを防ぎたい人はhead popular-names.txt | python q11.pyのように先にheadするか、python q11.py < popular-names.txt 2>/dev/null | headのようにエラー出力を捨てるかしましょう。

15. 末尾のN行を出力

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

Pythonのファイルオブジェクト(sys.stdinやopen()の戻り値)は、ファイルポインタを先頭から進めていくことしかできません（原則）。1回行数を数えてからもう1回ファイルを開きなおして...とやるのは無駄が多いです。readlines()して後ろをスライス...とやるのはメモリの浪費です。

ここはキューという先入れ後出しのデータ構造を知っていればスマートにできます。つまり、長さNのキューにファイルの中身を1行ずつどんどん入れていけば良いのです。するとキューの長さからはみ出た要素が勝手に出ていくので、最終的にキューの中には末尾N行だけが残るというわけです。

Pythonにおけるキューの実装はcollectionsモジュールのdequeを使いましょう。というかもう公式ドキュメントのdequeのレシピにtail()の例が書いてあるので、それがほぼこの問題の答えです。

以下、解答例です。

q15.py

from collections import deque
import sys

from q14 import arg_lines


def tail(N):
    buf = deque(sys.stdin, N)
    print(''.join(buf))


if __name__ == '__main__':
    tail(arg_lines())

dequeはリスト同様for文で回すこともできます。今まではリストをfor文で回してprint()してましたが、join()して一気にprint()する方が速いです（参考）。14番もprint(''.join(islice(sys.stdin, N)), end='')で十分でした。

Unixコマンドはtail -n 5でOKです。

以下、少し難易度が上がりますがぜひ理解してほしい話です。

イテラブルとイテレータ

前回の記事で「for文で回せるものをイテラブルという」と説明しました。ここで今まで出てきたイテラブルなデータ型 (+α)を分類すると次のようになります。細かい用語を覚えること自体に必要性は無いですが、今後新しいデータ型と出会ったときに何と似ているのかがわかると楽になることがあります。

• Iterable
  • Iterator
    • 組み込み関数zip(), enumerate()の戻り値
    • ファイルオブジェクト
    • itertools.islice()の戻り値
    • Generator（後段で説明します）
  • Collection
    • Sequence
      • list, tuple, str, range, colections.deque
    • Set
      • set, frozenset（変更不能な集合型）
    • Mapping
      • dict, collections.Counter, collections.defaultdict

ここでイテレータ (Iterator) について説明します（これまで騙し騙し扱っていました）。リストなどのデータ型は全要素を一度にメモリにのっけるので大きなサイズになると扱いにくいです。また、len()やインデクスを使う必要が無くただfor文や、str.join()などの引数で利用するだけの場合は無駄が多いです。特にループを最後の要素まで回す必要が無い場合に、後ろの方の要素まで生成するのは無駄な手間です。そのような欠点を解消したのがイテレータです。イテレータは１ループで１つの要素を返すだけなので、メモリを効率的に扱えるという利点があります。スライスは使えませんが、itertools.islice()でそれっぽいことができます。また、一度ループを回し切ってしまうと何もできなくなります。このような制約があるので、専らfor文やイテラブルを引数にとる関数で使います。

for文だけなくin演算やlen()に対応しているデータ型をコレクションと言ったりコンテナと言ったりします（公式ドキュメントではコンテナとされているが、抽象基底クラスの定義上はコレクションの方が厳密）。

シーケンス型のものは全てインデクスやスライスが使えます。

collectionsモジュールにはdequeの他にもCounterやdefaultdictといった便利なデータ型が定義されているので、これも知っておきましょう。この後の問題で使うかもしれません。

リスト内包表記とジェネレータ式

イテラブルオブジェクトに対して、ひとつずつ全要素に何らかの操作をしたいときや、条件に合う要素だけ抽出したいときがあります。そうした処理を簡潔に記述できるのが内包表記、およびジェネレータ式です。100本ノック03「円周率」の例で説明します。

tokens = 'Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics.'.split()

# リスト内包表記
stripped_list = [len(token.rstrip('.,')) for token in tokens]
print(stripped_list)

[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]

まずリスト内包表記から。以前はfor文の中でappend()していましたが、リスト内包表記ではappend()したいものを先に書き、後ろにfor文をくっつけて[]で囲みます。少しとっつきにくいかもしれませんが、こちらの書き方の方が高速に動作するので（参考）積極的に使いましょう。

次はジェネレータ式です。ジェネレータ式の戻り値はジェネレータ型といい、イテレータの一種です。イテレータは改めてfor文で回すか、別の関数に渡すという形でしか使えません。どちらかというと後者の方が普通の利用法です。

# ジェネレータ式
stripped_iter = (len(token.rstrip('.,')) for token in tokens)

for token in stripped_iter:
    print(token, end=' ')

3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 

' '.join(str(len(token.rstrip('.,'))) for token in tokens)

'3 1 4 1 5 9 2 6 5 3 5 8 9 7 9'

このように、ジェネレータ式はリスト内包表記の[]を()にしただけです。ただし関数の引数に渡すときはその()を省略できます。

関数にジェネレータ式を渡すと中間変数が減らせるというメリットがあります。リスト（内包表記）を渡す場合と比べると、メモリ使用量を減らせますし、多くの場合ジェネレータ式の方が高速です。

（稀にリストを渡すほうが高速な関数があり、このjoin()もその例外の一つのようです...）

ジェネレータ関数

ジェネレータ式は複雑な処理をしたいときには書きにくいという問題点があります。そこでイテレータを返す関数を定義したい場合があります。最も簡単な方法はyield文を使う方法で、そのようにして定義したものをジェネレータ関数と言います。もちろんジェネレータ関数が生成するオブジェクトもジェネレータ型です。

ジェネレータ関数を定義するには、yield 戻り値を関数の動作の「途中」（または最後）に置きます。returnはそこで関数の処理が終了させられ、関数内ローカル変数は消え去るという点が大きく異なります。

def tokens2lengths(tokens):
    for token in tokens:
        yield len(token.rstrip('.,'))

for token in tokens2lengths(tokens):
    print(token, end=' ')

3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 

何、ありがたみがわからないですって？そうかもしれないですね...。この2章でジェネレータ関数は使わないですね...。再帰関数の記述が簡単になるとは言われているが、再帰関数自体あまり書かない…。個人的には、次のような場合に使います。まず自作関数processがあったとします。

for elem in lis:
    if elem is not None:
        outstr = process(elem)
        print(outstr)

このコードはlisの要素数が多くなってくると関数呼び出し時間が馬鹿になりません。そこでprocessをジェネレータ関数化すると若干高速になります。条件式を吸収させることもでき、メイン関数がスッキリします。

for outstr in iter_process(lis):
    print(outstr)

ちょっと本筋ではない話が長くなってしまいました。次の問題を解きましょう。

とても細かい用語の揺れ

ドキュメントでは、ジェネレータとは通常ジェネレータ関数のことを指す、ジェネレータ関数が生成するオブジェクトはジェネレータイテレータと言う、という記述があります。しかしtype()関数を使ってジェネレータ関数（およびジェネレータ式）の戻り値の型を調べるとGeneratorと出てきます。このため、公式が言うジェネレータイテレータは非公式文書ではジェネレータと呼ばれることが多い気がします。

16. ファイルをN分割する

自然数Nをコマンドライン引数などの手段で受け取り，入力のファイルを行単位でN分割せよ．同様の処理をsplitコマンドで実現せよ．

難問です。いろいろな方法が考えられますが、ファイルの中身を一度にメモリに載せない縛りを貫くには、最初に全体の行数を数えてから分割するしか無さそうです。ファイルオブジェクトの参照点を先頭に戻すにはもう一回ファイルを開きなおすか、f.seek(0)（先頭0バイトを参照するという意味）を使うとできます。

そしてできるだけ均等になるようにN分割する方法が悩ましいです。例えば14行のものを4分割する場合は4行, 4行, 3行, 3行という具合に分けたいです。考えてみましょう。

それができれば4行読んで書き込むだけです。fi.readline()という、1行だけ読むメソッドがあるのですが、それの出番かもしれません。書き込み先はおそらく別々のファイルにするべきです。

以下、解答例です。

q16.py

import argparse
import sys


def main():
    parser = argparse.ArgumentParser(
        description='Output pieces of FILE to FILE1, FILE2, ...;')
    parser.add_argument('file')
    parser.add_argument('-n', '--number', type=int,
                        help='split FILE into n pieces')
    args = parser.parse_args()
    file_split(args.file, args.number)


def file_split(filename, N):
    with open(filename) as fi:
        n_lines = sum(1 for _ in fi)
        fi.seek(0)
        for nth, width in enumerate((n_lines+i)//N for i in range(N)):
            with open(f'{filename}.split{nth}', 'w') as fo:
                for _ in range(width):
                    fo.write(fi.readline())


if __name__ == '__main__':
    main()

$ python q16.py -n 3 popular-names.txt
$ wc -l popular-names.txt.split*

  926 popular-names.txt.split0
  927 popular-names.txt.split1
  927 popular-names.txt.split2
 2780 total

argparseの使い方は気にしなくて良いです。行数を数えるのに、今回はイテラブルの要素和を計算する組み込み関数sum()を使っています。

そして整数を均等に分ける方法です。m個のものをn人に分けるとき商はqで余りがrになったとしましょう。
このときは(n-r)人には普通にq個ずつ配って、残りのr人には余りを１個上乗せして(q+1)個ずつ配ると均等になります。

それをエレガントに書いたのが((n_lines+i)//N for i in range(N))の部分です。//で小数点切り捨て除算ができます。なぜこれで均等に分けられるのかはこちらのQiita記事をご覧ください。

行の順番を気にしない方針だとitertoolsのtee()とislice()を使う方法などが考えられます。メモリを気にしない方針だとzip_longest()を使うと簡単かもしれません。

Unixコマンドはsplit -n l/5 -d popular-names.txt popular-names.txtで良いですが、お使いの環境のsplitによっては動かないかもしれません。

後の問題は楽です。

17. １列目の文字列の異なり

1列目の文字列の種類（異なる文字列の集合）を求めよ．確認にはsort, uniqコマンドを用いよ．

集合に一列目をどんどん追加していくだけですね。リスト内包表記だけ上で説明しましたが、セット内包表記や辞書内包表記もあります。

以下、解答例です。

q17.py

import sys


names = {line.split('\t')[0] for line in sys.stdin}
print('\n'.join(names))

集合型は実行の度に順序が変わることに気を付けましょう。それが嫌であれば辞書型を使いましょう（CPython実装では3.6以降、公式には3.7以降の辞書型はkeyの追加順になります）。

Unixコマンドはcut -f1 popular-names.txt | sort | uniqになります。uniqは隣り合う行の重複を取り除くものなので、このようなことをするにはsortが必要です。

ラムダ式とソート

次の問題で一応使うのでラムダ式についてやっておきます。ラムダ式はちょっとした関数を定義するのに使います。例えばlambda a, b: a+bと書けばそれはもう２つの数の和を返す関数です。普通の関数のように呼び出すことも可能ですが、sort()関数のオプション引数として渡す使い方が主です。一応他の関数に渡したり、自作関数の戻り値に使ったりすることはあります。

sort()については公式のソート HOW TOが良い資料です。「昇順と降順」まで読めば十分です。

18. 各行を3コラム目の数値の降順にソート

各行を3コラム目の数値の逆順で整列せよ（注意: 各行の内容は変更せずに並び替えよ）．確認にはsortコマンドを用いよ（この問題はコマンドで実行した時の結果と合わなくてもよい）．

（コラムとは...さっきまで列って言ってたのに...）以下、解答例です。

q18.py

import sys


sorted_list = sorted(sys.stdin, key=lambda x: int(x.split('\t')[2]), reverse=True)
print(''.join(sorted_list))

3列目の数値は数値型にキャストしないと文字列のままであることに注意しましょう。キャストは組み込み関数でできます。

Unixコマンドはsort -k3 -nr popular-names.txtです。3番目の要素を数字と見なして昇順でソート、という意味です。

Unixのsortは大変優秀で、巨大なファイルだろうとout of memoryを起こさず実行してくれます。さらに比較的簡単に高速化できます(ロケールをいじる、分割して最後にマージする等)。

19. 各行の1コラム目の文字列の出現頻度を求め，出現頻度の高い順に並べる

各行の1列目の文字列の出現頻度を求め，その高い順に並べて表示せよ．確認にはcut, uniq, sortコマンドを用いよ．

ここでcollections.Counterの伏線が回収されました！ドキュメントを読めば問題無いでしょう。Counterはdictのサブクラスであるということもおさえておきましょう。

以下、解答例です。

q19.py

from collections import Counter
import sys


col1_freq = Counter(line.split('\t')[0] for line in sys.stdin)
for elem, num in col1_freq.most_common():
    print(num, elem)

Unixコマンドはcut -f1 popular-names.txt | sort | uniq -c | sort -nrです。パイプが連なるときはひとつひとつheadなどを使って中間出力を確認してみるのがいいと思います。

まとめ

• Unixコマンドの基礎
• ファイル読み書き
• str.replace()
• argparse
• collections
• イテレータとジェネレータ
• 内包表記
• ラムダ式とソート

次は３章

JSONファイルはjsonモジュールで読み込めます。正規表現については公式の正規表現 HOW TOで学びましょう。LGTMやコメントがあれば続編を執筆します。

(4/30追記)
第3章の解説を公開しました。→　https://qiita.com/hi-asano/items/8e303425052781d95f09