テキストエディタの作り方～検索・置換編～

C++版の検索と置換を実装しています。C#版でも実装したのですが、かなりいい加減に作っているので一旦仕様を決めようと思います。

まずはメモ帳の仕様から確認してみました。メモ帳の場合、上へ検索と下へ検索があります。文字列選択してない場合、カーソルの位置から上または下へ検索します。まぁ、そのままですよね。問題は文字列を選択していた場合です。

メモ帳の検索仕様
1. 上へ検索
2. 下へ検索
選択文字列と検索文字列が一致している場合
検索仕様まとめ
自作テキストエディタの仕様
1. 検索仕様
検索アルゴリズム
1. Quick Search(Sunday法)
サンプルコード

メモ帳の検索仕様

上へ検索

まず、文字列選択している時に上に検索した場合です。例えば以下の状態で上に「あああ」を検索すると2回目の「あああ」が選択されます。

・上に検索前
あああ　あああ　あ|ああ　あああ
↓
・上に検索後
あああ　あああ|　あああ　あああ

下へ検索

次に文字列選択して下に「あああ」検索した場合です。

・下に検索前
あああ　あああ　あ|ああ　あああ
↓
・下に検索後
あああ　あああ　あああ　あああ|

下に検索すると、上に検索と一緒の仕様なら、3回目の「あああ」が選択されると思ったのですが、そーではなく、4回目の「あああ」が選択されます。ちなみに文字列選択している場合、カーソル位置は関係ないようです。この結果から選択していた場合の検索は選択終了位置から検索するようです。

選択文字列と検索文字列が一致している場合

検索時に選択している文字とこれから検索する文字が一致している場合、次の文字列を検索します。

・上に検索前
あああ　あああ　ああああああ|
↓
・上に検索後
あああ　ああああああ| あああ

これは、検索文字をダブルクリックで選択して、CTRL+Fで検索ダイアログを表示して、そのまま検索することが多いと思うので、自然の動作ですね。まとめるとメモ帳の検索は下記です。

検索仕様まとめ

ちなみにVisual Studio、VS Codeも大体同じ仕様でした。

文字列選択していない場合はカーソルの位置から検索する
文字列選択している場合は選択終了位置から検索する
選択範囲の文字列と検索文字列が一致している場合は次を検索する

自作テキストエディタの仕様

最初はメモ帳準拠していたんですが、選択範囲を置換とかを考慮して最終的にはこうしました。おそらく多くのエディタで採用されていると思います。

検索仕様

文字列選択していない場合はカーソルの位置から検索する(メモ帳と同じ)
文字列選択している場合、上に検索する場合は選択終了位置から検索する
文字列選択している場合、下に検索する場合は選択開始位置から検索する
選択範囲の文字列と検索文字列が一致している場合は次を検索する(メモ帳と同じ)

検索アルゴリズム

検索仕様は決まりました。次は検索方法ですよね。色々試してみたんですが、自作テキストエディタでは以下の方法で検索しています。

大文字小文字を区別する場合、C#なら IndexOf で C++ なら std::find を利用しています。大文字小文字を区別しない場合は BM法を改良した Quick Search(Sunday法)を利用しています。標準ライブラリを利用した場合はそのまま、力業で検索する方法ですね。結構速かったのでそのまま利用しようと思います。Quick Search(Sunday法)は面白そうなので実装してみました。

Quick Search(Sunday法)

例えば、テキストから「あいうえお」を検索する場合です。先頭から1文字ずつ比較していきます。「あいうえ」までは同じですが、5文字目が異なります。

標準ライブラリの場合だと、1文字移動してインデックス1から再度検索ですが、Quick Searchの場合、不一致になると検索パターンの文字数の次のインデックスの文字が検索パターンに含まれているかどうかで次の検索開始位置を決めます。

例だとインデックス5の文字列ですね。含まれていないと最大、検索パターン文字列数+1移動して検索することができます。

ただ、検索パターンが「あああああ」みたいに同じ文字列の場合、移動量は検索パターン文字列数+1の6ではなく、最大2になります。これは仕方ないですね。

サンプルコード

C#での Quick Search(Sunday法) のサンプルコードです。移動量のテーブルを算出しています。

/// <summary>
/// 検索時の移動量のテーブルを返します。
/// </summary>
/// <param name="pattern">検索文字列</param>
/// <returns>移動量テーブル</returns>
private Dictionary<char, int> CreateTable(string pattern) {
    var table = new Dictionary<char, int>();

    // 重複する文字列があった場合は小さい方を優先
    for (int i = 0; i < pattern.Length; ++i) {
        table[pattern[i]] = pattern.Length - i;
    }
    return table;
}

こちらは実際の検索処理です。検索文字列を見つけるとその文字インデックスを返します。

/// <summary>
/// 指定した文字列を検索します。
/// </summary>
/// <param name="text">検索対象文字列</param>
/// <param name="pattern">検索文字列</param>
/// <param name="findPosition">検索開始位置</param>
/// <returns>見つかったインデックスを返します。見つからなかった場合は -1</returns>
public int QuickSearch(string text, string pattern, int findPosition) {
    int textLength = text.Length;
    int patternLength = pattern.Length;
    if (textLength < patternLength) {
        return -1;
    }

    // 移動量テーブル取得
    Dictionary<char, int> table = this.CreateTable(pattern, isNext);

    textLength -= patternLength;
    while (findPosition <= textLength) {
        // 比較    
        int patternIndex;
        for (patternIndex = 0; patternIndex < patternLength; patternIndex++) {
            if (text[findPosition + patternIndex] != pattern[patternIndex]) {
                break;
            }
        }
        // 一致した場合
        if (patternLength <= patternIndex) {
            return findPosition;
        }
        // 比較対象が存在しない場合
        if (findPosition == textLength) {
            break;
        }
        // インデックス移動
        if (table.TryGetValue(text[findPosition + patternLength], out int value)) {
            findPosition += value;
        } else {
            findPosition += patternLength + 1;
        }
    }
    return -1;
}