Pencarian string samar

Pencarian samar dengan kata 'praktis' menghasilkan saran kata 'prancis' pada platform Wikipedia bahasa Indonesia versi desktop

Pencarian string samar (bahasa Inggris: approximate string matching) ialah persoalan pencarian teks yang merupakan cabang dari ilmu komputer 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.

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.

Teknik pencarian string samar secara luas mencakup jarak kemiripan susunan karakter pula penyandian secara bunyi bahasa. Aspek bunyi terhadap pencarian string menyangkut pelafalan sebagai bunyi serupa yang berada dalam penanganan algoritme fonetik.

Konsep

Perkiraan kemiripan antara susunan karakter dengan pola, mengacu pada pengukuran yang acap dikenal sebagai jarak edit. 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.

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.

Secara matematis, pencarian string samar dapat didefinisikan sebagai dua buah susunan karakter antara $Teks[l\dots n]$ dan $Pola[l\dots m]$. Sebuah fungsi $Distansi(x[i\dots j],y[a\dots b])$ diberlakukan, kala parameter $x[i\dots j]$ dan $y[a\dots b]$ sebagai unit susunan karakter akan variabel $x$ dan $y$. Fungsi jarak bertugas menghitung jumlah minimal dari mengubah $x$ menjadi $y$ dengan tiga cakupan operasi. Setiap operasi yang berlangsung dihitung dengan nilai 1:

Substitusi

Beroperasi dengan mengambil satu karakter dalam $x$ atas mengganti karakter ke susunan karakter tujuan $y$, sebagai contoh:

• kope → kopi, yaitu mengganti karakter 'e' dengan huruf 'i'

Penambahan

Menyisipkan sebuah karakter ke dalam $x$ di posisi yang sama, sesuai karakter atas $y$, sebagai contoh:

• kpi → kopi, yaitu menambahkan karakter 'o' setelah huruf 'k'

Penyisipan dapat terjadi pada awal, pertengahan maupun sebagai akhir karakter.

Penghapusan

Merupakan kebalikan dari penambahan karakter, bertindak dengan menghilangkan karakter dalam $x$, sebagai contoh:

• 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:

• 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 $k$ sebagai kesalahan maksimum yang diperkenankan atas menghitung himpunan $Pola[i\dots j]$ dengan kondisi $Distansi(Teks[x\dots y],Pola[i\dots j])\leq k$.

Pengindeksan

Berdasarkan 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.

Perbandingan algoritme

Sebagai satu rancangan dalam pencarian string samar, pengukur kemiripan susunan karakter pula dikenal jarak edit, istilah lain dari jarak Levenshtein, 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.

Selain jarak Levenshtein, pencarian string samar terdapat beberapa algoritme lain yang telah diketahui seperti jarak Hamming, jarak Damerau-Levenshtein, jarak Jaro-Winkler.

Jarak Hamming

Artikel utama: Jarak Hamming

Jarak 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.

Jarak Levenshtein

Artikel utama: Jarak Levenshtein

Jarak 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.

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.

Jarak Damerau-Levenshtein

Jarak 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.

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.

Jarak Jaro-Winkler

Jarak 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.

Aplikasi

Persoalan pada pencarian string samar banyak diketahui diterapkan pada pencarian teks digital yang sehari-hari acap diperlukan dan biologi komputasi.

Pada topik bioinformatika terhadap biologi molekuler dengan mendukung pencarian kemiripan sekuens DNA, pencarian string samar atas pangkalan data GenBank menjadi alat mendasar.

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.

Di sektor akademi yang berhubungan dengan publikasi karya ilmiah, teknik pencarian string samar berlangsung atas efektivitas pengelolaan data tugas akhir mahasiswa di perpustakaan.