Back to : advanced-algorithms
Contents

(์•„์ง ์ž‘์„ฑ ์ค‘์ธ ๊ธ€์ž…๋‹ˆ๋‹ค)

์ด ๊ธ€์€ KMP ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ Trie ์ž๋ฃŒ๊ตฌ์กฐ์— ๋Œ€ํ•œ ์ดํ•ด๋ฅผ ์„ ํ–‰์œผ๋กœ ์š”๊ตฌํ•ฉ๋‹ˆ๋‹ค.

Motivation

Boyer-Moore ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ํ•ด๊ฒฐํ•˜๋Š” ๋ฌธ์ œ๋Š” KMP์™€ ๋˜‘๊ฐ™์ด, ์–ด๋–ค $n$๊ธ€์ž์˜ ๊ธด ํ…์ŠคํŠธ $T$์— ๋Œ€ํ•ด, ์งง์€ $m$๊ธ€์ž์˜ ํŒจํ„ด $P$๋ฅผ ๋งค์นญํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

  • ๊ฐ€์žฅ Naiveํ•˜๊ฒŒ $T$์˜ ๋ชจ๋“  ์œ„์น˜์— ๋Œ€ํ•ด $m$๊ธ€์ž๋ฅผ ๋งค์นญํ•ด๋ณด๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ $O(nm)$ ์ž…๋‹ˆ๋‹ค.
  • KMP ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์€ (์–ธ์  ๊ฐ€ ์ž‘์„ฑํ•  ๊ณ„ํš์€ ์žˆ์ง€๋งŒ ์šฐ์„ ์ˆœ์œ„๋Š” ๋‚ฎ์Šต๋‹ˆ๋‹ค) ์ด๋ฅผ $O(n + m)$ ์œผ๋กœ ์ค„์ธ ์—„์ฒญ๋‚œ ์„ฑ๊ณผ๋ฅผ ๋ณด์ž…๋‹ˆ๋‹ค.

Boyer-Moore ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ worst case์—์„œ๋Š” $O(nm)$์ด์ง€๋งŒ, string์ด ๋žœ๋คํ•˜๊ฒŒ ์ฃผ์–ด์ง„๋‹ค๋ฉด ํ‰๊ท  $O(n / m)$ ๋ณต์žก๋„๋ฅผ ๋ณด์ž…๋‹ˆ๋‹ค.

๊ธฐ๋ณธ์ ์œผ๋กœ, ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํŒจํ„ด์„ ์˜ค๋ฅธ์ชฝ๋ถ€ํ„ฐ ์™ผ์ชฝ์œผ๋กœ ๋งค์นญํ•˜๊ณ , ๋ฌธ์ž์—ด ์ž์ฒด๋Š” (์ฆ‰ ๋งค์นญํ•˜๋Š” ์œ„์น˜ ์ž์ฒด๋Š”) ์™ผ์ชฝ์—์„œ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๋ด…๋‹ˆ๋‹ค. ์ด ๋ฐฉํ–ฅ์˜ ์ฐจ์ด์— ์ฃผ๋ชฉํ•  ํ•„์š”๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. KMP์˜ ๊ฒฝ์šฐ๋Š” ํŒจํ„ด๊ณผ ํ…์ŠคํŠธ ๋ชจ๋‘ ์ขŒ -> ์šฐ ๋กœ ๋งค์นญํ•ฉ๋‹ˆ๋‹ค. ๊ฐ€๋Šฅํ•œํ•œ โ€˜์ฒซโ€™, โ€˜๋‘๋ฒˆ์งธโ€™ ์™€ ๊ฐ™์€ ๋ง์€ ์˜ค๋ฅธ์ชฝ์—์„œ ์™ผ์ชฝ์œผ๋กœ ๋งค์นญํ•˜๋Š” ์‹ค์ œ ์„ธํŒ…์—, โ€˜1๋ฒˆโ€™, โ€˜2๋ฒˆโ€™ ๋“ฑ์˜ ๋ง์€ ์ง„์งœ ์ธ๋ฑ์Šค๋ฅผ ์˜๋ฏธํ•˜๋„๋ก ์ž‘์„ฑํ–ˆ์Šต๋‹ˆ๋‹ค.

Algorithm : Bad Character Heuristic

