По умолчанию найденные документы сортируются по релевантности (соответствию запросу). Однако Вы можете потребовать, чтобы вместо этого в начало списка были помещены самые свежие (или, наоборот, самые старые документы). Для этого надо выбрать соответствующую установку в меню «Сортировать по...» на странице детального запроса.
Вы можете также ограничить поиск документами, созданными в определенный период времени: для этого необходимо на странице детального запроса указать «От даты ... до даты ...».
Можно потребовать, чтобы Rambler возвращал только те документы, где слова из запроса находятся на минимальном расстоянии друг от друга.
Режим «Ограничить расстояние между словами» может быть включен в детальном запросе. Все перечисленные выше правила могут быть использованы совместно друг с другом в необходимой Вам последовательности.
По умолчанию результаты поиска выдаются порциями по 15 документов. Меню «Выдавать по...» на странице детального запроса позволяет увеличить это число до 30 или 50. Меню «Форма вывода...» позволяет получать описания документов с увеличенной или уменьшенной подробностью.
Yandex. Yandex ежедневно просматривает сотни тысяч Web-страниц в поисках изменений или новых ссылок. Коллекция ссылок постоянно растет.
Yandex не требует от вас знания специальных команд для поиска. Достаточно набрать вопрос («где найти дешевые компьютеры» или «нужны телефоны москвы и московской области»), и вы получите результат - список страниц, где встречаются эти слова.
Независимо от того, в какой форме вы употребили слово в запросе, поиск учитывает все его формы по правилам русского языка. Например, если задан запрос «идти», то в результате поиска будут найдены ссылки на документы, содержащие слова «идти», «идет», «шел», «шла» и т.д. На запрос «окно» будет выдана информация, содержащая и слово «окон», а на запрос «отзывали» - документы, содержащие слово «отозвали».
При этом поиск не ограничен лишь словами или фразами. Yandex отыщет по названию Web-страницу компании или файл с нужной картинкой.
Aport. Обычно запрос представляет из себя просто одно или несколько слов.
По такому запросу находятся документы, в которых встречаются все слова запроса. Есть, правда, ограниченное число слов (союзы, предлоги и т.п.), которые в запросе игнорируются, так как не несут сами по себе смысловой нагрузки.
Например, по запросу: яблоки на снегу будут найдены все документы, в которых встречаются одновременно два слова: «яблоко» и «снег». Где в пределах документа расположены слова, в какой грамматической форме они находятся — не важно.
Стоит еще раз подчеркнуть важное и очень полезное свойство Апорта: независимо от того, в какой грамматической форме вы пишите в запросе слово, оно находится в документах во всех своих формах. Например, по запросу: человек шел будут найдены среди прочих и документы, содержащие текст «люди идут». Распознавание всех форм работает для обычных слов русского языка. Для экзотических слов, неологизмов и т.п. оно не проходит. В этом случае может пригодиться оператор «*».
Например, вы хотите найти все, касающееся деятельности президента России, в том числе и документы, содержащие слово «ельцинизм». Воспользуйтесь запросом: ельцин*. Он позволит вам найти то, что вы хотите (а также документы со словами Ельцинище, ельцинцы, ельциненок и т.п), поскольку звездочка заменяет собой любое число любых букв.
Вы можете искать документы не только по всему русскоязычному INTERNET, но и по его части. Самый простой случай — поиск по определенному серверу. Например: url=www.intel.ru собака
По данному запросу будут найдены все документы на сервере www.intel.ru, содержащие слово "собака". Возможно, вам интересно, а что будет, если написать просто: url=www.intel.ru
В этом случае вы получите список всех документов, расположенных на указанном вами сервере
Вы можете ограничивать поиск и сильнее — одним из каталогов сервера. Например: url=www.intel.ru/sobaki/сенбернар
По данному запросу документы, содержащие слово «сенбернар», будут искаться только в каталоге /sobaki (и его подкаталогах) московского сервера корпорации Intel.
List. На главной странице в верхней ее части расположены ссылки на наиболее популярные проекты. Ниже, под логотипом каталога, поисковая форма. В правой колонке и нижней части страницы - блоки самых актуальных новостей. Список ссылок на основные категории каталога занимает центральную часть. Цифры рядом с названием категории показывают количество сайтов, содержащихся в ней. Записанные мелким шрифтом заголовки отсылают при нажатиии на подкатегории раздела.
Щелкнув по любому из названий, Вы попадете в соответствующую рубрику и под логотипом List.ru увидите полный путь до нее, начиная с главной страницы. Каждый промежуточный уровень структуры доступен по отдельной ссылке. Поиск в каталоге реализован таким образом, что в результате запроса могут быть найдены как отдельные сайты, так и рубрики.
Допускается использованием языка запросов Yandex. Расположенная рядом с поисковой формой ссылка «Структура каталога» открывает в отдельном окне полный рубрикатор каталога. Реализована возможность перехода из рубрикатора в любую выбранную подкатегорию. Более детальное тематическое деление текущей рубрики представлено списком ссылок.
Помеченные символом “@” приведут в подкатегории, структурно входящие в другие разделы, но содержащие близкую по содержанию информацию. Если Вы хорошо представляете, в какой рубрике содержатся нужные ресурсы, лучше перейти в нужную подкатегорию, воспользовавшись любым из предоставляемых средств навигации по каталогу. В противном случае можно искать их в полном списке.
Каталог организован таким образом, что все сайты, содержащиеся на нижних уровнях структуры, представлены и в рубриках. Показываемый ниже список ресурсов упорядочен в алфавитном порядке, но, выбрав соответствующую сортировку («По времени добавления» или «По переходам»), можно просмотреть их по порядку добавления в каталог (начиная с самых «свежих») или в зависимости от популярности среди посетителей каталога. Ссылка с названия сайта открывает в отдельном окне его зарегистрированную в данной рубрике страницу. Пометки RUS и ENG означают наличие на сайте страниц, соответственно на русском и английском языках.
3. Алгоритмы поиска.
3.3.1 Алгоритм Кнута-Морриса-Пратта
Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово
X=x[1]x[2]... x[n]
и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1]... l[n], где
l[i]=длина слова l(x[1]...х[i])
(функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x[1]...x[i], одновременно являющегося его концом.
Какое отношение все это имеет к поиску подслова?
Другими словами, как использовать алгоритм КМП для определения того, является ли слово A подсловом слова B?
Решение. Применим алгоритм КМП к слову A#B, где # - специальная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A.
Описать алгоритм заполнения таблицы l[1]...l[n].
Решение. Предположим, что первые i значений l[1]...l[i] уже найдены. Мы читаем очередную букву слова (т.е. x[i+1]) и должны вычислить l[i+1].
Другими словами, нас интересуют начала Z слова
x[1]...x[i+1,
одновременно являющиеся его концами -из них нам надо брать самое длинное. Откуда берутся эти начала? Каждое из них (не считая пустого) получается из некоторого слова Z' приписыванием буквы x[i+1] . Слово Z' является началом и
концом слова x[1]...x[i]. Однако не любое слово, являющееся началом и концом слова x[1]...x[i], годится - надо, чтобы за ним следовала буква x[i+1].
Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова x[1]...x[i], являющиеся одновременно его концами. Из них выберем подходящие - те, за которыми идет буква x[i+1]. Из подходящих выберем самое длинное. Приписав в его конец х[i+1], получим искомое слово Z. Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции l из предыдущего раздела.
Вот что получается:
i:=1; 1[1]:=0;
{таблица l[1]..l[i] заполнена правильно}
while i <> n do begin
len:= l[i]
{len - длина начала слова x[1]..x[i], которое является
его концом; все более длинные начала оказались
неподходящими}
while (x[len+1]<>х[i+1]) and (len>0) do begin
{начало не подходит, применяем к нему функцию l}
len:=l[len];
end;
{нашли подходящее или убедились в отсутствии}
if x[len+1]=x[i+1] do begin
{х[1]..x[len] - самое длинное подходящее начало}
l[i+1]:=len+1;
end else begin
{подходящих нет}
l[i+1]:= 0;
i:=i+1;
Доказать, что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C.
Решение. Это не вполне очевидно: обработка каждой очередной буквы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней мере на 1, и в этом случае l[i+1] окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу величина l[i] может возрасти не более чем на 1, так что часто и сильно убывать она не может - иначе убывание не будет скомпенсировано возрастанием.
Более точно, можно записать неравенство
l[i+1]<l [i] - (число итераций на i-м шаге)+1
или
(число итераций на i-м шаге)<= l[i]-l[i+1]+1
Остается сложить эти неравенства по всем i и получить оценку
сверху для общего числа итераций.
Будем использовать этот алгоритм, чтобы выяснить, является ли слово X длины n подсловом слова Y длины m. (Как это делать с помощью специального разделителя #, описано выше.) При этом число действий будет не более C(n+m}, и используемая память тоже. Придумать, как обойтись памятью не более Cn (что может быть существенно меньше, если искомый образец короткий, а слово, в котором его ищут - длинное).
Решение. Применяем алгоритм КМП к слову А#В. При этом: вычисление значений l[1],...,l [n] проводим для слова X длины n и запоминаем эти значения. Дальше мы помним только значение l[i] для текущего i - кроме него и кроме таблицы
l[1]...l[n], нам для вычислений ничего не нужно.
На практике слова X и Y могут не находиться подряд, поэтому просмотр слова X и затем слова Y удобно оформить в виде разных циклов. Это избавляет также от хлопот с разделителем.
Написать соответствующий алгоритм (проверяющий, является ли слово X=x[1]...x[n] подсловом слова Y=y[1]...y[m]
Решение. Сначала вычисляем таблицу l[1]...l[n]как раньше. Затем пишем такую программу:
j:=0; len:=0;
{len - длина максимального качала слова X, одновременно
являющегося концом слова y[1]..j[j]}
while (len<>n) and (j<>m) do begin
while (x[len+1]<>у[j+1]) and (len>0) do begin
len: = l[len];
if x[len+1]=y[j+1] do begin
{x[1]..x[len] - самое длинное подходящее начало}
len:=len+1;
len:=0;
j:=j+1;
{если len=n, слово X встретилось; иначе мы дошли до конца
слова Y, так и не встретив X}
3.3.2 Алгоритм Бойера-Мура
Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвертую букву слова: если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. (В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы.)
Мы приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть x[1]...х[n] - образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором х[k]=s. Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам будет удобно положить pos[s]=0 (мы увидим дальше, почему).
Как заполнить массив pos?
Решение.
положить все pos[s] равными 0
for i:=1 to n do begin
pos[x[i]]:=i;
В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале last=n (длина образца), затем last постепенно увеличивается.
last:=n;
{все предыдущие положения образца уже проверены}
while last<= m do begin {слово не кончилось}
if x[m]<>y[last] then begin {последние буквы разные}
last:=last+(n-pos[y[last]]);
{n - pos[y[last]] - это минимальный сдвиг образца,
при котором напротив y[last] встанет такая же
буква в образце. Если такой буквы нет вообще,
то сдвигаем на всю длину образца}
если нынешнее положение подходит, т.е. если
x[i]..х[n]=y[last-n+1]..y[last],
то сообщить о совпадении;
last:=last+1;
Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s],
т.е. число букв в образце справа от последнего вхождения буквы Возможны разные модификации этого алгоритма. Например, можно строку
last:=last+i
заменить на
last:=last+(n-u),
где u - координата второго справа вхождения буквы x[n] в образец.
Как проще всего учесть это в программе
Решение. При построении таблицы pos написать
for i:=1 to n-1 do...
(далее как раньше), а в основной программе вместо
last:=last+1
написать
last:=last+n-pos[y[last]];
Приведенный упрощенный вариант алгоритма Бойера-Мура в некоторых случаях требует существенно больше n действий (число действий порядка mn), проигрывая алгоритму Кнута-Морриса-Пратта.
Пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это установить.
Решение. Пусть образец имеет вид baaa... aa, а само слово состоит только из букв а. Тогда на каждом шаге несоответствие выясняется лишь в последний момент.
Настоящий (не упрощенный) алгоритм Бойера-Мура гарантирует, что число действий не превосходит C(m+n) в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z (являющийся концом образца) совпал, а затем обнаружилось различие: перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о
входном слове? В нем обнаружен фрагмент, равный Z, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, все это (вычисление таблицы сдвигов и ее использование) можно уложить в C(m+ n) действий.
3.3.3 Алгоритм Рабина
Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным
образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах длины n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам.
В чем выигрыш при таком подходе. Казалось бы, ничего - ведь чтобы вычислить значение функции на слове в окошечке, все равно нужно прочесть все буквы этого слова. Так уж лучше их сразу сравнить с образцом. Тем не менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция.
Привести пример удобной для вычисления функции.
Решение. Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.)
Для каждой функции существуют слова, к которым она применима плохо. Зато другая функция в этом случае может работать хорошо. Возникает идея: надо запасти много функций и в начале работы алгоритма выбирать из них случайную. (Тогда враг, желающий подгадить нашему алгоритму, не будет знать, с какой именно функцией ему бороться.)
Привести пример семейства удобных функций.
Решение. Выберем некоторое число p (желательно простое, смотри далее) и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается, таким образом, своя функция). Сдвиг окошка на 1 соответствует вычитанию старшего члена (хn-1 следует вычислить заранее), умножению на x и добавлению свободного члена.
Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же простое, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно, если p больше числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если и много меньше p, то случайному x мало шансов попасть в неудачную точку.
4. ЗАКЛЮЧЕНИЕ.
С развитием INTERNET появилась возможность быстрого и удобного поиска необходимой документальной информации. Теперь можно не заниматься подбором и изучением огромного количества литературы в книжных магазинах и библиотеках. Информацию можно получить, не выходя из дома или офиса. Для этого нужен только непосредственно сам компьютер, подключенный к INTERNET с установленной специальной программой – браузером, предназначеной для просмотра содержимого Web-страниц.
Благодаря разнообразию поисковых систем, специально разработанным для рядового пользователя, каждый может без труда отсечь заведомо ненужный поток информации, лишь правильно сформулировав цель поиска.
5. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.
1. М. Пайк. Internet . СПб., 1996.
2. Пол Гилстер. Навигатор Internet. М., 1995
3. Энциклопедия Интернет, СПб, 2001
4. Информатика. Базовый курс. Учебник для ВУЗов, СПб, 2001
5. How the browsers compare//#"_com_1">
[N1]
Страницы: 1, 2, 3, 4
