Boyer Moore Horspool Algorithm
First Step
๋ฌธ์์ด์์ ์ผ์ ํ ๊ท์น์ ์ฐพ๋๊ฒ์ ๋ค์ํ๊ฒ ์ฌ์ฉํ ์ ์๊ณ ๊ฐ๋ฐ๊ณผ์ ์์ ์์ฃผ, ์ฝ๊ฒ ์ ํ ์ ์์ด์. ๋, ๋ค์ํ ํ๋ก๊ทธ๋จ์์ ๋ง์ด ์ฐ์ด๊ธฐ๋ ํฉ๋๋ค.
๊ทธ๋ฆฌ๊ณ ๊ทธ๋ฐ ๋ฌธ์์ด ๊ฒ์ ์๊ณ ๋ฆฌ์ฆ์ ํฌ๋์ค-๋ชจ๋ฆฌ์ค-ํ๋ซ ์๊ณ ๋ฆฌ์ฆ, ๋ณด์ด์ด-๋ฌด์ด-ํธ์คํ ์๊ณ ๋ฆฌ์ฆ, ๋ผ๋น-์นดํ ์๊ณ ๋ฆฌ์ฆ ๋ฑ์ ์ฌ์ฉํฉ๋๋ค.
์ ๋ ๊ทธ๋ฐ ์๊ณ ๋ฆฌ์ฆ ์ค BMH ์๊ณ ๋ฆฌ์ฆ์ ๋ํด ์ด์ผ๊ธฐ ํด๋ณด๋ ค๊ณ ํด์. ์ด๊ฑธ ๋จผ์ ์ด์ผ๊ธฐํ๋ ์ด์ ๋ ๊ฐ์ฅ ์ฝ๊ธฐ ๋๋ฌธ์ ๋๋ค!
Naive string search visualize
BMH ์๊ณ ๋ฆฌ์ฆ์ ์ด์ผ๊ธฐ ํ๊ธฐ ์ ์ ์ผ๋ฐ์ ์ธ ๋ฌธ์์ด ๊ฒ์์ ์ด์ผ๊ธฐ ํ๊ณ ์ถ์ด์. ์ผ๋ฐ์ ์ธ ๋ฌธ์์ด ๊ฒ์์ ๋ฐฉ๋ฒ์ ๊ทธ๋ฆผ์ผ๋ก ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ์์.
Naive string search code
Output Pattern found at index 0 Pattern found at index 9 Pattern found at index 13
์ด์ฒ๋ผ Naive string search๋ ๊ฒฐ๊ณผ๊ฐ์ ์ป๋ ๊ฐ์ฅ ์ ํต์ ์ธ ๋ฐฉ์์ด์์. ํ์ง๋ง ์ด๋ฐ ๊ธ์๊ฐ ์์ญ์ต๊ฐ๊ฐ ๋๋ค๋ฉด? ํ๋ํ๋ ์ผ์ผํ ๋น๊ตํ๋ ค๋ฉด ๊ต์ฅํ ๋ง์ ์๊ฐ์ด ๊ฑธ๋ฆด๊บผ์์. ๊ทธ๋์ ์ ๋ BMH ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐํด๋ณด๋ ค๊ณ ํด์.
Boyer-Moore-Horspool search theory
BMH ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ์ ๋ฌธ์์ด ๊ณ์ฐ ๊ณต์์ ์ด์ฉํด ํ๋ฅผ ๋ง๋ค์ด ์ฌ์ฉํฉ๋๋ค. 1. ๊ฒ์ ํค์๋์ ์ด ๊ธธ์ด๋ฅผ ๊ตฌํ๋ค. ****=> ์๋ฅผ ๋ค์ด TOOTH ๋ผ๋ ๋จ์ด๊ฐ ์๋ค๋ฉด ์ด๊ธธ์ด๋ 5๊ฐ ๋ ๊บผ์์. 2. ๊ฒ์ํ ํค์๋์์ ์กด์ฌํ๋ ๋ฌธ์์ index๋ก ์ด๋ฃจ์ด์ง ํ๋ก ๋ง๋ ๋ค.
T | O | O | T | H |
---|---|---|---|---|
0 | 1 | 2 | 3 | 4 |
3. ํด๋น ํ์์ index๋ฅผ (์ด๊ธธ์ด - index - 1) ๋ก ๋ณ๊ฒฝํ๋ค.
T | O | O | T | H |
---|---|---|---|---|
4 | 3 | 2 | 1 | 0 |
4. ํ์์ ๋ง์ง๋ง ๋ฌธ์์ ํค์๋์ ์กด์ฌํ์ง ์๋ ๋ค๋ฅธ ๋ฌธ์๋ ์ด๊ธธ์ด๋ก ๋ณ๊ฒฝํ๋ค.
T | O | O | T | H | * |
---|---|---|---|---|---|
4 | 3 | 2 | 1 | 5 | 5 |
5. ๋ง์ฝ ๊ฐ์ ๋ฌธ๊ฐ ์๋ค๋ฉด ํด๋น ๋ฌธ์์๋ฅผ ๊ฐ์ฅ ์์ ์ซ์๋ก ๊ธฐ์ค์ ์ก๋๋ค.
T | O | H | * |
---|---|---|---|
1 | 2 | 5 | 5 |
6. ์ด๋ฅผ ์ด์ฉํด์ ์์ฐจ์ ์ผ๋ก ๋ฌธ์๊ฐ ์ผ์นํ๋์ง ํ์ธํ๊ณ ๋งค์น๊ฐ ์๋๋ค๋ฉด ํ์ value ๋งํผ ์ด๋์ํจ๋ค.
์ฆ ์ด BMH ์๊ณ ๋ฆฌ์ฆ์ ๋งค์น๊ฐ ๋์ง ์์์๋ ํ์ฌ ๊ฒ์ index๋ฅผ ๊ณ์ฐ ๊ณต์๋งํผ ์ด๋์ํค๋๊ฒ ํต์ฌ์ด์์.
BMH algorithm visualize
BMH Algorithm code
์์ ์ด๋ก ์ ์ฝ๋๋ก ๋ํ๋ด๋ฉด ์๋์ ๊ฐ์๊บผ์์.
Reference.
Last updated