編集距離が最大3の文字列の平均数（アルファベットが大きい）
長さの文字列を考えてみましょう $n \geq 3$ アルファベット以上 $\{1,\dots, \sigma\}$。編集操作は、単一のシンボルの挿入、削除、または置換です。2つの文字列間の編集距離は、一方の文字列をもう一方の文字列に変換するために必要な編集操作の最小数です。与えられた文字列$S$ 長さの $n$ と $S_i \in \{1,\dots, \sigma\}$、私の質問は、最大で編集距離である個別の文字列の数に関連しています $3$ から $S$。
書きましょう $g_{k, \sigma}(S)$ アルファベット上の個別の文字列の数 $\{1,\dots, \sigma\}$ せいぜい編集距離です $k$ から $S$、すなわち $g_{k,\sigma}(S) = |\{S' : d(S', S) \leq k\}|$ どこ $d(-,-)$ 編集距離です。
しましょう $X_n$ アルファベット上のランダムな文字列を表す確率変数である $\{1,\dots, \sigma\}$ 長さの $n$、シンボルは均一かつ独立して選択されます。
これは私の質問に直接つながります：
しましょう $X_n$ 長さのランダムな文字列を表す確率変数である $n$、シンボルは均一かつ独立して選択されます。とは：
$$\mathbb{E}(g_{3, \sigma}(X_n))\;?$$
ために $\sigma=2$明示的な式を得ることができます $(40+6n-4n^2)/2^n-83/2+(331/12)n-6n^2+(2/3)n^3$。だから私の質問は、アルファベットのサイズへの依存は何ですか？$\sigma$ のように見える？
回答
変化するv。変更されていない文字列の長さ
私のコメントに応えて最初に示したように、変換された文字列の長さが元の文字列の長さと異なる可能性がある場合、一連の個別の編集操作（個別の結果をもたらす可能性のある操作）があるため、この問題は非常に困難になります）次の18個すべてが含まれます。
- 長さ+ 3 = 3挿入
- 長さ+ 2 = 2つの挿入と0または1つの置換
- 長さ+ 1 = 1回の挿入と0、1、または2回の置換
- 長さは変更されていません= 0、1、2、または3回の置換。1つの削除、1つの挿入、および0または1つの置換
- 長さ-1 = 1つの削除と0、1、または2つの置換
- 長さ-2 = 2つの削除と0または1つの置換
- 長さ-3 = 3つの削除
さらに、複数の挿入または複数の削除が実行されるたびに、カウントが非常に困難になります。一方、長さを変更しない必要がある場合は、考慮すべき編集の組み合わせが6つしかないため、これらの6つの組み合わせのいずれにも複数の挿入または複数の削除が含まれないため、問題はより扱いやすくなります。実際、6つのケースのそれぞれのカウントは比較的簡単になります。最もトリッキーなビットは、2つの異なる編集操作で同じ文字列が生成される場合に、インスタンスの二重カウントを回避するために割り引くことです。この問題は、別の質問への回答で解決されました。
6つのケースと過大評価の危険性最初に方位
を取得するために、このロジックを一般化できます。
- 文字列は維持する必要があります $n$ シンボル。
- 同一のシンボルのグループの予想数は $\frac{n+1}{\sigma}$
- 隣接する同一のシンボルペアの予想数は次のとおりです。 $\frac{n-1}{\sigma}$
- 端の数は2です。
したがって、5つの可能なタイプの単一編集をきめ細かく検討すると、次のようになります。
- 可能な置換の数は $n(\sigma-1)$
- 同一のシンボルのグループの予想される収縮数は次のとおりです。 $\frac{n+1}{\sigma}$
- 同じシンボルを持つ同一のシンボルのグループの予想される膨張数は次のとおりです。 $\frac{n+1}{\sigma}$
- 同じシンボルを持つ同一のシンボルのグループへの予想される挿入数は次のとおりです。 $\frac{n-1}{\sigma}$
- 最初または最後に異なる文字を挿入できる数は次のとおりです。 $2(\sigma-1)$
これで、その基本的なロジックを6つのケースのそれぞれに適用できます。
編集なし編集を
実行しないと、元の文字列のみが生成されるため、この場合は1つの結果になります。1つの置換
があります$n$ 異なる記号と $\sigma-1$ それぞれを異なるシンボルに置き換えることができる方法、 $n(\sigma-1)$ 結果。2つの置換
があります$\binom{n}{2}$ 異なるペアと $(\sigma-1)^2$ それぞれを変更する方法： $\binom{n}{2}(\sigma-1)^2$ 結果。3つの置換
があります$\binom{n}{3}$ 異なるトリオと $(\sigma-1)^3$ それぞれを変更する方法： $\binom{n}{3}(\sigma-1)^3$。1つの削除、1つの挿入、置換なし
この場合、このソリューションを一般化できます。$\sigma=2$ に $\sigma$、同じロジックを使用して、2つの置換が1つの削除と1つの挿入と同じ結果をもたらすインスタンスの二重カウントを回避します。
挿入が削除の左側にあり、次に2を掛ける場合を数えましょう。挿入と削除の複合効果は、最初のビットを置き換え、最後のビットを削除しながら、それらの間のすべての𝑘ビットを右にシフトすることです。 。この結果は、多くても𝑘置換によっても達成できるため、𝑘> 2が必要です。𝑥の実行内に𝑥を挿入すると、実行の最後に𝑥を挿入するのと同じ効果があります。したがって、挿入の右側のビットを常に補完するビットを挿入することにより、異なる効果を持つすべての挿入を1回カウントできます。同様に、実行内の削除は、実行開始時の削除と同じ効果があるため、0から1の間の変更に続く削除のみをカウントする必要があります。これにより、次の初期カウントが得られます。
$2\cdot\frac12\sum_{k=3}^n(n+1-k)=\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}2\;$
二重カウントを防ぐためのトリッキーなロジックは直接引き継がれるため、必要な変更は変数を置き換えることだけです。 $\sigma$ 固定用 $\sigma=2$：
$2\cdot\frac{1}{\sigma}\sum_{k=3}^n(n+1-k)=2\cdot\frac{1}{\sigma}\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}{\sigma}\;$
2つの置換としてすでに集計されている結果の過大カウントは、次の場合に次のように計算できます。 $\sigma=2$：
削除の前のビット以外に𝑘シフトされたビットにそれ以上の変更がない場合、挿入と削除の隣のビットのみが変更され、2つの置換でそれを達成できるため、減算する必要があります
$\sum_{k=3}^n\left(\frac12\right)^{k-2}(n+1-k)=\sum_{k=1}^{n-2}\left(\frac12\right)^{n-k-1}k=n-3+2^{-(n-2)}\;$
繰り返しますが、私たちの唯一の変更は、置き換えることです $\sigma$ 2の場合：
$\sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-2}(n+1-k)=\sum_{k=1}^{n-2}\left(\frac1{\sigma}\right)^{n-k-1}k=n-3+{\sigma}^{-(n-2)}\;$
また、シフトされたビットの範囲全体が0と1の交互の範囲で構成されている場合、挿入と削除を入れ替えても同じ効果が得られるため、この場合は二重にカウントし、減算する必要があります。
$\sum_{k=3}^n\left(\frac12\right)^{k-1}(n+1-k)\;$
交換 $\sigma$ 最終時間は次のようになります。
$\sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\;$
これらの2つのオーバーカウント（残念ながら、シンボルがバイナリの場合ほどきれいに組み合わせることができない）は、削除/挿入操作の初期カウントから差し引かれ、このケースで生成された全体的な結果が得られますが、上記のケース3では生成されません。
$\frac{(n-1)(n-2)}{\sigma}\ - \left(n-3+{\sigma}^{-(n-2)}\right) - \sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\;$
- 1回の削除、1回の挿入、1回の置換
同じ計算が最終的なケースに引き継がれます。ただし、ここでは、1つの削除と1つの挿入の各組み合わせ（上記のケース4ですでに集計されたトリプル置換の二重カウントを回避するために割引される）には、3番目の編集が伴います。$n-1$削除後に残っている元のシンボル。これらのそれぞれ以来$(n-1)$ シンボルは認めます $(\sigma-1)$ 新規置換の場合、6番目と最後のケースの総数は次のようになります。
$\left(\frac{(n-1)(n-2)}{\sigma}\ - \left(n-3+{\sigma}^{-(n-2)}\right) - \sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\right)(n-1)(\sigma-1);$
これらの6つのケースのそれぞれによって生成された（以前はカウントされていなかった）結果を合計すると、文字列の長さが変わらない場合に期待されるカウントが得られるはずです。それは醜いです（おそらく不必要に）が、私は正しいことを願っています。