Bagian Panduan untuk tugas sumber
Delapan pemeriksaan berikut berkorespondensi, secara berurutan, dengan lima tugas yang diratakan dari bagian Metrik Hamming dan tiga tugas dari bagian Metrik Levenshtein.
Buktikan bahwa fungsi \(d_H\) pada \(X^n\text{,}\) dengan \(X=\{0,1\}\text{,}\) benar-benar merupakan metrik. Rubrik: tangani tak-negatif, identitas titik, simetri, dan pertidaksamaan segitiga; jangan mengganti bukti umum dengan satu contoh numerik.
Petunjuk.
Jawaban.
Solusi.
Petunjuk 1. Setiap suku \(|x_i-y_i|\) bernilai nol atau satu.
Petunjuk 2. Terapkan pertidaksamaan segitiga nilai mutlak pada setiap koordinat, lalu jumlahkan.
Ya. Keempat aksioma metrik mengikuti sifat nilai mutlak pada setiap koordinat dan fakta bahwa jumlahnya nol tepat ketika semua koordinat sama.
Karena setiap \(|x_i-y_i|\geq0\text{,}\) jumlah \(d_H(x,y)=\sum_{i=1}^n|x_i-y_i|\) tak negatif. Jumlah ini nol tepat ketika setiap sukunya nol, yakni tepat ketika \(x_i=y_i\) untuk semua \(i\text{;}\) keadaan itu setara dengan \(x=y\text{.}\) Kesamaan \(|x_i-y_i|=|y_i-x_i|\) pada setiap koordinat memberi simetri.
Untuk \(x,y,z\in X^n\text{,}\) pertidaksamaan nilai mutlak memberi \(|x_i-y_i|\leq|x_i-z_i|+|z_i-y_i|\) untuk setiap \(i\text{.}\) Menjumlahkan dari \(i=1\) sampai \(n\) menghasilkan \(d_H(x,y)\leq d_H(x,z)+d_H(z,y)\text{.}\) Jadi \(d_H\) memenuhi seluruh aksioma metrik.
Pemeriksaan D.2. Tugas Hamming 2: jarak dua kata kode.
Untuk kode \(C\) pada bab utama, hitung \(d_H(c_2,c_8)\) dan tunjukkan koordinat mana yang menyumbang pada jarak tersebut.
Petunjuk.
Jawaban.
Solusi.
Petunjuk. Bandingkan \(000011\) dan \(001111\) dari kiri ke kanan.
\(d_H(c_2,c_8)=2\text{;}\) kedua kata berbeda tepat pada koordinat ketiga dan keempat.
Kita mempunyai \(c_2=(0,0,0,0,1,1)\) dan \(c_8=(0,0,1,1,1,1)\text{.}\) Selisih pada koordinat pertama, kedua, kelima, dan keenam adalah nol, sedangkan selisih pada koordinat ketiga dan keempat bernilai satu. Karena itu, \(d_H(c_2,c_8)=0+0+1+1+0+0=2\text{.}\)
Pemeriksaan D.3. Tugas Hamming 3: menyiapkan pesan untuk pendekodean.
Namai kelima blok pada pesan yang diterima sebagai \(r_1,\ldots,r_5\text{,}\) lalu tentukan blok mana yang sudah merupakan kata kode dalam \(C\text{.}\) Rubrik: pertahankan urutan blok dan cocokkan blok yang sah dengan indeks kata kodenya.
Petunjuk.
Jawaban.
Solusi.
Petunjuk. Bandingkan setiap blok enam bit dengan daftar \(c_1,\ldots,c_8\text{,}\) bukan hanya dengan panjangnya.
Bloknya adalah \(r_1=000111\text{,}\) \(r_2=001100=c_7\text{,}\) \(r_3=100000\text{,}\) \(r_4=000011=c_2\text{,}\) dan \(r_5=001001=c_4\text{.}\) Jadi \(r_2,r_4,r_5\) sudah berada dalam \(C\text{,}\) sedangkan \(r_1,r_3\) tidak.
Memisahkan pesan pada setiap spasi menghasilkan, dalam urutan yang diterima,
\begin{equation*}
000111,\quad001100,\quad100000,\quad000011,\quad001001.
\end{equation*}
Pencocokan langsung dengan delapan anggota \(C\) memberi \(001100=c_7\text{,}\) \(000011=c_2\text{,}\) dan \(001001=c_4\text{.}\) Tidak ada anggota daftar yang sama dengan \(000111\) atau \(100000\text{.}\) Audit ini menyiapkan dua sub-tugas pendekodean berikutnya tanpa menebak kata pengganti terlebih dahulu.
Pemeriksaan D.4. Tugas Hamming 4: mendeteksi galat transmisi.
Jelaskan bagaimana pesan yang diterima membuktikan bahwa sedikitnya satu galat transmisi telah terjadi, dengan asumsi setiap blok yang dikirim harus merupakan kata kode dalam \(C\text{.}\)
Petunjuk.
Jawaban.
Solusi.
Petunjuk. Keanggotaan dalam kode adalah uji validitas blok yang diterima.
Blok pertama \(000111\) dan blok ketiga \(100000\) bukan anggota \(C\text{;}\) karena blok yang sah harus berada dalam \(C\text{,}\) pesan tersebut tidak mungkin diterima tanpa galat.
Menurut definisi kode yang dipakai, pengirim hanya mengirim anggota \(C\text{.}\) Pemeriksaan keanggotaan pada tugas sebelumnya menunjukkan \(r_1\notin C\) dan \(r_3\notin C\text{.}\) Maka kedua blok yang diterima itu tidak mungkin identik dengan blok sah yang dikirim. Sedikitnya satu bit berubah pada masing-masing blok tersebut. Sebaliknya, fakta bahwa \(r_2,r_4,r_5\in C\) tidak membuktikan bahwa bit-bitnya pasti tidak berubah; galat berganda secara prinsip dapat mengubah satu kata kode menjadi kata kode lain. Yang pasti dari data ini ialah adanya galat pada blok pertama dan ketiga.
Pemeriksaan D.5. Tugas Hamming 5: semua hasil pendekodean terdekat.
Ganti setiap blok yang diterima dengan setiap kata kode yang berjarak paling dekat. Temukan seluruh pesan hasil, bukan hanya satu pilihan. Rubrik: hitung jarak terhadap kedelapan kata kode untuk setiap blok dan nyatakan semua keadaan seri.
Petunjuk.
Jawaban.
Solusi.
Petunjuk 1. Susun satu baris delapan jarak untuk setiap \(r_j\text{.}\)
Petunjuk 2. Empat kata kode sama-sama berjarak satu dari blok pertama.
Blok terdekatnya adalah \(r_1\mapsto\{c_2,c_3,c_5,c_8\}\text{,}\) \(r_2\mapsto c_7\text{,}\) \(r_3\mapsto c_1\text{,}\) \(r_4\mapsto c_2\text{,}\) dan \(r_5\mapsto c_4\text{.}\) Jadi terdapat tepat empat pesan hasil.
Dengan kolom dalam urutan \(c_1,\ldots,c_8\text{,}\) seluruh vektor jarak adalah
\begin{align*}
(d_H(r_1,c_i))_{i=1}^8 \amp = \amp (3,1,1,3,1,3,3,1),\\
(d_H(r_2,c_i))_{i=1}^8 \amp = \amp (2,4,2,2,2,2,0,2),\\
(d_H(r_3,c_i))_{i=1}^8 \amp = \amp (1,3,3,3,3,3,3,5),\\
(d_H(r_4,c_i))_{i=1}^8 \amp = \amp (2,0,2,2,2,2,4,2),\\
(d_H(r_5,c_i))_{i=1}^8 \amp = \amp (2,2,2,0,4,2,2,2).
\end{align*}
Minimum baris pertama ialah satu dan dicapai pada kolom \(2,3,5,8\text{.}\) Minimum baris ketiga ialah satu dan hanya dicapai pada kolom pertama. Tiga blok yang memang sudah berupa kata kode mempunyai minimum nol yang unik pada kolomnya sendiri.
Oleh sebab itu, seluruh kemungkinan pesan terkoreksi, dalam urutan blok, ialah
\begin{gather*}
(c_2,c_7,c_1,c_2,c_4),\\
(c_3,c_7,c_1,c_2,c_4),\\
(c_5,c_7,c_1,c_2,c_4),\\
(c_8,c_7,c_1,c_2,c_4).
\end{gather*}
Dekode tetangga terdekat tidak menyediakan informasi untuk memilih satu di antara empat kemungkinan ini bagi blok pertama.
Pemeriksaan D.6. Tugas Levenshtein 1: dari “green” ke “grease”.
Ubah “green” menjadi “grease” dengan operasi penyisipan, penghapusan, dan substitusi yang diizinkan. Berikan urutan terpendek, identifikasi setiap operasi, dan buktikan bahwa lebih sedikit operasi tidak mungkin.
Petunjuk.
Jawaban.
Solusi.
Petunjuk 1. Pertahankan awalan “gre”, lalu ubah dua huruf dan tambahkan satu huruf.
Petunjuk 2. Karena panjang sasaran lebih besar satu, lintasan dengan paling banyak dua operasi harus memakai tepat satu penyisipan dan paling banyak satu substitusi.
Salah satu urutan terpendek adalah “green” → “grean” → “greas” → “grease”. Jadi \(d_L(\text{green},\text{grease})=3\text{.}\)
Substitusikan huruf keempat “e” dengan “a” untuk memperoleh “grean”. Substitusikan “n” dengan “s” untuk memperoleh “greas”, lalu sisipkan “e” di ujung. Ini memberi batas atas tiga operasi.
Untuk batas bawah, perubahan panjang dari lima menjadi enam memerlukan sedikitnya satu penyisipan. Jika seluruh perubahan memakai paling banyak dua operasi, hitungan panjang memaksa tepat satu penyisipan, tanpa penghapusan, dan paling banyak satu substitusi. Menghapus calon huruf yang disisipkan dari “grease” menghasilkan salah satu dari “rease”, “gease”, “grase”, “grese”, “greae”, atau “greas”. Jarak Hamming masing-masing dari “green” adalah \(5,4,3,2,2,2\text{.}\) Tidak satu pun dapat diperoleh dari “green” dengan paling banyak satu substitusi. Jadi dua operasi mustahil, sedangkan tiga operasi sudah dicapai; jaraknya tepat tiga.
Pemeriksaan D.7. Tugas Levenshtein 2: membuktikan metrik pada \(\Sigma^\ast\).
Misalkan \(\Sigma^\ast\) adalah himpunan semua untai berhingga atas alfabet \(\Sigma\text{.}\) Buktikan bahwa banyak minimum operasi penyisipan, penghapusan, dan substitusi mendefinisikan metrik \(d_L\) pada \(\Sigma^\ast\text{.}\) Rubrik: jelaskan bahwa minimum ada, lalu buktikan keempat aksioma.
Petunjuk.
Jawaban.
Solusi.
Petunjuk 1. Semua huruf \(x\) dapat dihapus, kemudian semua huruf \(y\) disisipkan.
Petunjuk 2. Balik urutan operasi untuk simetri dan sambungkan dua urutan terpendek untuk pertidaksamaan segitiga.
Fungsi \(d_L\) merupakan metrik pada \(\Sigma^\ast\text{.}\) Urutan kosong memberi identitas, pembalikan operasi memberi simetri, dan penyambungan urutan edit memberi pertidaksamaan segitiga.
Untuk sembarang untai \(x,y\text{,}\) ada urutan edit berhingga: hapus seluruh \(|x|\) huruf \(x\text{,}\) lalu sisipkan seluruh \(|y|\) huruf \(y\text{.}\) Jadi himpunan panjang urutan edit dari \(x\) ke \(y\) adalah subhimpunan tak kosong dari bilangan bulat tak negatif; menurut prinsip pengurutan baik, himpunan itu mempunyai minimum. Karena panjang urutan edit tak negatif, \(d_L(x,y)\geq0\text{.}\)
Jika \(x=y\text{,}\) urutan kosong mempunyai panjang nol, sehingga \(d_L(x,y)=0\text{.}\) Sebaliknya, jarak nol berarti minimum dicapai oleh urutan tanpa operasi; urutan demikian tidak mengubah untai, jadi \(x=y\text{.}\) Setiap substitusi dapat dibalik dengan substitusi, setiap penyisipan dengan penghapusan, dan setiap penghapusan dengan penyisipan. Membalik urutan terpendek dari \(x\) ke \(y\) menghasilkan urutan sama panjang dari \(y\) ke \(x\text{.}\) Maka \(d_L(y,x)\leq d_L(x,y)\text{;}\) menukar peran \(x,y\) memberi pertidaksamaan sebaliknya, sehingga jaraknya simetris.
Akhirnya, sambungkan urutan terpendek dari \(x\) ke \(z\) dengan urutan terpendek dari \(z\) ke \(y\text{.}\) Hasilnya adalah suatu urutan dari \(x\) ke \(y\) sepanjang \(d_L(x,z)+d_L(z,y)\text{.}\) Karena \(d_L(x,y)\) adalah panjang minimum, \(d_L(x,y)\leq d_L(x,z)+d_L(z,y)\text{.}\) Keempat aksioma terpenuhi.
Pemeriksaan D.8. Tugas Levenshtein 3: memilih koreksi ejaan terdekat.
Hitung secara tepat jarak Levenshtein dari “tupotagry” ke “topography”, “topology”, dan “tautology”. Tentukan pilihan pemeriksa ejaan dan buktikan bahwa setiap jarak yang dilaporkan memang minimum.
Petunjuk.
Jawaban.
Solusi.
Petunjuk 1. Isi tabel jarak untuk semua pasangan awalan, bukan hanya mencocokkan huruf pada posisi yang sama.
Petunjuk 2. Rekurensi mengambil minimum dari penghapusan, penyisipan, dan substitusi atau pencocokan terakhir.
Jaraknya berturut-turut adalah \(5\text{,}\) \(4\text{,}\) dan \(5\text{.}\) Karena itu, pilihan terdekat yang unik adalah “topology”.
Untuk awalan sepanjang \(i\) dan \(j\text{,}\) definisikan \(D(i,j)\) sebagai jarak keduanya. Nilai batasnya \(D(i,0)=i\) dan \(D(0,j)=j\text{.}\) Jika huruf terakhir sama, letakkan \(\epsilon_{ij}=0\text{;}\) jika berbeda, letakkan \(\epsilon_{ij}=1\text{.}\) Meninjau operasi terakhir memberi rekurensi
\begin{equation*}
D(i,j)=\min\{D(i-1,j)+1,\ D(i,j-1)+1,\ D(i-1,j-1)+\epsilon_{ij}\}.
\end{equation*}
Argumen berdasarkan operasi terakhir menunjukkan bahwa setiap urutan edit masuk ke salah satu dari tiga kasus ini; karena itu, tabel tersebut memberi batas bawah sekaligus batas atas.
Untuk sumber “tupotagry”, baris terakhir tabel, mulai dari awalan sasaran kosong, adalah
\begin{align*}
\text{topography}: \amp (9,8,7,7,6,5,4,4,5,6,5),\\
\text{topology}: \amp (9,8,7,7,6,6,6,5,4),\\
\text{tautology}: \amp (9,8,7,7,7,7,7,7,6,5).
\end{align*}
Unsur terakhir memberi jarak \(5,4,5\text{.}\) Batas atas itu juga tampak pada urutan edit berikut; setiap anak panah adalah satu operasi:
“tupotagry” → “topotagry” → “topogtagry” → “topogragry” → “topograpry” → “topography”;
“tupotagry” → “topotagry” → “topolagry” → “topologry” → “topology”;
“tupotagry” → “taupotagry” → “tautotagry” → “tautolagry” → “tautologry” → “tautology”. Karena nilai minimum terkecil adalah empat dan hanya dimiliki “topology”, itulah koreksi menurut aturan tetangga terdekat.