ํ…์ŠคํŠธ abcacbcadc ์—์„œ ํŒจํ„ด acbcda๋ฅผ ๋งค์นญํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ์ด๋•Œ, ๋’ค์—์„œ๋ถ€ํ„ฐ ์•ž์œผ๋กœ ๋งค์นญ์„ ์‹œ๋„ํ•˜๋Š” ๊ฒƒ์€ ํ…์ŠคํŠธ abcacb ์™€ acbcda๋ฅผ ๋งค์นญํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ ์ฒซ ๊ธ€์ž (ํŒจํ„ด์„ ์˜ค๋ฅธ์ชฝ๋ถ€ํ„ฐ ์ฝ์œผ๋ฏ€๋กœ ํ…์ŠคํŠธ์™€ ํŒจํ„ด์˜ ์ฒซ ๊ธ€์ž๋Š” ๊ฐ๊ฐ 6๋ฒˆ ์œ„์น˜์ธ b์™€ a์ž…๋‹ˆ๋‹ค!) ๋ฅผ ๋งค์นญํ•˜๋ ค๊ณ  ์‹œ๋„ํ–ˆ์„ ๋•Œ, a๋ฅผ ์ฐพ์•„์•ผ ํ•˜๋Š”๋ฐ b๋ฅผ ์ฐพ์•˜์œผ๋ฏ€๋กœ ์‹คํŒจํ–ˆ์Šต๋‹ˆ๋‹ค.

Naive matching์€ ์—ฌ๊ธฐ์„œ ํฌ๊ธฐํ•˜๊ณ  ๋‹ค์Œ ์œ„์น˜์ธ bcacbc์™€์˜ ๋งค์นญ์„ ์‹œ๋„ํ•˜๊ฒ ์ง€๋งŒ, Boyer-Moore์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์—ฌ๊ธฐ์„œ โ€œ๊ทธ๋Ÿผ ๋งŒ์•ฝ, ์ด 6๋ฒˆ์œ„์น˜์˜ b๋ฅผ ๊ผญ ์จ์•ผ ํ•œ๋‹ค๋ฉด, ์–ด๋””๊นŒ์ง€ ๋‚ด๊ฐ€ ํŒจํ„ด์„ ๋ฐ€์–ด์•ผ b๋ฅผ ์“ธ ์ˆ˜ ์žˆ๋Š๋ƒ?โ€ ๋ผ๋Š” ์งˆ๋ฌธ์„ ๋˜์ง‘๋‹ˆ๋‹ค. ์ƒ๊ฐํ•ด๋ณด๋ฉด ํ…์ŠคํŠธ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ํŒจํ„ด์„ ํ•œ์นธ ๋ฐ€์–ด๋ดค์ž, ํŒจํ„ด์˜ 5๋ฒˆ ๊ธ€์ž์ธ d์™€ b๋ฅผ ๋งค์นญํ•˜๊ฒŒ ๋  ๊ฒƒ์ด๊ณ  ์ด๋Š” ์–ด์ฐจํ”ผ ์‹คํŒจํ•  ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ํŒจํ„ด์˜ ๋งจ ๋’ค๋ฅผ ๊ธฐ์ค€์œผ๋กœ 3๊ธ€์ž๋ฅผ ๋ฐ€์–ด์•ผ b๋ฅผ ํ…์ŠคํŠธ 6๋ฒˆ b์— ๋งž์ถœ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ์ด๋งŒํผ์„ pushํ•ด ๋ฒ„๋ฆด ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ ์ด โ€˜bโ€™ ๋ฅผ Bad Character ๋ผ๊ณ  ๋ถ€๋ฅผ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์ด๋ฅผ ์ข€๋” ์ •๋ฆฌํ•˜๋ฉดโ€ฆ

  • Bad character๊ฐ€ ํŒจํ„ด์— ์•„์˜ˆ ๋“ฑ์žฅํ•˜์ง€ ์•Š์œผ๋ฉด, ํŒจํ„ด์„ ํ™• ๋ฐ€์–ด์„œ ์•„์˜ˆ ๋„˜์–ด๊ฐ€๋„ ๋ฉ๋‹ˆ๋‹ค.
  • Bad character๊ฐ€ ํŒจํ„ด์—์„œ ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ์— ๋“ฑ์žฅํ•˜๋Š” ์œ„์น˜๊ฐ€ ํ˜„์žฌ ๋ณด๊ณ ์žˆ๋Š” bad character์˜ ํŒจํ„ด์—์„œ์˜ ์œ„์น˜๋ณด๋‹ค ์™ผ์ชฝ์ด๋ฉด, ๊ทธ๋งŒํผ์„ ๋ฐ€์–ด๋„ ๋ฉ๋‹ˆ๋‹ค.
  • Bad character๊ฐ€ ํŒจํ„ด์—์„œ ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ์— ๋“ฑ์žฅํ•˜๋Š” ์œ„์น˜๊ฐ€ ํ˜„์žฌ ๋ณด๊ณ ์žˆ๋Š” bad character์˜ ํŒจํ„ด์—์„œ์˜ ์œ„์น˜๋ณด๋‹ค ์˜ค๋ฅธ์ชฝ์ด๋ฉด ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ •๋ณด๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค.

