回答編集履歴

1

「最短一致の問題点」の説明追記

2017/11/03 08:43

投稿

think49
think49

スコア18156

test CHANGED
@@ -9,6 +9,10 @@
9
9
 
10
10
 
11
11
  最短一致の解は既に示されているので、後者のパターンを書きます。
12
+
13
+
14
+
15
+ ### 最長一致
12
16
 
13
17
 
14
18
 
@@ -28,15 +32,103 @@
28
32
 
29
33
  ```Java
30
34
 
31
- Pattern p = Pattern.compile("<name>[^<]*(?:<(?!/name>)[^>]*>[^<]*)*</name>");
35
+ Pattern p = Pattern.compile("<name>[^<]*(?:<(?!/?name>)[^>]*>[^<]*)*</name>");
32
36
 
33
37
  ```
34
38
 
35
39
 
36
40
 
41
+ この書き方はname要素が入れ子にならない前提で書いてます。
42
+
43
+ 入れ子になる場合は `<name>` と `</name>` を同数消費する必要がありますが、説明が複雑化する為、ここでは省略します。
44
+
45
+
46
+
47
+ ### 最短一致の問題点
48
+
49
+
50
+
37
51
  最短一致は簡単に見えますが、**バックトラック**が発生するので最長一致パターンよりはどうしても遅くなります。
38
52
 
53
+
54
+
55
+ ```Java
56
+
57
+ Pattern p = Pattern.compile("<name>.*?</name>");
58
+
59
+ ```
60
+
61
+
62
+
63
+ 上記正規表現をマッチさせる前提で、後続に `</name>` がN個存在したとするなら、バックトラック回数は**「N * (N - 1) / 2」回**です。
64
+
65
+ name要素が増える程、遅くなる計算になります。
66
+
67
+ そして、「name要素の内容となる文字列長」「</name>と<name>間の文字列長」が長ければ、それだけ文字列の消費量が多くなるので、更に遅くなります。
68
+
69
+
70
+
71
+ 最短一致(`*?`)の後続に複数のタグが存在する場合に期待通りに動作しない点にも注意が必要になります。
72
+
73
+ 例えば、正規表現パターンを次のように変更した場合、
74
+
75
+
76
+
77
+ ```Java
78
+
79
+ Pattern p = Pattern.compile("<class><name>.*?</name></class>");
80
+
81
+ ```
82
+
83
+
84
+
85
+ 次の文字列の全体「`"<class><name>.foo</name>bar</class>piyo</name></class>"`」にマッチしてしまいます。
86
+
87
+
88
+
89
+ ```Java
90
+
91
+ "<class><name>.foo</name>bar</class>piyo</name></class>"
92
+
93
+ ```
94
+
95
+
96
+
39
- また、最短一致(`*?`)の後続に複数タグ(`</name></class>`)存在す場合期待通りに動作点にも注意が必要になります。
97
+ 最短一致後続の正規表現パターン**全体**依存するで、`</name></class>`がまで盲目的消費てしまいます。
98
+
99
+ 対して、次の最長一致パターンは内容を**テキストノードに限定している**ので、タグを乗り越える危険性はありません。
100
+
101
+
102
+
103
+ ```Java
104
+
105
+ <class><name>[^<]*</name></class>
106
+
107
+ ```
108
+
109
+
110
+
111
+ 既存の正規表現を書き換える場合、次のような性質の違いがあります。
112
+
113
+
114
+
115
+ - 最短一致は後続パターンが変わる度に見直さなければならない(最短一致の挙動が変わってしまう)
116
+
117
+ - 最長一致は後続パターンが変わっても、バックトラックが発生しない限りは見直す必要がない
118
+
119
+ - **絶対最大指定子**はバックトラックが発生しないので、後続パターンが変わっても見直す必要がない
120
+
121
+
122
+
123
+ この性質の違いから、最短一致はメンテナンス性が低いと思います。
124
+
125
+
126
+
127
+ ### 更新履歴
128
+
129
+
130
+
131
+ - 2017/11/03 17:43 「最短一致の問題点」の説明追記
40
132
 
41
133
 
42
134