Pythonで同様の文字列を生成する方法

Question

Levenshtein distance（文字列編集距離）に基づいて同様の文字列を生成する方法が不思議です。理想的には、私はソース文字列（それに似た他の文字列を生成するために使用される文字列）を渡すのが好きです。文字列の数を生成する必要があり、パラメータとしての閾値、つまり生成されたセットはしきい値より大きくなければなりません。私はそれを達成するために何をPythonパッケージにするべきですか？またはこれをどのように実装するか考えていますか？

Answer 1

私はあなたが別の方法（逆）で問題を考えることができると思います。

• 与えられた文字列は、と表示されています。です。
• しきい値（編集距離）が与えられた場合、それはkと言います。
• 次に、異なる「編集」の組み合わせをkステップで適用します。

たとえば、のは、K = 2を言うと仮定しましょう許可edit modesあなたがいる：

• 1つの文字
• 代わる別のものと1つの文字を追加する1つの文字
• を削除します。

その後論理は以下のようなものです：あなたは、いくつかの複雑になりますが、それはまだなんとかです事前に定義された辞書、に固執する必要がある場合

input = 'sittin' 
for num in 1 ... n: # suppose you want to have n strings generated 
    my_input_ = input 
    # suppose the edit distance should be smaller or equal to k; 
    # but greater or equal to one 
    for i in in 1 ... randint(k): 
    pick a random edit mode from (delete, add, substitute) 
    do it! and update my_input_ 

。この場合、編集は有効でなければなりません。