Алгоритм Бойера и Мура

Поиск образа в строке по методу Кнута, Морриса, Пратта дает выигрыш только в том случае, когда несовпадению символов из образа и строки предшествовало некоторое число совпадений. Если при сравнении образа и анализируемой части строки сопоставляемые символы различны, то образ сдвигается только на один символ. Продвижение образа более чем на единицу происходит лишь в том случае, когда происходит совпадение нескольких символов образа и строки. К несчастью, это скорее исключение, чем правило: совпадения встречаются значительно реже, чем несовпадения. Поэтому выигрыш от использования КМП-стратегии в большинстве случаев поиска в обычных текстах весьма незначителен.

В 1975 г. Р. Бойер и Д. Мур предложили метод, который не только улучшает обработку самого плохого случая, но дает выигрыш в промежуточных ситуациях. Скорость в алгоритме Бойера-Мура достигается за счет того, что удается пропускать те части текста, которые заведомо не участвуют в успешном сопоставлении. Данный алгоритм, называемый БМ-поиском, основывается на необычном соображении - сравнение символов начинается с конца образа, а не с начала.

Как и при работе КМП-алгоритма, перед началом поиска образу сопоставляется таблица <7, используемая в дальнейшем при смещении образа по строке. При создании матрицы d используется таблица кодов символов ASCII. Любой печатный или служебный символ имеет свой код. Например, код символа п - 110, g - 103, код пробела - 32. Коды ASCII печатных символов приведены в табл. 2.1. Таблица ASCII содержит 256 символов. Поэтому матрицу d можно объявить как одномерный целочисленный массив, состоящий из 256 элементов: int d[256].

Первоначально всем элементам матрицы d присваивается значение, равное длине образа. Длину образа можно получить, используя функцию int strlen{char *) из библиотеки .

Следующим шагом является присвоение каждому элементу таблицы <7, индекс которого равен коду ASCII, текущего рассматриваемого символа образа, значения равного удаленности текущего символа от конца образа.

Рассмотрим формирование таблицы d на примере образа Hooligan. Поскольку данный образ содержит восемь символов, то его длина равна восьми. Соответственно, на начальном этапе все элементы массива d инициализируются числом 8:

Таблица 2.1

Таблица ASCII. Печатные символы

Код

Символ

Код

Символ

Код

Символ

Код

Символ

Код

Символ

Код

Символ

Код

Символ

32

пробел

55

7

78

N

101

е

124

|

208

Р

231

3

33

?

56

8

79

О

102

f

125

}

209

С

232

и

34

п

57

9

80

Р

103

Я

126

210

Т

233

й

35

#

58

:

81

Q

104

h

211

У

234

к

36

$

59

!

82

R

105

i

168

Ё

212

ф

235

л

37

%

60

<

83

S

106

j

184

ё

213

X

236

м

38

&

61

=

84

т

107

k

214

Ц

237

н

39

1

62

>

85

и

108

1

192

А

215

ч

238

О

40

(

63

9

86

V

109

m

193

Б

216

ш

239

п

41

>

64

87

W

110

n

194

В

217

щ

240

р

42

*

65

А

88

X

111

0

195

Г

218

ъ

241

с

43

+

66

В

89

Y

112

P

196

д

219

ы

242

т

44

1

67

С

90

Z

113

q

197

Е

220

ь

243

У

45

-

68

D

91

1

114

r

198

Ж

221

э

244

ф

46

#

69

Е

92

115

s

199

3

222

ю

245

X

47

/

70

F

93

1

116

t

200

И

223

я

246

ц

48

0

71

G

94

Л

117

u

201

Й

224

а

247

ч

49

1

72

Н

95

118

V

202

К

225

б

248

II]

50

2

73

I

96

'

119

w

203

л

226

в

251

ы

51

3

74

J

97

а

120

X

204

М

227

г

252

ь

52

4

75

К

98

b

121

У

205

Н

228

д

253

э

53

5

76

L

99

с

122

z

206

О

229

е

254

ю

54

6

77

М

100

d

123

207

п

230

ж

255

я

Далее происходит присваивание элементам массива d соответствующих значений, равных расстоянию от рассматриваемого символа до конца образа. При этом индекс элемента массива d, который получает новое значение, определяется кодом ASCII рассматриваемого символа. Так, код ASCII последнего символа образа Hooligan - п - равен 110. Поскольку данный символ является последним, то удаленность от конца образа равна нулю. Таким образом:

также на языке программирования Си можно записать:

Код ASCII предпоследнего символа образа Hooligan - а - равен 97. Удаленность данного символа от конца образа равна 1 и следовательно:

или

