Fast Fuzzy String Search System for Large-Scale Data

プロジェクト概要

100万件規模の文字列データベースから、類似文字列を高速に検索するシステムをC言語で開発しました。

検索対象は編集距離3以内の文字列です。文字の追加、削除、置換を3回以内で変換できる候補を、検索漏れなしで抽出することを目指しました。

5人チームで約1カ月、私はアルゴリズムのコア設計を担当しました。

• 使用言語: C言語, Python(性能評価のみ)
• 達成成果: 精度100%を達成(実行時間:18.65秒)

アルゴリズムの概要

100万件すべてに対して編集距離を正確に計算すると、処理が追いつきません。

類似文字列検索では BK 木などの木構造を使う方法もありますが、今回は導入を見送りました。

文字列長に対する許容エラー率が高く（約20%）、木探索によるランダムアクセスがCPUキャッシュのヒット率を下げ、ボトルネックになると判断したためです。

代わりに明らかに違うものを安く弾き、怪しいものだけを精密に調べるという多段階フィルタのパイプラインを設計しました。

インデックスの構築

15文字の文字列を4パートに分割し、各パートを整数値に変換してインデックスを作成しました。 検索時は、この索引で候補を先に絞ります。

ソートには比較操作不要でO(N)の計数ソートを採用し、検索時のメモリアクセスも連続的になるよう配慮しました。

3段階のフィルタリング

検索クエリに対して、次の順でフィルタを適用します。

• ヒストグラム間L1距離: 文字種の出現頻度を比較し、差が6を超える候補を除外。これにより全候補の約91.8%を高速に棄却しました。

• ハミング距離計算: 64bit XOR演算とハードウェア命令のビットカウントを活用し、置換のみの類似度を定数時間で判定。最終マッチの約25%をここで確定。

• Myersのビット並列アルゴリズム: Eugene W. Myersのビット並列アルゴリズムを採用。動的計画法の表計算を論理演算のみに置き換え、条件分岐なしで厳密な編集距離を算出。

計算コストが低い順に適用することで、計算量の重いMyersのアルゴリズムの実行を9割以上スキップできました。

評価と分析

実装後、プログラム内部の処理効率を計測・プロファイリングしました。

• ヒストグラムフィルタによってMyers法による高負荷な計算の実行を9割以上スキップできたことが最大の高速化要因でした。
• 一方、ヒストグラムを通過した候補のうち最終マッチに至ったのは**0.26%**でした。文字の構成は似ているが並び順が異なる候補をどう減らすかが、今後の課題です。

今後の改善点と考察

アルゴリズム設計の視点

高速化の焦点を候補生成後のフィルタリングに当てすぎたことが反省点です。文字列を4分割ではなく5分割にすることで、鳩ノ巣原理により「少なくとも2か所の完全一致」が保証されることに気が付きました。過剰なフィルタリング処理を実装するよりも、分割数の最適化で検証候補自体を生成させない設計に注力すべきでした。

チーム開発の視点

GitHubを用いた並行開発（ブランチ運用とプルリクエスト統合）を計画しましたが、タスクの切り出しが粗く、特定のメンバーに実装負荷が偏りました。 原因は、コードを書き始める前に技術的な前提知識やデータ構造の設計意図をチーム全体で同期しきれていなかったことです。この経験から、ツールの運用ルールだけでなく、事前の設計共有とドキュメント化の重要性を学びました。