偶数回の繰り返しにのみマッチさせる正規表現【python】

# 要旨
正規表現で特定文字列の偶数回/奇数回の連続にのみマッチし、奇数回/偶数回の連続にはマッチしない正規表現を定義したい。結論としては、以下のように書ける。

```Python
# 引数に与えた文字列の偶数回の繰り返しのみにマッチする（奇数回の繰り返しにマッチしない）正規表現文字列を返す
def get_even_repeat_pattern(s):
  return "(?<!{0})(?:{0}{0})+(?!{0})".format(s)
  
# 引数に与えた文字列の偶数回の繰り返しのみにマッチする（奇数回の繰り返しにマッチしない）正規表現文字列を返す
def get_odd_repeat_pattern(s):
  return "(?<!{0}){0}(?:{0}{0})*(?!{0})".format(s)

print("偶数回マッチ")
print(get_even_repeat_pattern("a"))
print("奇数回マッチ")
print(get_odd_repeat_pattern("a"))
```

```
偶数回マッチ
(?<!a)(?:aa)+(?!a)
奇数回マッチ
(?<!a)a(?:aa)*(?!a)
```

# テスト

`re.findall`の出力との比較を想定したテストケースとしている。


```Python
# 偶数回マッチのテストケース。出力はre.findallの結果を想定
even_testcase = [
  ["a",[]], #aの奇数回繰り返しには空のリストを返す
  ["aa",["aa"]], #aの偶数回繰り返しには繰り返し文字列を返す
  ["aaa",[]], #aの奇数回繰り返しには空のリストを返す
  ["aaaa",["aaaa"]], #aの偶数回繰り返しには繰り返し文字列を返す
  ["baabaaabaaaab",["aa","aaaa"]] #偶数回の繰り返しだけ返す
]

odd_testcase = [
  ["a",["a"]], #aの奇数回繰り返しには繰り返し文字列を返す
  ["aa",[]], #aの偶数回繰り返しには空のリストを返す
  ["aaa",["aaa"]], #aの奇数回繰り返しには繰り返し文字列を返す
  ["aaaa",[]], #aの偶数回繰り返しには空のリストを返す
  ["baabaaabaaaab",["aaa"]] #奇数回の繰り返しだけ返す
]

import unittest

class Test(unittest.TestCase):
  def test_get_even_repeat_pattern(self):
    for arg, expected in even_testcase:
      pattern = get_even_repeat_pattern("a")
      self.assertEqual(re.findall(pattern, arg), expected)
  
  def test_get_odd_repeat_pattern(self):
    for arg, expected in odd_testcase:
      pattern = get_odd_repeat_pattern("a")
      self.assertEqual(re.findall(pattern, arg), expected)

if __name__ == "__main__":
  unittest.main()      
```

```
..
----------------------------------------------------------------------
Ran 2 tests in 0.001s

OK
```


# 解説

"a"の繰り返しを例に取る。

偶数回の繰り返しは"aa"の１回以上の繰り返し、つまり正規表現では"(?:aa)+"のように書けるが、これだけだと、"aaa"のような奇数回の繰り返しに対してもその一部にマッチしてしまい不完全である。

```Python
pattern = "(?:aa)+"
print(re.findall(pattern, "aa")) #出力 ["aa"] -> ok
print(re.findall(pattern, "aaa")) #出力 ["aa"] -> ng
```

そこで、偶数回の繰り返しの前後に"a"が登場しないという条件を追加する。これは否定後読み、否定先読みで実現できる。

```Python
pattern = "(?<!a)(?:aa)+(?!a)" #(?<!...)、(?!...)は文字列"..."が先または後に続かないという意味
print(re.findall(pattern, "aa")) #出力 ["aa"] -> ok
print(re.findall(pattern, "aaa")) #出力 [] -> ok 
```

最後に、aを変数化して、任意の文字列の偶数回の繰り返しにのみマッチする正規表現パターンを返す関数を作る

```Python
def get_even_repeat_pattern(s):
  return "(?<!{0})(?:{0}{0})+(?!{0})".format(s)
  
print(get_even_repeat_pattern("a"))
print(get_even_repeat_pattern("ab"))
```

```
(?<!a)(?:aa)+(?!a)
(?<!ab)(?:abab)+(?!ab)
```

なお、今回はテストしないが、2つめの出力のように、引数sが"ab"のように2文字以上の場合も正しく機能する。

奇数回の繰り返しは偶数回の繰り返しパターンを少し編集するだけでよい。
具体的には`奇数=1+偶数`なので、偶数回の繰り返しパターンの直前（直後でもよい）に"a"を1つ追加すればよい。よって奇数回の繰り返しのみにマッチする正規表現は以下となる。

