java - 正则表达式匹配引号中的字符串，里面有双引号

Question

我面临着匹配以下格式的输入的挑战:

• 输入由键=值对组成。 key 以斜杠开头。该值可以是数字或引号中的字符串。
• 该值可以选择包含转义引号，即引号后跟引号 ("")。这种转义引号应被视为值(value)的一部分。无需检查转义引号是否平衡(例如以另一个转义引号结尾)。

正则表达式应匹配序列中给定的键=值部分，并且不应因长输入而中断(例如，值是 10000 个字符)。

首先我想到了这个解决方案:

/(\w+)=(\d+|"(?:""|[^"])+"(?!"))

它的表现还不错，但是它在 Java6 中因长输入的 StackOverflowError 而失败(例如现金 regexplanet)。我尝试对其进行一些改进以使其运行得更快:

/(\w+)=(\d+|"(?:""|[^"]+)+"(?!"))

但是如果输入不匹配，它会在试图匹配它的回溯中进入无限循环。

然后我来到这个正则表达式:

/(\w+)=(\d+|".+?(?<!")(?:"")*"(?!"))

执行速度较慢，但​​似乎可以解决任务。

谁能推荐更好/更快的正则表达式？

示例输入:

/mol_type="protein" /transl_table=11 /note="[CDS] (""multi
line)"  nn  /organism="""Some"" Sequence" nn  /organism="Some ""Sequence"""
/translation="MHPSSSRIPHIAVVGVSAIFPGSLDAHGFWRDILSGTDLITDVPSTHWLVE
DYYDPDPSAPDKTYAKRGAFLKDVPFDPLEWGVPPSIVPATDTTQLLALIVAKRVLEDAAQGQFE
SMSRERMSVILGVTSAQELLASMVSRIQRPVWAKALRDLGYPEDEVKRACDKIAGNYVPWQESSF
PGLLGNVVAGRIANRLDLGGTNCVTDAACASSLSAMSMAINELALGQSDLVIAGGCDTMNDAFMY
MCFSKTPALSKSGDCRPFSDKADGTLLGEGIAMVALKRLDDAERDGDRVYAVIRGIGSSSDGRSK
SVYAPVPEGQAKALRRTYAAAGYGPETVELMEAHGTGTKAGDAAEFEGLRAMFDESGREDRQWCA
LGSVKSQIGHTKAAAGAAGLFKAIMALHHKVLPPTIKVDKPNPKLDIEKTAFYLNTQARPWIRPG
DHPRRASVSSFGFGGSNFHVALEEYTGPAPKAWRVRALPAELFLLSADTPAALADRARALAKEAE
VPEILRFLARESVLSFDASRPARLGLCATDEADLRKKLEQVAAHLEARPEQALSAPLVHCASGEA
PGRVAFLFPGQGSQYVGMGADALMTFDPARAAWDAAAGVAIADAPLHEVVFPRPVFSDEDRAAQE
ARLRETRWAQPAIGATSLAHLALLAALGVRAEAFAGHSFGEITALHAAGALSAADLLRVARRRGE
LRTLGQVVDHLRASLPAAGPAASASPAAAASVPKASTAAVPAVASVAAPGAAEVERVVMAVVAET
TGYPAEMLGLQMELESDLGIDSIKRVEILSAVRDRTPGLSEVDASALAQLRTLGQVVDHLRASLP
AASAGPAVAAPAAKAPAVAAPTGVSGATPGAAEVERVVMAVVAETTGYPAEMLGLQMELESDLGI
DSIKRVEILSAVRDRTPGLAEVDASALAQLRTLGQVVDHLRASLGPAAVTAGAAPAEPAEEPAST
PLGRWTLVEEPAPAAGLAMPGLFDAGTLVITGHDAIGPALVAALAARGIAAEYAPAVPRGARGAV
FLGGLRELATADAALAVHREAFLAAQAIAAKPALFVTVQDTGGDFGLAGSDRAWVGGLPGLVKTA
ALEWPEASCRAIDLERAGRSDGELAEAIASELLSGGVELEIGLRADGRRTTPRSVRQDAQPGPLP
LGPSDVVVASGGARGVTAATLIALARASHARFALLGRTALEDEPAACRGADGEAALKAALVKAAT
SAGQRVTPAEIGRSVAKILANREVRATLDAIRAAGGEALYVPVDVNDARAVAAALDGVRGALGPV
TAIVHGAGVLADKLVAEKTVEQFERVFSTKVDGLRALLGATAGDPLKAIVLFSSIAARGGNKGQC
DYAMANEVLNKVAAAEAARRPGCRVKSLGWGPWQGGMVNAALEAHFAQLGVPLIPLAAGAKMLLD
ELCDASGDRGARGQGGAPPGAVELVLGAEPKALAAQGHGGRVALAVRADRATHPYLGDHAINGVP
VVPVVIALEWFARAARACRPDLVVTELRDVRVLRGIKLAAYESGGEVFRVDCREVSNGHGAVLAA
ELRGPQGALHYAATIQMQQPEGRVAPKGPAAPELGPWPAGGELYDGRTLFHGRDFQVIRRLDGVS
RDGIAGTVVGLREAGWVAQPWKTDPAALDGGLQLATLWTQHVLGGAALPMSVGALHTFAEGPSDG
PLRAVVRGQIVARDRTKADIAFVDDRGSLVAELRDVQYVLRPDTARGQA"
/note="primer of  Streptococcus pneumoniae

预期输出(来自 regexhero.net ):

Answer 1

为了在合理的时间内失败，您确实需要避免灾难性的回溯。这可以使用原子分组 (?>...) 来完成:

/(\w+)=(\d+|"(?>(?>""|[^"]+)+)"(?!"))

# (?>(?>""|[^"]+)+)
(?>               # throw away the states created by (...)+
    (?>           # throw away the states created by [^"]+
        ""|[^"]+
    )+
)

在永远不会匹配的字符串上使用 (?:""|[^"]+)+ 时出现的问题与每次匹配新 的事实有关[^"] 字符，正则表达式引擎可以选择使用内部或外部 + 量词。

这导致回溯有很多可能性，在返回失败之前引擎必须尝试所有这些。

我们知道，如果在引擎到达终点时我们还没有找到匹配项，我们将永远不会:我们需要做的就是丢弃回溯位置以避免出现问题，这就是原子分组的目的.

查看 DEMO : 24 步失败，同时保持成功案例的速度(不是真正的基准测试工具，但灾难性回溯很容易发现)