Бојер-Мур алгоритам за претрагу ниски
У рачунарству Бојер-Мур алгоритам за претрагу ниски је ефикасан алгоритам за претрагу низова који је стандардни репер за практично претраживање ниски у литератури.[1] Развили су га Роберт С. Бојер и Ј Стротер Мур.[2] Алгоритам претпроцесује ниску која се тражи (узорак), али не ниску која се тражи (у тексту). Због тога је погодан за примене где се текст не састоји од више третрага али узорак да. Бојер-Мур алгоритам користи информације које су прикупљене током претпроцесирања да би прескочио делове текста, разултирајући мањим сталним фактором од многих других алторитама за ниске. У принципу, алгоритам ради брже док се дужина узорка повећава.
Дефиниције
[уреди | уреди извор]| A | N | P | A | N | M | A | N | - |
| P | A | N | - | - | - | - | - | - |
| - | P | A | N | - | - | - | - | - |
| - | - | P | A | N | - | - | - | - |
| - | - | - | P | A | N | - | - | - |
| - | - | - | - | P | A | N | - | - |
| - | - | - | - | - | P | A | N | - |
од k=3 до k=8. Подударају се у k=5.
- S[i] односи се на карактер у индексу i ниске S, почевши од 1.
- S[i..j] се односи на подниску ниске S почевши од i и завршавајући се на j, закључно.
- Префикс из S је подниска S[1..i] за неко i у размаку [1, n], где је n дужина S.
- Суфикс из S је подниска S[i..n] за неко i у размаку [1, n], где је n дужина S.
- Ниска која се тражи зове се узорак и зове се симболом P.
- Ниска кроз коју се претражује зове се текст и зове се симболом T.
- Дужина P је n.
- Дужина T је m.
- Поравнање од P до T је индекс k у T такав да последњи карактер из P је поравнат са индексом k из T.
- Подударање или појава P се јавља у виду усклађивања ако је P еквивалентно са T[(k-n+1)..k].
Опис
[уреди | уреди извор]Бојер-Мур алгоритам тражи појављивања P у T вршећи експлицитно поређење карактера на различитим поравнањима. Уместо претраге сировом снагом свих поравнања (којих има m-n+1). Бојер-Мур користи информације добијене из претпроцесирања P да прескочи што више поравнања.
Алгоритам почиње код поравнања k = n, тако да је почетак P је поравнат са почетком T. Карактери P и T се онда пореде почевши од индекса n у P и k у Т, идући ка доле: ниске се упарују од краја ка почетку од P. Поређења се настављају све док не дође или до неусклађености или се дође до почетка P (што значи да је дошло до поклапања), после чега је поравнање померено удесно у складу са максималном вредношћу која је дозвољена одређеним правилима. Поређења се поново врше у новом поравнању, и процес се понавља све док поравнање не прође крај T.
Правила за померање се имплементирају као константе табеле за преглед, коришћењем табеле добијене током претпроцесирања P.
Правила за померање
[уреди | уреди извор]Правило лошег карактера
[уреди | уреди извор]Опис
[уреди | уреди извор]| - | - | - | - | X | - | - | K | - | - | - |
| A | N | P | A | N | M | A | N | A | M | - |
| - | N | N | A | A | M | A | N | - | - | - |
| - | - | - | N | N | A | A | M | A | N | - |
карактера са узорком ННААМАН.
Правило лошег карактера разматра карактер у T код ког процес поређења не успе (претпостављајући да ће до таквог неуспеха доћи). Следеће појављивање тог карактера лево у P се проналази, и промена коју доноси тај догађај у складу са непогођеним догађајем у T се предлаже. Ако се непогођени карактер не појави лево у P, предлаже се померање које помера цело P после тачке неслагања.
Претпроцесирање
[уреди | уреди извор]Методе варирају у тачном облику табела које правило лошег карактера треба да узме, али једноставно решење инстант-време претргагом је следеће: направити 2D табелу која се индексира прво по идексу карактера cу алфабету о другог по индексу i у узорку. Ово проналажење враћа појављивање c' y P са следећим највећим индексом j < i или -1 ако нема таквог догађаја. Предложено померање ће онда бити i - j, са O(1) временском сложеношћу и O(kn) просторном, претпостављајући коначну дужину речи дужине k.
Добро правило суфикса
[уреди | уреди извор]Опис
[уреди | уреди извор]| - | - | - | - | X | - | - | K | - | - | - | - | - |
| M | A | N | P | A | N | A | M | A | N | A | P | - |
| A | N | A | M | P | N | A | M | - | - | - | - | - |
| - | - | - | - | A | N | A | M | P | N | A | M | - |
Добро правило суфикса је упадљиво сложеније у оба концепта и имплементације од правила лошег карактера. То је разлог зашто поређења почињу на крају узорка радије него на почетку, и формално се наводи као:[3]
Претпоставимо да за дато поравнање из P и T, подстринг t из T одговара суфиксу из P, али до неслагања долази током следећег поређења улево. Онда пронаћи, уколико постоји, најдеснију копију t' из t у P тако да t' није суфикс из P и карактер лево од t' у P се раликује од карактера лево од t у P. Помера се P удесно тако да подниска t' у P је испод подниске t у T. Ако t' не постоји, онда помери улево од P после левог краја t у T за најмању величину тако да префикс помереног узорка се подудара са суфиксом t у T. Ако такво померање није могуће, онда помери P за n места удесно. Ако се појави P, онда помери P за најмању величину тако да одговарајући префикс помереног P се подудара са суфиксом настанка из P у T. Ако такво померање није могуће, онда помери P за n места, то јест, помери P поред T.
Претпроцесирање
[уреди | уреди извор]Добро правило префикса захтева две табеле: једну да користи у генералном случају, и још једну да се користи када када или генерални случај не врати неки значајан резултат или дође до подударања. Ове табеле ће бити одређене L и H односно. Њихове дефиниције су као што следи :[3]
За свако i, L[i] је највећа позиција мања од n таква да ниска P[i..n] се подудара са суфиксом од P[1..L[i]] и таква да карактер претходног чији суфикс није једнак P[i-1]. L[i] је постављен на нулу ако нема позиције која задовољава услов.
Нека H[i] означава дужину највећег суфикса из P[i..n] који је такође и префикс из P, ако он постоји. Ако не постоје, онда је H[i] постављен на нулу.
Обе табеле се могу направити тако да буду O(n) временска сложеност и да користе O(n) просторну сложеност. Поравнање померања индекса i у P је добијено из n - L[i] или n - H[i]. H би требало само да се користи ако је L[i] нула или је дошло до подударања.
Галил правило
[уреди | уреди извор]Једноставна али веома важна имплементација Бојер-Мура, поставио је Галил 1979.[4] За разлику од померања, Галил правило бави се убрзавањем поређења током сваког поравнања тако што прескаче делове за које се зна да се подударају. Претпоставимо да код поравнања k1, P се пореди са T до карактера c из T. Онда ако се P помера до k2 тако да је леви крај између c и k1, је следећа фаза префикса из P мора се подударати са подниском T[(k2 - n)..k1]. Тако да ако поређења дођу до позиције k1 of T, појављивање из P може се забележити без експлицитног проверања после k1. Поред тога што побољшава ефикасност Бојер-Мура, Галил правило увек мора даје lлинеарно време егзекуције у најгорем случају.
Перформансе
[уреди | уреди извор]Бојер-Мур алгоритам како је наведно у оригиналном раду има најгори случај временске сложености O(n+m) само ако се узорак не појави у тексту. Ово су први доказали Кнут, Морис, и Прат 1977,[5] затим Гуиба and Одлизко 1980[6] са горњом границом од 5m поређења у најгорем случају. Кол је дао доказ да горња граинца од 3m поређења у најгорем случају 1991.[7]
Када се узорак појави у тексту, временска сложеност оригиналног алгоритма је O(nm) у најгорем случају. Ово је лако видети када се и узорак и текст састоје само од истих понабљајућих карактера. Међутим, укључење Галил правила даје линеарну сложеност у свим случајевима.[4][7]
Имплементације
[уреди | уреди извор]Разне имплементације постоје у ралзичитим програмским језицима. У C++-y, Boost обезбеђује generic Boyer–Moore search имплементације у Алгоритми библиотеци.
Python имплементација
[уреди | уреди извор]from typing import *
# This version is sensitive to the English alphabet in ASCII for case-insensitive matching.
# To remove this feature, define alphabet_index as ord(c), and replace instances of "26"
# with "256" or any maximum code-point you want. For Unicode you may want to match in UTF-8
# bytes instead of creating a 0x10FFFF-sized table.
ALPHABET_SIZE = 26
def alphabet_index(c: str) -> int:
"""Return the index of the given character in the English alphabet, counting from 0."""
val = ord(c.lower()) - ord("a")
assert val >= 0 and val < ALPHABET_SIZE
return val
def match_length(S: str, idx1: int, idx2: int) -> int:
"""Return the length of the match of the substrings of S beginning at idx1 and idx2."""
if idx1 == idx2:
return len(S) - idx1
match_count = 0
while idx1 < len(S) and idx2 < len(S) and S[idx1] == S[idx2]:
match_count += 1
idx1 += 1
idx2 += 1
return match_count
def fundamental_preprocess(S: str) -> List[int]:
"""Return Z, the Fundamental Preprocessing of S.
Z[i] is the length of the substring beginning at i which is also a prefix of S.
This pre-processing is done in O(n) time, where n is the length of S.
"""
if len(S) == 0: # Handles case of empty string
return []
if len(S) == 1: # Handles case of single-character string
return [1]
z = [0 for x in S]
z[0] = len(S)
z[1] = match_length(S, 0, 1)
for i in range(2, 1 + z[1]): # Optimization from exercise 1-5
z[i] = z[1] - i + 1
# Defines lower and upper limits of z-box
l = 0
r = 0
for i in range(2 + z[1], len(S)):
if i <= r: # i falls within existing z-box
k = i - l
b = z[k]
a = r - i + 1
if b < a: # b ends within existing z-box
z[i] = b
else: # b ends at or after the end of the z-box, we need to do an explicit match to the right of the z-box
z[i] = a + match_length(S, a, r + 1)
l = i
r = i + z[i] - 1
else: # i does not reside within existing z-box
z[i] = match_length(S, 0, i)
if z[i] > 0:
l = i
r = i + z[i] - 1
return z
def bad_character_table(S: str) -> List[List[int]]:
"""
Generates R for S, which is an array indexed by the position of some character c in the
English alphabet. At that index in R is an array of length |S|+1, specifying for each
index i in S (plus the index after S) the next location of character c encountered when
traversing S from right to left starting at i. This is used for a constant-time lookup
for the bad character rule in the Boyer-Moore string search algorithm, although it has
a much larger size than non-constant-time solutions.
"""
if len(S) == 0:
return [[] for a in range(ALPHABET_SIZE)]
R = [[-1] for a in range(ALPHABET_SIZE)]
alpha = [-1 for a in range(ALPHABET_SIZE)]
for i, c in enumerate(S):
alpha[alphabet_index(c)] = i
for j, a in enumerate(alpha):
R[j].append(a)
return R
def good_suffix_table(S: str) -> List[int]:
"""
Generates L for S, an array used in the implementation of the strong good suffix rule.
L[i] = k, the largest position in S such that S[i:] (the suffix of S starting at i) matches
a suffix of S[:k] (a substring in S ending at k). Used in Boyer-Moore, L gives an amount to
shift P relative to T such that no instances of P in T are skipped and a suffix of P[:L[i]]
matches the substring of T matched by a suffix of P in the previous match attempt.
Specifically, if the mismatch took place at position i-1 in P, the shift magnitude is given
by the equation len(P) - L[i]. In the case that L[i] = -1, the full shift table is used.
Since only proper suffixes matter, L[0] = -1.
"""
L = [-1 for c in S]
N = fundamental_preprocess(S[::-1]) # S[::-1] reverses S
N.reverse()
for j in range(0, len(S) - 1):
i = len(S) - N[j]
if i != len(S):
L[i] = j
return L
def full_shift_table(S: str) -> List[int]:
"""
Generates F for S, an array used in a special case of the good suffix rule in the Boyer-Moore
string search algorithm. F[i] is the length of the longest suffix of S[i:] that is also a
prefix of S. In the cases it is used, the shift magnitude of the pattern P relative to the
text T is len(P) - F[i] for a mismatch occurring at i-1.
"""
F = [0 for c in S]
Z = fundamental_preprocess(S)
longest = 0
for i, zv in enumerate(reversed(Z)):
longest = max(zv, longest) if zv == i + 1 else longest
F[-i - 1] = longest
return F
def string_search(P, T) -> List[int]:
"""
Implementation of the Boyer-Moore string search algorithm. This finds all occurrences of P
in T, and incorporates numerous ways of pre-processing the pattern to determine the optimal
amount to shift the string and skip comparisons. In practice it runs in O(m) (and even
sublinear) time, where m is the length of T. This implementation performs a case-insensitive
search on ASCII alphabetic characters, spaces not included.
"""
if len(P) == 0 or len(T) == 0 or len(T) < len(P):
return []
matches = []
# Preprocessing
R = bad_character_table(P)
L = good_suffix_table(P)
F = full_shift_table(P)
k = len(P) - 1 # Represents alignment of end of P relative to T
previous_k = -1 # Represents alignment in previous phase (Galil's rule)
while k < len(T):
i = len(P) - 1 # Character to compare in P
h = k # Character to compare in T
while i >= 0 and h > previous_k and P[i] == T[h]: # Matches starting from end of P
i -= 1
h -= 1
if i == -1 or h == previous_k: # Match has been found (Galil's rule)
matches.append(k - len(P) + 1)
k += len(P) - F[1] if len(P) > 1 else 1
else: # No match, shift by max of bad character and good suffix rules
char_shift = i - R[alphabet_index(T[h])][i]
if i + 1 == len(P): # Mismatch happened on first attempt
suffix_shift = 1
elif L[i + 1] == -1: # Matched suffix does not appear anywhere in P
suffix_shift = len(P) - F[i + 1]
else: # Matched suffix appears in P
suffix_shift = len(P) - 1 - L[i + 1]
shift = max(char_shift, suffix_shift)
previous_k = k if shift >= i + 1 else previous_k # Galil's rule
k += shift
return matches
C имплементација
[уреди | уреди извор]#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdlib.h>
#define ALPHABET_LEN 256
#define max(a, b) ((a < b) ? b : a)
// BAD CHARACTER RULE.
// delta1 table: delta1[c] contains the distance between the last
// character of pat and the rightmost occurrence of c in pat.
//
// If c does not occur in pat, then delta1[c] = patlen.
// If c is at string[i] and c != pat[patlen-1], we can safely shift i
// over by delta1[c], which is the minimum distance needed to shift
// pat forward to get string[i] lined up with some character in pat.
// c == pat[patlen-1] returning zero is only a concern for BMH, which
// does not have delta2. BMH makes the value patlen in such a case.
// We follow this choice instead of the original 0 because it skips
// more. (correctness?)
//
// This algorithm runs in alphabet_len+patlen time.
void make_delta1(ptrdiff_t *delta1, uint8_t *pat, size_t patlen) {
for (int i=0; i < ALPHABET_LEN; i++) {
delta1[i] = patlen;
}
for (int i=0; i < patlen-2; i++) {
delta1[pat[i]] = patlen-1 - i;
}
}
// true if the suffix of word starting from word[pos] is a prefix
// of word
bool is_prefix(uint8_t *word, size_t wordlen, ptrdiff_t pos) {
int suffixlen = wordlen - pos;
// could also use the strncmp() library function here
// return ! strncmp(word, &word[pos], suffixlen);
for (int i = 0; i < suffixlen; i++) {
if (word[i] != word[pos+i]) {
return false;
}
}
return true;
}
// length of the longest suffix of word ending on word[pos].
// suffix_length("dddbcabc", 8, 4) = 2
size_t suffix_length(uint8_t *word, size_t wordlen, ptrdiff_t pos) {
size_t i;
// increment suffix length i to the first mismatch or beginning
// of the word
for (i = 0; (word[pos-i] == word[wordlen-1-i]) && (i < pos); i++);
return i;
}
// GOOD SUFFIX RULE.
// delta2 table: given a mismatch at pat[pos], we want to align
// with the next possible full match could be based on what we
// know about pat[pos+1] to pat[patlen-1].
//
// In case 1:
// pat[pos+1] to pat[patlen-1] does not occur elsewhere in pat,
// the next plausible match starts at or after the mismatch.
// If, within the substring pat[pos+1 .. patlen-1], lies a prefix
// of pat, the next plausible match is here (if there are multiple
// prefixes in the substring, pick the longest). Otherwise, the
// next plausible match starts past the character aligned with
// pat[patlen-1].
//
// In case 2:
// pat[pos+1] to pat[patlen-1] does occur elsewhere in pat. The
// mismatch tells us that we are not looking at the end of a match.
// We may, however, be looking at the middle of a match.
//
// The first loop, which takes care of case 1, is analogous to
// the KMP table, adapted for a 'backwards' scan order with the
// additional restriction that the substrings it considers as
// potential prefixes are all suffixes. In the worst case scenario
// pat consists of the same letter repeated, so every suffix is
// a prefix. This loop alone is not sufficient, however:
// Suppose that pat is "ABYXCDBYX", and text is ".....ABYXCDEYX".
// We will match X, Y, and find B != E. There is no prefix of pat
// in the suffix "YX", so the first loop tells us to skip forward
// by 9 characters.
// Although superficially similar to the KMP table, the KMP table
// relies on information about the beginning of the partial match
// that the BM algorithm does not have.
//
// The second loop addresses case 2. Since suffix_length may not be
// unique, we want to take the minimum value, which will tell us
// how far away the closest potential match is.
void make_delta2(ptrdiff_t *delta2, uint8_t *pat, size_t patlen) {
ssize_t p;
size_t last_prefix_index = patlen-1;
// first loop
for (p=patlen-1; p>=0; p--) {
if (is_prefix(pat, patlen, p+1)) {
last_prefix_index = p+1;
}
delta2[p] = last_prefix_index + (patlen-1 - p);
}
// second loop
for (p=0; p < patlen-1; p++) {
size_t slen = suffix_length(pat, patlen, p);
if (pat[p - slen] != pat[patlen-1 - slen]) {
delta2[patlen-1 - slen] = patlen-1 - p + slen;
}
}
}
// Returns pointer to first match.
// See also glibc memmem() (non-BM) and std::boyer_moore_searcher (first-match).
uint8_t* boyer_moore (uint8_t *string, size_t stringlen, uint8_t *pat, size_t patlen) {
ptrdiff_t delta1[ALPHABET_LEN];
ptrdiff_t delta2[patlen]; // C99 VLA
make_delta1(delta1, pat, patlen);
make_delta2(delta2, pat, patlen);
// The empty pattern must be considered specially
if (patlen == 0) {
return string;
}
size_t i = patlen - 1; // str-idx
while (i < stringlen) {
ptrdiff_t j = patlen - 1; // pat-idx
while (j >= 0 && (string[i] == pat[j])) {
--i;
--j;
}
if (j < 0) {
return &string[i+1];
}
ptrdiff_t shift = max(delta1[string[i]], delta2[j]);
i += shift;
}
return NULL;
}
Java имплементација
[уреди | уреди извор] /**
* Returns the index within this string of the first occurrence of the
* specified substring. If it is not a substring, return -1.
*
* There is no Galil because it only generates one match.
*
* @param haystack The string to be scanned
* @param needle The target string to search
* @return The start index of the substring
*/
public static int indexOf(char[] haystack, char[] needle) {
if (needle.length == 0) {
return 0;
}
int charTable[] = makeCharTable(needle);
int offsetTable[] = makeOffsetTable(needle);
for (int i = needle.length - 1, j; i < haystack.length;) {
for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
if (j == 0) {
return i;
}
}
// i += needle.length - j; // For naive method
i += Math.max(offsetTable[needle.length - 1 - j], charTable[haystack[i]]);
}
return -1;
}
/**
* Makes the jump table based on the mismatched character information.
*/
private static int[] makeCharTable(char[] needle) {
final int ALPHABET_SIZE = Character.MAX_VALUE + 1; // 65536
int[] table = new int[ALPHABET_SIZE];
for (int i = 0; i < table.length; ++i) {
table[i] = needle.length;
}
for (int i = 0; i < needle.length - 1; ++i) {
table[needle[i]] = needle.length - 1 - i;
}
return table;
}
/**
* Makes the jump table based on the scan offset which mismatch occurs.
* (bad character rule).
*/
private static int[] makeOffsetTable(char[] needle) {
int[] table = new int[needle.length];
int lastPrefixPosition = needle.length;
for (int i = needle.length; i > 0; --i) {
if (isPrefix(needle, i)) {
lastPrefixPosition = i;
}
table[needle.length - i] = lastPrefixPosition - i + needle.length;
}
for (int i = 0; i < needle.length - 1; ++i) {
int slen = suffixLength(needle, i);
table[slen] = needle.length - 1 - i + slen;
}
return table;
}
/**
* Is needle[p:end] a prefix of needle?
*/
private static boolean isPrefix(char[] needle, int p) {
for (int i = p, j = 0; i < needle.length; ++i, ++j) {
if (needle[i] != needle[j]) {
return false;
}
}
return true;
}
/**
* Returns the maximum length of the substring ends at p and is a suffix.
* (good suffix rule)
*/
private static int suffixLength(char[] needle, int p) {
int len = 0;
for (int i = p, j = needle.length - 1;
i >= 0 && needle[i] == needle[j]; --i, --j) {
len += 1;
}
return len;
}
Варијанте
[уреди | уреди извор]Бојер-Мур-Хорспул алгоритам је упрошћавање Бојер-Мур алгоритма само користећи правило лошег карактера.
Апостолико-Ђијанкарлов алгоритам убрзава процес проверавања да ли је до подударања дошло код одрешеног поравнања прескачући екплицитне провере карактера. Ово користи информације сакупљене током претпроцесирања узорка у спајању са суфкисом се подудараца са дужином забележеном при сваком покушају подударања. Чување дужина погођених суфикса захтева додатну табелу која је једнака величини текста који се претражује.
Види још
[уреди | уреди извор]- Кнут-Морис-Прат алгоритам
- Апостолико-Ђијанкарлов алгоритам
- Ахо-Коразик алгоритам подударности ниски
- Рабин-Карп алгоритам
- Суфиксно стабло
Референце
[уреди | уреди извор]- ^ Hume and Sunday (1991) [Fast String Searching] SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 21(11), 1221–1248 (NOVEMBER 1991)
- ^ Boyer, Robert S.; Moore, J Strother (октобар 1977). „A Fast String Searching Algorithm.”. Comm. ACM. New York, NY, USA: Association for Computing Machinery. 20 (10): 762—772. ISSN 0001-0782. doi:10.1145/359842.359859.
- ^ а б Gusfield, Dan (1999) [1997], „Chapter 2 - Exact Matching: Classical Comparison-Based Methods”, Algorithms on Strings, Trees, and Sequences (1 изд.), Cambridge University Press, стр. 19—21, ISBN 978-0-521-58519-4
- ^ а б Galil, Z. (септембар 1979). „On improving the worst case running time of the Boyer-Moore string matching algorithm”. Comm. ACM. New York, NY, USA: Association for Computing Machinery. 22 (9): 505—508. ISSN 0001-0782. doi:10.1145/359146.359148.
- ^ Knuth, Donald; Morris, James H.; Pratt, Vaughan (1977). „Fast pattern matching in strings”. SIAM Journal on Computing. 6 (2): 323—350. doi:10.1137/0206024. Архивирано из оригинала 04. 01. 2010. г. Приступљено 30. 05. 2013.
- ^ Guibas, Odlyzko; Odlyzko, Andrew (1977). „A new proof of the linearity of the Boyer-Moore string searching algorithm”. Proceedings of the 18th Annual Symposium on Foundations of Computer Science. Washington, DC, USA: IEEE Computer Society: 189—195. doi:10.1109/SFCS.1977.3.
- ^ а б Cole, Richard (септембар 1991). „Tight bounds on the complexity of the Boyer-Moore string matching algorithm”. Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics: 224—233. ISBN 978-0-89791-376-8.
Спољашње везе
[уреди | уреди извор]- Original paper on the Boyer-Moore algorithm
- Пример Бојер-Мур алгоритма са странице J Strother Moore, једног од проналача алгоритма
- Richard Cole's 1991 paper proving runtime linearity