```
pattern = "(?<!a)a(?:aa)*(?!a)"
print(re.findall(pattern, "a")) #出力 ["a"] -> ok
print(re.findall(pattern, "aa")) #出力 [] -> ok
print(re.findall(pattern, "aaa")) #出力 ["aaa"] -> ok 
```

偶数の場合と比較すると、`(?:aa)+`が`a(?:aa)*`に変わっている。aが直前に追加しただけでなく、末尾の`+`（1回以上の繰り返し）を`*`（0回以上の繰り返し）にしている。これは"a"１文字にもマッチさせるためである。

偶数回の場合と同様に、関数として一般化すると以下のようになる。

```Python
def get_odd_repeat_pattern(s):
  return "(?<!{0}){0}(?:{0}{0})*(?!{0})".format(s)
  
print(get_odd_repeat_pattern("a"))
print(get_odd_repeat_pattern("ab"))
```

```
(?<!a)a(?:aa)*(?!a)
(?<!ab)ab(?:abab)*(?!ab)
```

# 応用例

ダブルクオテーションが入れ子になっている文章で、一番外側（第一階層）のダブルクオテーションの中身全体を抽出したい。ただし深い階層のダブルクオテーションは必ず偶数回連続で登場するものとする。異なる階層のダブルクオテーションが隣り合うこともあり得る（LINEのトーク履歴がこれに近い構造になっている）
例えば、入力と期待出力を以下とする。

入力

```
'文章１は"あなたは""私が""""あなたが間違っている""""と言った""と言った。"であり文章２は"""こんにちは""といった"'
```

出力

```
['あなたは""私が""""あなたが間違っている""""と言った""と言った。', '""こんにちは""と言った']
```

普通にダブルクオテーションで囲まれた領域を抽出するだけだとうまく行かない

```Python
import re
pattern = '"(.+?)"'

text = '文章１は"あなたは""私が""""あなたが間違っている""""と言った""と言った。"であり文章２は"""こんにちは""といった"'
print(re.findall(pattern, text))
```


```
['あなたは', '私が', '"', '"', 'と言った', 'と言った。', '"', '"といった']
```

そこで、奇数回のダブルクオテーションで囲まれた領域を抽出する。第一階層のダブルクオテーションと第二階層のダブルクオテーションが隣り合うことがあり得るが、第二階層以降は必ず偶数個なので、第一階層と隣り合っている場合は、奇数個のダブルクオテーションの塊になることを利用する。

```Python
import re

text = '文章１は"あなたは""私が""""あなたが間違っている""""と言った""と言った。"であり文章２は"""こんにちは""といった"'

# ダブルクオテーションの奇数回繰り返しにマッチする正規表現を定義
def get_odd_repeat_pattern(s):
  return "(?<!{0}){0}(?:{0}{0})*(?!{0})".format(s)

odd_pattern = get_odd_repeat_pattern('"')

# ダブルクオテーションの奇数回の繰り返しを別文字列に変換
tmp = re.sub(odd_pattern, lambda x: "<quote_{}>".format(len(x.group(0))), text)
print("\nダブルクオテーションの奇数回の繰り返しを別文字列に変換")
print(tmp)

# 変換後の文字列で囲まれた領域をfindall
contents_tmp = re.findall(r"<quote_\d+>.+?<quote_\d>", tmp)
print("\n変換後の文字列で囲まれた領域をfindall")
print(contents_tmp)

# 別文字列をもとに戻す
quote_str_pattern = r"<quote_(\d+)>"
contents = []
for c in contents_tmp:
  c = re.sub(quote_str_pattern, lambda x: '"'*int(x.group(1)), c)
  contents.append(c)
print("\n変換した文字列をもとに戻す")
print(contents)

# 各コンテンツの外側のダブルクオートを外す
contents = [c[1:-1] for c in contents]
print("\n各コンテンツの外側のダブルクオートを外す")
print(contents)
```

```
ダブルクオテーションの奇数回の繰り返しを別文字列に変換
文章１は<quote_1>あなたは""私が""""あなたが間違っている""""と言った""と言った。<quote_1>であり文章２は<quote_3>こんにちは""といった<quote_1>

変換後の文字列で囲まれた領域をfindall
['<quote_1>あなたは""私が""""あなたが間違っている""""と言った""と言った。<quote_1>', '<quote_3>こんにちは""といった<quote_1>']

変換した文字列をもとに戻す
['"あなたは""私が""""あなたが間違っている""""と言った""と言った。"', '"""こんにちは""といった"']

各コンテンツの外側のダブルクオートを外す
['あなたは""私が""""あなたが間違っている""""と言った""と言った。', '""こんにちは""といった']
```