C#における高速検索・強調表示：拼音首字母対応、文字列エンコーディング、キーワードハイライトの実装

何百万ものファイル名のようなアイテムを処理する検索において、各マッチングの効率は総検索時間に大きく影響します。ファイル名とキーワードの照合ごとに複雑な処理を行うと、累積的な影響が総時間に及び、ユーザーエクスペリエンスを損なう可能性があります。本稿では、TDSにおけるテキスト検索ロジックについて詳述し、参考として提供します。

一、拼音首文字変換

文字列「123四五六78abc」を例にとり、キーワード「sw」で「四五」、「六」で「六」をそれぞれヒットさせることを想定します。漢字の拼音首文字を取得するには、まず文字のUnicodeエンコーディングを取得する必要があります。多音字を考慮しない場合、テーブル参照で簡単に実装できます。文字が中国語の範囲内であれば、対応する首文字を直接返します。具体的な実装は以下の通りです。


return iCnChar switch
{
    >= 45217 and <= 45252 => 'A',
    >= 45253 and <= 45760 => 'B',
    >= 45761 and <= 46317 => 'C',
    >= 46318 and <= 46825 => 'D',
    >= 46826 and <= 47009 => 'E',
    >= 47010 and <= 47296 => 'F',
    >= 47297 and <= 47613 => 'G',
    >= 47614 and <= 48118 => 'H',
    >= 48119 and <= 49061 => 'J',
    >= 49062 and <= 49323 => 'K',
    >= 49324 and <= 49895 => 'L',
    >= 49896 and <= 50370 => 'M',
    >= 50371 and <= 50613 => 'N',
    >= 50614 and <= 50621 => 'O',
    >= 50622 and <= 50905 => 'P',
    >= 50906 and <= 51386 => 'Q',
    >= 51387 and <= 51445 => 'R',
    >= 51446 and <= 52217 => 'S',
    >= 52218 and <= 52697 => 'T',
    >= 52698 and <= 52979 => 'W',
    >= 52980 and <= 53688 => 'X',
    >= 53689 and <= 54480 => 'Y',
    >= 54481 and <= 65289 => 'Z',
    _ => throw new ArgumentOutOfRangeException(nameof(iCnChar), iCnChar, null)
};

上記変換後、文字列「123四五六78abc」は新しい文字列「123swl78abc」になります。そのため、元のテキストに対する検索は、元の文字列と拼音文字列の2回マッチングが必要です。現在、複数の方法を試しましたが、String.Containsが最も効率的であることがわかりました。StringComparison.OrdinalIgnoreCaseパラメータは、大文字小文字を区別せずに文字のUnicode値を直接比較するため、追加の文字変換操作を回避し、高速な文字列比較を実現します。組み込みメソッドを使用することで、基盤となる最適化を最大限に活用し、不要な計算を削減して全体的なパフォーマンスを向上させることができます。

二、ストレージとインデックスによる補助最適化

拼音首文字の事前変換は、リアルタイムの拼音変換よりもマッチング速度がはるかに高速です。ただし、ストレージ容量が極端に逼迫している場合を除きます。しかし、文字列が1つ増えると、文字列検索も1回増えることになり、文字列検索は時間を要する操作です。さらに最適化する方法はないでしょうか。

（一）パターン文字列

まず、特定長のchar配列をパターン文字列として作成します。長さ6の["a","b","c","1","2","3"]を例にとると、このパターン文字列には関心のある要素が含まれています。すべての漢字がアルファベットの空間にマッピングされているため、このパターン文字列は有限です。0-9の10個の記号と26個のアルファベット、およびその他の記号を合わせても64未満であるため、64ビット長のlong型でエンコーディングを簡単に格納できます。

（二）文字列エンコーディング

対象ファイル名「apple 1」を例にとります。パターン文字列の長さに対応するビット列0_0_0_0_0_0を初期化し、文字ごとにスキャンします。パターン文字列中のaと1がヒットした場合、ビット列記録により1_0_0_1_0_0が得られます。

対象ファイル名「xyz7890」を例にとります。パターン文字列の長さに対応するビット列0_0_0_0_0_0を初期化し、文字ごとにスキャンします。パターン文字列のいずれにもヒットしなかった場合、ビット列記録により0_0_0_0_0_0が得られます。

対象ファイル名「231cbaa」を例にとります。パターン文字列の長さに対応するビット列0_0_0_0_0_0を初期化し、文字ごとにスキャンします。パターン文字列のすべての文字がヒットした場合、ビット列記録により1_1_1_1_1_1が得られます。

有限のビット列はint32またはint64で簡単に格納でき、十分な容量があります。このバイナリエンコーディング方式は、ストレージスペースを節約するだけでなく、検索効率も大幅に向上させます。ブール演算（OR演算など）は、メモリのビットレベルで直接操作するため、文字列操作よりもはるかに高速です。一方、文字列操作は、文字ごとの比較と処理が必要です。

（三）キーワード予備選別

対象ファイル名「apple 1」を例にとると、この時点でのビット列は1_0_0_1_0_0 = 36（int値で表示）です。

  • キーワード「apel」を検索し、パターン文字列とマッチさせると、キーワードのビット列は1_0_0_1_0_0 = 36（10進数）になります。
  • キーワード「bpel」を検索し、パターン文字列とマッチさせると、キーワードのビット列は0_1_0_1_0_0 = 20（10進数）になります。

キーワードと対象ファイル名に対してOR演算を実行します。


int indexOriginTxt; // 初期化済みと仮定
int indexKeyTxt;    // 初期化済みと仮定
if (indexOriginTxt | indexKeyTxt != indexKeyTxt) return "インデックス予備選別失敗";

