Прежде, чем приступить к рассмотрению алгоритма Бойера-Мура, приведем простейший алгоритм поиска, называемый «методом грубой силы».

function Find(const S, P : String) : Integer;
var  i, j : Integer;
begin  
Result := 0;
if Length(P) > Length(S) then Exit;
for i := 1 to Length(S) - Length(P) + 1 do
  for j := 1 to Length(P) do
    if P[j] <> S[i+j-1] then Break      
     else if j = Length(P) then      begin        Result := i;
      Exit;
    end;
end;

Функция Find ищет подстроку P в строке S и возвращает индекс первого символа подстроки или 0, если подстрока не найдена. Хотя в общем случае этот метод, как и большинство методов грубой силы, малоэффективен, в некоторых ситуациях он вполне приемлем. Мы сами воспользуемся похожим алгоритмом при построении таблицы смещений для метода Бойера-Мура.

Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Прежде чем рассмотреть работу этого алгоритма, уточним некоторые термины. Под строкой мы будем понимать всю последовательность символов текста. Собственно говоря, речь не обязательно должна идти именно о тексте. В общем случае строка – это любая последовательность байтов. Поиск подстроки в строке осуществляется по заданному образцу, т. е. некоторой последовательности байтов, длина которой не превышает длину строки. Наша задача заключается в том, чтобы определить, содержит ли строка заданный образец.

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

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

Величина смещения для каждого символа образца зависит только от порядка символов в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца. Поясним все вышесказанное на простом примере. Пусть у нас есть набор символов из пяти символов: a, b, c, d, e и мы хотим найти вхождение образца “abbad” в строке “abeccacbadbabbad”.

Искомый шаблон — «abbad»

 abeccacbadbabbad
 abbad

Накладываем образец на строку. Последний символ исходной строки «с» не содержится в образце. Сдвигаем образец вправо на 5 позиций в соответствии со значением смещения для «с»:

 abeccacbadbabbad
      abbad

Три символа образца совпали, а четвертый — нет. Сдвигаем образец вправо на величину последнего сравниваемого символа исходной строки «c», т. е. 5:

 abeccacbadbabbad
           abbad

Последний символ исходной строки «a» снова не совпадает с символом шаблона. Cдвигаем образец на 1 позицию и получаем искомое вхождение образца:

 abeccacbadbabbad
            abbad

Google использует алгоритм израильского студента Ори Алона (Ori Alon) под названием Орион (Orion). В Google идею Orion реализовали в виде вариантов уточнения поисковых запросов. Пользователю предлагается ряд других поисковых запросов, которые тематически близки к тому, что он искал (например, по запросу [Французская революция] предлагаются [Робеспьер], [Наполеон], [Американская революция] и т.д.). Эти варианты обычно располагаются внизу поисковой страницы. Судя по всему, системе всё равно, на каком языке осуществлялся запрос, Orion отлично работает и на русском, и ещё на 36 языках.

Алгоритм Orion способен осуществлять «экспертный» поиск и находить тематически близкие страницы, даже если они не содержат текста поискового запроса.

Сообщается, что алгоритм Orion оптимизирует поиск за счет отображения только наиболее релевантных результатов, то есть страниц, содержащих информацию, наиболее точно подходящую под параметры запроса. Плюс ко всему, Orion будет принимать во внимание такой фактор, как качество индексируемых сайтов. Помимо этого, в новый алгоритм включена такая функция как отображение ключевых слов по теме запроса. Разработчик Orion привел пример поиска сайтов по запросу «Война за независимость».

При поиске в Google благодаря новому алгоритму поисковик, помимо наиболее релевантных страниц, выдаст список ключевых фигур и событий войны среди которых Бен Гурион или Пальмах. Стоит отметить, что война за независимость была и в США, однако в своем примере Алон не упомянул ни одну из фигур североамериканского военного конфликта.

Еще немного хотелось бы рассказать про PageRank от гугла, ведь он тоже используется при опеределении порядка вывода страниц в поиске.

PR (PageRank). Что такое, как рассчитывается и как увеличить этот «Гугл ПР» читайте ниже в заметке. Там же есть и специальная наглядная таблица как поисковая машина Google вычисляет и апдейтит этот показатель.

Google PR - показатель, который позволяющий получить информацию о весе (значимости) страницы в поисковой системе Google, и в некоторых других поисковых системах. Например , Яндекс ТИЦ не показывает вес (значимость) конкретной страницы, а только о вес всего сайта. Показатель, PR нужен Google - для оценки веса каждой страницы, на которой размещены объявления системы. Кому интересно как Google высчитывает PR (PageRank) прикрепляю ниже наглядную таблицу.

Google PR рассчитывается поисковой системой Google в реальном времени и состоит из большей, чем 10, шкалы. Гугл делает апдейт PR ежедневно, но обычно раз в 3 месяца апдейтит и «тулбарный» ПиАр и округляет PR до единиц. Это сделано для уменьшения нагрузки на сервера Google. Со времени обновления тулбарного PR, реальный PR, исходя из которого Гугл учитывает вес страницы, может изменяться, как в большую так и в меньшую сторону.

А как увеличить Google PR ?

Увеличить Google PR просто и не просто :) Нужно, просто больше ссылок на ваш сайт (блог) с других сайтов. Чем более PR -истый сайт тем больше веса(значимости) он передаёт вашему сайту.

 1. Пример № 1: чтобы получить PR 6, нужно хотя бы 3 ссылки с PR7 или 18 ссылок с PR6.
 2. Пример № 2: чтобы получить PR 4, нужно чтобы на вас было 18 ссылок с сайта с PR 4 или 3 ссылки с сайта с PR 5.
 3. Пример № 3: если на вас будет 101 ссылка с сайта с PR 2 или 555 ссылок с сайта с PR 1, ваш сайт получит троечку.
 Вы все можете найти в таблице, удачи.  

Алгоритм Кнута — Морриса — Пратта

Google

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

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

PageRank

algotitmy.ppt

В презентации вы можете посмотреть дерево целей, логотип и мои выводы по поводу проделанной работы.

Проект выполнял Боровский Виталий 11а