Rata-rata jumlah string dengan jarak edit maksimal 3 (alfabet lebih besar)

Question

Pertimbangkan untaian panjang $n \geq 3$ di atas alfabet $\{1,\dots, \sigma\}$. Operasi edit adalah penyisipan, penghapusan, atau penggantian simbol tunggal. Jarak edit antara dua string adalah jumlah minimum operasi edit yang diperlukan untuk mengubah satu string menjadi string lainnya. Diberikan sebuah string$S$ panjangnya $n$ dengan $S_i \in \{1,\dots, \sigma\}$, pertanyaan saya berkaitan dengan jumlah string berbeda yang paling banyak mengedit jarak $3$ dari $S$.

Mari kita tulis $g_{k, \sigma}(S)$ untuk jumlah string berbeda di atas alfabet $\{1,\dots, \sigma\}$ yang merupakan jarak edit paling banyak $k$ dari $S$, yaitu $g_{k,\sigma}(S) = |\{S' : d(S', S) \leq k\}|$ dimana $d(-,-)$ adalah jarak edit.

Membiarkan $X_n$ menjadi variabel acak yang mewakili string acak di atas alfabet $\{1,\dots, \sigma\}$ panjangnya $n$, dengan simbol yang dipilih secara seragam dan independen.

Ini mengarah langsung ke pertanyaan saya:

Membiarkan $X_n$ menjadi variabel acak yang mewakili panjang string acak $n$, dengan simbol yang dipilih secara seragam dan independen. Apa yang:

$$\mathbb{E}(g_{3, \sigma}(X_n))\;?$$

Untuk $\sigma=2$kita bisa mendapatkan rumus eksplisit $(40+6n-4n^2)/2^n-83/2+(331/12)n-6n^2+(2/3)n^3$. Jadi pertanyaan saya adalah, apa ketergantungan pada ukuran alfabet$\sigma$ terlihat seperti?

Answer 1

Memvariasikan v. Panjang String Tidak Berubah

Jika, seperti yang Anda tunjukkan pada awalnya sebagai tanggapan atas komentar saya, panjang string yang diubah dapat berbeda dari panjang aslinya, maka masalah ini menjadi jauh lebih sulit karena rangkaian operasi pengeditan yang berbeda (operasi yang berpotensi menghasilkan hasil yang berbeda ) mencakup semua 18 hal berikut:

• panjang +3 = 3 sisipan
• panjang +2 = 2 sisipan dan 0 atau 1 substitusi
• panjang +1 = 1 penyisipan dan 0, 1, atau 2 substitusi
• panjang tidak berubah = 0, 1, 2, atau 3 substitusi; 1 penghapusan, 1 penyisipan, dan 0 atau 1 substitusi
• panjang -1 = 1 penghapusan dan 0, 1, atau 2 substitusi
• panjang -2 = 2 penghapusan dan 0 atau 1 substitusi
• panjang -3 = 3 penghapusan

Setiap kali beberapa penyisipan atau beberapa penghapusan dilakukan, lebih lagi, penghitungan menjadi sangat sulit. Sebaliknya, jika kami mengharuskan panjangnya tetap tidak berubah, kami hanya memiliki 6 kombinasi pengeditan untuk dipertimbangkan dan masalah menjadi lebih mudah ditangani karena tidak satu pun dari 6 kombinasi tersebut yang melibatkan banyak penyisipan atau penghapusan ganda. Memang, penghitungan untuk masing-masing dari enam kasus menjadi relatif mudah; bit tersulit adalah diskon untuk menghindari contoh penghitungan ganda ketika dua operasi pengeditan yang berbeda akan menghasilkan string yang sama - masalah diselesaikan dalam jawaban untuk pertanyaan lain .

Enam Kasus dan Bahaya Overcounting
Untuk mengetahui arah awal, kita dapat menggeneralisasi logika ini :

• Tali harus dipertahankan $n$ simbol.
• Jumlah kelompok simbol identik yang diharapkan adalah $\frac{n+1}{\sigma}$
• Jumlah yang diharapkan dari pasangan simbol identik yang berdekatan adalah $\frac{n-1}{\sigma}$
• Jumlah ujungnya adalah 2.

Pertimbangan mendetail dari lima kemungkinan jenis pengeditan tunggal menghasilkan:

• Jumlah kemungkinan substitusi adalah $n(\sigma-1)$
• Jumlah penyusutan yang diharapkan dari sekelompok simbol identik adalah $\frac{n+1}{\sigma}$
• Jumlah ekspansi yang diharapkan dari sekelompok simbol identik dengan simbol yang sama adalah $\frac{n+1}{\sigma}$
• Jumlah yang diharapkan dari sisipan ke dalam kelompok simbol identik dengan simbol yang sama adalah $\frac{n-1}{\sigma}$
• Jumlah kemungkinan penyisipan karakter yang berbeda di awal atau akhir adalah $2(\sigma-1)$

Sekarang kita dapat menerapkan logika dasar itu ke masing-masing dari enam kasus kita:

1. tidak ada pengeditan
   Tidak melakukan pengeditan apa pun hanya menghasilkan string asli, jadi 1 hasil untuk kasus ini.

2. satu substitusi
   Ada$n$ simbol yang berbeda dan $\sigma-1$ cara masing-masing dapat diganti menjadi simbol yang berbeda, jadi $n(\sigma-1)$ hasil.

3. dua substitusi
   Ada$\binom{n}{2}$ pasangan yang berbeda dan $(\sigma-1)^2$ cara untuk memodifikasi masing-masing: $\binom{n}{2}(\sigma-1)^2$ hasil.

4. tiga substitusi
   Ada$\binom{n}{3}$ trio yang berbeda dan $(\sigma-1)^3$ cara untuk memodifikasi masing-masing: $\binom{n}{3}(\sigma-1)^3$.

5. satu penghapusan, satu penyisipan, tidak ada substitusi
   Untuk kasus ini, kita dapat menggeneralisasi solusi ini untuk$\sigma=2$ untuk setiap $\sigma$, menggunakan logika yang sama untuk menghindari penghitungan ganda instance tersebut di mana dua substitusi akan menghasilkan hasil yang sama seperti satu penghapusan dan satu penyisipan.

Mari kita hitung kasus di mana penyisipan berada di sebelah kiri penghapusan dan kemudian dikalikan dengan 2. Efek gabungan dari penyisipan dan penghapusan adalah menggeser semua bit 𝑘 di antara mereka ke kanan sambil mengganti yang pertama dan menghapus yang terakhir . Hasil ini juga dapat dicapai dengan paling banyak 𝑘 substitusi, jadi kita membutuhkan 𝑘> 2. Memasukkan 𝑥 dalam run of 𝑥s memiliki efek yang sama seperti menyisipkan 𝑥 di akhir proses. Dengan demikian kita dapat menghitung semua penyisipan dengan efek berbeda satu kali dengan selalu menyisipkan bit yang melengkapi yang ada di sebelah kanan penyisipan. Demikian pula, penghapusan dalam proses memiliki efek yang sama seperti penghapusan di awal proses, jadi kita hanya harus menghitung penghapusan yang mengikuti perubahan antara 0 dan 1. Itu memberi kita hitungan awal:

$2\cdot\frac12\sum_{k=3}^n(n+1-k)=\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}2\;$

Karena logika rumit untuk mencegah penghitungan ganda terbawa langsung, satu-satunya modifikasi yang diperlukan adalah mengganti variabel $\sigma$ untuk diperbaiki $\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}\;$

Kelebihan hasil yang telah dihitung sebagai dua substitusi dapat dihitung sebagai berikut: $\sigma=2$:

Jika tidak ada perubahan lebih lanjut dalam bit 𝑘 yang digeser selain yang sebelum penghapusan, maka hanya bit di sebelah penyisipan dan penghapusan yang berubah, dan kita dapat mencapainya dengan 2 substitusi, jadi kita harus mengurangi

$\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)}\;$

Sekali lagi, satu-satunya modifikasi kami adalah menggantinya $\sigma$ untuk 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)}\;$

Juga, jika seluruh rentang bit yang digeser terdiri dari nol dan satu bergantian, maka menukar penyisipan dan penghapusan menghasilkan efek yang sama, jadi dalam hal ini kami menghitung ganda dan perlu mengurangi

$\sum_{k=3}^n\left(\frac12\right)^{k-1}(n+1-k)\;$

Menukar $\sigma$ waktu terakhir menghasilkan:

$\sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\;$

Kedua kelebihan ini (yang sayangnya, tidak dapat digabungkan dengan bersih seperti ketika simbolnya biner) kemudian dikurangkan dari penghitungan awal operasi penghapusan / penyisipan untuk menghasilkan hasil keseluruhan yang dihasilkan oleh kasus ini, tetapi tidak dengan kasus 3 di atas:

$\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. satu penghapusan, satu penyisipan, satu substitusi
   Perhitungan yang sama dibawa ke kasus terakhir. Di sini, bagaimanapun, setiap kombinasi dari satu penghapusan dan satu penyisipan - juga didiskontokan untuk menghindari penghitungan ganda substitusi rangkap tiga yang sudah dihitung dalam kasus 4 di atas - disertai dengan suntingan ketiga: substitusi yang melibatkan salah satu dari$n-1$simbol asli yang tersisa setelah penghapusan. Karena masing-masing ini$(n-1)$ simbol mengakui $(\sigma-1)$ substitusi baru, jumlah total untuk kasus keenam dan terakhir menjadi:

$\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);$

Menjumlahkan hasil (yang sebelumnya tidak dihitung) yang dihasilkan oleh masing-masing dari enam kasus ini harus menghasilkan hitungan yang diharapkan ketika panjang string tetap tidak berubah. Itu jelek (mungkin tidak perlu), tapi saya harap benar.