Levenshtein Distance

Contents

1 Pendahuluan
2 Levenshtein Distance
3 Calculator Step : Levenshtein Distance Type
4 Contoh Penggunaan
5 Penutup
6 Sumber Referensi

Pendahuluan

Bagi yang terlibat dalam operasional pemeliharaan data sehari-hari - terutama data master - tentunya menyadari akan sulitnya tugas tersebut. Bukan karena sistem yang dikembangkan tidak baik, namun banyaknya perkara human error.

Sebagai salah satu contoh, double entri data "serupa tapi tak sama". Berikut adalah detilnnya :

Misalkan kita memiliki entri "Ferry" dan "Feri" pada data master pelanggan. Kedua entri tersebut sebenarnya mengacu kepada orang yang sama namun terjadi 2 kali entri. Bukankah ini akan potensial menjadikan laporan kita kacau ?

Bagaimana kita mencoba mendeteksi kasus seperti itu di Pentaho Data Integration ? Untuk versi 3.2 kita memiliki tipe kalkulasi yang namanya "Levenshtein Distance". Berikut adalah penjelasan lengkap dari kalkulasi tersebut.

Terima kasih kepada Pak Herman Darmawan dari Sentosa Group (The Body Shop) yang telah memperkenalkan penerapan metode yang sangat berguna ini kepada penulis.

Levenshtein Distance

Levenshtein Distance atau sering disebut juga edit distance adalah suatu pengukuran (metrik) yang dihasilkan melalui perhitungan jumlah perbedaan ("jarak") yang terdapat diantara dua untaian karakter (string).

Perbedaan yang diukur adalah jumlah minimal operasi penambahan (insert), penghapusan (delete) dan penggantian karakter (substitute) yang dibutuhkan untuk meniadakan perbedaan diantara keduanya.

Sebagai contoh jika kita memiliki 2 kata sebagai berikut :

"Budi" dan "Budhi", maka diperlukan 1 penambahan untuk menyamakan kedua string tersebut :

penambahan karakter "h" pada string "Budi" menjadi "Budhi".

"Jambu" dan "Jauh", maka diperlukan 3 perubahan yaitu :

penghapusan 2 karakter "mb" dari string "Jambu" menjadi "Jau"
penambahan 1 karakter "h" pada akhir string menjadi "Jauh"

dstnya

Kelihatan sederhana ? Terbayangkan kegunaannya untuk kepentingan cleansing data ?

Terbayangkan juga bagaimana membuat script atau program untuk mengakomodasi hal tersebut ? Cukup sulit bukan ?

Calculator Step : Levenshtein Distance Type

Pada Kettle versi 3.x ternyata pada step calculator sudah menyediakan tipe kalkulasi ini. Berikut adalah screenshot dari dialog "Select the calculation type" yang muncul dari step tersebut. Terlihat adanya pilihan Levenshtein Distance dengan source dan target dimasukkan pada kolom "A" dan "B".

Contoh Penggunaan

Misalkan kita memiliki data berpasangan terlihat seperti gambar di bawah ini (dokumen Excel) dan perlu kita kalkulasi perbedaannya. Apakah Anda familiar dengan data seperti ini di organisasi/perusahan/instansi Anda ?
Susunlah suatu transformation dengan 2 step

Excel Input : untuk membaca file Excel di atas
Calculator : untuk menghitung Levenshtein Distance dari pasangan data yang dibaca (keyword1 / keyword2)

Masukkan konfigurasi step calculator seperti pada gambar berikut di bawah ini.
Lakukan preview pada step Calculator
Selesai

Contoh data maupun transformation bisa Anda download pada bagian akhir artikel ini.

Penutup

Levenshtein Distance atau edit distance merupakan metode perbandingan dua string yang sangat berguna dan telah diintegrasikan ke dalam Pentaho Data Integration melalui step Calculator.

Sederhana namun sisi aplikatif dan praktisnya yang sangat luas menjadikan tipe kalkulasi ini tidak dapat diabaikan begitu saja. Sebagai contoh, untuk membantu proses pembersihan (cleansing) data master inventori Anda yang ternyata sebenarnya harus satu entri tapi menjadi double.

Aplikasi orisinal dari Pak Herman adalah sebagai berikut :

data di-cross join dari kolom nama produk untuk semua row data pada master terkait,
menerapkan kalkulasi Levenshtein Distance ini,
melakukan filtering untuk perbedaan 1 atau 2 karakter
hasil output terakhir adalah merupakan laporan yang menjadi basis melakukan proses cleansing data untuk menjaga kualitas data yang tinggi.

Demikian sharing artikel dari penulis untuk para pengunjung sekalian, semoga banyak mendapatkan manfaat darinya.

Untuk diskusi lebih lanjut mengenai Pentaho secara umum atau Pentaho Data Integration secara khusus Anda dapat bergabung dengan kami di milis Pentaho User Group Indonesia dengan cara mengirimkan email ke pentaho-id+subscribe@googlegroups.com.