Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T10:26:55Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 10.26
Baris 1:		Baris 1:
	'''Algoritma Boyer-Moore''' adalah salah satu [[algoritme pencarian string]], dipublikasikan oleh [[Robert Boyer\|Robert S. Boyer]], dan [[J. Strother Moore]] pada tahun 1977.		'''Algoritma Boyer-Moore''' adalah salah satu [[algoritme pencarian string]], dipublikasikan oleh [[Robert Boyer\|Robert S. Boyer]], dan [[J. Strother Moore]] pada tahun 1977.

	Algoritma ini dianggap sebagai algoritma yang paling efisien pada aplikasi umum. Tidak seperti [[algoritma pencarian]] string yang ditemukan sebelumnya, algoritma Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide di balik algoritma ini adalah bahwa dengan memulai pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat.		Algoritma ini dianggap sebagai algoritma yang paling efisien pada aplikasi umum.<ref>Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5</ref> Tidak seperti [[algoritma pencarian]] string yang ditemukan sebelumnya, algoritma Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide di balik algoritma ini adalah bahwa dengan memulai pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat.<ref>Boyer, Robert Moore, J. 1977. A Fast String Searching Algorithm. Comm. ACM 20: 762–772 doi:[https://dx.doi.org/10.1145%2F359842.359859]</ref>

	== Cara kerja ==		== Cara kerja ==
Baris 48:		Baris 48:
	if (i > g and (suff[i + n - 1 - f] < i - g))		if (i > g and (suff[i + n - 1 - f] < i - g))
	suff[i]:= suff[i + n - 1 - f];		suff[i]:= suff[i + n - 1 - f];
	else		else
	if (i < g)		if (i < g)
	g:= i;		g:= i;
Baris 83:		Baris 83:
	endfor		endfor
	endif		endif
	endfor		endfor
	for (i = 0 to n - 2)		for (i = 0 to n - 2)
	bmGs[n - 1 - suff[i]]:= n - 1 - i;		bmGs[n - 1 - suff[i]]:= n - 1 - i;
Baris 97:		Baris 97:

	Deklarasi:		Deklarasi:
	i, j, shift, bmBcShift, bmGsShift: integer		i, j, shift, bmBcShift, bmGsShift: integer
	BmBc: array[0..255] of interger		BmBc: array[0..255] of interger
	BmGs: array[0..n-1] of interger		BmGs: array[0..n-1] of interger

	Algoritma:		Algoritma:
	preBmBc(n, P, BmBc)		preBmBc(n, P, BmBc)
	preBmGs(n, P, BmGs)		preBmGs(n, P, BmGs)
	i:=0		i:=0
	while (i<= m-n) do		while (i<= m-n) do
	j:=n-1		j:=n-1
	while (j >=0 n and T[i+j] = P[j]) do		while (j >=0 n and T[i+j] = P[j]) do
	j:=j-1		j:=j-1
	endwhile		endwhile
Baris 120:		Baris 120:
	== Kompleksitas ==		== Kompleksitas ==
	Tabel untuk penggeseran bad-character dan good-suffix dapat dihitung dengan [[kompleksitas waktu]] dan ruang sebesar O(n + σ) dengan σ adalah besar ruang alfabet. Sedangkan pada fase pencarian, algoritma ini membutuhkan waktu sebesar O(mn), pada kasus terburuk, algoritma ini akan melakukan 3n pencocokkan karakter, tetapi pada performa terbaiknya algoritma ini hanya akan melakukan O(m/n) pencocokkan.		Tabel untuk penggeseran bad-character dan good-suffix dapat dihitung dengan [[kompleksitas waktu]] dan ruang sebesar O(n + σ) dengan σ adalah besar ruang alfabet. Sedangkan pada fase pencarian, algoritma ini membutuhkan waktu sebesar O(mn), pada kasus terburuk, algoritma ini akan melakukan 3n pencocokkan karakter, tetapi pada performa terbaiknya algoritma ini hanya akan melakukan O(m/n) pencocokkan.

	~~== Referensi ==~~


	== Lihat pula ==		== Lihat pula ==
Baris 133:		Baris 130:
	* [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html Halaman berisi penjelasan tentang Boyer-Moore dan juga sebuah applet yang menganimasikan cara kerjanya]		* [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html Halaman berisi penjelasan tentang Boyer-Moore dan juga sebuah applet yang menganimasikan cara kerjanya]

			== Referensi ==
			<references />

	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Boyer-Moore&oldid=29380643 Wikipedia bahasa Indonesia], revisi 29380643 (2026-06-23T15:52:19Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Boyer-Moore&oldid=29380643 Wikipedia bahasa Indonesia], revisi 29380643 (2026-06-23T15:52:19Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29380643; atribusi sumber disertakan.

2026-08-23T09:55:09Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29380643; atribusi sumber disertakan.

Halaman baru

'''Algoritma Boyer-Moore''' adalah salah satu [[algoritme pencarian string]], dipublikasikan oleh [[Robert Boyer|Robert S. Boyer]], dan [[J. Strother Moore]] pada tahun 1977.

Algoritma ini dianggap sebagai algoritma yang paling efisien pada aplikasi umum. Tidak seperti [[algoritma pencarian]] string yang ditemukan sebelumnya, algoritma Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide di balik algoritma ini adalah bahwa dengan memulai pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat.

== Cara kerja ==
Misalnya ada sebuah usaha pencocokan yang terjadi pada <math>teks[i..i+n-1]</math>, dan anggap ketidakcocokan pertama terjadi di antara <math>teks[i+j]</math> dan <math>pattern[j]</math>, dengan <math>0 < j < n</math>. Berarti, <math>teks[i+j+1..i+n-1] = pattern[j+1..n-1]</math> dan <math> a=teks[i+j]</math> tidak sama dengan <math>b=pattern[j] </math>. Jika <math>u</math> adalah akhiran dari pattern sebelum <math>b</math> dan <math>v</math> adalah sebuah awalan dari pattern, maka penggeseran-penggeseran yang mungkin adalah:
# Penggeseran good-suffix yang terdiri dari menyejajarkan potongan <math>teks[i+j+1..i+n-1] = pattern[j+1..n-1]</math> dengan kemunculannya paling kanan di pattern yang didahului oleh karakter yang berbeda dengan <math>pattern[j]</math>. Jika tidak ada potongan seperti itu, maka algoritma akan menyejajarkan akhiran <math>v</math> dari <math>teks[i+j+1..i+n-1]</math> dengan awalan dari pattern yang sama.
# Penggeseran bad-character yang terdiri dari menyejajarkan <math>teks[i+j]</math> dengan kemunculan paling kanan karakter tersebut di pattern. Bila karakter tersebut tidak ada di pattern, maka pattern akan disejajarkan dengan <math>teks[i+n+1]</math>.

Secara sistematis, langkah-langkah yang dilakukan algoritma Boyer-Moore pada saat mencocokkan string adalah:
# Algoritma Boyer-Moore mulai mencocokkan pattern pada awal teks.
# Dari kanan ke kiri, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
## Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
## Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
# Algoritma kemudian menggeser pattern dengan memaksimalkan nilai penggeseran good-suffix dan penggeseran bad-character, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.

== Pseudocode ==
Berikut adalah pseudocode algoritma Boyer-Moore pada fase pra-pencarian:
procedure preBmBc(
input P: array[0..n-1] of char,
input n: integer,
input/output bmBc: array[0..n-1] of integer
)
Deklarasi:
i: integer

Algoritma:
for (i:= 0 to ASIZE-1)
bmBc[i]:= m;
endfor
for (i:= 0 to m - 2)
bmBc[P[i]]:= m - i - 1;
endfor

procedure preSuffixes(
input P: array[0..n-1] of char,
input n: integer,
input/output suff: array[0..n-1] of integer
)

Deklarasi:
f, g, i: integer

Algoritma:
suff[n - 1]:= n;
g:= n - 1;
for (i:= n - 2 downto 0) {
if (i > g and (suff[i + n - 1 - f] < i - g))
suff[i]:= suff[i + n - 1 - f];
else
if (i < g)
g:= i;
endif
f:= i;
while (g >= 0 and P[g] = P[g + n - 1 - f])
--g;
endwhile
suff[i] = f - g;
endif
endfor

procedure preBmGs(
input P: array[0..n-1] of char,
input n: integer,
input/output bmBc: array[0..n-1] of integer
)
Deklarasi:
i, j: integer
suff: array [0..RuangAlpabet] of integer

preSuffixes(x, n, suff);

for (i:= 0 to m-1)
bmGs[i]:= n
endfor
j:= 0
for (i:= n - 1 downto 0)
if (suff[i] = i + 1)
for (j:=j to n - 2 - i)
if (bmGs[j] = n)
bmGs[j]:= n - 1 - i
endif
endfor
endif
endfor
for (i = 0 to n - 2)
bmGs[n - 1 - suff[i]]:= n - 1 - i;
endfor

Dan berikut adalah pseudocode algoritma Boyer-Moore pada fase pencarian:
procedure BoyerMooreSearch(
input m, n: integer,
input P: array[0..n-1] of char,
input T: array[0..m-1] of char,
output ketemu: array[0..m-1] of boolean
)

Deklarasi:
i, j, shift, bmBcShift, bmGsShift: integer
BmBc: array[0..255] of interger
BmGs: array[0..n-1] of interger

Algoritma:
preBmBc(n, P, BmBc)
preBmGs(n, P, BmGs)
i:=0
while (i<= m-n) do
j:=n-1
while (j >=0 n and T[i+j] = P[j]) do
j:=j-1
endwhile
if(j < 0) then
ketemu[i]:=true;
endif
bmBcShift:= BmBc[chartoint(T[i+j])]-n+j+1
bmGsShift:= BmGs[j]
shift:= max(bmBcShift, bmGsShift)
i:= i+shift

== Kompleksitas ==
Tabel untuk penggeseran bad-character dan good-suffix dapat dihitung dengan [[kompleksitas waktu]] dan ruang sebesar O(n + σ) dengan σ adalah besar ruang alfabet. Sedangkan pada fase pencarian, algoritma ini membutuhkan waktu sebesar O(mn), pada kasus terburuk, algoritma ini akan melakukan 3n pencocokkan karakter, tetapi pada performa terbaiknya algoritma ini hanya akan melakukan O(m/n) pencocokkan.

== Referensi ==

== Lihat pula ==
* [[Daftar algoritme]]
* [[Algoritme pencarian string]]
* [[Algoritme Knuth-Morris-Pratt]]

== Pranala luar ==
* [http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf Artikel original tentang Boyer-Moore]
* [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html Halaman berisi penjelasan tentang Boyer-Moore dan juga sebuah applet yang menganimasikan cara kerjanya]

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Boyer-Moore&oldid=29380643 Wikipedia bahasa Indonesia], revisi 29380643 (2026-06-23T15:52:19Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Algoritma Boyer-Moore - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29380643; atribusi sumber disertakan.