文字列類似結合

2つの文字列データの中から類似文字列ペアを全て列挙する問題を文字列類似結合(string similarily join)とよぶ。この問題は、データベースの統合に用いられている。

文字列間の距離を測る尺度の一つとして編集距離(edit distance)がある。編集距離は文字に対する挿入、削除、置換に着目した尺度である。

文字列類似結合では、 工夫しない場合は全ての文字列ペアに対して距離計算を行う必要がある。高速化の既存手法としては、ハッシュ、qgram、トライを用いたものがある。