OR演算後の値が元の値と等しくない場合、キーワードと対象ファイル名がパターン文字列に存在しない文字を含んでいることを示します。

複数のキーワードの場合：


int indexOriginTxt;  // ファイル名
int indexKeyTxt1;  // 検索キーワード1、初期化済みと仮定
int indexKeyTxt2;  // 検索キーワード2、初期化済みと仮定
int indexKeyTxt3;  // 検索キーワード3、初期化済みと仮定
int indexKeyTxtFinal = indexKeyTxt2 | indexKeyTxt3;

if (indexOriginTxt | indexKeyTxtFinal != indexKeyTxt)
{
    return "インデックス予備選別失敗";
}
else
{
    // ...通常のテキスト検索
}

intまたはlongのOR演算は非常に軽量で、string.Containsよりもはるかに高速です。キーワードが多く、ファイル名が長いほど、フィルタリング効果は高まります。この予備選別メカニズムにより、大量の不一致ファイル名を迅速に除外し、後続の正確なマッチングの計算量を大幅に削減して、全体的な検索効率を向上させることができます。

基盤となる技術詳細：

  • 予備選別メカニズム： ビット演算による予備選別は、大量の不一致ファイル名を迅速に除外し、後続の正確なマッチングの計算量を削減できます。
  • パフォーマンス上の利点： ビット演算は非常に高速であり、大規模データの迅速なフィルタリングに適しています。

三、キーワードハイライト（v1.1.7で追加）

Avaloniaでは、ファイル名の表示はTextBlockコントロールを介して行われ、そのInlinesプロパティはカスタムハイライトコンバーターにバインドされます。


<TextBlock Inlines="{Binding FileName, Converter={StaticResource HighlightConverter}}" />

このコンバータークラスはIValueConverterインターフェイスを実装する必要があり、Avaloniaの依存性注入コンテナーによって自動的にインスタンス化されます。そのコアメソッドはConvertで、元のテキストをマッチしたキーワードに従って分割し、ハイライト表示用のInlineCollectionを構築します。具体的な実装は以下の通りです。

  • テキストセグメントを格納するためのInlineCollectionオブジェクトを初期化します。
  • 前処理されたキーワードマッチング結果（通常は開始位置でソートし、隣接または重複する区間をマージする必要がある）を反復処理します。
  • 非マッチング領域については、通常のRunオブジェクトを追加してテキストを表示します。
  • マッチング領域については、Runオブジェクトを作成し、ハイライトブラシ（例：Brushes.Yellow）を設定して前景​​色を変更します。
  • 複数のキーワードによって区間が重複したり、重複したりする問題に注意が必要です。アルゴリズム（区間マージなど）を使用して、各文字が1回だけ処理されるようにする必要があります。

// テキスト要素（Run）を格納するためのインライン要素コレクションを作成
var inlines = new InlineCollection();

// ソートおよび統合されたすべての検索結果を反復処理
foreach (var result in results)
{
    // 元のテキストから現在のセグメントのサブ文字列を抽出
    // result.Start: セグメントの開始位置
    // result.Length: セグメントの長さ
    var textSegment = nameOrigin.Substring(result.Start, result.Length);
    
    // テキストセグメントを表示するためのテキスト要素（Run）を作成
    var run = new Run(textSegment);

    // 現在のセグメントがマッチ項目である場合、ハイライトスタイルを適用
    // result.IsMatch: このセグメントが検索マッチ項目であるかどうかを示す
    if (result.IsMatch) 
    {
        // 前景色をハイライトブラシに設定し、マッチしたテキストを強調表示
        run.Foreground = highlightBrush;
        
        // オプション：その他のハイライトスタイルを追加（太字、背景色など）
        // run.FontWeight = FontWeight.Bold;
        // run.Background = Brushes.Yellow;
    }

    // テキスト実行をインラインコレクションに追加
    inlines.Add(run);
}

// 完成したインライン要素コレクションを返す
// このコレクションは、AvaloniaのTextBlockなどのコントロールで直接使用でき、ハイライト効果付きのテキストを表示できます。
return inlines;

注意点として、複数のキーワードをハイライトした後、substringの領域を再配置し、重複を排除または結合する必要があります。この設計は、ハイライト表示の正確性を保証するだけでなく、同じテキスト領域の重複処理を回避し、レンダリング効率を向上させます。これにより、ユーザーは検索キーワードがテキスト内のどこにあるかを明確に確認でき、ユーザーエクスペリエンスが向上します。

すべてのコンバーターは仮想モードでオンデマンドで実行されるため、パフォーマンス要件を良好に満たすことができます。

四、最後に

TDS検索ソフトウェアに関するその他の情報は、この公式アカウントの記事を参照してください：https://mp.weixin.qq.com/s/inD-brKhii57UJnCYLgxKQ

現在、TDS検索のバージョンは1.1.7に更新され、多くの詳細が最適化され、ハイライト、ディスクキャッシュインデックス、その他のオプションなどの機能が追加されています。ぜひご利用ください。

このツールについてご提案やご意見がありましたら、いつでもお気軽にご連絡ください！プロジェクトはGitHubで完全にオープンソース化されています。

お役に立てば、ぜひ「Star」⭐️で応援してください！https://github.com/LdotJdot/TDS

*****重要** WeChat公式アカウント「萤火初芒」をフォローしてください。問題があれば、公式アカウントにメッセージを残してください。作者はすぐに返信し、交流します～！！！***

タグ: C# 検索アルゴリズム 文字列処理 Unicode ビット演算

8月13日 12:42 投稿

ホットタグ

©2026 異端開発室