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

Сравнение строк. Стандартный алгоритм.
    Наша задача состоит в том, чтобы найти первое вхождение некоторой подстроки в длинном тексте. Поиск последующих вхождений основан на том же подходе. Это сложная задача, поскольку совпадать должна вся строка целиком. Стандартный алгоритм начинает со сравнения первого символа текста с первым символом подстроки. Если они совпадают, то происходит переход ко второму символу текста и подстроки. При совпадении выравниваются следующие символы. Так продолжается до тех пор, пока не окажется, что подстрока целиком совпала с отрезком текста, или пока не встретятся несовпадающие символы. В первом случае задача решена, во втором мы сдвигаем указатель текущего положения в тексте на один символ и заново начинаем сравнение с подстрокой. Этот процесс изображен ниже.

    Здесь поиск образца they в тексте there they are. При первом проходе три первых символа подстроки совпадают с символами текста. Однако только седьмой проход дает полное совпадение (Совпадение находится после 13 сравнений символов).
Текст:
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
Текст:
t
h
e
r
e
t
h
e
y
a
r
e
Проход 4:
t
h
e
y
Текст:
t
h
e
r
e
t
h
e
y
a
r
e
Проход 5:
t
h
e
y
Текст:
t
h
e
r
e
t
h
e
y
a
r
e
Проход 6:
t
h
e
y
Текст:
t
h
e
r
e
t
h
e
y
a
r
e
Проход 7:
t
h
e
y

    Следующий алгоритм осуществляет стандартное сравнение строк: 
subLoc = 1 	// указатель текущего сравниваемого символа в подстроке
textLoc = 1		// указатель текущего сравниваемого символа в тексте
textStart = 1	// указатель на начало сравнения в тексте

while TextLoc <= length(text) and subLoc <= length(substring) do
	if text[textLoc] = substring[subLoc] then
		textLoc = textLoc + 1
		subLoc = subLoc + 1
	else
		// начать сравнение заново со следующего символа
		textStart = textStart + 1
		textLoc = textLoc + 1
		subLoc = subLoc + 1
	end if
end while

if (subLoc > length(substring)) then
	return textStart 	// совпадение найдено
else
	return 0		// совпадение не найдено
end if
    Из алгоритма ясно, что основная операция - сравнение символов, и именно число сравнений и следует подсчитывать. В наихудшем случае при каждом проходе совпадают все символы за исключением последнего. Сколько раз это может произойти? По одному разу на каждый символ текста. Если длина подстроки равна S, а длина текста равна T, то, похоже, в наихудшем случае число сравнений будет равно S(T - S + 1). Посмотрим теперь, возможна ли в принципе такая ситуация. Будем искать подстроку XX...XXY, состоящую из S - 1 буквы X и одной буквы Y, в тексте XX...XXXXX, состоящем из T букв X. Такой набор символов и дает искомое наихудшее поведение. Следует отметить, что в естественных языках таких слов обычно не бывает, поэтому можно ожидать, что производительность приведенного алгоритма на текстах естественного языка оказывается намного выше. Как показывают исследования, на текстах естественного языка сложность приведенного алгоритма оказывается немногим больше T.
    Проблема стандартного алгоритма заключается в том, что он затрачивает много усилий впустую. Если сравнение начала подстроки уже произведено, то полученную информацию можно использовать для того, чтобы определить начало следующего сравниваемого отрезка текста. Например, при первом проходе в примере выше расхождение с образцом осуществляется на четвертом символе, а в первых трех символах произошло совпадение. При взгляде на образец видно, что третий символ встречается в нем лишь однажды, поэтому первые три символа текста можно пропустить и начать следующее сравнение с четвертого, а не со второго символа текста. Существуют различные способы использования этой возможности, например: алгоритм Кнута-Морриса-Пратта, алгоритм Бойера-Мура.
Рейтинг@Mail.ru Rambler's Top100
Сайт управляется системой uCoz