Algorithm : Good Suffix Heuristic

์ด ๋ฐฉ๋ฒ•์€ ์ž์„ธํžˆ ์„ค๋ช…ํ•˜์ง€ ์•Š์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. (์ด์œ ๋Š” ํ›„์ˆ ํ•ฉ๋‹ˆ๋‹ค) Good suffix๋ž€, ์–ด๋–ป๊ฒŒ ๋ณด๋ฉด ์œ„ Bad character์˜ 3๋ฒˆ ๊ฒฝ์šฐ์— ์–ป๋Š” ์ •๋ณด๊ฐ€ ์—†์Œ์„ ๊ฑฐ๊พธ๋กœ ์ด์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์ธ๋ฐ์š”. 3๋ฒˆ ๊ฒฝ์šฐ๋Š” ์•„๋งˆ๋„ ๊ฝค ๋งŽ์€ ๊ธ€์ž๋“ค์ด ๋งž์€ ๋‹ค์Œ ์ฒ˜์Œ์œผ๋กœ bad character๋ฅผ ๋งŒ๋‚œ ์ƒํ™ฉ์ผ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ฆ‰ pattern์˜ ๊ฝค ๊ธด suffix๊ฐ€ ์ด๋ฏธ ๋งž๊ณ  ์žˆ๋Š” ์ƒํ™ฉ์ด๋ผ๋Š” ์˜๋ฏธ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ์ด Good suffix๋ฅผ ํŒจํ„ด์—์„œ ๋‹ค์‹œ ๋งž์ถ”๋ ค๋ฉด ์–ผ๋งŒํผ ์ด๋™ํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋ฏธ๋ฆฌ ๋ชจ๋‘ precomputationํ•ด ๋‘๋ฉด, ๊ทธ๋งŒํผ์„ ์ ํ”„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹น์—ฐํžˆ ๋งž๋Š” suffix๊ฐ€ ๊ธธ์ˆ˜๋ก ์ด suffix๋ฅผ ๋‹ค์‹œ ๋งž์ถ”๊ธฐ๊ฐ€ ์–ด๋ ค์šธ ๊ฒƒ์ด๋ฏ€๋กœ, ๊ฝค ๋ฉ€๋ฆฌ ์ ํ”„ํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ด precomputation์€ โ€œPattern์˜ ๊ธธ์ด k์ธ suffix๊ฐ€ ๋‹ค์‹œ suffix๋กœ ๋“ฑ์žฅํ•˜๋Š” pattern์˜ prefix ์œ„์น˜โ€ ๋ฅผ ๋งˆํ‚นํ•˜๋ฉด ๋˜๊ณ , KMP์˜ ์‹คํŒจํ•จ์ˆ˜์™€ ๋งค์šฐ ์œ ์‚ฌํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Boyer-Moore-Horspool Algorithm

Horspool์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์œ„ Boyer-Moore์—์„œ Good suffix heuristic์„ ์•„์˜ˆ ํฌ๊ธฐํ•˜๊ณ , Bad character๋Š” ํ•ญ์ƒ ํ˜„์žฌ ๋งค์นญ ์œ„์น˜์˜ ๋งˆ์ง€๋ง‰ ๊ธ€์ž๋งŒ ๊ณ ๋ คํ•ฉ๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ํ•ด๋„ ํ‰๊ท  ์‹œ๊ฐ„ ๋ณต์žก๋„ $O(n / m)$ ๋น„์Šทํ•œ ์‹œ๊ฐ„์„ ์œ ์ง€ํ•  ์ˆ˜ ์žˆ์Œ์ด ์•Œ๋ ค์ ธ ์žˆ์ง€๋งŒ, ๊ทธ ์ฆ๋ช… ๊ณผ์ •์€ ์—„์ฒญ๋‚œ ์ˆ˜์‹๊ณผ ๊ณ ํ†ต์Šค๋Ÿฌ์šด ์ฆ๋ช… (๋ถ€๋“ฑ์‹ ์ค„์ด๊ธฐ)์„ ์š”๊ตฌํ•ฉ๋‹ˆ๋‹ค. ๋‹ค๋งŒ, ์ถฉ๋ถ„ํžˆ ๋žœ๋คํ•œ ํ…์ŠคํŠธ์— ๋Œ€ํ•ด์„œ๋Š” B-M-H๊ฐ€ ๊ต‰์žฅํžˆ ๋น ๋ฆ„์ด ์ž˜ ์•Œ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.

