Python 正则表达式灾难性回溯

Question

我正在从 Ms word 生成的 XML 文件中搜索一些短语。关键是任何短语都可以被一些 XML 标记打断，这些标记可以出现在单词之间，甚至在单词内部，如您在示例中所见:

</w:rPr><w:t> To i</w:t></w:r><w:r wsp:rsidRPr="00EC3076"><w:rPr><w:sz w:val="17"/><w:lang w:fareast="JA"/></w:rPr><w:t>ncrease knowledge of and acquired skills for implementing social policies with a view to strengthening the capacity of developing countries at the national and community level.</w:t></w:r></w:p>

所以我处理这个问题的方法是简单地将所有 XML 标签缩减为相同长度的 # 字符簇，这样当我找到任何短语时，正则表达式将忽略每两个字符之间的所有 XML 标签。

我基本上需要的是这个短语在实际 xml 文档中的跨度，所以我将使用这个跨度来处理 xml 文档，我不能使用克隆。

这种方法非常有效，但是有些短语会导致灾难性的回溯，例如下面的例子，所以我需要有人指出回溯从何而来，或者提出更好的问题解决方案。

================================

这是一个例子:

我有这段文本，其中有一些 # 字符簇(我想保留)，并且空格也是不可预测的，例如:

Relationship to the #################strategic framework ################## for the period 2014-2015####################: Programme 7, Economic and Social Affairs, subprogramme 3, expected

accomplishment (c)#######

为了匹配下面的短语:

Relationship to the strategic framework for the period 2014-2015: programme 7, Economic and Social Affairs, subprogramme 3, expected accomplishment (c)

我想出了这个正则表达式来适应不可预测的 # 和空格字符:

u'R#*e#*l#*a#*t#*i#*o#*n#*s#*h#*i#*p#*\\s*#*t#*o#*\\s*#*t#*h#*e#*\\s*#*s#*t#*r#*a#*t#*e#*g#*i#*c#*\\s*#*f#*r#*a#*m#*e#*w#*o#*r#*k#*\\s*#*f#*o#*r#*\\s*#*t#*h#*e#*\\s*#*p#*e#*r#*i#*o#*d#*\\s*#*2#*0#*1#*4#*\\-#*2#*0#*1#*5#*:#*\\s*#*p#*r#*o#*g#*r#*a#*m#*m#*e#*\\s*#*7#*\\,#*\\s*#*E#*c#*o#*n#*o#*m#*i#*c#*\\s*#*a#*n#*d#*\\s*#*S#*o#*c#*i#*a#*l#*\\s*#*A#*f#*f#*a#*i#*r#*s#*\\,#*\\s*#*s#*u#*b#*p#*r#*o#*g#*r#*a#*m#*m#*e#*\\s*#*3#*\\,#*\\s*#*e#*x#*p#*e#*c#*t#*e#*d#*\\s*#*a#*c#*c#*o#*m#*p#*l#*i#*s#*h#*m#*e#*n#*t#*\\s*#*\\(#*c#*\\)'

它在我想要匹配的所有其他短语中工作正常，但是这个有一个问题导致一些灾难性的回溯，有人能发现它吗？

原文是用xml标签隔开的，为了让正则更简单，我把标签换成这些#簇，原文如下:

</w:rPr><w:t>Relationship to the </w:t></w:r><w:r><w:rPr><w:i/><w:sz w:val="17"/><w:sz-cs w:val="17"/></w:rPr><w:t>strategic framework </w:t></w:r><w:r wsp:rsidRPr="00EC3076"><w:rPr><w:i/><w:sz w:val="17"/><w:sz-cs w:val="17"/></w:rPr><w:t> for the period 2014-2015</w:t></w:r><w:r wsp:rsidRPr="00EC3076"><w:rPr><w:sz w:val="17"/><w:sz-cs w:val="17"/></w:rPr><w:t>: Programme 7, Economic and Social Affairs, subprogramme 3, expected accomplishment (c)</w:t>

Answer 1

由于情况那么复杂 - 不要使用正则表达式，只需逐个符号地检查你的行符号:

etalone = "String to find"
etalone_length = len(etalone)
counter = 0
for symbol in your_line:
    if symbol == etalone[counter]:
        counter += 1
        if counter == etalone_length:
            print("String matches")
            break
    elif symbol != " " and sybmol != "#":
        # Bad char found
        print("Does not match!")
else:  # exited 'for' before full etalone matched
    print("Does not match!")

我刚刚发现，如果我们匹配的第一个符号不是我们正在寻找的符号，那么上面的方法实际上不会起作用。 这个怎么样:

1. 克隆你的字符串
2. 从克隆中删除“#”
3. 匹配模式
4. 如果模式匹配——获取匹配结果的位置
5. 通过该位置 - 找到匹配的第一个符号的确切出现。就像如果整行是 a#b##ca#d#f 而我们要查找的行是 adf 那么我们将从 second< 开始匹配/em> 一个 符号。
6. 在原始行中找到第 n 次出现的符号 a。设置计数器 =
7. 使用上述算法(在 break 之前存储为跨度开始和计数器作为跨度结束)