逆レーベンシュタイン距離

Question

レーベンシュタイン距離では、これらの2つのストリングを考えれば、彼らのレーベンシュタイン距離は何ですか？どのように文字列とlevenshtein距離を取って、そのlevenshtein距離内のすべての文字列を生成するつもりですか？ （それはまた、文字セットを取ります）。だから私は文字列xと距離dを渡す場合。 d-1とd-2を含むその編集距離内のすべての文字列を私に与えるでしょう.... d-n; （n <d）。

予想される機能：

>>> getWithinDistance('apple',2,{'a','b',' '}) 
['applea','appleb','appel','app le'...] 

プログラムは、スペースが文字セットに含まれているようapp leを生成することが可能であることに注意してください。

Answer 1

これにはLevenshtein automatonというデータ構造があります。文字列（メンバーは1つしかないかもしれません）と固定距離kから構成し、次に格納する文字列のうち、最大でkのすべての文字列に対してクエリを実行できます。 Pythonの実装については、hereを参照してください。

また、このような文字列のバックトラッキングを使用して深さ制限検索を行うこともできます。