正则表达式匹配引号中带有双引号的字符串

Question

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

• 输入由键=值对组成.关键始于斜线.该值可以是引号中的数字或字符串.
• 该值可以选择包含转义引号,即引号后跟引号("").这种逃逸的报价应被视为价值的一部分.无需检查转义的报价是否平衡(例如,以另一个转义报价结束).

正则表达式应该与序列的给定key = value部分匹配,并且不应该为长输入中断(例如,值为10000个字符).

首先我来到这个解决方案:

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

并且它执行得不错,但是在Java6中,对于长输入(例如,cashes regexplanet),StackOverflowError失败了.我尝试改进它以便更快地运行:

/(\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 [^"]+
        ""|[^"]+
    )+
)

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

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

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

查看演示：失败时的 24 个步骤，同时保持成功案例的速度（不是真正的基准测试工具，但灾难性回溯很容易发现）