Algoritma Pencocokan String Naif dengan Python: Contoh, Unggulan & Pro & Kontra

Ketika ada kebutuhan untuk menemukan pola input dalam string karakter, coders dan programmer menggunakan algoritma pencocokan string. Biasanya, dalam kasus string pendek, pemrogram python lebih suka menggunakan pendekatan naif di mana, program memeriksa setiap posisi dalam string input untuk pola kueri. Jika cocok, itu diberikan output dengan nomor posisi.

Salah satu alasan terbesar mengapa algoritma pencocokan string naif digunakan adalah karena cepat dan menghasilkan hasil yang cukup akurat. Selain itu, tidak memerlukan pra-pemrosesan. Bagaimanapun, kami akan membahas keuntungan ini pada tahap selanjutnya dalam posting ini. Mari kita pahami dulu algoritma untuk pencarian pola menggunakan pendekatan naif.

Algoritma Pencarian Pola Naif

Dalam pencarian pola string naif, program menguji posisi pola input P [1……i] dalam string karakter T [1…..m].

Perhatikan bahwa panjang teks atau string input akan selalu lebih besar atau sama dengan panjang pola.

Berikut adalah algoritma pencarian pola naif untuk bahasa pemrograman yang berbeda.

Mulai

tepuk = pola Ukuran

str = ukuran string

untuk i = 0 hingga (str – tepuk), do

untuk j = 0 untuk menepuk, lakukan

jika teks[i+j] pola[j], maka

putuskan lingkarannya

selesai

jika j == tepuk, maka

tampilkan posisi i sebagai pola yang ditemukan

selesai

Akhir

Algoritma ini cukup penting dalam ilmu komputer, karena membantu memberikan hasil pencarian sebagai keluaran.

Baca : Jenis-Jenis Algoritma AI Yang Harus Anda Ketahui

Contoh Pencocokan String Naif di Python

Berikut adalah contoh di mana pendekatan pencarian pola naif digunakan dalam kode python.

# Program Python untuk Pencocokan String Naif

# Algoritma pencarian

pencarian def (P, T):

X = len(P)

Y = len(T)

# Sebuah loop untuk menggeser P[] satu per satu */

untuk i dalam rentang (X – Y + 1):

j = 0

# Untuk indeks i saat ini, periksa

# untuk pencocokan pola */

untuk j dalam rentang (0, X):

jika (txt[i + j] ! = P[j]):

merusak

jika (j == X – 1):

print (“Pola ditemukan pada posisi “, i)

# Kode Pengemudi

jika __name__ == '__main__':

T = “UPGRADEDUBUPGRAABUPGRADEDU”

P = “UPGRAD”

pencarian (P, T)

keluaran :

Pola ditemukan pada posisi 0

Pola ditemukan di posisi 17

Penjelasan: Posisi pertama adalah posisi ke- 0 . Sejak pola “UPGRAD” pertama kali terlihat di sini, output menunjukkan bahwa pola tersebut ditemukan di posisi 0.

Demikian pula pola selanjutnya ditemukan pada posisi 17.

Kasus Terbaik Pencarian Pola Naif

Hanya ada satu kasus terbaik untuk algoritma pencarian pola naif, tidak seperti dua kasus terburuk.

Kasus terbaik terjadi ketika karakter pertama dalam teks pola tidak ada di string input.

Contoh:

T[] = “UPGRADEDUHIJKLUPGRA”;

P[] = “TUPGRA”;

Oleh karena itu, jumlah kasus pola yang cocok adalah O(n).

Kasus Terburuk Pencarian Pola Naif

Ada dua kasus terburuk dalam pendekatan pencarian string naif.

1. Ketika semua karakter dalam pola sama dengan yang ada di string input.

T[] = “EEEEEEEEEEEEEEE”;

P[] = “EEE”;

1. Ketika hanya karakter terakhir dalam pola yang berbeda dari string input.

T[] = “EEEEEEEEEEED”;

P[] = “EEEED”;

Dalam kasus seperti itu, jumlah perbandingan dalam O(m*(n-m+1)).

Fitur Algoritma Pencocokan String Naif

Algoritma pencocokan string dimaksudkan untuk menemukan semua kemunculan pola tertentu dalam sebuah teks.

Berikut adalah fitur utama dari algoritma.

1. Ini adalah metode paling sederhana di antara semua untuk mencari pola dalam teks input. Ini memeriksa semua karakter satu per satu dalam string karakter yang diberikan.
2. Ia menemukan kecocokan string yang tepat - baik itu kemunculan pola yang lebih atau lebih tepat.
3. Ini lebih banyak digunakan ketika ada teks kecil. Selain itu, tidak memerlukan fase pra-pemrosesan.
4. Metode pencarian ini tidak menempati ruang ekstra untuk bekerja dan mencari pola dalam string.

Baca juga: Struktur Data & Algoritma di Python

Keuntungan dari Pencarian Pola Naif

1. Tidak ada fase pra-pemrosesan yang diperlukan dalam pendekatan pencarian naif, karena waktu berjalannya sama dengan waktu pencocokan.
2. Tidak ada ruang operasi tambahan yang dibutuhkan.
3. Perbandingan pola dengan string dapat dilakukan dalam urutan apa pun.

Kekurangan Pencocokan String Naif

Hanya ada satu kelemahan dari pendekatan pencocokan string naif, yaitu tidak efisien. Hal ini karena ketika telah menemukan posisi, tidak menggunakannya lagi untuk mencari posisi lainnya. Ini kembali ke titik awal dan mencari pola lagi. Jadi, itu tidak menggunakan informasi dari shift sebelumnya lagi.

Kesimpulan

Algoritma pencocokan string naif adalah pendekatan yang paling disukai untuk menemukan posisi pola tersebut dalam teks tertentu karena berbagai alasan seperti tidak ada persyaratan pra-pemrosesan, tidak ada ruang ekstra untuk operasi, dll. Namun, itu tidak dapat digunakan untuk teks yang lebih besar karena inefisiensi untuk melakukan operasi besar lebih cepat.

Kami berharap posting ini memberi Anda ide yang sangat bagus tentang pendekatan pencarian pola naif dengan python. Untuk mempelajari tentang penggunaan pendekatan ini dan mendapatkan pemahaman topik yang lebih luas, hubungi para ahli di upGrad. Kami memiliki kursus yang dirancang khusus untuk individu yang ingin memperluas keahlian mereka. Hubungi kami hari ini!

Jika Anda tertarik untuk mempelajari lebih lanjut tentang AI, pembelajaran mesin, lihat PG Diploma IIIT-B & upGrad dalam Pembelajaran Mesin & AI yang dirancang untuk para profesional yang bekerja dan menawarkan 450+ jam pelatihan ketat, 30+ studi kasus & tugas, Status Alumni IIIT-B, 5+ proyek batu penjuru praktis & bantuan pekerjaan dengan perusahaan-perusahaan top.