Algoritma Pencarian String untuk Teks Besar dengan Java

1. Perkenalan

Di artikel ini, kami akan menunjukkan beberapa algoritme untuk mencari pola dalam teks besar. Kami akan menjelaskan setiap algoritma dengan kode yang disediakan dan latar belakang matematika sederhana.

Perhatikan bahwa algoritma yang disediakan bukanlah cara terbaik untuk melakukan pencarian teks lengkap dalam aplikasi yang lebih kompleks. Untuk melakukan pencarian teks lengkap dengan benar, kita dapat menggunakan Solr atau ElasticSearch.

2. Algoritma

Kami akan mulai dengan algoritme penelusuran teks naif yang paling intuitif dan membantu menemukan masalah lanjutan lainnya yang terkait dengan tugas itu.

2.1. Metode Pembantu

Sebelum kita mulai, mari kita tentukan metode sederhana untuk menghitung bilangan prima yang kita gunakan dalam algoritma Rabin Karp:

public static long getBiggerPrime(int m) { BigInteger prime = BigInteger.probablePrime(getNumberOfBits(m) + 1, new Random()); return prime.longValue(); } private static int getNumberOfBits(int number) { return Integer.SIZE - Integer.numberOfLeadingZeros(number); } 

2.2. Pencarian Teks Sederhana

Nama algoritma ini menggambarkannya dengan lebih baik daripada penjelasan lainnya. Ini solusi paling alami:

public static int simpleTextSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0; while ((i + patternSize) = patternSize) return i; } i += 1; } return -1; }

Ide dari algoritma ini sangat mudah: lakukan iterasi melalui teks dan jika ada kecocokan untuk huruf pertama dari pola, periksa apakah semua huruf dari pola tersebut cocok dengan teks.

Jika m adalah jumlah huruf dalam pola, dan n adalah jumlah huruf dalam teks, kompleksitas waktu algoritma ini adalah O (m (nm + 1)) .

Skenario terburuk terjadi dalam kasus String yang memiliki banyak kejadian parsial:

Text: baeldunbaeldunbaeldunbaeldun Pattern: baeldung

2.3. Algoritma Rabin Karp

Seperti disebutkan di atas, algoritma Pencarian Teks Sederhana sangat tidak efisien ketika pola panjang dan ketika ada banyak elemen pola yang berulang.

Ide dari algoritma Rabin Karp adalah menggunakan hashing untuk menemukan pola dalam sebuah teks. Di awal algoritma, kita perlu menghitung hash dari pola yang nantinya digunakan dalam algoritma. Proses ini disebut kalkulasi sidik jari, dan penjelasan detailnya dapat kita temukan di sini.

Hal penting dari tahap pra-pemrosesan adalah kompleksitas waktunya adalah O (m) dan iterasi melalui teks akan mengambil O (n) yang memberikan kompleksitas waktu dari keseluruhan algoritma O (m + n) .

Kode algoritma:

public static int RabinKarpMethod(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; long prime = getBiggerPrime(patternSize); long r = 1; for (int i = 0; i < patternSize - 1; i++) { r *= 2; r = r % prime; } long[] t = new long[textSize]; t[0] = 0; long pfinger = 0; for (int j = 0; j < patternSize; j++) { t[0] = (2 * t[0] + text[j]) % prime; pfinger = (2 * pfinger + pattern[j]) % prime; } int i = 0; boolean passed = false; int diff = textSize - patternSize; for (i = 0; i <= diff; i++) { if (t[i] == pfinger) { passed = true; for (int k = 0; k < patternSize; k++) { if (text[i + k] != pattern[k]) { passed = false; break; } } if (passed) { return i; } } if (i < diff) { long value = 2 * (t[i] - r * text[i]) + text[i + patternSize]; t[i + 1] = ((value % prime) + prime) % prime; } } return -1; }

Dalam skenario terburuk, kompleksitas waktu untuk algoritma ini adalah O (m (n-m + 1)) . Namun, secara rata-rata algoritma ini memiliki kompleksitas waktu O (n + m) .

