2

re.sub() バックトラックを引き起こす可能性のあるいくつかの複雑なパターン（コードによって作成された）で使用しています。

Python 2.6で特定の回数の反復を行った後、中止するre.sub（たとえば、パターンが見つからないふりをしたり、エラーを発生させたりする）実用的な方法はありますか？

サンプル（これはもちろんダムパターンですが、複雑なテキスト処理エンジンによって動的に作成されます）：

>>>re.sub('[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*[i1l!|](?:[^i1l!|\\w]|[i1l!|])*[l1i!|](?:[^l1i!||\\w]|[l1i!|])*','*','ilililililililililililililililililililililililililililililililililil :x')

4

2 に答える 2

4

壊滅的なバックトラッキング (外部正規表現の難しい問題) の可能性について正規表現を分析するか、バックトラッキングを許可しない別の正規表現エンジンを使用する以外に、唯一の方法はこの性質のタイムアウトを使用することだと思います:

import re
import signal

class Timeout(Exception): 
    pass 

def try_one(pat,rep,s,t=3):
    def timeout_handler(signum, frame):
        raise Timeout()

    old_handler = signal.signal(signal.SIGALRM, timeout_handler) 
    signal.alarm(t) 

    try: 
        ret=re.sub(pat, rep, s)

    except Timeout:
        print('"{}" timed out after {} seconds'.format(pat,t))
        return None

    finally:
        signal.signal(signal.SIGALRM, old_handler) 

    signal.alarm(0)
    return ret

try_one(r'^(.+?)\1+$', r'\1' ,"a" * 1000000 + "b")

1 つの文字 (この場合は 100 万個の「a」文字) の大量の繰り返しを置き換えようとすることは、古典的な壊滅的な正規表現の失敗です。完了するまでに数万年かかります (少なくとも Python や Perl では。Awk は異なります)。

3 秒間試行した後、正常にタイムアウトし、次のように出力されます。

"^(.+?)\1+$" timed out after 3 seconds
于 2012-09-18T06:39:39.190 に答える
-1

countここであなたを助けることができます：

In [9]: re.sub ?
Type:       function
Base Class: <type 'function'>
String Form:<function sub at 0x00AC7CF0>
Namespace:  Interactive
File:       c:\python27\lib\re.py
Definition: re.sub(pattern, repl, string, count=0, flags=0)
Docstring:
Return the string obtained by replacing the leftmost
non-overlapping occurrences of the pattern in string by the
replacement repl.  repl can be either a string or a callable;
if a string, backslash escapes in it are processed.  If it is
a callable, it's passed the match object and must return
a replacement string to be used.


In [13]: a = "bbbbbbb"

In [14]: x = re.sub('b', 'a', a, count=3)

In [15]: x
Out[15]: 'aaabbbb'
于 2012-09-18T06:02:43.697 に答える