Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Поиск в строках, массивах, последовательностях /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


8  Обозначения и определения.
8  Краткий обзор алгоритмов
8  Алгоритм Хорспула
8  Быстрый поиск
8  Алгоритм оптимального несовпадения
8  Алгоритм максимального сдвига
8  Tурбо Боуер-Мур
8  Турбо - обращенние сегмента
8  Алгоритм Сдвига-Или
8  Алгоритм грубой силы
8  Построение автомата
8  Алгоритм Карпа-Рабина
8  Алгоритм Морриса-Пратта
8  Алгоритм Кнута-Морриса-Пратта
8  `Не такой уж наивный` алгоритм
8  Алгоритм Боуера-Мура
8  Алгоритм обращения сегмента
Точный поиск подстроки в строке - Программирование от RIN.RU
Точный поиск подстроки в строке

В данном обзоре нам хотелось бы рассмотреть наиболее известные алгоритмы поиска. На самом деле их гораздо больше, однако многие нам показались уж слишком неоптимальными.


Данные алгоритмы ищут все вхождения подстроки в текст.


Для практических целей рекомендуются в первую очередь улучшения Боуера-Мура: Боуер-Мур-Хорспул, Быстрый поиск, Оптимальное несовпадение, Максимальный сдвиг и Турбо-БМ,а также несколько специфичные Турбо-обращение сегмента и Сдвиг-Или







SpeedSIP значительно снижает расходы на телефонную связь и сервисы:
  • бесплатные звонки внутри сети,
  • выгодные международные и междугородные звонки,
  • СМС по всему миру,
  • покупка прямого номер любой страны,
  • видеосвязь и видеоконференции.


  • В этом разделе :

    8  Обозначения и определения.
    Термины не обязательно запоминать: будут в алгоритме - вернетесь.

    8  Краткий обзор алгоритмов


    8  Алгоритм Хорспула
    Этот алгоритм - некоторое упрощение стандартного Боуера - Мура.

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

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

    8  Алгоритм максимального сдвига
    Вариант алгоритма быстрого поиска, просматривающий символы образца от соответствующего наибольшему сдвигу к наименьшему.

    8  Tурбо Боуер-Мур
    Турбо - БМ является улучшением алгоритма Боуера - Мура.

    8  Турбо - обращенние сегмента
    Этот алгоритм является улучшением алгоритма обращенного сегмента уменьшающим наибольшее число сравнений до 2*n.

    8  Алгоритм Сдвига-Или
    Пусть R - битовый массив размера m. Вектор R i - значение массива R после обработки очередного символа. Он содержит информацию обо всех совпадениях префиксов х, которые кончаются на позиции i в тексте ( 0 <= j <= m - 1 ):

    8  Алгоритм грубой силы
    Этот алгоритм заключается в проверке всех позиций текста с 0 по n - m на предмет совпадения с началом образца.

    8  Построение автомата
    Cтроим автомат ( DFA ): A(x) = (Q, i, T, d).

    8  Алгоритм Карпа-Рабина
    Хеширование может позволить нам избежать квадратичного количества сравнений символов в обычных ситуациях.

    8  Алгоритм Морриса-Пратта
    Этот алгоритм появился в результате тщательного анализа алгоритма грубой силы.

    8  Алгоритм Кнута-Морриса-Пратта
    Этот алгоритм был получен благодаря глубокому анализу алгоритма Морриса-Пратта. Итак, посмотрим, что еще можно сделать, чтобы увеличить размер сдвига.

    8  `Не такой уж наивный` алгоритм


    8  Алгоритм Боуера-Мура
    Один из наиболее известных и, эффективных ( Это особенно касается его дальнейших улучшений ) для ОБЫЧНЫХ ПРИЛОЖЕНИЙ ( то есть редакторов текста, например ) алгоритму.

    8  Алгоритм обращения сегмента
    Данный алгоритм имеет квадратичный худший случай, однако в среднем оптимален.

    8  Обозначения и определения.
    8  Краткий обзор алгоритмов
    8  Алгоритм Хорспула
    8  Быстрый поиск
    8  Алгоритм оптимального несовпадения
    8  Алгоритм максимального сдвига
    8  Tурбо Боуер-Мур
    8  Турбо - обращенние сегмента
    8  Алгоритм Сдвига-Или
    8  Алгоритм грубой силы
    8  Построение автомата
    8  Алгоритм Карпа-Рабина
    8  Алгоритм Морриса-Пратта
    8  Алгоритм Кнута-Морриса-Пратта
    8  `Не такой уж наивный` алгоритм
    8  Алгоритм Боуера-Мура
    8  Алгоритм обращения сегмента

     
      
      
        Copyright ©  RIN 2003 - 2004      * Обратная связь
    Новое: салат с гребешками .