Аналогичным образом изменяются значения элементов таблицы <7, соответствующие символам образа g, /, /, о:

В том случае, когда образ содержит несколько одинаковых символов, элементу таблицы d, соответствующему данному символу, присваивается значение, равное удаленности от конца образа самого правого из одинаковых символов. Так, образ Hooligan содержит два символа о, удаленность от конца образа первого из них равно шести, удаленность второго - пять. В этом случае будет равно пяти.

В рассматриваемом примере присваивание значений элементам массива d происходит при продвижении по образу справа налево. Таким образом, легко определить, был ли уже рассмотрен тот или иной символ, выполнив проверку на содержимое соответствующего элемента массива d: если элемент содержит значение, равное длине образа, значит данный символ еще не рассматривался. Поэтому, когда будет рассматриваться второй символ образа Hooligan, символ о, удаленность которого от конца образа равна шести, проверка содержимого соответствующего элемента массива d покажет, что d[‘o' не равно длине образа - 8, что свидетельствует о том, что символ о уже встречался, и ] изменяться не должно.

Следует отметить также, что элементу массива <7, соответствующего символу //, должно быть присвоено значение семь, т. е. фактическая удаленность символа Н от конца образа:

На рис. 2.8 показан образ и значения элементов массива d, соответствующие символам данного образа.

Вторым этапом работы алгоритма БМ-поиска после построения таблицы d является собственно сам поиск образа в строке. При сравнении образа со строкой образ продвигается по строке слева направо, однако посимвольные сравнения образа и строки выполняются справа налево.

Сравнение образа со строкой происходит до тех пор, пока: 1) не будет рассмотрен весь образ, что говорит о том, что соответствие между образом и некоторой частью строки найдено; 2) не закончится строка, что значит, что вхождений, соответствующих образу в строке нет; 3) не произойдет несовпадения символов образа и строки, что вызывает сдвиг образа на несколько символов вправо и продолжение процесса поиска.

Образ и значения элементов массива d, соответствующие символам образа

Рис. 2.8. Образ и значения элементов массива d, соответствующие символам образа

В том случае, если произошло несовпадение символов, смещение образа по строке определяется значением элемента таблицы d, причем индексом данного элемента является код ASCII символа строки. Подчеркнем, что, несмотря на то, что массив d формируется на основе образа, при смещении индексом служит символ из строки. На рис. 2.9 показан пример работы алгоритма БМ-поиска, сравниваемые символы подчеркнуты.

Поиск образа в строке по методу Бойера и Мура

Рис. 2.9. Поиск образа в строке по методу Бойера и Мура

На первой итерации произошло несовпадение символа образа п и символа строки о. Значение элемента (i[4o’] равно пяти. Поэтому образ смещается вправо на пять символов. Если бы произошло совпадение этих двух символов, то далее рассматривался бы предпоследний символ образа и соответствующий ему символ строки и т. д.

При очередном сравнивании образа и строки происходит несовпадение символов п и g. Опять же, используя в качестве индекса элемента массива d код ASCII символа строки g, получаем значение два: d[‘g’] = 2. Образ сдвигается на два символа вправо. Таким образом, образ постепенно сдвигается по строке до тех пор, пока образ в строке не будет найден или не кончится строка.

Эффективность БМ-алгоритма. Замечательным свойством БМ-поиска является то, что почти всегда, кроме специально построенных примеров, он требует значительно меньше N сравнений. В самых же благоприятных обстоятельствах, когда последний символ образа всегда попадает на несовпадающий символ строки, число сравнений равно N / М.

Задания

  • 1. Написать программу поиска образа в строке по методу Кнута, Морриса и Пратта. Предусмотреть возможность существования в образе пробела. Ввести опцию чувствительности / нечувствительности к регистру.
  • 2. Написать программу поиска образа в строке по методу Бойера и Мура. Предусмотреть возможность существования в образе пробела. Ввести опцию чувствительности / нечувствительности к регистру.
  • 3. Ниже приведен листинг программы, формирующей таблицу d по КМП-алгоритму. При каком образе таблица d будет сформирована неверно? При какой строке и каком образе положительный результат не будет получен?

  • 4. Реализовать в программе алгоритм прямого поиска строки и КМП- алгоритм. Сравнить эффективность поиска образа в строке обоими алгоритмами по количеству итераций.
  • 5. Реализовать в программе алгоритм прямого поиска строки и БМ-алгоритм. Сравнить эффективность поиска образа в строке обоими алгоритмами по количеству итераций.
  • 6. Разработать и программно реализовать усовершенствованный алгоритм, объединяющий БМ-алгоритм с КМП-алгоритмом, который при сдвиге образа использует две таблицы, полученные согласно данным алгоритмам.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >