言語処理100本ノック-23:セクション構造

[言語処理100本ノック 2015](http://www.cl.ecei.tohoku.ac.jp/nlp100/)[「第3章: 正規表現」](http://www.cl.ecei.tohoku.ac.jp/nlp100/#ch3)の[23本目「セクション構造」](http://www.cl.ecei.tohoku.ac.jp/nlp100/#sec23)記録です。
今回は正規表現の**後方参照・m回の繰り返し**を学びます。

# 参考リンク

|リンク|備考|
|:--|:--|
|[023.セクション構造.ipynb](https://github.com/YoheiFukuhara/nlp100/blob/master/03.%E6%AD%A3%E8%A6%8F%E8%A1%A8%E7%8F%BE/023.%E3%82%BB%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3%E6%A7%8B%E9%80%A0.ipynb)|回答プログラムのGitHubリンク|
|[素人の言語処理100本ノック:23](http://qiita.com/segavvy/items/691ac169dd5b36e6a187)|多くのソース部分のコピペ元|
|[ゼロから覚えるPython正規表現の基本とTips](https://qiita.com/FukuharaYohei/items/459f27f0d7bbba551af7)|当ノックで学習した内容を整理しました|
|[正規表現 HOWTO](https://docs.python.org/ja/3/howto/regex.html#regex-howto)|Python公式の正規表現How To|
|[re --- 正規表現操作](https://docs.python.org/ja/3/library/re.html)|Python公式のreパッケージ説明|
|[Help:早見表](https://ja.wikipedia.org/wiki/Help:%E6%97%A9%E8%A6%8B%E8%A1%A8)|Wikipediaの代表的なマークアップの早見表|
# 環境

|種類|バージョン|内容|
|:--|:--|:--|
|OS|Ubuntu18.04.01 LTS|仮想で動かしています|
|pyenv|1.2.15|複数Python環境を使うことがあるのでpyenv使っています|
|Python|3.6.9|pyenv上でpython3.6.9を使っています<br>3.7や3.8系を使っていないことに深い理由はありません<br>パッケージはvenvを使って管理しています|

上記環境で、以下のPython追加パッケージを使っています。通常のpipでインストールするだけです。

|種類|バージョン|
|:--|:--|
|pandas|0.25.3|

# [第3章: 正規表現](http://www.cl.ecei.tohoku.ac.jp/nlp100/#ch3)
## 学習内容
> Wikipediaのページのマークアップ記述に正規表現を適用することで，様々な情報・知識を取り出します．
>> 正規表現, JSON, Wikipedia, InfoBox, ウェブサービス

## ノック内容
> Wikipediaの記事を以下のフォーマットで書き出したファイル[jawiki-country.json.gz](http://www.cl.ecei.tohoku.ac.jp/nlp100/data/jawiki-country.json.gz)がある．

> - 1行に1記事の情報がJSON形式で格納される
> - 各行には記事名が"title"キーに，記事本文が"text"キーの辞書オブジェクトに格納され，そのオブジェクトがJSON形式で書き出される
> - ファイル全体はgzipで圧縮される

> 以下の処理を行うプログラムを作成せよ．

### [23. セクション構造](http://www.cl.ecei.tohoku.ac.jp/nlp100/#sec23)
> 記事中に含まれるセクション名とそのレベル（例えば"== セクション名 =="なら1）を表示せよ．

### 課題補足(「セクション」について)
「セクション」は[Help:早見表](https://ja.wikipedia.org/wiki/Help:%E6%97%A9%E8%A6%8B%E8%A1%A8)での「見出し」のことで`== Level N ==`形式です(`N`の数だけ`=`が続きます)。
ファイル内の以下の部分を正規表現で抽出します。`=`の間にスペースがある場合もあります。

```text:ファイル内の「セクション」部分抜粋
==地理==
===気候===
=== 哲学 ===
```

# 回答
## 回答プログラム [023.セクション構造.ipynb](https://github.com/YoheiFukuhara/nlp100/blob/master/03.%E6%AD%A3%E8%A6%8F%E8%A1%A8%E7%8F%BE/023.%E3%82%BB%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3%E6%A7%8B%E9%80%A0.ipynb)

```python
import re

import pandas as pd

def extract_by_title(title):
    df_wiki = pd.read_json('jawiki-country.json', lines=True)
    return df_wiki[(df_wiki['title'] == title)]['text'].values[0]

wiki_body = extract_by_title('イギリス')

# rを先頭にするとraw string でエスケープシーケンス無視
# 3重クォートで途中改行無視
# re.VERBOSEオプションを使うことによって、空白とコメント無視
# re.MULTILINEで複数行に対して検索
# 非貪欲マッチにすることで、短い文字列を検索
sections = re.findall(r'''
                      ^         # 文字列の先頭
                      (={2,})   # キャプチャ対象、2回以上の'='
                      \s*       # 非キャプチャ、余分な0個以上の空白('哲学'や'婚姻'の前後に余分な空白があるので除去)
                      (.+?)     # キャプチャ対象、任意の文字が1文字以上、非貪欲(以降の条件の巻き込み防止)
                      \s*       # 非キャプチャ、余分な0個以上の空白
                      \1        # 後方参照、1番目のキャプチャ対象(={2,})と同じ内容
                      $         # 行末
                      ''', wiki_body, re.MULTILINE+re.VERBOSE)

for section in sections:
    level = len(section[0]) - 1    # '='の数-1
    print('{indent}{sect}({level})'.format(
        indent='\t'*(level-1), sect=section[1], level=level))
```

## 回答解説
今回のメインは以下の部分です。

```python:
sections = re.findall(r'''
                      ^         # 文字列の先頭
                      (={2,})   # キャプチャ対象、2回以上の'='
                      \s*       # 非キャプチャ、余分な0個以上の空白('哲学'や'婚姻'の前後に余分な空白があるので除去)
                      (.+?)     # キャプチャ対象、任意の文字が1文字以上、非貪欲(以降の条件の巻き込み防止)
                      \s*       # 非キャプチャ、余分な0個以上の空白
                      \1        # 後方参照、1番目のキャプチャ対象(={2,})と同じ内容
                      $         # 行末
                      ''', wiki_body, re.MULTILINE+re.VERBOSE)
```

### [m回の繰り返し](https://docs.python.org/ja/3/library/re.html#regular-expression-syntax)
`{m, n}`とすることで正規表現を`m`回から`n`回、できるだけ多く繰り返したものにマッチさせる結果の正規表現にします(貪欲マッチ)。
今回は`n`部分を省略しているので、上限がない2回以上の繰り返しです。
もし繰り返し回数を指定したい場合は{m}とし、非貪欲マッチにしたい場合は`{m, n}?`とします。

### [後方参照](https://qiita.com/FukuharaYohei/items/459f27f0d7bbba551af7#%E5%BE%8C%E6%96%B9%E5%8F%82%E7%85%A7)で前の結果の再利用
`\number`を使うことで前のグループの中身にマッチさせることができます。[公式シンタックス](https://docs.python.org/ja/3/library/re.html#regular-expression-syntax)では下記の記述。

> 同じ番号のグループの中身にマッチします。グループは 1 から始まる番号をつけられます。例えば、 (.+) \1 は、 'the the' あるいは '55 55' にマッチしますが、 'thethe' にはマッチしません(グループの後のスペースに注意して下さい)。この特殊シーケンスは最初の 99 グループのうちの一つとのマッチにのみ使えます。 number の最初の桁が 0 であるか、 number が 3 桁の 8 進数であれば、それはグループのマッチとしてではなく、 8 進値 number を持つ文字として解釈されます。文字クラスの '[' と ']' の間では全ての数値エスケープが文字として扱われます。

具体的にはこんな感じで、`\1`部分は前の`(ab)`でマッチした部分と同じ意味でabcabはマッチしますが、abdddは4文字目と5文字目がabではないのでマッチしません。
※Pythonのリストなどは0からカウントしますが、正規表現では1からカウントです。

```python
>>> print(re.findall(r'''(ab).\1''', 'abcab abddd'))
['ab']
```
### 

```python:
for section in sections:
    level = len(section[0]) - 1    # '='の数-1
    print('{indent}{sect}({level})'.format(
        indent='\t'*(level-1), sect=section[1], level=level))
```

### 出力結果(実行結果)
プログラム実行すると以下の結果が出力されます。

```bash:出力結果
国名(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)
```