Как работают алгоритмы
Chapter 9 Algorithm Design Paradigms Divide and Conquer

Глава 9: Парадигмы проектирования алгоритмов

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

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

Разделяй и властвуй

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

Типичный алгоритм разделяй и властвуй состоит из трех шагов:

  1. Разделение: Если проблема достаточно мала, чтобы быть решенной напрямую, решите ее. В противном случае разделите проблему на более мелкие подзадачи.
  2. Покорение: Рекурсивно решите каждую подзадачу.
  3. Объединение: Объедините решения подзадач, чтобы получить решение исходной проблемы.

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

Сортировка слиянием: классический алгоритм разделяй и властвуй

Одним из наиболее известных примеров алгоритма разделяй и властвуй является сортировка слиянием, которую мы подробно изучали в Главе 2. Напомним, что сортировка слиянием сортирует массив, разделяя его на две половины, рекурсивно сортируя каждую половину и затем объединяя отсортированные половины.

Вот высокоуровневое описание алгоритма сортировки слиянием:Алгоритм сортировки слиянием:

function mergesort(array):
    # Если массив содержит 1 или меньше элементов, возвращаем его
    if array.length <= 1:
        return array
    else:
        # Находим середину массива
        mid = array.length / 2
        # Рекурсивно сортируем левую и правую половины
        left = mergesort(array[0:mid])
        right = mergesort(array[mid:])
        # Объединяем отсортированные половины
        return merge(left, right)

Функция merge объединяет два отсортированных массива в один отсортированный массив:

function merge(left, right):
    # Создаем результирующий массив
    result = []
    # Пока в обоих массивах есть элементы
    while left is not empty and right is not empty:
        # Сравниваем первые элементы и добавляем меньший в результат
        if left[0] <= right[0]:
            append left[0] to result
            remove left[0] from left
        else:
            append right[0] to result
            remove right[0] from right
    # Добавляем оставшиеся элементы в результат
    append remaining elements of left to result
    append remaining elements of right to result
    # Возвращаем результат
    return result

Стратегия "разделяй и властвуй" позволяет сортировке слиянием достичь худшего случая времени работы O(n log n), что делает ее одним из наиболее эффективных универсальных алгоритмов сортировки.

Теорема Мастера

Время работы многих алгоритмов "разделяй и властвуй" можно проанализировать с помощью Теоремы Мастера, которая предоставляет общую формулу для рекуррентных соотношений вида:

T(n) = aT(n/b) + f(n)

Здесь a - количество рекурсивных вызовов, n/b - размер каждой подзадачи, и f(n) - стоимость разделения задачи и объединения результатов.

Теорема Мастера утверждает, что решение этого рекуррентного соотношения:

  1. Если f(n) = O(n^(log_b(a) - ε)) для некоторой константы ε > 0, то T(n) = Θ(n^log_b(a)).
  2. Если f(n) = Θ(n^log_b(a)), то T(n) = Θ(n^log_b(a) * log n).
  3. Если f(n) = Ω(n^(log_b(a) + ε)) для некоторой константы ε > 0, и если af(n/b) ≤ cf(n) для некоторой константы c < 1 и всех достаточно больших n, то T(n) = Θ(f(n)).

Для сортировки слиянием мы имеем a = 2 (два рекурсивных вызова), b = 2 (каждая подзадача вдвое меньше), и f(n) = Θ(n) (слияние занимает линейное время). Поскольку log_2(2) = 1, мы находимся в случае 2 Теоремы Мастера, и время работы равно Θ(n log n).

Другие алгоритмы "разделяй и властвуй"

Многие другие алВот перевод на русский язык с сохранением оригинального кода:

Алгоритмы могут быть разработаны с использованием парадигмы "разделяй и властвуй". Некоторые примечательные примеры включают:

  • Быстрая сортировка (Quicksort): Подобно сортировке слиянием, быстрая сортировка является алгоритмом сортировки "разделяй и властвуй". Он разбивает массив вокруг опорного элемента, рекурсивно сортирует подмассивы слева и справа от опорного элемента и объединяет результаты.

  • Двоичный поиск: Алгоритм двоичного поиска для поиска элемента в отсортированном массиве можно рассматривать как алгоритм "разделяй и властвуй". Он сравнивает целевое значение со средним элементом массива и рекурсивно ищет левую или правую половину в зависимости от результата сравнения.

  • Умножение Карацубы: Это алгоритм "разделяй и властвуй" для умножения двух n-значных чисел за время O(n^log_2(3)) ≈ O(n^1.585), что быстрее, чем традиционный алгоритм O(n^2).

  • Алгоритм Штрассена для умножения матриц: Алгоритм Штрассена умножает две матрицы n × n за время O(n^log_2(7)) ≈ O(n^2.807), что улучшает наивный алгоритм O(n^3).

Эти примеры демонстрируют универсальность и мощь парадигмы "разделяй и властвуй" для разработки эффективных алгоритмов.

Жадные алгоритмы

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

Ключевые характеристики жадных алгоритмов:

  1. Они делают локально оптимальный выбор на каждом шаге, не беспокоясь о будущих последствиях.
  2. Они предполагают, что локально оптимальный выбор приведет к глобально оптимальному решению.
  3. Они никогда не пересматривают предыдущие решения.

Жадные алгоритмы часто просты для понимания и реализации, и они могут быть очень эффективными. Однако они не всегда дают оптимальное решение, так как локально оптимальные выборы могут не привести к глобально оптимальному решению.

Кодирование Хаффмана: Жадный алгоритм для сжатия данных

ХаффманВот перевод на русский язык:

Кодирование Хаффмана, с которым мы познакомились в Главе 5, является жадным алгоритмом для построения оптимального префиксного кода для сжатия данных. Алгоритм строит двоичное дерево снизу вверх, присваивая более короткие битовые последовательности более частым символам.

