言語処理100本ノック第3章で学ぶ正規表現

## はじめに

社内のメンバーを中心にした勉強会で[言語処理100本ノック](http://www.cl.ecei.tohoku.ac.jp/nlp100)を解いているのですが、その解答コードや、解く過程で便利だなと思った小技のまとめです。自分で調べたり検証したりした内容が多いですが、他の勉強会メンバーが共有してくれた情報も入っています。

今回は正規表現ですが、初歩的な内容から手強い難問まで揃っていて解き応えがありました。

自分はこれまで本格的に正規表現を学ぶ機会がなかったので事前に基礎知識をおさらいしたのですが、[本家Pythonのドキュメント](https://docs.python.org/ja/3/library/re.html)や[WWWクリエイターズ](http://www-creators.com/archives/4278)のページが読みやすくまとまっていて助けになりました。チュートリアルっぽいドキュメントとしてはRubyの達人[伊藤さん](https://qiita.com/jnchito/items/893c887fbf19e17d3ff9)が書いたものもあり、行き詰まったときの参考になるかと思います。

## シリーズ

- [言語処理100本ノック第2章で学ぶUNIXコマンド](https://qiita.com/Yusuke196/items/35668859ea70bc9539f5)
- [言語処理100本ノック第3章で学ぶ正規表現](https://qiita.com/Yusuke196/items/47203be382f60d653da7)（この記事）
- [言語処理100本ノック第4章で学ぶ形態素解析](https://qiita.com/Yusuke196/items/b41e70b3a60cbac25294)

## 環境

- macOS
- Python 3.8.1
- JupyterLab

## コード

### 前処理

ipynb（またはPython）ファイルと同じディレクトリに`jawiki-country.json.gz`を置いて

```bash
!gzip -d jawiki-country.json.gz
```

とすると、zipを解凍できます。

### 20. JSONデータの読み込み

```py
import json

def load_uk():
    with open('jawiki-country.json') as file:
        for item in file:
            d = json.loads(item)

            if d['title'] == 'イギリス':
                return d['text']

print(load_uk())
```

```:結果
{{redirect|UK}}
{{基礎情報 国
|略名 = イギリス
|日本語国名 = グレートブリテン及び北アイルランド連合王国
|公式国名 = {{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>
...
```

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

```py
import re

def extract_categ_lines():
    return re.findall(r'.*Category.*', load_uk())

print(*extract_categ_lines())
```

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

問題文に「行を抽出」という言葉が入っているので、まず`split()`を使って`load_uk()`の戻り値を行ごとに切り分けたくなる気もしますが、そういった処理は必須ではありません。`.`は「改行を除く任意の一文字」を表すので、上のように書けば`Category`という文字列を含む行だけを取り出せます。

### 22. カテゴリ名の抽出

```py
def extract_categs():
    return re.findall(r'.*Category:(.*?)\]', load_uk())
    
print(*extract_categs())
```

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

`Category:`の直後の文字列を取得するべく`()`で囲ってキャプチャします。ただし、その後ろにある`]`もまとめて取ってしまわないよう、`*`の後ろに`?`をつけて非貪欲に（最短一致するように指定）しました。

### 23. セクション構造

```py
def extract_sects():
    tuples = re.findall(r'(={2,})\s*([^\s=]*).*', load_uk())

    sects = []
    for t in tuples:
        if t[0] == '==':
            sects.append([t[1], 1])
        elif t[0] == '===':
            sects.append([t[1], 2])
        elif t[0] == '====':
            sects.append([t[1], 3])

    return sects

print(*extract_sects())
```

```:結果
['国名', 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]
```

`^\s=`は「空白でも`=`でもない任意の文字」という意味なので、`[^\s=]+`は「空白でも`=`でもない任意の文字が1つ以上続いたもの」ということになります。これが今回取得したい値の1つ目であるセクション名ですね。これに加えて`={2,}`を`()`で囲んでおくと、「`=`が2つ以上続いたもの」が取れます。

マッチ1回につき、以上の2つの値が入ったタプルが1つ返ってくるので、あとはそれを使いつつ`for`文で返り値を作りました。返り値の形式については指定がないのでこだわらなくてよいと思いますが、自分は配列の配列としました。

ちなみに、上のコードではまず`sects`というリストを用意しておいて、そこに要素を入れていき、最後に返すというステップを踏んでいますが、`yield`を使うとそのあたりをもう少し簡潔に書けます。

```py
def extract_sects_2():
    tuples = re.findall(r'(={2,})\s*([^\s=]+).*', load_uk())

    for t in tuples:
        if t[0] == '==':
            yield [t[1], 1]
        elif t[0] == '===':
            yield [t[1], 2]
        elif t[0] == '====':
            yield [t[1], 3]

print(*extract_sects_2())
```

`yield`を使った関数はジェネレータと呼ばれ、イテレータ（ジェネレータ・イテレータ）を返すのですが（詳しくは[Pythonのドキュメント](https://docs.python.org/ja/3/glossary.html#term-generator)を参照）、そのイテレータは上記のように`*`を前につけて展開したり、`list()`に渡すことでリストに変換したりできるようです。

### 24. ファイル参照の抽出

```py
def extract_media_files():
    return re.findall(r'(?:File|ファイル):(.+?)\|', load_uk())

extract_media_files()
```

```:結果
['Royal Coat of Arms of the United Kingdom.svg',
 'Battle of Waterloo 1815.PNG',
 'The British Empire.png',
 'Uk topo en.jpg',
 'BenNevis2005.jpg',
 ...
```

「`File`または`ファイル`」を表現するために`()`を使わないといけないのですが、ここをキャプチャしたいわけではないので`(`の直後に`?:`を書きました。

ちなみに最終行で`print()`を使っていないのは、ここでリストなどを返すとJupyterが勝手に整形してから出力してくれるためです。

### 25. テンプレートの抽出

```py
def extract_template():
    data = re.search(r'\{\{基礎情報.*\n\}\}', load_uk(), re.DOTALL).group()
    tuples = re.findall(r'\n\|(.+?)\s=\s(.+?)(?:(?=\n\|)|(?=\}\}\n))', data, re.DOTALL)

    return dict(tuples)

extract_template()
```

```:結果

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

個人的には、この章で一番苦労した問題でした。とはいえ苦労の過程も勉強になったので、問題の核心となる`re.findall()`の部分について少し詳しく書いておきます。ここでどのような正規表現を使うか考えるとき、おそらく最初は

```py
re.findall(r'\n\|(.+)\s=\s(.+)\n\|', data)
```

のようなコードが頭に浮かぶかと思います。しかし、これを実行してみると`'日本語国名': 'グレートブリテン及び北アイルランド連合王国',`など偶数番目に取りたかった部分が取れていないことが分かります。この原因は、

`\n|略名 = イギリス\n|日本語国名`

のような文字列があったとき、上の正規表現だと`\n|略名 = イギリス\n|`がマッチしたあと、次のマッチを探し始めるのは`日`から後ろの文字列になってしまうためです（[ドキュメント](https://docs.python.org/ja/3/library/re.html)の表現を使うなら、上の正規表現は`日`の前の`\n|`を「消費」してしまうため、うまくいかない）。

ではどうするかというと、`\n|`が消費されないようにするための「先読み」という方法があります。コードとしては、正規表現の`\n\|`を`(?=)`で囲って以下のようにすればOKです。

```py
re.findall(r'\n\|(.+)\s=\s(.+)(?=\n\|)', load_uk())
```

これでもう一度実行すると、`日本語国名`などの行もきちんと取れているはずです。ただ、ここで取得された文字列をよく見ると、公式国名について説明した部分が最初の一行しか含まれていません。これは、2つ目の`()`の中に書かれた`.+`はこのままだと「改行（`\n`）を除く任意の文字が1つ以上続いたもの」にマッチする、つまり行をまたいで取得するということができないためです。

そこで、`findall()`に`re.DOTALL`というモジュールを渡します。そうすると、`.+`は「任意の文字が1つ以上続いたもの」を取ってきてくれるようになるのですが、`+`を貪欲なままにしておくと逆に取得しすぎてしまうので後ろに`?`をつけることにしましょう。

```py
re.findall(r'\n\|(.+?)\s=\s(.+?)(?=\n\|)', load_uk(), re.DOTALL)
```

これでおおよそOKかと思いますが、返ってくる結果をよく見ると最後のところで取得し過ぎるという問題があります。そこで、パターンの後ろの文字列を先読みして`}}\n`だった場合もマッチするよう、次のように修正します。

```py
re.findall(r'\n\|(.+?)\s=\s(.+?)(?:(?=\n\|)|(?=\}\}\n))', data, re.DOTALL)
```

これでようやく問題文の指定を満たすコードが書けましたが、一行にいろいろ詰め込み過ぎていると感じる場合は、以下のように`re.complile()`を使って行を分けるのもありだと思います。

```py
pattern = re.compile(r'\n\|(.+?)\s=\s(.+?)(?:(?=\n\|)|(?=\}\}\n))', re.DOTALL)
tuples = pattern.findall(data)
```

なお、正規表現の部分にも改行を入れたい場合は`re.DOTALL`の後に`+ re.MULTILINE`をつけるといった方法もあるようです。

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

```py
def remove_emphases():
    d = extract_template()
    return {key: re.sub(r'\'{2,5}', '', val) for key, val in d.items()}

remove_emphases()
```

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

25に比べると、正規表現については基礎的な知識だけで解ける問題ですが、`2,`の後に空白を入れてしまうと場合によって動かないという注意点があります。

辞書の内包表記はPython独特の記法かと思いますが、慣れてくると簡潔に書けるので個人的にはよく使っています。

### 27. 内部リンクの除去

```py
def remove_links():
    d = remove_emphases()
    return {key: re.sub(r'\[\[.*?\|?(.+?)\]\]', r'\\1', val) for key, val in d.items()}

remove_links()
```

```:結果
{'略名': 'イギリス',
 '日本語国名': 'グレートブリテン及び北アイルランド連合王国',
 '公式国名': '{{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>\n*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}（スコットランド・ゲール語）<br/>\n*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}（ウェールズ語）<br/>\n*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}（アイルランド語）<br/>\n*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}（コーンウォール語）<br/>\n*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}（スコットランド語）<br/>\n**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}（アルスター・スコットランド語）</ref>',
 '国旗画像': 'Flag of the United Kingdom.svg',
 '国章画像': 'ファイル:Royal Coat of Arms of the United Kingdom.svg|85px|イギリスの国章',
 ...
```

やりたいことを「`[[]]`で囲まれている箇所があったら、その中身を取り出す。ただし、その中に`|`があったら`|`の後ろだけを取り出す」と定義して解いてみました。`|`は出てくるか出てこないか分からないので、後ろに`?`をつけて0回または1回の繰り返しにマッチするよう指定しています。

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

```py
def remove_markups():
    d = remove_links()
    # 外部リンクを除去
    d = {key: re.sub(r'\[http:.+?\s(.+?)\]', '\\1', val) for key, val in d.items()}
    # ref（開始タグも終了タグもまとめて）とbrを除去
    d = {key: re.sub(r'</?(ref|br).*?>', '', val) for key, val in d.items()}
    return d

remove_markups()
```

```:結果
{'略名': 'イギリス',
 '日本語国名': 'グレートブリテン及び北アイルランド連合王国',
 '公式国名': '{{lang|en|United Kingdom of Great Britain and Northern Ireland}}英語以外での正式国名:\n*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}（スコットランド・ゲール語）\n*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}（ウェールズ語）\n*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}（アイルランド語）\n*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}（コーンウォール語）\n*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}（スコットランド語）\n**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}（アルスター・スコットランド語）',
 '国旗画像': 'Flag of the United Kingdom.svg',
 ...
 '人口値': '63,181,775United Nations Department of Economic and Social Affairs>Population Division>Data>Population>Total Population',
 ...
```

`{{lang|.+?|.+?}}`のようなパターンも除去すべきかと思いましたが、~~疲れてきたので~~ 早見表には載っていなかったので今回はそのままとしました。

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

```py
import requests
import json

def get_flag_url():
    d = remove_markup()['国旗画像']
    
    url = 'https://www.mediawiki.org/w/api.php'
    params = {'action': 'query',
              'titles': f'File:{d}',
              'format': 'json',
              'prop': 'imageinfo',
              'iiprop': 'url'}
    res = requests.get(url, params)

    return res.json()['query']['pages']['-1']['imageinfo'][0]['url']

get_flag_url()
```

```:結果
'https://upload.wikimedia.org/wikipedia/commons/a/ae/Flag_of_the_United_Kingdom.svg'
```

最後だけ急にHTTPの知識を問うような問題。リクエストとレスポンスについて知らないと少し解きにくいと思います。よく分からないのでざっくり理解したいという場合は[こちら](https://www.youtube.com/watch?v=zq50JwOU_ls&t=91s)の動画、もう少し詳しく知りたければ[MDNのドキュメント](https://developer.mozilla.org/ja/docs/Web/HTTP/Overview)が参考になるかもしれません。

この問題では、MediaWiki APIにPythonなどでGETリクエストを投げると返ってくるレスポンスから国旗画像のURLを抜き出せばいいのですが、そのためには特別にモジュールをインポートする必要があります。

外部パッケージをインストールする手間をかけたくなければurllib.requestを使うこともできるようですが、自分は過去にインストールしていたこともあってrequestsを使うことにしました。こちらの方がコードが簡潔になりますし、MediaWikiの[こちら](https://www.mediawiki.org/wiki/API:Imageinfo#Example)のページにあるサンプルほか、広く使われているので書きやすいかなという気がします。

ちなみに中盤の7行は下のように2行で書くこともできますが、この場合はURLが横に伸びすぎてしまうので、上記のように行を分けるなどした方がよいでしょう。

```py
url = f'https://www.mediawiki.org/w/api.php?action=query&titles=File:{d}&format=json&prop=imageinfo&iiprop=url'    
res = requests.get(url)
```

## まとめ

正規表現は言語処理に限らずWeb開発などでも使われるツールですが、この章は様々なトピックを広くカバーしていて、いい教材だと感じました。

以上、正確かつ簡潔なコードを目指して書きましたが、もし間違いなどありましたらコメントお願いします。