正規表現で最長一致だけでなく，全ての一致したパターンを取りたい

Question

前提・実現したいこと

説明が難しいので，具体例を用いて説明します．
'ABccABcccDEccccDE'
という文字列から前後パターンが前'AB'，後'DE'となっている文字列を抽出したいです．
前後パターンの間は，改行以外の文字が2~10文字とします．
この例だと，
「ABccABcccDE」，「ABcccDE」，「ABcccDEccccDE」
の３つが取りたいものです．
「ABccABcccDEccccDE」は前後パターンの間の文字数が10を超えているので取得しません．
実際に利用したいのは前後パターンの間の改行以外の文字列なので，その部分だけ抽出できれば尚良いです．

試したこと

正規表現のre.findallを用いて実装してみました．

body = 'ABccABcccDEccccDE'
front = 'AB'
rear = 'DE'
s = re.findall(front + '.{2,10}' + rear, body)
print(s)
#['ABccABcccDE']

結果は最長文字数の'ABccABcccDE'しか取得できませんでした．
色々調べた結果，最長一致を取得してしまうようなのは仕様で，先読みアサーションなるものを用いたものなどをみましたが，どのようにすればいいのかわかっていません．

補足情報（FW/ツールのバージョンなど）

Python3.9

Comments

[Zuishin]

正規表現を使うとかえって難しくなります。AB と DE を検索してそのすべての組み合わせを自分で求めるのが一番楽だと思います。

[moko_7]

そうなんですね．ありがとうございます．

Answer 1

なんらかの正規表現を書いて、それを使ったfindallか何かを使って一発必中で
['ABccABcccDE', 'ABcccDE', 'ABcccDEccccDE']
を得るのは難しいです。なので、こういうプログラムを書くことになるのではないかと思います。

import re

body = 'ABccABcccDEccccDE'
front = 'AB'
rear = 'DE'

front_indexes = [m.span() for m in re.finditer(front, body)]  # => [(0, 2), (4, 6)]
rear_indexes = [m.span() for m in re.finditer(rear, body)]  # => [(9, 11), (15, 17)]

pairs = [
  (front_index, rear_index) 
    for front_index in front_indexes 
    for rear_index in rear_indexes
      if 2 <= rear_index[0] - front_index[1] <= 10
]  # => [((0, 2), (9, 11)), ((4, 6), (9, 11)), ((4, 6), (15, 17))]

result = [body[front_index[0]:rear_index[1]] for front_index, rear_index in pairs]

print(result)  # => ['ABccABcccDE', 'ABcccDE', 'ABcccDEccccDE']

追記

上記に挙げたコードは、何をやっているかが分かりやすいかもしれませんが、ちょっと芸がない気がしました。それで

• one-pass（所与のbodyの最初から最後まで走査するのを一回で済ませること）で、出来ないか？
• 無駄を省く何らかの最適化が出来ないか？

ということで以下のコードになりました。

# body = 'ABccABcccDEccccDE'
body = 'AB123AB67890DExxDEyyyABzzDE##ABDE@@@@@DE'  # 動作確認用
front = 'AB'
rear = 'DE'

MIN_LENGTH = 2
MAX_LENGTH = 10

result = []  # 条件に該当した文字列を格納するリスト
front_indexes = []  # front文字列の開始位置をappendしつつ、使わなくなったものは先頭からpop(0)で削除していくFIFOリスト

# body を左から読み、front および rear の出現を処理するループ
for i in range(len(body)):
  if body[i:i+len(front)] == front:
    front_indexes.append(i)
  elif body[i:i+len(rear)] == rear:
    for i_fr in [*front_indexes]:
      s = body[i_fr + len(front):i] # AB と DE の間にある文字列
      if len(s) <= MAX_LENGTH:
        if MIN_LENGTH <= len(s):
          result.append(s)
      else: # len(s) が MAX_LENGTH を超えたので、このsを作ったi_frをfront_indexesから削除
        front_indexes.pop(0)


print(result)
print(front_indexes)

• サンプル ???? tera: 369789 別案@replit

出力結果：

['123AB67890', '67890', '67890DExx', 'zz', 'zzDE##AB', 'DE@@@@@']

[29]

基本的な流れは以下です。

• body を左端から右端まで読み、front文字列が見つかったら、front_indexesにその位置を追加します。
• rear文字列が見つかったら、front_indexesに保持している、frontのインデクスを小さいほうから読み、frontとrearに挟まれている部分文字列をs として作ります。
• s の長さが要件を満たしていれば、該当文字列のリストに追加します。
• s の長さが要件の最大長を超えていれば、そのsを作ったfrontインデクスは、以後、使われないので、front_indexesから削除します。

上記の実行例では、front文字列の出現箇所は、0, 5, 21, 29 の4箇所ですが、プログラムの実行中、front_indexesの長さは最大2までにしかならず、プログラム終了時には最後の出現位置の 29 のみを含むリストになっています。

※いちおう良さげに動いてるっぽいですが、どこかバグっていたら、コメントからお知らせください。

Comments

[moko_7]

やはり難しそうですね．
これを実装してうまくいくことも確認できました．
みなさん同じ回答をしてくださっていますが，ソースコード付きですぐに解決に至ったのでこの回答をベストアンサーとさせていただきます．
回答してくださった皆様ありがとうございました

[退会済みユーザー]

コメントありがとうございます。別案を追記しました。参考にしていただければと思います〜????

Answer 2

同じ文字部分を繰り返し使うようなのは正規表現では無理そうな気がします。

ABとDEの位置を全部求めて、その組み合わせ（直積）を作って（例えばforの二重ループ）、
位置の差が希望通りのものだけを抽出すればいいかと思います。
あとはその位置でスライスで抜き出す。

Comments

[moko_7]

みたいですね．ありがとうございます．

Answer 3

既に解決済みですが参考までに。。。

import re

body = 'ABccABcccDEccccDE'

greedy = re.findall(r'.?(?=(AB.{2,10}DE))', body)
non_greedy = re.findall(r'.?(?=(AB.{2,10}?DE))', body)

matched_all = list(set(greedy + non_greedy))

print(matched_all)

#
# ['ABccABcccDE', 'ABcccDEccccDE', 'ABcccDE']

Comments

[moko_7]

ありがとうございます．
正規表現でも一応できるんですね．参考になります．
しかし，処理時間に難がありそうですね．
膨大なデータを扱うとなると，ベストアンサーとさせていただいた手法と比べるとかなり差が出ました．

[melian]

もしかしたら、 r'.*?(?=(AB.{2,10}DE))' と r'.*?(?=(AB.{2,10}?DE))' に変える(先頭の .? を .*? に変更する)と少しはマシになるかもしれません。ちなみに何倍程度の差になりましたでしょうか？ 後々の参考に知っておきたいです。

[moko_7]

いくつかの前後パターンで約30000記事（１記事あたり500文字程度）に対して検索を行なったところ，正確ではないですが，大体20倍ほどの差が出ました． .*?に変えてやってみたところさらに時間がかかり，計測を諦めました．何か自分が間違ってしまっているかもしれません．すみません

[melian]

ありがとうございます、お手間を取らせてしまいました。

[moko_7]

少し取れてるものが少ないと思ったので検証した結果，
body = 'ABccDEcDEcDE'のようなとき
['ABccDE', 'ABccDEcDEcDE']
となってしまいます

[melian]

ああ、その問題がありました。最短一致と最長一致の2通りしか拾っていませんので。。。

[moko_7]

なるほど．やはり正規表現では難しそうですね