Вот высокоуровневое описание алгоритма кодирования Хаффмана:

  1. Создайте узел-лист для каждого символа и добавьте его в очередь с приоритетом.
  2. Пока в очереди больше одного узла:
    • Удалите два узла с наименьшей частотой из очереди.
    • Создайте новый внутренний узел с этими двумя узлами в качестве потомков и с частотой, равной сумме частот двух узлов.
    • Добавьте новый узел в очередь с приоритетом.
  3. Оставшийся узел является корневым узлом, и дерево завершено.

Жадный выбор заключается в том, чтобы всегда объединять два узла с наименьшей частотой. Этот локально оптимальный выбор приводит к глобально оптимальному префиксному коду.

Вот пример кодирования Хаффмана в действии:

Предположим, у нас есть следующие частоты символов:

d: 1
e: 1

Вот дерево Хаффмана для этого примера:

      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

Результирующие коды Хаффмана:

A: 00
B: 01
C: 10
D: 110
E: 111

Поэтому исходная строка "AAAABBBCCCDDDEEE" будет закодирована как:

00000000010101101010110110110111111111

Кодирование Хаффмана достигает сжатия, назначая более короткие коды более частым символам. Коды являются префиксными, что означает, что ни один код не является префиксом другого, что позволяет однозначно декодировать.

Сжатие LZW

Сжатие Lempel-Ziv-Welch (LZW) - это алгоритм сжатия на основе словаря, который строит словарь (или кодовую книгу) строк во время сжатия входных данных. LZW широко используется в утилитах сжатия файлов и использовался в формате изображений GIF.

Ключевая идея LZW заключается в замене строк символов одиночными кодами. Он читает входную строку символ за символом и кодирует строку в компактное представление, заменяя каждую фиксированную длинуВот перевод на русский язык с сохранением оригинального кода:

Алгоритм сжатия данных с переменной длиной кода. Чем длиннее строка, тем больше места экономится при ее кодировании в виде одного числа.

Вот пошаговое описание того, как работает сжатие LZW:

  1. Инициализируйте словарь, чтобы он содержал все строки из одного символа.
  2. Найдите самую длинную строку W в словаре, которая соответствует текущему входному значению.
  3. Выведите индекс словаря для W в выходные данные и удалите W из входных данных.
  4. Добавьте W, за которым следует следующий символ во входных данных, в словарь.
  5. Перейдите к шагу 2.

Рассмотрим пример. Предположим, мы хотим сжать строку "ABABABABA" с помощью LZW.

  1. Инициализируйте словарь, чтобы он содержал "A" и "B".
  2. Самое длинное совпадение - "A". Выведите его индекс (0) и удалите его из входных данных. Теперь словарь содержит "A", "B" и "AB".
  3. Самое длинное совпадение - "B". Выведите его индекс (1) и удалите его из входных данных. Теперь словарь содержит "A", "B", "AB" и "BA".
  4. Самое длинное совпадение - "AB". Выведите его индекс (2) и удалите его из входных данных. Теперь словарь содержит "A", "B", "AB", "BA" и "ABA".
  5. Самое длинное совпадение - "ABA". Выведите его индекс (4) и удалите его из входных данных. Теперь словарь содержит "A", "B", "AB", "BA", "ABA" и "ABAB".
  6. Самое длинное совпадение - "BA". Выведите его индекс (3). Входные данные теперь пусты.

Сжатое представление "ABABABABA" - это последовательность индексов [1], которая требует меньше битов для представления, чем исходное ASCII-представление.

Декомпрессия работает аналогичным образом, но в обратном порядке:

  1. Инициализируйте словарь, чтобы он содержал все строки из одного символа.
  2. Прочитайте код X из входных данных.
  3. Выведите строку для X из словаря.
  4. Если предыдущий код существует, добавьте предыдущую строку, объединенную с первым символом строки для X, в словарь.
  5. Перейдите к шагу 2.

Сжатие LZW простое и быстрое, что делает его хорошим выбором для многих приложений. Однако у него есть некоторые ограничения. Размер словаря может значительно увеличиваться, потребляя значительное количество памяти. Кроме того,Вот перевод на русский язык:

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

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

Заключение

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

Мы начали с обсуждения сортировки строк, которая представляет собой оптимизированные алгоритмы сортировки, использующие специальные свойства строк. Индексированный подсчет, LSD-радикс-сортировка и MSD-радикс-сортировка обеспечивают эффективные методы сортировки строк на основе их отдельных символов.

Затем мы рассмотрели деревья-суффиксы, древовидную структуру данных для хранения и извлечения строк. Деревья-суффиксы позволяют быстро выполнять поиск по префиксам и широко используются в таких приложениях, как автозаполнение и таблицы маршрутизации IP.

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

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

Наконец, мы исследовали алгоритмы сжатия данных, которые уменьшают размер данных, используя избыточность и шаблоны во входных данных. Мы рассмотрели кодирование длин серий, кодирование Хаффмана и сжатие Лемпеля-Зива-Велча, каждое из которых имеет свои сильные стороны и области применения.

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

Работа со строковыми данными

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

# Импортируем необходимые библиотеки
import re
import string
 
# Определяем функцию для очистки текста
def clean_text(text):
    # Удаляем знаки пунктуации
    text = re.sub(r'[{}]+'.format(string.punctuation), '', text)
    # Переводим текст в нижний регистр
    text = text.lower()
    return text
 
# Пример использования функции
sample_text = "This is a sample text. It contains some punctuation, like periods, commas, and exclamation marks!"
cleaned_text = clean_text(sample_text)
print(cleaned_text)
Chapter 8 Algorithm Analysis TechniquesChapter 10 Intractable Problems and Approximation Algorithms