-1

私は大きな問題を抱えています。壊滅的なバックトレース (http://www.regular-expressions.info/catastrophic.html) で 1 つの検証を行います。しかし、私はその理由を理解するのに苦労しています。多分誰かがアイデアを持っていますか？それに加えて、正規表現はすべてのユースケースで完全に機能します。

regex: "^((^|[^A-Za-z]+)[A-Z][A-Za-z]*)*[^A-Za-z]*$"

問題の入力:

"Disposable
BHT,
Tocopheryl AcetateHydrating Shave Gel
Aqua,
Glycerin,
Palmitic Acid,
Triethanolamine,
Isopentane,
Glyceryl Oleate,
Stearic Acid,
Isobutane,
Sorbitol,
Parfum,
Hydroxyethylcellulose,
Myristic Acid,
PEG-90M,
Butyrospermum Parkii Butter Extract,
Lauric Acid,
PTFE,
PEG-23M,
Propylene Glycol,
Glyceryl Acrylate/Acrylic Acid Copolymer,
PVM/MA Copolymer,
Silica,
Methylparaben,
Propylparaben,
BHT,
Limonene,
Benzyl Salicylate,
Linalool,
CI 42053,
CI 42090
Series Thermal Face Scrub
PEG-4,
Magnesium Sulfate,
PEG/PPG-300/55 Copolymer,
Polyethylene,
Polypropylene,
Laureth-23,
Stearyl Alcohol,
Dioleoylethyl Hydroxyethylmonium Methosulfate,
Cetyl Alcohol,
Behentrimonium Chloride,
Distearyldimonium Chloride,
Hydroxypropylcellulose,
Parfum,
Methylparaben,
Propylparaben,
Niacinamide,
Alcohol Denat,
Hexylene Glycol,
Benzyl Salicylate,
AquaClassic Clean Shampoo
Aqua,
Sodium Lauryl Sulfate,
Sodium Laureth Sulfate,
Glycol Distearate,
Zinc Carbonate,
Sodium Chloride,
Sodium Xylenesulfonate,
Zinc Pyrithione,
Cocamidopropyl Betaine,
Dimethicone,
Sodium Benzoate,
Guar Hydroxypropyltrimonium Chloride,
Hydrochloric Acid,
Hexyl Cinnamal,
Linalool,
Butylphenyl Methylpropional,
Magnesium Carbonate Hydroxide,
Ammonium Laureth Sulfate,
Magnesium Nitrate,
Sodium Polynaphthalenesulfonate,
Methylchloroisothiazolinone,
Magnesium Chloride,
CI 42090,
Citric Acid,
Methylisothiazolinone,
Tetrasodium EDTA,
CI 17200,
DMDM Hydantoin    Perspirant Deodorant Spray Sport Protect 48H
Butane,
Isobutane,
Cyclopentasiloxane,
Aluminum Chlorohydrate,
Cyclodextrin,
Disteardimonium Hectorite,
Dimethicone,
Aqua,
Triethyl Citrate,
Alpha-Isomethyl Ionone,
Butylphenyl Methylpropional,
Citral,
Citronellol,
Coumarin,
Geraniol,
Limonene,
Linalool
Pillite Series Instant Hydration Moisturiser +SPF 15
Aqua,
Glycerin,
Ethylhexyl Salicylate,
Niacinamide,
Butyl Methoxydibenzoylmethane,
Dimethicone,
Polyethylene,
Octocrylene,
Isopropyl Palmitate,
Phenylbenzimidazole Sulfonic Acid,
Sorbitan Stearate,
Triethanolamine,
Cetyl Alcohol,
Sodium Acrylates Copolymer,
Aluminum Starch Octenylsuccinate,
Stearyl Alcohol,
Caprylic/Capric Triglyceride,
Panthenol,
Benzyl Alcohol,
Dimethiconol,
Fragrance,
Ethylparaben,
Cetearyl Glucoside,
Cetearyl Alcohol,
PEG 100 Stearate,
Propylparaben,
Disodium EDTA,
C12-13 Pareth-3,
Palmitic Acid,
Stearic Acid,
Benzyl Salicylate,
Laureth-7,
Linalool,
Butylphenyl Methylpropional,
Myristic Acid,
Coumarin,
Heptadecanoic Acid,
Benzyl Benzoate"

ありがとう！

4

1 に答える 1

3

問題は、次の形式の句があることです

(something*)*

これは、正規表現が正しく一致する場合は正常に機能しますが、行の 1 つが不正な形式である場合、事態は壊滅的に悪化します。これは、バックトラッキングと、正規表現エンジンが試行するすべてのさまざまな組み合わせによるものです。

最長の回線の場合:

ジレット シリーズ インスタント ハイドレーション モイスチャライザー +SPF 15

この行が正規表現と一致しない場合、正規表現エンジンは、この行が正規表現と一致しないことに気付くまでに 2,251,799,813,685,248 (2^51) 回試行する必要があります。

修正はリンク先のページにあります。単語と単語の交互のシーケンスを探しているので、バックトラックは役に立ちません (単語は単語/非単語/単語のシーケンスに分割できないため)。所有量指定子を使用することで、バックトラッキングを防ぐことができます (つまり、正規表現が単語または単語以外に一致すると、その一致は放棄されません)。

所有量指定子を使用するには、すべての量指定子の末尾にプラスを付けるだけです。

(something*)*になる(something*+)*+

于 2012-10-19T10:59:09.353 に答える