近似文字列マッチング問題の一つの可能な定義は、次のとおりです。 . . p m{\displaystyle P=p_{1}p_{2}…p_{m}}
とテキスト文字列T=t1t2…t n{\displaystyle T=t_{1}t_{2}\dots t_{n}}
、部分文字列T j’,j=t j’…t j{\displaystyle T_{j’,j}=t_{j’}\dots t_{j}}
tのすべての部分文字列のうち、パターンpまでの編集距離が最小です。
ブルートフォースアプローチは、tのすべての部分文字列に対してpまでの編集距離を計算し、最小距離を持つ部分文字列を選択することです。 ただし、このアルゴリズムの実行時間はO（n3m）になります。
売り手によって提案されたより良い解決策は、動的プログラミングに依存しています。 テキストTの各位置jとパターンPの各位置iについて、パターンのi番目の文字P i{\displaystyle P_{i}}
と任意の部分文字列T j’,j{\displaystyle T_{j’,j}}
位置jで終わるtの。
テキストTの各位置jとパターンPの各位置iについて、位置jで終わるTのすべての部分文字列を調べ、それらのうちのどれがパターンPのi最初の文字までの最小距離を持つかを決定します。この最小距離をE(i,j)と書きます。 すべてのiとjについてE(i,j)を計算した後、元の問題の解決策を簡単に見つけることができます。e(m,j)が最小である部分文字列です（mはパターンPの長さです）
E(m,j)を計算することは、二つの文字列間の編集距離を計算することに非常に似ています。 唯一の違いは、最初の行をゼロで初期化し、計算のパスを保存する必要があること、つまりE(i−1,j)、E(i,j−1)またはE(i−1,j−1)をe(i,j)の計算に使用したかどうかです。
E(x,y)値を含む配列で、最後の行の最小値を選択し、それをE(x2,y2)とし、計算のパスを逆方向にたどり、行番号0に戻します。 私たちが到着したフィールドがE（0、y1）であれば、T。.. Tは、パターンPまでの最小編集距離を持つTの部分文字列です。
e(x,y)配列の計算には、動的計画アルゴリズムでO(mn)時間がかかり、逆方向作業フェーズにはO(n+m)時間がかかります。もう一つの最近のアイデアは、類似性結合です。
マッチングデータベースが大規模なデータに関連する場合、動的計画アルゴリズムとのO(mn)時間は限られた時間内には機能しません。 したがって、アイデアは、文字列のすべてのペアの類似性を計算する代わりに、候補ペアの数を減らすことです。 広く使用されているアルゴリズムは、フィルタ検証、ハッシュ、局所性に敏感なハッシュ（LSH）、試行および他の貪欲および近似アルゴリズムに基づいてい それらのほとんどは、いくつかのフレームワーク（Map-Reduceなど）に合わせて同時に計算するように設計されています。