対策は2つあります。
- 最短一致を使う
- 最長一致で
</name>
を乗り越えない正規表現パターンを指定する
最短一致の解は既に示されているので、後者のパターンを書きます。
最長一致
Java
1Pattern p = Pattern.compile("<name>[^<]*</name>");
この書き方はname要素の子に他のタグが存在しない場合に機能します。
他のタグが入る可能性があるなら、次のように書きます。
Java
1Pattern p = Pattern.compile("<name>[^<]*(?:<(?!/?name>)[^>]*>[^<]*)*</name>");
この書き方はname要素が入れ子にならない前提で書いてます。
入れ子になる場合は <name>
と </name>
を同数消費する必要がありますが、説明が複雑化する為、ここでは省略します。
最短一致の問題点
最短一致は簡単に見えますが、バックトラックが発生するので最長一致パターンよりはどうしても遅くなります。
Java
1Pattern p = Pattern.compile("<name>.*?</name>");
上記正規表現をマッチさせる前提で、後続に </name>
がN個存在したとするなら、バックトラック回数は**「N * (N - 1) / 2」回**です。
name要素が増える程、遅くなる計算になります。
そして、「name要素の内容となる文字列長」「</name>と<name>間の文字列長」が長ければ、それだけ文字列の消費量が多くなるので、更に遅くなります。
最短一致(*?
)の後続に複数のタグが存在する場合に期待通りに動作しない点にも注意が必要になります。
例えば、正規表現パターンを次のように変更した場合、
Java
1Pattern p = Pattern.compile("<class><name>.*?</name></class>");
次の文字列の全体「"<class><name>.foo</name>bar</class>piyo</name></class>"
」にマッチしてしまいます。
Java
1"<class><name>.foo</name>bar</class>piyo</name></class>"
最短一致は後続の正規表現パターン全体に依存するので、</name></class>
が来るまで盲目的に消費してしまいます。
対して、次の最長一致パターンは内容をテキストノードに限定しているので、タグを乗り越える危険性はありません。
Java
1<class><name>[^<]*</name></class>
既存の正規表現を書き換える場合、次のような性質の違いがあります。
- 最短一致は後続パターンが変わる度に見直さなければならない(最短一致の挙動が変わってしまう)
- 最長一致は後続パターンが変わっても、バックトラックが発生しない限りは見直す必要がない
- 絶対最大指定子はバックトラックが発生しないので、後続パターンが変わっても見直す必要がない
この性質の違いから、最短一致はメンテナンス性が低いと思います。
更新履歴
- 2017/11/03 17:43 「最短一致の問題点」の説明追記
Re: travel_saki さん
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/10/30 14:09
2017/10/30 14:18
2017/10/30 14:38
2017/10/30 14:51
2017/10/30 16:26
2017/10/30 19:05
2017/11/02 15:24
2017/11/03 02:51 編集
2017/11/03 03:20
2017/11/03 08:46