Хотя этот обзор написан относительно давно, он, судя по всему, еще не потерял актуальности. Перечисленные в нем задачи и методы их решения составляют основу интенсивных исследований. Активные эксперименты с суффиксными деревьями привели к резкому снижений требуемой ими памяти, так что они становятся де-факто стандартом в приложениях, связанных с нестрогим поиском в словарях больших объемов. Список примеров легко продолжить.

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

Те, кто не любят и/или не могут читать on-line, могут скачать текст в формате html или RTF. Вы можете скачать также исходный (английский) текст в ps-формате.

• 1. ВВЕДЕНИЕ
• 2. ЗАДАЧА
  • 2. 1 Определение задачи
• 3. ОБЗОР АЛГОРИТМОВ
  • 3. 1 Сопоставления строк
  • 3. 2 Расстояния между строками
    • 3. 2.1 Обобщенные задачи
  • 3. 3 Нечеткое сопоставление строк
    • 3. 3.1 Специальные устройства
  • 3. 4 Максимальная повторяющаяся подстрока
• 4. АЛГОРИТМЫ
  • 4. 1 Поиск образцов
    • 4. 1.1 Наивный подход
    • 4. 1.2 Кнут-Моррис-Пратт
    • 4. 1.3 Бойер-Мур
    • 4. 1.4 Бойер-Мур-Хорспул
    • 4. 1.5 Сандей: Быстрый поиск, Максимальный сдвиг, Оптимальное несовпадение
    • 4. 1.6 Хьюм и Сандей. Улучшенные алгоритмы Бойера-Мура и Наименьшая цена
    • 4. 1.7 Харрисон
    • 4. 1.8 Карп-Рабин
  • 4. 2 Расстояние между строками и самая длинная общая подпоследовательность
    • 4. 2.1 Вагнер-Фишер
    • 4. 2.2 Хиршберг
    • 4. 2.3 Хант-Шиманский
    • 4. 2.4 Машек-Патерсон
    • 4. 2.5 Укконен
    • 4. 2.6 Самая тяжелая общая подпоследовательность
  • 4. 3 НЕЧЕТКОЕ СОПОСТАВЛЕНИЕ СТРОК
    • 4. 3.1 k несовпадений - Ландау-Вишкин
    • 4. 3.2 k различий - Ландау-Вишкин
  • 4. 4 Самая длинная повторяющася подстрока
    • 4. 4.1 Наивный подход
    • 4. 4.2 Суффиксные деревья
• 5. НАЗАД, К ИСХОДНОЙ ЗАДАЧЕ
  • 5. 1 Система
  • 5. 2 Задача
• 6. ПРИЛОЖЕНИЕ A: АСИМПТОТИЧЕСКАЯ ЗАПИСЬ
• 7. ЛИТЕРАТУРА

Вы можете попасть на эту страницу по одному из следующих адресов:
http://learn.at/infoscope/string_search/Stephen-92/index.html
http://now.at/infoscope/string_search/Stephen-92/index.html
http://read.at/infoscope/string_search/Stephen-92/index.html

Дата последней модификации: 10 октября 2000 г.