Pencarian string samar
Pencarian string samar (bahasa Inggris: approximate string matching) ialah persoalan pencarian teks yang merupakan cabang dari ilmu komputer[1] yaitu metode perbandingan teks antara susunan karakter dengan pola yang perkirakan paling serupa dengan menyebut, kendati terjadi kesalahan antara dua susunan karakter baik di dalam pola yang menyebabkan susunan karakter menjadi berbeda atau jauh dari persis, pencarian string tetap mampu menemukan pola sepadan. Berlainan dengan pencarian string klasik yang mengadakan perbandingan susunan karakter secara tepat. Dengan begitu, permasalahan pencarian string samar berisi banyak kerumitan daripada pencarian string lampau.[2]
Maksud utama terhadap pencarian string samar hadir dari kualitas teks yang rendah disebabkan kesalahan pengetikan, galat dari alat pengenalan karakter optis, kesalahan ejaan dalam pola dan pencarian atas nama-nama asing. Aspek pencarian string samar memandang pengindeksan teks sebagai satu masalah utama.[1]
Teknik pencarian string samar secara luas mencakup jarak kemiripan susunan karakter pula penyandian secara bunyi bahasa.[2] Aspek bunyi terhadap pencarian string menyangkut pelafalan sebagai bunyi serupa yang berada dalam penanganan algoritme fonetik.[3]
Konsep
suntingPerkiraan kemiripan antara susunan karakter dengan pola, mengacu pada pengukuran yang acap dikenal sebagai jarak edit.[2] Proses pengubahan terhadap susunan karakter mengikuti pengukuran atas jumlah minimum dari operasi penambahan, penghapusan dan penggantian (substitusi) karakter agar mencapai susunan karakter yang dimaksud. Distansi yang paling sedikit antara dua string ialah kian serupa.[1]
Metode pencarian string secara samar yang dapat mengubah susunan karakter ke bentuk susunan karakter serupa, sangat sesuai atas transformasi kata tidak baku menjadi kata baku, sebab pencarian string samar menghendaki berdasarkan kemiripan penulisan.[3]
Secara matematis, pencarian string samar dapat didefinisikan sebagai dua buah susunan karakter antara dan . Sebuah fungsi diberlakukan, kala parameter dan sebagai unit susunan karakter akan variabel dan . Fungsi jarak bertugas menghitung jumlah minimal dari mengubah menjadi dengan tiga cakupan operasi. Setiap operasi yang berlangsung dihitung dengan nilai 1:[2]
![{\displaystyle Teks[l\dots n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f26d2844ba5f152bdb84bc95120d86940140a938)
![{\displaystyle Pola[l\dots m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ea77afd4b6a8de5072083245fccf3ec2ca44538)
![{\displaystyle Distansi(x[i\dots j],y[a\dots b])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45285dab3ad740b1203936d977c9ba19a137ad15)
![{\displaystyle x[i\dots j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1370d574d88855ec16eaa7227fe806720a47143e)
![{\displaystyle y[a\dots b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/644bb55dcd335787c0188513f0794be385fed595)
Substitusi
suntingBeroperasi dengan mengambil satu karakter dalam atas mengganti karakter ke susunan karakter tujuan , sebagai contoh:[4]
- kope → kopi, yaitu mengganti karakter 'e' dengan huruf 'i'
Penambahan
suntingMenyisipkan sebuah karakter ke dalam di posisi yang sama, sesuai karakter atas , sebagai contoh:[4]
- kpi → kopi, yaitu menambahkan karakter 'o' setelah huruf 'k'
Penyisipan dapat terjadi pada awal, pertengahan maupun sebagai akhir karakter.
Penghapusan
suntingMerupakan kebalikan dari penambahan karakter, bertindak dengan menghilangkan karakter dalam , sebagai contoh:[4]
- kopii → kopi, yaitu sebagai operasi yang menghilangkan karakter 'i'
Pengubahan susunan karakter pula perlu memenuhi kondisi pertidaksamaan segitiga atas operasi pemindahan karakter (transposisi) yang melibatkan penukaran huruf berurutan, sebagai contoh:[3]
- yagn → yang, yaitu menukar huruf 'gn' ke 'ng', cakupan operasi masih bernilai 1
Akhir sebagai masukan dari penyelesaian atas persoalan pencarian string samar ialah menentukan sebagai kesalahan maksimum yang diperkenankan atas menghitung himpunan dengan kondisi .[2]
![{\displaystyle Pola[i\dots j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b37839caec80e5af9b34904bf97724a9277bc67b)
![{\displaystyle Distansi(Teks[x\dots y],Pola[i\dots j])\leq k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4c1595a4370c8c7eea0064c0508d7a35cddafa7)
Pengindeksan
suntingBerdasarkan tradisi, algoritme pencarian string samar dikelompokkan ke dalam dua kategori mencakup saluran langsung dan luar. Pada teknik saluran langsung, pencarian berlangsung tanpa sebuah indeks. Pengembangan yang paling dikenal ialah algoritme bitap.[5]
Perbandingan algoritme
suntingSebagai satu rancangan dalam pencarian string samar, pengukur kemiripan susunan karakter pula dikenal jarak edit, istilah lain dari jarak Levenshtein,[3] yang termasuk ke dalam algoritme pemrograman dinamis, sebab fungsi jarak menggunakan penghitungan berbasis pemrograman dinamis yang diketahui sangat fleksibel dalam menambah operasi pengubahan baru ataupun dalam mengganti nilai operasi.[1]
Selain jarak Levenshtein, pencarian string samar terdapat beberapa algoritme lain yang telah diketahui seperti jarak Hamming, jarak Damerau-Levenshtein, jarak Jaro-Winkler.[3][4]
Jarak Hamming
suntingJarak Hamming sebagai satu dari algoritme pencarian string samar bekerja dengan mengukur jarak dua buah susunan karakter yang berukuran sama, membandingkan karakter atas susunan karakter di posisi yang sama berdasarkan jumlah simbol berbeda atas kedua susunan karakter.
Jarak Hamming hanya mendukung operasi substitusi karakter.[3]
Jarak Levenshtein
suntingJarak Levenshtein atau jarak edit, satu dari algoritme pencarian string samar lain yang menghitung metrik dari susunan karakter awal ke susunan karakter tujuan berdasarkan jumlah operasi susunan karakter yang paling sedikit. Operasi susunan karakter yang dilibatkan meliputi operasi penyisipan, penghapusan dan substitusi.
Algoritme jarak Levenshtein banyak dipakai ke segala bidang seperti pada mesin pencari, pengenalan ucapan, pengujian DNA, pemeriksa ejaan, deteksi plagiarisme, dll.[6]
Perihal program pemeriksa ejaan yang melingkupi pengolahan teks menjadi sejalan, sebab program perlu mengenali susunan karakter dengan keselarasan terdekat kala susunan karakter tidak ditemukan dalam daftar kata yang menempatkan pencarian string samar kian fundamental.[7]
Jarak Damerau-Levenshtein
suntingJarak Damerau-Levenshtein merupakan perluasan dari jarak Levenshtein yang pula mengukur perbedaan dua susunan karakter, tetapi bersifat lebih restriktif.
Faktor pembeda antara jarak Levenshtein dengan jarak Damerau-Levenshtein terletak pada operasi transposisi yaitu menukar dua karakter yang berdekatan sebagai tambahan atas operasi yang diperkenankan kepada tiga operasi pengeditan karakter tunggal mencakup penyisipan, penghapusan dan substitusi.[8]
Pada beberapa kasus, tanpa operasi transposisi, operasi pengubahan susunan karakter dapat menjadi dua operasi baik itu operasi substitusi sebanyak dua maupun operasi penghapusan dan penyisipan yang digunakan beriringan.[9]
Jarak Jaro-Winkler
suntingJarak Jaro-Winkler berawal dari metrik jarak Jaro yang mengukur kesamaan dua susunan karakter berdasarkan nilai angka. Nilai awal ditandai dengan 0 sebagai ketaksamaan dari susunan karakter, sementara kemiripan susunan karakter yang ditemukan, mengacu pada nilai yang lebih tinggi.
Jaro-Winkler berjalan dengan asas pada menghitung banyak susunan karakter, jumlah karakter yang sama antara dua susunan karakter dan jumlah transposisi. Secara umum, Jaro-Winkler terdapat pada fungsi deteksi duplikat atau plagiarisme.[3]
Aplikasi
suntingPersoalan pada pencarian string samar banyak diketahui diterapkan pada pencarian teks digital yang sehari-hari acap diperlukan dan biologi komputasi.[1]
Pada topik bioinformatika terhadap biologi molekuler dengan mendukung pencarian kemiripan sekuens DNA, pencarian string samar atas pangkalan data GenBank menjadi alat mendasar.[7]
Bidang ilmu filsafat sebagai fundamen dalam berpikir kritis, ada keperluan dengan menerapkan pencarian string samar yang terdapat kemampuan autokomplet (pelengkap kata otomatis) atas memudahkan pengguna akhir pada menelusuri berbagai istilah-istilah filosofi secara aplikasi seluler.[4]
Di sektor akademi yang berhubungan dengan publikasi karya ilmiah, teknik pencarian string samar berlangsung atas efektivitas pengelolaan data tugas akhir mahasiswa di perpustakaan.[6]
Referensi
sunting- ^ a b c d e Baeza-Yates, R; Navarro, G (1998). Fast Approximate String Matching in a Dictionary (Prosiding. SPIRE'98). IEEE.
- ^ a b c d e Narendra Kumar; et al. (2010). "Approximate string matching Algorithm". International Journal on Computer Science and Engineering (IJCSE). 2 (3): 641–644. ISSN 0975-3397.
- ^ a b c d e f g Rochmawati, Y; Kusumaningrum, R (April 2016). "Studi Perbandingan Algoritma Pencarian String dalam Metode Approximate String Matching untuk Identifikasi Kesalahan Pengetikan Teks". Jurnal Buana Informatika. 7 (2): 125–134.
- ^ a b c d e Nasution, Elvi Sahara; Hasibuan, Nelly Astuti; Suginam (Oktober 2018). "Implementasi Algoritma Approximate String Matching Pada Aplikasi Filosofi Berbasis Android" (Konferensi Nasional Teknologi Informasi dan Komputer (KOMIK)). 2 (1). ISSN 2597-4645.
- ^ Sumeet Dua; et al. (2011). Information Intelligence, Systems, Technology and Management: 5th International Conference, ICISTM 2011, Gurgaon, India (Prosiding). Springer Science & Business Media. hlm. 199. ISBN 978-3642194221.
- ^ a b Gurning, Ardi Isbad Amar; Zarnelly; Adawiyah, Arabiatul (Februari 2016). "Penerapan Fuzzy String Matching Pada Aplikasi Pencarian Tugas Akhir Mahasiswa Jurusan Sistem Informasi Berbasis Web". Jurnal Rekayasa dan Manajemen Sistem Informasi. 2 (1). ISSN 2502-8995.
- ^ a b Skiena, Steven. "Approximate String Matching". Stony Brook Algorithm Repository (Repositori). Diakses tanggal 15 Juni 2020.
- ^ "String Distance Function" (Definisi). Algorithmic Solutions. Diakses tanggal 19 Juni 2020.
- ^ "String Comparison and String Distance" (Tutorial). Alias-i. Diakses tanggal 20 Juni 2020.