57913


お世話になります。

HTMLファイルを読ませて、そこからタグを一つ一つ拾い上げるコードを作成中なのですが、そこそこ2000kb程度のテキストに検索をかけると、何度やってもフリーズしてしまいます。

VisualStudioCommunity2019,バージョンは16.2.4です。

コード、もしくは正規表現のパターンに間違いなどありましたらご指摘ください。

以下がコードです。

[code]

    string stBuff = File.ReadAllText("xxx.htm",Encoding.UTF8);
    
    stBuff = stBuff.Replace("\r\n", "");
    stBuff = stBuff.Replace("\n", "");
    
    ofd = null;
    
    int id = 0;
    //while (true)  うまくいかないのでループは外してあります。
    {
        Match mc = Regex.Match(
            stBuff,
            @"<(?<tag>.*?)>[^<>]*?</\k<tag>>"
        );
    
        if (!mc.Success)
        {
            //break;
        }
    
        MessageBox.Show(mc.Value);
        stBuff = stBuff.Replace(mc.Value, "『" + id + "』");
        id++;
    
        this.Text = "" + id;
    }
    
    this.textBox1.Text = stBuff;
    
[/code]


CC BY-SA 4.0
2019-09-06T07:54:00.707
57905
2019-09-07T12:16:49.760
2019-09-06T07:56:50.163
3060
9374
question
c# 正規表現
C# 正規表現でテキスト内のタグを見つけようとするとフリーズする


原因そのものは[正規表現のバックトラッキング](https://docs.microsoft.com/ja-jp/dotnet/standard/base-
types/backtracking-in-regular-
expressions)が指数関数的な回数で発生しているため、実行に長時間を要し、フリーズしたように観測されます。

例として

[code]

    <ul><li>item0</li><li>item1</li></ul>
    
[/code]

上記HTMLコード片でなぜ多数のバックトラッキングが発生するかを説明すると

  * `<(?<tag>.*?)>` = `<ul>`、`[^<>]*?` = ``、 `</\k<tag>>` ≠ `</ul>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>`、`[^<>]*?` = ``、 `</\k<tag>>` ≠ `</ul><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>`、`[^<>]*?` = `i`、 `</\k<tag>>` ≠ `</ul><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>`、`[^<>]*?` = `it`、 `</\k<tag>>` ≠ `</ul><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>`、`[^<>]*?` = `ite`、 `</\k<tag>>` ≠ `</ul><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>`、`[^<>]*?` = `item`、 `</\k<tag>>` ≠ `</ul><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>`、`[^<>]*?` = `item0`、 `</\k<tag>>` ≠ `</ul><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>item0</li>`、`[^<>]*?` = ``、 `</\k<tag>>` ≠ `</ul><li>item0</li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>item0</li><li>`、`[^<>]*?` = ``、 `</\k<tag>>` ≠ `</ul><li>item0</li><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>item0</li><li>`、`[^<>]*?` = `i`、 `</\k<tag>>` ≠ `</ul><li>item0</li><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>item0</li><li>`、`[^<>]*?` = `it`、 `</\k<tag>>` ≠ `</ul><li>item0</li><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>item0</li><li>`、`[^<>]*?` = `ite`、 `</\k<tag>>` ≠ `</ul><li>item0</li><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>item0</li><li>`、`[^<>]*?` = `item`、 `</\k<tag>>` ≠ `</ul><li>item0</li><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>item0</li><li>`、`[^<>]*?` = `item1`、 `</\k<tag>>` ≠ `</ul><li>item0</li><li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>item0</li><li>item1</li>`、`[^<>]*?` = ``、 `</\k<tag>>` ≠ `</ul><li>item0</li><li>item1</li>` → 失敗
  * `<(?<tag>.*?)>` = `<ul><li>item0</li><li>item1</li></ul>`、`[^<>]*?` = ``、 `</\k<tag>>` ≠ `</ul><li>item0</li><li>item1</li></ul>` → 失敗
  * 文字列終端まですべて失敗したため、開始位置をずらす
  * `<(?<tag>.*?)>` = `<li>`、`[^<>]*?` = ``、 `</\k<tag>>` ≠ `</li>` → 失敗
  * `<(?<tag>.*?)>` = `<li>`、`[^<>]*?` = `i`、 `</\k<tag>>` ≠ `</li>` → 失敗
  * `<(?<tag>.*?)>` = `<li>`、`[^<>]*?` = `it`、 `</\k<tag>>` ≠ `</li>` → 失敗
  * `<(?<tag>.*?)>` = `<li>`、`[^<>]*?` = `ite`、 `</\k<tag>>` ≠ `</li>` → 失敗
  * `<(?<tag>.*?)>` = `<li>`、`[^<>]*?` = `item`、 `</\k<tag>>` ≠ `</li>` → 失敗
  * `<(?<tag>.*?)>` = `<li>`、`[^<>]*?` = `item0`、 `</\k<tag>>` = `</li>` → 成功

といった探索が行われます。

簡単な回答としては `<(?<tag>.*?)>` が`<>`文字を認めないよう `<(?<tag>[^<>]*?)>`
とすることである程度の速度改善は見られますが、本質的には解決していません。それは

  * `<ul id="list">`とあった場合は`</ul id="list">`を探す
  * `<br>`や`<br/>`とあった場合は`</br>`や`</br/>`を探す
  * `<UL>～</ul>`とあった場合は`</UL>`を探す

といった、HTMLとしては正しい記述に対してどのように対応するかの方針が必要です。これらの方針が定まらないことには置換されないタグが残り続け、上記のようなバックトラッキングを多数発生させます。

* * *

ここからは質問の範囲から外れますが、仮に理想的に解決する正規表現が実現できたとして

[code]

    <ul><li>item0</li><li>item1</li></ul>
    
[/code]

とあった場合、

[code]

    // １周目
    <ul>『0』<li>item1</li></ul>
    
    // ２周目
    <ul>『0』『1』</ul>
    
    // ３周目
    『2』
    
[/code]

という結果になります。そもそもの問題として、これが期待するでしょうか？ 期待しない結果だとすると質問そのものが無意味になるように思います。


CC BY-SA 4.0
2019-09-07T02:55:37.180
57913
2019-09-07T12:16:49.760
2019-09-07T12:16:49.760
4236
4236
57905
answer