Коллекция алгоритмов

Алгоритм Бойера-Мура
    В отличие от других алгоритмов сравнения строк ("Стандартный алгоритм сравнения строк", "Алгоритм Кнута-Морриса-Пратта") алгоритм Бойера-Мура осуществляет сравнение с образцом справа налево, а не слева направо. Исследуя искомый образец, можно осуществить более эффективные прыжки в тексте при обнаружении несовпадения.
    В примере ниже мы сначала сравниваем y с r и обнаруживаем несовпадение. Поскольку мы знаем, что буква r вообще не входит в образец, мы можем сдвинуться в тексте на целых четыре буквы (то есть на длину образца) вправо. Затем мы сравниваем букву y с h и вновь обнаруживаем несовпадение. Однако поскольку на этот раз h входит в образец, мы можем сдвинуться вправо только на две буквы так, чтобы буквы h совпали. Затем мы начинаем сравнение справа и обнаруживаем полное совпадение кусочка текста с образцом. В алгоритме Бойера-Мура делается 6 сравнений вместо 13 сравнений в стандартном алгоритме.

Пример 1. Поиск образца they в тексте there they are (совпадение находится после 6 сравнений символов)
Текст:
t
h
e
r
e
t
h
e
y
a
r
e
Проход 1:
t
h
e
y
Текст:
t
h
e
r
e
t
h
e
y
a
r
e
Проход 2:
     
t
h
e
y
Текст:
t
h
e
r
e
t
h
e
y
a
r
e
Проход 3:
t
h
e
y

    Подобное улучшение порождает одну проблему. При сравнении на в примере ниже происходит совпадение по буквам k, n, i, однако буква h в слове tinkle не совпадает с буквой t в слове think. Если мы ограничимся предложенным улучшением, то придется сдвинуться вправо по тексту всего на один символ, несмотря на то, что совпадение подстрок ink означает, что мы немедленно после сдвига наткнемся на несовпадение, и это несовпадение можно предугадать.

Пример 2. Проблема со сдвигом
Текст:
t
h
e
t
i
n
k
l
e
o
f
a
b
e
l
l
Образец:
t
h
i
n
k
Текст:
t
h
e
t
i
n
k
l
e
o
f
a
b
e
l
l
Образец:
t
h
i
n
k

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

Алгоритм сравнения
    Мы дали общее описание того, как будут использоваться массивы сдвигов и прыжков. Массив сдвигов содержит величины, на которые может быть сдвинут образец при несовпадении очередного символа. В массиве прыжков содержатся величины, на которые можно сдвинуть образец, чтобы совместить ранее совпавшие символы с вновь совпадающими символами строки. При несовпадении очередного символа образца с очередным символом текста может осуществиться несколько возможностей. Сдвиг в массиве сдвигов может превышать сдвиг в массиве прыжков, а может быть и наоборот. (Совпадение этих величин - простейшая возможная ситуация.) О чем говорят эти возможности? Если элемент массива сдвигов больше, то это означает, что несовпадающий символ оказывается "ближе" к началу, чем повторно появляющиеся завершающие символы строки. Если элемент массива прыжков больше, то повторное появление завершающих символов строки начинается ближе к началу образца, чем несовпадающий символ. В обоих случаях нам следует пользоваться большим из двух сдвигов, поскольку меньший сдвиг неизбежно опять приводит к несовпадению из-за того, что мы знаем о втором значении. Так, например, если значение сдвига равно 2, а значение прыжка 4, то сдвиг на два символа не позволит найти соответствие образцу: несовпадающий символ все равно окажется невыровненным. Однако, если сдвинуть на четыре символа, то под ранее несовпадающим символом окажется подходящий символ образца, и при этом сохраняется возможность того, что завершающие символы образца будут совпадать с новыми соответствующими символами текста.
    Поскольку речь идет только о большем из двух значений, алгоритм имеет следующий вид: 
textLoc = length(pattern)
patternLoc = length(pattern)
while (textLoc <= length(text)) and (patternLoc> 0) do
	if text[textLoc] = pattern[patternLoc] then
		textLoc = textLoc - 1
		patternLoc = patternLoc - 1
	else
		textLoc = textLoc + MAX(slide[text[textLoc]], jump[patternLoc])
		patternLoc = length(pattern)
	end if
end while

if patternLoc = 0 then
	return textLoc + 1	// совпадение найдено	
else
	return 0
end if

Массив сдвигов
    Обратимся теперь к массиву сдвигов. В примере ниже мы начинаем сравнение при textLoc = 6 и patternLoc = 6. Поскольку проверяемые символы совпадают, значения обеих переменных textLoc и patternLoc уменьшаются; следующие два символа тоже совпадают, поэтому уменьшение происходит еще один раз, и значения обеих переменных будут равны 4. В следующем символе происходит несовпадение.

Пример 3 (а). Выбор величины сдвига из массива сдвига
 
.
t
e
x
t
L
o
c
Текст:
b
a
a
b
a
c
a
c
b
a
c
b
Образец:
a
b
a
c
a
c
 
.
p
a
t
t
e
r
n
L
o
c

    Мы хотим сдвинуть образец таким образом, чтобы очередной символ b в тексте совпал с символом b образца, как показано в примере ниже. Затем мы заново начинаем процесс сравнения с правого конца образца. Для этого переменной patternLoc следует вновь присвоить значение длины образца, а переменную textLoc следует увеличить на 4 - действительную величину сдвига образца.

Пример 3 (б). Выбор величины сдвига из массива сдвига
                .   t e x t L o c      
