\documentclass[a4paper]{article}
\def\titlestr{Algoritma\ Boyer-Moore}
\def\authorstr{Adhi\ Hargo}
% ==============================================================================
\title{\titlestr}
\author{\authorstr}
\date{}
\input{adhi-hdr}
\input{adhi-lnk}
\usepackage{adhi-bk}
\usepackage{adhi-nw}
\usepackage{listings}
% ==============================================================================
\begin{document}
\maketitle

Pencarian deretan karakter tertentu dalam sebuah korpus teks adalah topik yang
tidak  pernah habis diselami oleh para ilmuwan komputer; masih banyak individu
yang mendapat gelar Ph.D karena menemukan algoritma pencarian yang lebih efisien
dan cepat dari para pendahulunya. Salah satu algoritma yang populer dan kerap
digunakan dalam berbagai produk pengolah teks adalah algoritma Boyer-Moore.

% ==============================================================================
\section{Prinsip Dasar}
% ==============================================================================
Algoritma Boyer-Moore dapat dijelaskan sebagai berikut. Anggap terdapat sebuah
string
$$S = S[1], \ldots, S[i]$$
dan harus diperiksa apakah sebuah string lain
$$T = T[1], \ldots, T[j],\quad j \leq i$$
merupakan substring dari $S$. Dengan kata lain, harus diperiksa apakah terdapat
substring
$$S' = S[k], \ldots, S[k + j],\quad k + j \leq i$$
dari $S$ di mana $S' \equiv T$. Algoritma Boyer-Moore adalah algoritma pencarian
teks yang memanfaatkan fakta bahwa:
\begin{itemize}
\item Bila terdapat setidaknya satu elemen dalam
    $\left\{ s\, |\, s \in S' \right\}$
    yang tidak berada dalam $T$, maka $$S' \neq T.$$ Saat kondisi tersebut
    ditemui, lakukan perubahan nilai $$k \leftarrow k + j$$ (selama $k + j \leq i$)
    sedemikian sehingga $S'$ diganti sepenuhnya.
\item Bila terdapat simbol $a = S[k + l]$ dan $a' = T[m]$ di mana $a = a'$ namun
    $l \neq m$ terdapat kemungkinan ada $k'$ dan substring lain dari $S$,
    $$S'' = S[k'], \ldots, S[k' + j],\quad k' + j \leq i$$
    di mana $S'' \equiv T$. Saat kondisi tersebut ditemui, lakukan perubahan
    nilai $$k \leftarrow k + |m - l|$$ sedemikian sehingga $l = m$.
\end{itemize}

Masih terdapat masalah bila hanya kedua langkah tersebut yang digunakan, karena
bila string yang kita hadapi, misalnya, adalah

{\sf abbabbabababbabababbbaaaa\ldots }

dan string yang ingin kita cari di dalamnya adalah

{\sf aaaa }

lalu pencocokan linear dilakukan dari indeks terkecil, maka pergeseran indeks $k$
akan terlalu sering dilakukan; batas bawah unjuk kerja pencarian dengan cara
ini mendekati unjuk kerja algoritma \textsl{brute-force}. Langkah optimasi
lebih lanjut adalah memulai pencocokan dari elemen dengan indeks terbesar 
($S[k + j]$ dan $T[j]$), yang berakibat meminimalkan pergeseran indeks $k$.


% ==============================================================================
\section{Program Pencari Teks dalam C++}
% ==============================================================================
\subsection{Inisialisasi Program}
Berikut ini contoh program yang mengimplementasikan algoritma di atas. Hal
pertama yang dilakukan adalah mendeklarasikan semua pustaka yang akan digunakan
dalam program (program ini menggunakan STL), dan definisi tipe:
@d Pemuatan pustaka dan definisi tipe
@{#include <iostream>
#include <fstream>
#include <string>
typedef std::string::size_type OFFSET;
@| string ifstream cout endl OFFSET @}

\verb|std::iostream| dan \verb|std::fstream| digunakan terutama untuk melakukan operasi
I/O terhadap file (mencari string) dan terhadap konsol (memberitahukan ditemukannya
string dalam file). \verb|std::string| digunakan untuk menampung teks; metode
dari kelas ini yang akan banyak kita gunakan adalah \verb|rfind(C)|, yang mencari
pemunculan paling kanan karakter dalam variabel \verb|C| dalam objek string dan
mengembalikan indeks pemunculan tersebut, bila ditemukan, atau
\verb|std::string::npos| bila tidak ditemukan. \verb|npos| -- dan karakter
pemisah path -- dideklarasikan sebagai konstanta. Pemrograman juga akan lebih
mudah apabila kita gabungkan seluruh elemen \textsl{namespace} STL ke dalam
\textsl{namespace} global (yang sebaiknya dihindari untuk program yang lebih
kompleks):
@d Pemuatan pustaka...
@{using namespace std;
const OFFSET NPOS = string::npos;
const char SEP = '\\';
@| NPOS @}

\clearpage
% ==============================================================================
\subsection{Implementasi Algoritma}
Inisialisasi algoritma dilakukan dengan menciptakan konstanta-konstanta yang
menyimpan panjang karakter dalam string $S$ dan $T$ dan variabel-variabel yang
menyimpan keadaan temporer algoritma:
@d Inisialisasi algoritma Boyer-Moore
@{const OFFSET i = S.length();
const OFFSET j = T.length();
OFFSET k = 0; // Posisi S' dalam setiap loop.
OFFSET l = j - 1; // Indeks dalam T
@| i j k l @}

Eksekusi algoritma dilakukan dalam sebuah loop\ldots
@d Loop pencocokan karakter
@{while ((k + j) < i)
{
    if (S[k + l] == T[l])
    {@< Kedua karakter sama @>}
    else
    {@< Kedua karakter tidak sama @>}
}@}
di mana algoritma akan segera berhenti bila kesesuaian karakter terjadi sampai
indeks terkecil
@d Kedua karakter sama
@{if (l == 0)
{   return k;   } // S' ditemukan
else
{   --l;    }@}
atau bergeser, dengan besar pergeseran bergantung pada apakah karakter tertentu
dalam $S'$ ada dalam $T$:
@d Kedua karakter tidak sama
@{l = T.rfind(S[k + l]);
k = (l == NPOS) ? (k + j) : (k + l);
l = j - 1;@}

Seluruh proses algoritma kita rangkum dalam sebuah subrutin,
\verb|search(S,T)| yang mengembalikan $k$ bila terdapat substring yang memenuhi,
atau \verb|NPOS| bila tidak.
@d Subrutin pencari teks
@{OFFSET search(string S, string T)
{
    @< Inisialisasi algoritma... @>
    @< Loop pencocokan karakter @>
    return NPOS; // S' tidak ditemukan
}
@| search @}

\clearpage
% ==============================================================================
\subsection{Fungsi Driver dan Keseluruhan Program}
Program secara keseluruhan hanya berisi dua buah subrutin: rutin utama dan rutin
pencari teks, yang sudah mencukupi untuk program contoh kita di sini.
@o search.cpp
@{@< Pemuatan pustaka dan... @>
@< Subrutin pencari... @>
@< Rutin utama @>
@}

Meskipun hanya contoh, program ini harus cukup versatil agar dapat menerima
input dari pengguna dan membaca file korpus teks yang cukup besar. Karenanya
rutin utama, yaitu \verb|main(C,V)|, bertugas memeriksa apakah pengguna
memberikan argumen atau tidak. Bila ya lanjutkan eksekusi, namun bila tidak
tampilkan pesan pertolongan:
@d Rutin utama
@{int main(int argc, char ** argv)
{
    OFFSET prognameidx = string(argv[0]).rfind(SEP);
    char * progname = (prognameidx == NPOS) ?
        argv[0]:
        argv[0] + prognameidx + 1;
    if (argc > 2)
    {
        @< Inisialisasi teks @>
        @< Jalankan rutin pencarian @>
    }
    else
    {
        cout << "PENGGUNAAN:" << endl
            << "\t" << progname << " [TEKS] [FILE]" << endl;
        exit(1);
    }
}
@| main argc argv progname prognameidx @}

Untuk menyederhanakan program, langkah pencegahan kesalahan yang diambil
cenderung minimal. Salah satunya adalah ditentukannya batas ukuran pembacaan
file sebesar 2MB untuk mencegah program membaca file yang terlalu besar%
\footnote{Program pengolah teks nyata seperti kompiler menggunakan mekanisme
buffer.} yang potensial menyebabkan \textsl{overflow} memori.
@d Inisialisasi teks
@{const unsigned int UKURAN_BACA = 2048 * 1024;
char * fname = argv[argc-1];
char * textbuffer = new char[UKURAN_BACA];
{
    ifstream ftext;
    ftext.open( fname, ios::binary);
    if (!ftext.is_open())
    {
        cout << "Tidak dapat membuka file " << fname << endl;
        exit(1);
    }
    ftext.read(textbuffer,UKURAN_BACA);
    ftext.close();
}
string S(textbuffer);
delete textbuffer;
@| UKURAN_BACA fname textbuffer ftext S @}

Karena teks korpus kita tentukan harus berada dalam file tertentu, kita
mendapatkan kebebasan untuk menggunakan spasi dalam teks yang dicari, meski
tetap dalam batasan tertentu:
@d Inisialisasi teks
@{
string T = argv[1];
for (int i = 2; i < argc - 1; ++i)
{
    T.append(" ");
    T.append(argv[i]);
}
@| T @}

Dan berikut potongan kode yang menjalankan rutin pencarian, dan menampilkan 
hasilnya. Skema pemuatan teks yang digunakan turut memuat karakter \emph{newline}
dalam buffer, namun karena subrutin pencarian tidak memiliki respon khusus atas 
karakter tersebut, informasi baris tidak dapat diikutsertakan.
@d Jalankan rutin pen...
@{OFFSET hasil = search(S,T);
if (hasil == NPOS)
    cout << "Teks tidak ditemukan: "
        << "\"" << T << "\"" << endl;
else
    cout << "Teks ditemukan pada offset " << hasil
        << ": \"" << S.substr(hasil, T.length()) << "\"" << endl;
@| hasil @}

\appendix

\section{Makro Pecahan yang Didefinisikan}
@m

\section{Variabel dan Fungsi yang Digunakan/Didefinisikan}
@u

\section{File yang Didefinisikan}
@f

\section{Listing Kode C++}
Berikut listing kode sumber hasil ekstrak dari tulisan ini. Program dapat 
dikompilasi dengan Borland C++ v5.5.

{\footnotesize\lstinputlisting[language=C++,basicstyle=\sffamily]{search.cpp}}

\end{document}