Bagian Metrik Levenshtein
Metrik Levenshtein merupakan salah satu ukuran jarak yang digunakan para peneliti untuk memahami DNA. DNA tersusun atas dua rantai nukleotida, yang saling berpilin membentuk heliks ganda. Nukleotida terdiri atas empat jenis: adenin (A), sitosin (C), guanin (G), dan timin (T). Nukleotida pada kedua rantai dalam suatu untai DNA saling berpasangan (A dengan T dan C dengan G), sehingga nukleotida pada satu rantai menentukan nukleotida pada rantai lainnya. Karena itu, kita dapat merepresentasikan suatu untai DNA dengan untai huruf dari alfabet \(\{A, C, G, T\}\text{.}\) Salah satu persoalan yang dihadapi peneliti DNA adalah cara membandingkan dua untai DNA, dan metrik Levenshtein merupakan salah satu cara untuk mengukur jarak di antara keduanya. Metrik lain dapat digunakan, tetapi metrik Levenshtein sesuai untuk tugas ini karena beberapa alasan. Selama evolusi, perubahan pada urutan DNA terjadi karena substitusi nukleotida, atau karena penyisipan maupun penghapusan nukleotida. Perubahan evolusioner ini dapat dimodelkan lebih baik oleh operasi-operasi yang menentukan jarak Levenshtein daripada oleh metrik lain. Selain itu, metrik Levenshtein dapat digunakan untuk menghitung jarak antara untai-untai yang panjangnya berbeda. Metrik Levenshtein juga diterapkan dalam pemeriksa ejaan, pengenalan wicara, dan deteksi plagiarisme otomatis. Untuk memahami cara menghitung metrik Levenshtein, perhatikan pertanyaan tentang seberapa jauh jarak antara kata “green” dan “grease”.
Untuk membandingkan kedua kata ini, kita harus dapat mengubah, menambahkan, atau menghapus huruf. Jika \(x = x_1x_2 \cdots x_n\) merupakan suatu untai huruf, kita memperbolehkan operasi-operasi berikut:
- penghapusan:
ganti \(x\) dengan \(x_1 \cdots x_{i-1}x_{i+1} \cdots x_n\) untuk suatu \(i\text{,}\)
- penyisipan:
ganti \(x\) dengan \(x_1 \cdots x_{i}yx_{i+1} \cdots x_n\text{,}\) dengan \(y\) merupakan huruf yang diperbolehkan dan \(0 \leq i \leq n\text{,}\)
- substitusi:
ganti \(x\) dengan \(x_1 \cdots x_{i-1}yx_{i+1} \cdots x_n\text{,}\) dengan \(y\) merupakan huruf yang diperbolehkan dan \(1 \leq i \leq n\text{.}\)
Kegiatan 4.2.
(a)
Dengan menggunakan operasi-operasi yang diperbolehkan, ubahlah kata “green” menjadi kata “grease”. Sebutkan secara spesifik setiap operasi yang Anda gunakan. (Catatan: untai-untai huruf antara tidak harus membentuk kata yang dapat dikenali.) Berapa banyak operasi yang Anda gunakan?
Jika diperlukan tiga operasi untuk mengubah “green” menjadi “grease”, kita dapat mengatakan bahwa jarak antara “green” dan “grease” paling besar 3. Akan tetapi, mungkin saja “green” dapat diubah menjadi “grease” dengan kurang dari 3 operasi, sehingga penilaian kita tentang jarak antara kedua kata tersebut dapat berubah. Secara umum, untuk mendefinisikan jarak Levenshtein \(d_L\) antara untai \(x\) dan untai \(y\) di atas suatu alfabet tetap \(\Sigma\text{,}\) misalkan \(m_d\) menyatakan banyaknya penghapusan, \(m_i\) menyatakan banyaknya penyisipan, dan \(m_s\) menyatakan banyaknya substitusi yang digunakan untuk mengubah \(x\) menjadi \(y\text{.}\) Mungkin terdapat banyak kombinasi berbeda dari \(m_d\text{,}\) \(m_i\text{,}\) dan \(m_s\) yang mengubah \(x\) menjadi \(y\text{,}\) sehingga kita menginginkan jumlah terkecil.
Definisi 4.2.
Jarak Levenshtein \(d_L(x,y)\) antara untai \(x\) dan \(y\) adalah
\begin{equation*}
d_L(x,y) = \min\{m_d+m_i+m_s\}\text{.}
\end{equation*}
Kegiatan 4.3.
(a)
Buktikan bahwa fungsi jarak Levenshtein benar-benar merupakan metrik pada himpunan \(\Sigma^*\) semua untai berhingga di atas alfabet tetap \(\Sigma\) (baik yang membentuk kata bermakna maupun tidak).
(b)
Sebuah pemeriksa ejaan memperbaiki kata yang salah eja “tupotagry”. Dengan menggunakan metrik Levenshtein, kata manakah yang akan dipilih pemeriksa ejaan sebagai kata yang paling dekat dengan “tupotagry”? Mengapa?
\begin{equation*}
\text{"topography"} \qquad \text{"topology"} \qquad \text{"tautology"}
\end{equation*}