Текст: b a a b a c a c b a c b              
Образец:     a b a c a c                      
                .   p a t t e r n L o c

    Для реализации этих действий определим увеличение переменной textLoc при несовпадении очередных символов. Воспользуемся массивом slide длины, равной числу символов, которые могут появиться в тексте. Начальные значения всех сдвигов полагаем равными длине образца, поскольку обнаружение в тексте символа, отсутствующего в образце, должно привести к сдвигу указателя в тексте на всю длину образца. Затем происходит замена значения для всех символов образца. Если символ появляется в образце неоднократно, то величина сдвига должна быть такой, чтобы совместить с символом в тексте последнее вхождение символа в образце. Совмещение с предыдущими вхождениями будет осуществляться с помощью прыжков, которые мы обсудим ниже. Вот как вычисляются значения сдвига: 
for каждого символа ch в алфавите do
	slide[ch] = length(pattern)
end for

for i = 1 to length(pattern) do
	slide[pattern[i]] = length(pattern) - i
end for
    Выполнив этот алгоритм на образце datadata, Вы получите slide[d] = 3, slide[a] = 0 и slide[t] = 1; для всех остальных букв алфавита значение сдвига будет равно 8.

Массив прыжков
    Массив jump, размер которого совпадает с длиной образца, описывает взаимоотношение частей образца. Этот массив позволяет, например, при несовпадении символа h образца с символом t текста в примере 2 сдвинуть образец целиком за сравниваемый символ. Этот новый массив также отслеживает повторение символов в конце образца, которые могут заменять сравниваемые символы. Пусть, например, образец имеет вид abcdbc, и в процессе сравнения два последних символа образца совпали с символами текста, а в третьем символе обнаружилось расхождение. Тогда массив jump говори, насколько следует сдвинуть образец, чтобы символы bc в позициях 5 и 6 совпали с символами bc в позициях 2 и 2. Таким образом, массив jump содержит информацию о наименьшем возможном сдвиге образца, который совмещает уже совпавшие символы с их следующим появлением в образце.
    Предположим, что мы имеем дело с образцом, в котором несовпадение очередного символа означает, что образец следует сдвинуть целиком за место начало сравнения. В примере 4 изображены отрезок текста и образец. Символы X в образце могут быть произвольными; они призваны проиллюстрировать процедуру.

Пример 4. Определение величины прыжка
Текст: a b c d e f g h i j k l m n
Образец: X X X X X                  

    Если образец нужно сдвинуть целиком на всю длину, то символы X должны соотнестись с символами от f до j, то есть новое значение переменной textLocбудет равно 10. Если несовпадение произошло на символе e, когда textLoc = 5, то для сдвига образца нужно к textLoc прибавить 5.
    Если же несовпадение произошло на символе d, то есть при textLoc = 4, то для сдвига нужно увеличить textLoc на 6. При несовпадении на символах c, b или a увеличение составит соответственно 7, 8 или 9. В общем случае при несовпадении последнего символа увеличение составляет длину образца, а при несовпадении первого символа - удвоенную длину без единицы. Эти соображения и служат основой для инициализации массива jump.
    Посмотрим теперь на образец, в котором некоторые наборы символов с конца образца повторяются. мы хотим узнать, насколько следует увеличивать указатель textLoc для правильного сдвига образца (не принимая во внимание возможностей, обеспечиваемых массивом slide). Представим для этого, что мы сравниваем образец сам с собой. Рассмотрим вновь образец abcdbc. Если последний символ в нем не совпадает с соответствующим символом текста, мы можем просто увеличить переменную textLoc на единицу и начать проверку заново. Если последний символ совпал, а следующий с конца нет, то можно сдвинуться на всю длину образца, поскольку каждому вхождению символа b в образец предшествует вхождение символа c. Если же совпали последние два символа, а третий с конца не совпал, то переменную textLoc можно увеличить на 5, чтобы совместить символы bc, совпавшие с последними двумя буквами образца, со вторым и третьим символами образца.
    Следующий алгоритм вычисляет элементы массива jump. Первый цикл инициализирует массив jump. Второй цикл изменяет элементы массива в зависимости от повторений последних символов. Третий и четвертый циклы исправляют максимальные значения сдвигов в начале (соответственно, в конце) массива jump в зависимости от найденных совпадений подстрок образца. 
// установить максимально возможные значения прыжка
for i = 1 to length(pattern) do
	jump[i] = 2*length(pattern) - i
end for

// сравнение окончания образца с предыдущими его символами
test = length(pattern)
target = length(pattern) + 1
while test > 0 do
	link[test] = target
	while target <= length(pattern) and pattern[test] /= pattern[target] do
		jump[target] = MIN(jump[target], length(pattern) - test)
		target = link[target]
	end while
	test = test  1
	target = target - 1
end while
for i = 1 to target do
	jump[i] = MIN(jump[i], length(pattern) + target - i)
end for

temp = link[target]
while target <= length(pattern) do
	while target <= temp do
		jump[target] = MIN(jump[target], temp - target + length(pattern))
		target = target + 1
	end while
	temp = link[temp]
end while
    В таблице ниже приведены состояния массивов jump и link после завершения каждого цикла алгоритма на образце datadata.

Первый цикл
jump 15 14 13 12 11 10 9 8
Второй цикл
link 5 6 7 8 7 8 8 9
jump 15 14 13 12 11 10 3 1
Третий цикл
jump 11 10 9 8 11 10 3 1
Четвертый цикл
jump 11 10 9 8 11 10 3 1


Рейтинг@Mail.ru Rambler's Top100
Сайт управляется системой uCoz