Qt 正規表現 貪欲マッチ vs 最小マッチ：QRegExp::setMinimal() の効果

基本的な考え方

正規表現において、量指定子（*, +, ?, {n,m} など）は、直前のパターンが何回繰り返されるかを指定します。デフォルトでは、これらの量指定子は最大マッチ、つまり可能な限り長く文字列にマッチしようとします。

一方、setMinimal(true) を呼び出すと、量指定子は最小マッチ、つまり可能な限り短い文字列にマッチしようとします。

具体例で説明

次の文字列と正規表現を考えてみましょう。

文字列
"<a>text1</a><a>text2</a>" 正規表現: <a>.*</a>

• setMinimal(true) を呼び出した場合
  .* は可能な限り短くマッチしようとするため、最初の <a> と最初の </a> の間の "text1" に囲まれた "<a>text1</a>" にマッチします。次に、残りの文字列に対して同様にマッチングが行われ、"<a>text2</a>" にもマッチします。

• デフォルト（最大マッチ）の場合
  .* は可能な限り長くマッチしようとするため、<a> で始まり </a> で終わる最長の文字列、つまり "<a>text1</a><a>text2</a>" 全体にマッチします。

コード例

#include <QCoreApplication>
#include <QRegExp>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QString str = "<a>text1</a><a>text2</a>";
    QRegExp rx("<a>.*</a>");

    // デフォルト（最大マッチ）
    qDebug() << "Default (Greedy):";
    int pos = rx.indexIn(str);
    while (pos != -1) {
        qDebug() << rx.cap();
        pos = rx.indexIn(str, pos + rx.matchedLength());
    }

    // 最小マッチを設定
    rx.setMinimal(true);
    qDebug() << "\nMinimal (Non-Greedy):";
    pos = rx.indexIn(str);
    while (pos != -1) {
        qDebug() << rx.cap();
        pos = rx.indexIn(str, pos + rx.matchedLength());
    }

    return a.exec();
}

このコードの出力

Default (Greedy):
"<a>text1</a><a>text2</a>"

Minimal (Non-Greedy):
"<a>text1</a>"
"<a>text2</a>"

setMinimal(true) の使用場面

• 曖昧なパターンに対して、意図しない広範囲のマッチングを防ぎたい場合。
• ログファイルなどから、特定のパターンに囲まれた最小限の情報を抽出したい場合。
• HTMLやXMLなどの構造化されたテキストから、特定のタグで囲まれた部分を個別に抽出したい場合。

---

1. 期待される最小マッチが得られない
   

   • 原因
     正規表現のパターン自体が最小マッチを妨げている可能性があります。例えば、量指定子の後に続くパターンが、最小マッチした部分の直後に存在しない場合などです。
   • 例
     文字列 "ababab" に対して正規表現 "a.*b" で setMinimal(true) を設定しても、最初の "ab" ではなく "ababab" 全体にマッチする可能性があります。これは、.* の後の b が文字列の最後にしか存在しないためです。
   • 対策
     正規表現のパターンを見直し、最小マッチが正しく機能するように調整する必要があります。必要であれば、より具体的なパターンを使用したり、グループ化を活用したりします。