Selain itu, ada versi Monte Carlo dari algoritme ini yang lebih cepat, tetapi dapat menghasilkan kecocokan yang salah (positif palsu).

2.4 Algoritma Knuth-Morris-Pratt

Dalam algoritma Pencarian Teks Sederhana, kita melihat bagaimana algoritma bisa menjadi lambat jika ada banyak bagian teks yang cocok dengan polanya.

Ide dari algoritma Knuth-Morris-Pratt adalah perhitungan tabel shift yang memberi kita informasi dimana kita harus mencari kandidat pola kita.

Implementasi Java dari algoritma KMP:

public static int KnuthMorrisPrattSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; int[] shift = KnuthMorrisPrattShift(pattern); while ((i + patternSize) = patternSize) return i; } if (j > 0) { i += shift[j - 1]; j = Math.max(j - shift[j - 1], 0); } else { i++; j = 0; } } return -1; }

Dan inilah cara kami menghitung tabel shift:

public static int[] KnuthMorrisPrattShift(char[] pattern) { int patternSize = pattern.length; int[] shift = new int[patternSize]; shift[0] = 1; int i = 1, j = 0; while ((i + j) 
    
      0) { i = i + shift[j - 1]; j = Math.max(j - shift[j - 1], 0); } else { i = i + 1; j = 0; } } } return shift; }
    

Kompleksitas waktu dari algoritma ini juga O (m + n) .

2.5. Algoritma Boyer-Moore Sederhana

Dua ilmuwan, Boyer dan Moore, muncul dengan ide lain. Mengapa tidak membandingkan pola dengan teks dari kanan ke kiri, bukan dari kiri ke kanan, sambil menjaga arah pergeseran tetap sama:

public static int BoyerMooreHorspoolSimpleSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; while ((i + patternSize) <= textSize) { j = patternSize - 1; while (text[i + j] == pattern[j]) { j--; if (j < 0) return i; } i++; } return -1; }

Seperti yang diharapkan, ini akan berjalan dalam waktu O (m * n) . Tetapi algoritma ini mengarah pada implementasi kejadian dan heuristik pertandingan yang mempercepat algoritma secara signifikan. Kami dapat menemukan lebih banyak di sini.

2.6. Algoritma Boyer-Moore-Horspool

Ada banyak variasi implementasi heuristik dari algoritma Boyer-Moore, dan yang paling sederhana adalah variasi Horspool.

Versi algoritma ini disebut Boyer-Moore-Horspool, dan variasi ini memecahkan masalah pergeseran negatif (kita dapat membaca tentang masalah pergeseran negatif dalam deskripsi algoritma Boyer-Moore).

Seperti algoritma Boyer-Moore, kompleksitas waktu skenario kasus terburuk adalah O (m * n) sedangkan kompleksitas rata-rata adalah O (n). Penggunaan spasi tidak bergantung pada ukuran pola, tetapi hanya pada ukuran alfabet yaitu 256 karena itulah nilai maksimum karakter ASCII dalam alfabet Inggris:

public static int BoyerMooreHorspoolSearch(char[] pattern, char[] text) { int shift[] = new int[256]; for (int k = 0; k < 256; k++) { shift[k] = pattern.length; } for (int k = 0; k < pattern.length - 1; k++){ shift[pattern[k]] = pattern.length - 1 - k; } int i = 0, j = 0; while ((i + pattern.length) <= text.length) { j = pattern.length - 1; while (text[i + j] == pattern[j]) { j -= 1; if (j < 0) return i; } i = i + shift[text[i + pattern.length - 1]]; } return -1; }

4. Kesimpulan

Dalam artikel ini, kami menyajikan beberapa algoritme untuk penelusuran teks. Karena beberapa algoritme memerlukan latar belakang matematika yang lebih kuat, kami mencoba menampilkan ide utama di bawah setiap algoritme dan menyediakannya dengan cara yang sederhana.

Dan, seperti biasa, kode sumber dapat ditemukan di GitHub.