知的で高度な言語処理を実現するには，辞書，シソーラス，コーパスなどの言語資源の整備・構築が欠かせない．一方，実際のテキストに対して，言語資源を活用するときにボトルネックとなるのが，表層表現が実テキストと言語資源では一致しない問題である．例えば，「スパゲティー」には，「スパゲッティ」「スパゲティ」「スパゲッテー」などの異表記があるが，完全一致の文字列マッチングでは，これらの異表記から言語資源に含まれるエントリ（例えば「スパゲティー」）を引き出すことができない．ウェブなどの大規模かつ統制されていないテキストには，大量の異表記や表記誤りが含まれると考えられ，これらの実テキストに対して言語処理を頑健に適用するには，言語資源とテキストを柔軟にマッチングさせる技術が必要である．文字列を標準的な表記に変換してからマッチングさせる手法として，ステミング~\cite{Porter:80}，レマタイゼーション~\cite{Okazaki:08,Jongejan:09}，スペル訂正~\cite{Brill:00,Ahmad:05,Li:06,Chen:07}，人名表記の照合~\cite{Takahashi:95}，カタカナ異表記の生成及び統一~\cite{獅々堀:94}，等が代表的である．これらの研究に共通するのは，与えられた文字列から標準形に変換するための文字列書き換え規則を，人手，マイニング，もしくは機械学習で獲得していることである．これらの研究では，語幹やカタカナ異表記など，異表記のタイプに特化した文字列書き換え規則を獲得することに，重点が置かれる．本論文では，より一般的なタスク設定として，与えられた文字列に似ている文字列を，データベースの中から見つけ出すタスク（{\bf類似文字列検索}）を考える．本論文では，「文字列の集合$V$の中で，検索クエリ文字列$x$と類似度が$\alpha$以上の文字列を全て見つけ出す操作」を，類似文字列検索と定義する．この操作は，$V$の部分集合$\mathcal{Y}_{x,\alpha}$を求める問題として記述できる．\begin{equation}\mathcal{Y}_{x,\alpha}=\{y\inV\bigm|{\rmsim}(x,y)\geq\alpha\}\label{equ:approximate-string-retrieval}\end{equation}ただし，${\rmsim}(x,y)$は文字列$x$と$y$の類似度を与える関数（{\bf類似度関数}）である．この問題の単純な解法は，検索クエリ文字列$x$が与えられる度に，文字列の類似度を総当たりで$|V|$回計算することである．文字列集合の要素数$|V|$が小さいときには，総当たりで解を求めることも可能だが，文字列集合が膨大（例えば数百万オーダー以上の要素数）になると，実用的な時間で解けなくなる．本論文では，自然言語処理でよく用いられる類似度関数であるコサイン係数，ジャッカード係数，ダイス係数，オーバーラップ係数に対して，式\ref{equ:approximate-string-retrieval}の簡潔かつ高速なアルゴリズムを提案する．本論文の貢献は，以下の2点に集約される．\begin{enumerate}\itemまず，類似文字列検索における必要十分条件及び必要条件を導出し，式\ref{equ:approximate-string-retrieval}が転置リストにおける{\bf$\tau$オーバーラップ問題}~\cite{Sarawagi:04}として正確に解けることを示す．次に，$\tau$オーバーラップ問題の効率的な解法として，{\bfCPMerge}アルゴリズムを提案する．このアルゴリズムは，$\tau$オーバーラップ問題の解となり得る文字列の数をできるだけコンパクトに保つ特徴がある．提案手法の実装は非常に容易であり，C++で実装したライブラリ\footnote{SimString:http://www.chokkan.org/software/simstring/}を公開している．\item提案手法の優位性を示すため，英語の人名，日本語の単語，生命医学分野の固有表現を文字列データとして，類似文字列検索の性能を評価する．実験では，類似文字列検索の最近の手法であるLocalitySensitiveHashing(LSH)~\cite{Andoni:08}，SkipMerge,DivideSkip~\cite{Li:08}等と提案手法を比較する．実験結果では，提案手法が全てのデータセットにおいて，最も高速かつ正確に文字列を検索できることが示される．\end{enumerate}本論文の構成は以下の通りである．次節では，類似文字列検索の必要十分条件，必要条件を導出し，式\ref{equ:approximate-string-retrieval}が$\tau$オーバーラップ問題として正確に解けることを示す．第\ref{sec:method}節では，本論文が提案するデータ構造，及び$\tau$オーバーラップ問題の効率的なアルゴリズムを説明する．第\ref{sec:evaluation}節で，評価実験とその結果を報告する．第\ref{sec:related-work}節では，類似文字列検索の関連研究をまとめる．第\ref{sec:conclusion}節で，本論文の結論を述べる．