Horspool์€ ๊ต‰์žฅํžˆ ์‰ฝ๊ฒŒ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋จผ์ € ๊ฐ character์— ๋Œ€ํ•ด ํŒจํ„ด์˜ ์˜ค๋ฅธ์ชฝ ๋์—์„œ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด (ํ•˜์ง€๋งŒ ์˜ค๋ฅธ์ชฝ ๋์€ ์•„๋‹Œ) ๋“ฑ์žฅ ์œ„์น˜๋ฅผ ๊ณ„์‚ฐํ•ด ๋‘๊ณ , bad character์— ๊ฑธ๋ฆฌ๋ฉด ๊ทธ๋งŒํผ pushํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

์—ฌ๊ธฐ์„œ๋Š” ์ •๋ง ๋Ÿฌํ”„ํ•œ ์ฆ๋ช…โ€ฆ๋„ ์•„๋‹ˆ๊ณ  argument๋ฅผ ํ•˜๋‚˜ ์†Œ๊ฐœํ•˜๊ณ  ๋งˆ์น˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์•ŒํŒŒ๋ฒณ $q$๊ธ€์ž ์ค‘ ๋žœ๋คํ•˜๊ฒŒ ์ƒ์„ฑ๋œ string $P, T$์—์„œ์˜ Horspool ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ฐ€์ •ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ด์ค‘ ํ•œ ๊ธ€์ž๊ฐ€ ํŒจํ„ด์˜ ์˜ค๋ฅธ์ชฝ ๋์—์„œ ์–ผ๋งˆ๋‚˜ ๋ฉ€๋ฆฌ ์žˆ์„์ง€ ๊ทธ ๊ธฐ๋Œ“๊ฐ’์„ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ์•ŒํŒŒ๋ฒณ $x$๋ฅผ ์ด์šฉํ•˜์—ฌ $k$๊ธธ์ด ์ด์ƒ์˜ jump๋ฅผ ํ—ˆ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋’ค์—์„œ $k-1$๊ฐœ์˜ ๊ธ€์ž๋Š” $x$๊ฐ€ ์•„๋‹Œ ๋‹ค๋ฅธ ๊ธ€์ž์—ฌ์•ผ ํ•˜๋ฏ€๋กœ, ์ ํ”„ ๊ธธ์ด๊ฐ€ $k$ ์ด์ƒ์ผ ํ™•๋ฅ ์€ $\left(1-\frac{1}{q}\right)^{k-1}$ ์ž…๋‹ˆ๋‹ค. $r = \left(1-\frac{1}{q}\right)$ ๋กœ ์“ฐ๋ฉด ํŽธํ•˜๊ฒŒ ์ด๋ฅผ $r^{k-1}$ ๋กœ ์“ธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

$\expect{X} = \sum_{k = 1}^{\infty} \P(X \geq k)$ ์˜ ๊ณต์‹์„ ์ด์šฉํ•ฉ๋‹ˆ๋‹ค. $k \geq m+1$์˜ ํ™•๋ฅ ์€ 0์ด๋ฏ€๋กœ, \(\expect{\text{jump length}} = \sum_{j = 1}^{m} r^{j-1} = \frac{r^m - 1}{r - 1}= q(1 - r^m)\)

๋”ฐ๋ผ์„œ, $m$์ด ์ถฉ๋ถ„ํžˆ ํฌ๋ฉด ๋Œ€์ถฉ $q$ ์ •๋„์˜ shift๋Š” ๊ธฐ๋Œ€ํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, $O(n / q)$ ์ •๋„์˜ ํผํฌ๋จผ์Šค๋Š” ๊ธฐ๋Œ€ํ•ด ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹น์—ฐํžˆ ์ด๋Š” ๊ฐ ๊ธ€์ž๊ฐ€ iid random์ด๋ผ๋Š” ์ด๋ฃจ์–ด์ง€์ง€ ์•Š๋Š” ๊ฐ€์ •์ด ๋“ค์–ด๊ฐ”์„ ๋ฟ๋งŒ ์•„๋‹ˆ๋ผ, ๊ฐ ์œ„์น˜์—์„œ bad character๋ฅผ ๋งŒ๋‚˜๋Š” ๋ฐ ๊ฑธ๋ฆฌ๋Š” ๋งค์นญ๊ฐœ์ˆ˜๋„ ๋ฌด์‹œํ•˜๊ณ  ์žˆ์ง€๋งŒ, ๊ฐ„๋‹จํ•œ argument๋กœ๋Š” ๊ทธ๋Ÿญ์ €๋Ÿญ ๊ธฐ๋Šฅํ•ฉ๋‹ˆ๋‹ค.