Технологии поиска документальной информации в INTERNET

  • Добавили06.08.2003
  • Размер42,19 Kб
  • Скачали3976

Y, так и не встретив X 3. 3. 2 Алгоритм Бойера-Мура Этот алгоритм делает то, что на первый взгляд кажется невозможным в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец.

Как так может быть Идея проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвертую букву слова если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы.

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

Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором хks. Эти сведения будем хранить в массиве poss если символ s вовсе не встречается, то нам будет удобно положить poss0 мы увидим дальше, почему. Как заполнить массив pos Решение.

положить все poss равными 0 for i1 to n do begin posxii end В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале lastn длина образца, затем last постепенно увеличивается. lastn все предыдущие положения образца уже проверены while last m do begin слово не кончилось if xm ylast then begin последние буквы разные lastlastn-posylast n - posylast - это минимальный сдвиг образца, при котором напротив ylast встанет такая же буква в образце.

Если такой буквы нет вообще, то сдвигаем на всю длину образца end else begin если нынешнее положение подходит, т. е. если xi хnylast-n1 ylast, то сообщить о совпадении lastlast1 end end Знатоки рекомендуют проверку совпадения проводить справа налево, т.

е. начиная с последней буквы образца в которой совпадение заведомо есть. Можно также немного сэкономить, произведя вычитание заранее и храня не poss, а n-poss, т.

е. число букв в образце справа от последнего вхождения буквы Возможны разные модификации этого алгоритма. Например, можно строку lastlasti заменить на lastlastn-.

Скачать
Контрольная Коммуникации и связь 13.08.2008

Все об интернете

1 1. История сети Интернет 2 2. Что такое Интернет 3-4 3. Применения Интернета 4-7 3.1 Электронная почта 4 3.2 Передача файлов 5 3.3 Удаленный доступ 5 3.4 Как движутся данные – среда передачи 6 3.5 Коммутируемые линии 6 3.6 Арендуемые линии 6 3.7 Микроволновая

Реферат Компьютерные сети 24.06.2000

Глобальная сеть INTERNET

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

Курсовая Информатика 11.06.2010

гипертекстовая технология

… …3 1 Гипертекст… 5 1.1 Понятие гипертекста…5 1.2 История развития гипертекста…7 1.3 Простая технология построения гипертекста….10 2 Гипертекстовая технология… 12 2.1 Общие понятия… 12 2.2 Применения гипертекстовых технологий… 15 2.3 Гипертекстовые Web-документы….

Курсовая Журналистика, издательское дело и СМИ 23.12.2009

Источники информации (Общая характеристика)

Информация- это творчество, а не ремесло, когда по Старой форме штампуют несколько изделий… А. Рубинов. На этапе разработки замысла журналистского произведения необходимо, прежде всего, определиться с объектом изучения. В качестве данного объекта изучения

5ballov.qip.ru рекомендует:

  • Выбор ВУЗа

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

  • Как сдать ЕГЭ

    Прежде, чем идти в выбранный вуз с документами, нужно сначала получить аттестат, который выдается после сдачи экзаменов. А подготовиться к ним можно в нашем разделе ЕГЭ. Там также представлены варианты за прошлые года.

  • Подготовка к ГИА

    Для девятиклассников не менее важно окончание учебного года. Их также ждет государственная итоговая аттестация. Подготовиться к ней можно на нашем сайте в разделе ГИА. Главное помнить: самоподготовка - это путь к успешной сдаче.

Облако тегов