regex - 正規表現と文字列の間の編集距離を計算することは可能ですか？

Question

もしそうなら、その方法を説明してください。

Re：距離とは-「2つの文字列間の距離は、一方を他方に変換するために必要な編集の最小数として定義されます。」

たとえば、xyzからXYZへの編集には3回かかるため、文字列xYZはXYZとxyzに近くなります。

パターンが[0-9]{3}またはたとえば123の場合、a23はab3よりもパターンに近くなります。

正規表現と一致しない文字列の間の最短距離をどのように見つけることができますか？

上記は、ダメラウ・レーベンシュタイン距離アルゴリズムです。

Answer 1

有限状態マシンを使用して、これを効率的に（つまり、時間的に線形に）行うことができます。トランスデューサーを使用する場合は、変換の仕様をかなりコンパクトに記述し、単に挿入または削除するよりもはるかに微妙な変換を行うことができます-開始点としての有限状態トランスデューサーのウィキペディア、およびFSAツールキットやFSA6などのソフトウェアを参照してください（これも完全に安定したWebデモではありません）。FSA操作用のライブラリはたくさんあります。前の2つがあなたの唯一の、または最良の選択肢であることを示唆したくはありません。私が聞いたのは2つだけです。

ただし、効率的で近似的な検索が必要な場合は、柔軟性は低くなりますが、すでに実装されているオプションがあります。TREは、一致のコスト、つまり一致までの距離を返す近似一致関数を備えています。 、あなたの視点から。

Answer 2

最も近い一致した文字列とサンプルの間のレーベンシュタイン距離が最小の文字列を意味する場合、それは可能であると確信していますが、正規表現を自分でDFAに変換してから、いつでも一致させてみてください。何かが失敗し、それが通過したかのように非決定的に続行し、数の違いを追跡します。これにはA*検索などを使用できますが、非常に非効率的です（O（2 ^ n）最悪の場合）