1

お世話になります。

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

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

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

以下がコードです。

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;
3
  • 知識・技能の習得が目的でなければ、手段を変えてこんなライブラリを使うとか。AngleSharp/AngleSharp, C#でモダンにスクレイピングするならAngleSharp
    – kunif
    2019年9月7日 13:50
  • プログラムの動作を説明するなら、大抵の場合は「入力(元となるデータ)」と「期待する出力結果」が必要かと思います。今回の場合ならそれぞれ「対象の文字列」「マッチさせたい文字列」です。"HTMLから読み込む"ではなく、まずは適当なダミーの文字列を用意してみてはいかがでしょうか。 / それらを踏まえて、うまく動かないプログラムではどのようなルールで動作するつもりなのかを説明してあると回答も付きやすいのかなと思います。 参考: 最小限の・確認可能なサンプルコードの書き方
    – cubick
    2019年9月7日 17:45
  • ありがとうございます。どうやら正規表現が間違っていたようです。ちなみに、やりたかったのは『入れ子のない、開始と終了で可見込まれているタグ』を取得する方法でした。今の記述ですと、終了タグにまで属性を探してしまうようでした。 2019年9月8日 5:27

1 件の回答 1

4

原因そのものは正規表現のバックトラッキングが指数関数的な回数で発生しているため、実行に長時間を要し、フリーズしたように観測されます。

例として

<ul><li>item0</li><li>item1</li></ul>

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


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

<ul><li>item0</li><li>item1</li></ul>

とあった場合、

// 1周目
<ul>『0』<li>item1</li></ul>

// 2周目
<ul>『0』『1』</ul>

// 3周目
『2』

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

1
  • いつもありがとうございます。ご指摘いただいた内容を見て、やはり正規表現の記述が間違っていたようです。終了タグには、属性は入ってきませんものね。そこを踏まえて修正してます。さて、このプログラムの用途ですが、まさしく期待していた結果が上記の例です。何がやりたかったかというと、並列してDictionaryを配置し、置き換えた文字を辞書に詰め込んでいくことで、簡単な可逆圧縮をやってみようと思っていました。どう実用的に役に立つかは別として、勉強用であり、はたまた何かの役に立つときのために…です。 2019年9月8日 5:24

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。