2. 意図しない短いマッチング
   

   • 原因
     setMinimal(true) を設定したことで、本来はもっと長くマッチしてほしい部分が途中で途切れてしまうことがあります。
   • 例
     HTMLのコメント に対して正規表現 で setMinimal(true) を設定すると、`

---

例1: HTMLタグの抽出 (最小マッチの利点)

この例では、複数のHTMLタグを含む文字列から、個々の <a> タグの内容を抽出します。setMinimal(true) を使用することで、意図しない長いマッチングを防ぎます。

#include <QCoreApplication>
#include <QRegExp>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QString html = "<div><a>Link 1</a>Some text<a>Link 2</a></div>";
    QRegExp rx("<a>(.*?)</a>"); // <a> と </a> で囲まれた部分をキャプチャ (非貪欲マッチ)

    qDebug() << "--- setMinimal(false) (デフォルト: 最大マッチ) ---";
    rx.setMinimal(false);
    int pos = rx.indexIn(html);
    while (pos != -1) {
        qDebug() << "マッチ全体:" << rx.cap();
        qDebug() << "キャプチャ (内容):" << rx.cap(1);
        pos = rx.indexIn(html, pos + rx.matchedLength());
    }

    qDebug() << "\n--- setMinimal(true) (最小マッチ) ---";
    rx.setMinimal(true);
    pos = rx.indexIn(html);
    while (pos != -1) {
        qDebug() << "マッチ全体:" << rx.cap();
        qDebug() << "キャプチャ (内容):" << rx.cap(1);
        pos = rx.indexIn(html, pos + rx.matchedLength());
    }

    return a.exec();
}

このコードの出力

--- setMinimal(false) (デフォルト: 最大マッチ) ---
マッチ全体: "<a>Link 1</a>Some text<a>Link 2</a>"
キャプチャ (内容): "Link 1</a>Some text<a>Link 2"

--- setMinimal(true) (最小マッチ) ---
マッチ全体: "<a>Link 1</a>"
キャプチャ (内容): "Link 1"
マッチ全体: "<a>Link 2</a>"
キャプチャ (内容): "Link 2"

説明

• setMinimal(true)
  setMinimal(true) を設定すると、.* は可能な限り短くマッチしようとします。そのため、最初の <a> と次の </a> の間の "Link 1" が最初のマッチとなり、その後、次の <a> と </a> の間の "Link 2" が次のマッチとなります。これにより、個々の <a> タグの内容を正しく抽出できます。
• setMinimal(false) (デフォルト)
  正規表現 <a>(.*)</a> の .* は、可能な限り長くマッチしようとするため、最初の <a> から最後の </a> までを一つのマッチとして捉えてしまいます。キャプチャされた内容は、意図しない "Link 1</a>Some text<a>Link 2" となります。

例2: コメントの抽出 (最小マッチの重要性)

この例では、C++スタイルの複数行コメントを含む文字列から、個々のコメントを抽出します。

#include <QCoreApplication>
#include <QRegExp>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QString code = "/* This is a\nmulti-line comment. */\nint main() {\n  // Single-line comment\n  /* Another\n   * multi-line\n   * comment. */\n  return 0;\n}";
    QRegExp rx("/\\*(.*?)\\*/"); // /* と */ で囲まれた部分をキャプチャ (非貪欲マッチ)

    qDebug() << "--- setMinimal(false) (デフォルト: 最大マッチ) ---";
    rx.setMinimal(false);
    int pos = rx.indexIn(code);
    while (pos != -1) {
        qDebug() << "マッチ全体:" << rx.cap();
        qDebug() << "キャプチャ (コメント):" << rx.cap(1);
        pos = rx.indexIn(code, pos + rx.matchedLength());
    }

    qDebug() << "\n--- setMinimal(true) (最小マッチ) ---";
    rx.setMinimal(true);
    pos = rx.indexIn(code);
    while (pos != -1) {
        qDebug() << "マッチ全体:" << rx.cap();
        qDebug() << "キャプチャ (コメント):" << rx.cap(1);
        pos = rx.indexIn(code, pos + rx.matchedLength());
    }

    return a.exec();
}

このコードの出力

--- setMinimal(false) (デフォルト: 最大マッチ) ---
マッチ全体: "/* This is a\nmulti-line comment. */\nint main() {\n  // Single-line comment\n  /* Another\n   * multi-line\n   * comment. */"
キャプチャ (コメント): " This is a\nmulti-line comment. */\nint main() {\n  // Single-line comment\n  /* Another\n   * multi-line\n   * comment. "

--- setMinimal(true) (最小マッチ) ---
マッチ全体: "/* This is a\nmulti-line comment. */"
キャプチャ (コメント): " This is a\nmulti-line comment. "
マッチ全体: "/* Another\n   * multi-line\n   * comment. */"
キャプチャ (コメント): " Another\n   * multi-line\n   * comment. "

説明

• setMinimal(true)
  setMinimal(true) を設定することで、.* は最初の /* に続く最初の */ まででマッチを停止します。これにより、個々の複数行コメントを正しく抽出することができます。
• setMinimal(false) (デフォルト)
  正規表現 /\\*(.*)\\*/ の .* は、最初の /* から最後の */ までを一つの大きなコメントとしてマッチングしてしまいます。

例3: 量指定子の挙動の変化

この例では、* 量指定子の最小マッチと最大マッチの違いをより直接的に示します。

#include <QCoreApplication>
#include <QRegExp>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QString text = "aaaaabbbbbbaaaaa";
    QRegExp rx("a*b");

    qDebug() << "--- setMinimal(false) (デフォルト: 最大マッチ) ---";
    rx.setMinimal(false);
    int pos = rx.indexIn(text);
    while (pos != -1) {
        qDebug() << "マッチ:" << rx.cap();
        pos = rx.indexIn(text, pos + rx.matchedLength());
    }

    qDebug() << "\n--- setMinimal(true) (最小マッチ) ---";
    rx.setMinimal(true);
    pos = rx.indexIn(text);
    while (pos != -1) {
        qDebug() << "マッチ:" << rx.cap();
        pos = rx.indexIn(text, pos + rx.matchedLength());
    }

    return a.exec();
}

このコードの出力

--- setMinimal(false) (デフォルト: 最大マッチ) ---
マッチ: "aaaaabbbbb"
マッチ: "aaaaa"

--- setMinimal(true) (最小マッチ) ---
マッチ: "b"
マッチ: "b"

• setMinimal(true)
  a* は可能な限り少ない 'a' (つまり、ゼロ個) にマッチしようとします。そのため、'a' がなくても直後の 'b' にマッチし (b)、'a' が連続する部分では 'b' がないためマッチしません。
• setMinimal(false) (デフォルト)
  a* は可能な限り多くの 'a' にマッチしようとするため、最初の 'b' の前にある全ての 'a' とその 'b' (aaaaabbbbb)、そして次の 'b' がないため残りの 'a' 全て (aaaaa) にマッチします。

---

非貪欲な量指定子を直接使用する

最も一般的で推奨される方法は、正規表現パターン内で直接、非貪欲な量指定子を使用することです。量指定子の直後に ? を追加することで、その量指定子は最小マッチを行います。

• {n,m}?: n 回以上 m 回以下の最小マッチ
• ??: 0回または1回の最小マッチ（優先的に0回）
• +?: 1回以上の最小マッチ
• *?: 0回以上の最小マッチ

例

#include <QCoreApplication>
#include <QRegExp>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QString html = "<div><a>Link 1</a>Some text<a>Link 2</a></div>";
    QRegExp rx1("<a>(.*)</a>");   // 貪欲マッチ (デフォルト)
    QRegExp rx2("<a>(.*?)</a>");  // 非貪欲マッチ

    qDebug() << "--- 貪欲マッチ ---";
    rx1.indexIn(html);
    qDebug() << rx1.cap(1); // "Link 1</a>Some text<a>Link 2"

    qDebug() << "\n--- 非貪欲マッチ ---";
    int pos = rx2.indexIn(html);
    while (pos != -1) {
        qDebug() << rx2.cap(1); // "Link 1", "Link 2"
        pos = rx2.indexIn(html, pos + rx2.matchedLength());
    }

    return a.exec();
}

この例では、rx2 の正規表現 <a>(.*?)</a> の * の後に ? を追加することで、最小マッチを実現しています。setMinimal(true) を明示的に呼び出す必要はありません。

利点

• QRegExp オブジェクトの状態を変更する必要がないため、意図しない影響を防ぎやすくなります。
• コードがより簡潔で読みやすくなります。
• 正規表現パターンを見ただけで、その部分が最小マッチを行うことが明確になります。

欠点

• 既存の正規表現パターンを後から最小マッチに変更したい場合に、パターン自体を修正する必要があります。

文字クラスや否定文字クラスの活用

最小マッチが必要な範囲をより具体的に定義することで、貪欲なマッチングを防ぐことができます。

例
HTMLタグの内容を抽出する別の方法

#include <QCoreApplication>
#include <QRegExp>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QString html = "<div><a>Link 1</a>Some text<a>Link 2</a></div>";
    QRegExp rx("<a>([^<]*)</a>"); // <a> と </a> の間で '<' 以外の文字が0回以上続く

    int pos = rx.indexIn(html);
    while (pos != -1) {
        qDebug() << rx.cap(1); // "Link 1", "Link 2"
        pos = rx.indexIn(html, pos + rx.matchedLength());
    }

    return a.exec();
}

この例では、.* の代わりに [^<]* を使用しています。[^<] は < 以外の任意の1文字にマッチする文字クラスであり、* が続くことで「< 以外の文字が0回以上続く」という意味になります。これにより、<a> タグの開始から次の </a> タグの直前までの内容を、貪欲マッチに頼らずに抽出できます。

利点

• 場合によっては、非貪欲な量指定子よりも効率的なマッチングが可能です。
• より明確にマッチさせたい範囲を制御できます。

欠点

• 対象とする文字列の構造を正確に理解している必要があります。
• 正規表現パターンが複雑になることがあります。

文字列操作関数との組み合わせ

正規表現を使用する代わりに、QString クラスが提供する indexOf(), lastIndexOf(), mid() などの文字列操作関数を組み合わせて、目的の文字列を抽出することも可能です。

例
HTMLタグの内容を抽出するさらに別の方法

#include <QCoreApplication>
#include <QString>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QString html = "<div><a>Link 1</a>Some text<a>Link 2</a></div>";
    int startTagIndex = 0;
    while ((startTagIndex = html.indexOf("<a>", startTagIndex)) != -1) {
        int endTagIndex = html.indexOf("</a>", startTagIndex);
        if (endTagIndex != -1) {
            QString content = html.mid(startTagIndex + 3, endTagIndex - (startTagIndex + 3));
            qDebug() << content; // "Link 1", "Link 2"
            startTagIndex = endTagIndex + 4;
        } else {
            break;
        }
    }

    return a.exec();
}

この例では、正規表現を使わずに、indexOf() で <a> と </a> の位置を見つけ、mid() でその間の文字列を抽出しています。

利点

• 単純なパターンであれば、正規表現エンジンよりも高速に動作する可能性があります。
• 正規表現の複雑さを避け、より直感的なコードで記述できます。

欠点

• 正規表現の持つ強力な表現力を活用できません。
• 複雑なパターンや柔軟なマッチングが必要な場合には、コードが煩雑になる可能性があります。

QRegExp::setMinimal(true) の代替方法としては、主に以下の3つが挙げられます。

1. 正規表現パターン内で非貪欲な量指定子 (*?, +?, ??, {n,m}?) を直接使用する
   最も一般的で推奨される方法です。
2. 文字クラスや否定文字クラスを活用して、マッチ範囲をより具体的に定義する
   より詳細な制御が可能になります。
3. QString の文字列操作関数を組み合わせて処理する
   単純なパターンであれば、より直感的で高速な場合があります。