Глава 6: Строки в алгоритмах

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

Сортировка строк

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

Сортировка с подсчетом ключей

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

Вот пример сортировки с подсчетом ключей:

Ввод:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
Вывод: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

Алгоритм работает следующим образом:

Подсчитать частоту каждого символа в строках.
Вычислить начальный индекс для каждого символа в отсортированном массиве.
Скопировать строки в отсортированный массив, используя подсчеты для определения позиций.

Сортировка с подсчетом ключей работает за O(n + R) времени, где n - это общее количество символов в строках, а R - размер алфавита (количество различных символов). Это делает его очень эффективным алгоритмом для сортировки строк с небольшим размером алфавита.

Сортировка LSD Radix

Сортировка LSD Radix (сортировка по наименее значащей цифре) является расширением сортировки с подсчетом ключей.Вот перевод на русский язык:

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

Вот пример сортировки LSD radix:

Ввод:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
Вывод: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

Алгоритм работает следующим образом:

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

Сортировка LSD radix работает за O(w * n) времени, где w - длина строк, а n - количество строк. Это делает ее эффективным выбором для сортировки строк фиксированной длины.

Сортировка MSD Radix

Сортировка MSD radix - это рекурсивный вариант сортировки radix, который может обрабатывать строки разной длины. Как и быстрая сортировка, сортировка MSD radix разбивает массив на подмассивы, которые могут быть отсортированы независимо.

Вот пример сортировки MSD radix:

Ввод:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
Вывод: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

Алгоритм работает следующим образом:

Разбить массив на подмассивы на основе первого символа каждой строки.
Рекурсивно отсортировать каждый подмассив.

Сортировка MSD radix имеет худший случай времени работы O(n * w), но на практике она часто быстрее, чем сортировка LSD radix для строк разной длины.

Деревья Tries

Trie (произносится "трай") - это древовидная структура данных для хранения строк, которая позволяет эффективно выполнять поиск по префиксу и поиск строк. Каждый узел в trie представляет собой символ, а путь от корня до узла представляет префикс строки.Вот русский перевод этого markdown-файла с сохранением оригинального кода:

Строки, хранящиеся в дереве Trie.

Вот пример дерева Trie, хранящего строки "sea", "sells", "she", "shells" и "shore":

     (корень)
    /  |  \
   s   h   o
  / \     / \
 e   h   r   t
 |   |   |   |
 a   e   e   h
     |       |
     l       e
     |       |
     l       r
     |
     s

Деревья Trie поддерживают следующие операции:

Вставка строки в дерево Trie.
Поиск строки в дереве Trie.
Удаление строки из дерева Trie.
Поиск всех строк с заданным префиксом.

Временная сложность этих операций составляет O(w), где w - длина вставляемой, искомой или удаляемой строки. Это делает деревья Trie очень эффективной структурой данных для задач, связанных с обработкой строк.

Поиск подстроки

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

Грубый поиск

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

Вот пример грубого поиска:

Текст:    "abacadabrabracabracadabrabrabracad"
Образец: "abracadabra"
Вывод:  [13]

Алгоритм грубой силы имеет худшее время работы O(n * m), где n - длина текста, а m - длина образца. Хотя он прост в реализации, он может быть неэффективным для больших текстов и образцов.

Алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта (KMP) - это эффективный алгоритм поиска подстроки, использующий предварительно вычисленную "функцию отказа" для избежания ненужных сравнений.

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

Вот пример работы алгоритма KMP:

Текст:    "abacadabrabr
```Вот перевод на русский язык:

"acabracadabrabrabracad"
Шаблон: "abracadabra"
Вывод: [13]

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

Алгоритм Бойера-Мура

Алгоритм Бойера-Мура - это еще один эффективный алгоритм поиска подстроки, который работает путем предварительной обработки строки шаблона. В отличие от KMP, который начинает сравнения с начала шаблона, Бойер-Мур начинает с конца и работает в обратном направлении.

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

Вот пример алгоритма Бойера-Мура:

Текст:   "abacadabrabracabracadabrabrabracad"
Шаблон: "abracadabra"
Вывод:  [13]

Бойер-Мур имеет лучший случай времени выполнения O(n/m) и худший случай времени выполнения O(n * m), но на практике он часто является самым быстрым алгоритмом поиска подстроки для больших алфавитов.

Регулярные выражения

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

Регулярное выражение - это последовательность символов, которая определяет шаблон поиска. Самая простая форма регулярного выражения - это буквальная строка, такая как "hello", которая точно соответствует строке "hello". Однако регулярные выражения также включают специальные символы и конструкции, которые позволяют создавать более сложные шаблоны:

. (точка) соответствует любому одиночному символу.
* (звездочка) соответствует нулю или более вхождениям предыдущего символа или группы.
+ (плюс) соответствует одному или более вхождениям предыдущего символа или группы.
? (вопросительный знак) соответствует нулю или одному вхождению предыдущего символа или группы.
^ (крышка) соответствует началу строки.
$ (доллар) соответствует концу строки.
[] (квадратные скобки) определяют класс символов, соответствующих любому одиночному символу.Вот перевод этого markdown-файла на русский язык. Для кода я не переводил комментарии, а только сам код.

Вот несколько примеров регулярных выражений и шаблонов, которые они соответствуют:

a.b соответствует любой строке из трех символов, которая начинается с "a" и заканчивается на "b", например, "acb", "a5b" или "a b".
a*b соответствует любой строке, состоящей из нуля или более символов "a", за которыми следует один символ "b", например, "b", "ab", "aab" или "aaab".
a+b соответствует любой строке, состоящей из одного или более символов "a", за которыми следует один символ "b", например, "ab", "aab" или "aaab", но не "b".
a?b соответствует либо "ab", либо "b".
^a соответствует любой строке, начинающейся с "a".
a$ соответствует любой строке, заканчивающейся на "a".
[aeiou] соответствует любому одиночному гласному символу.

Регулярные выражения поддерживаются многими языками программирования и инструментами, включая Java, Python и Unix-утилиты, такие как grep и sed. Они широко используются для задач, таких как проверка данных, обработка текста и анализ журналов.

Сжатие данных

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

Кодирование длин серий

Кодирование длин серий (RLE) - это простой безвозвратный метод сжатия, который заменяет повторяющиеся последовательности одинаковых символов (серии) одним экземпляром символа и подсчетом количества его повторений.

Вот пример RLE:

Ввод:  "AAAABBBCCCDDDEEE"
Вывод: "4A3B3C3D3E"

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

Кодирование Хаффмана

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

Частоты в входных данных. Более частые символы назначаются более короткими кодами, а менее частые символы - более длинными кодами.

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

После построения дерева код для каждого символа определяется путем от корня до соответствующего листового узла, причем левая ветвь представляет "0", а правая ветвь - "1".

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

Вход:  "AAAABBBCCCDDDEEE"
Выход: "000010011001011100101"

Дерево Хаффмана:
      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

В этом примере "A" назначен код "00", "B" - "01", "C" - "10", "D" - "110", а "E" - "111". Сжатый вывод получается путем замены каждого символа во входе его соответствующим кодом.

Кодирование Хаффмана является оптимальным префиксным кодом, что означает, что ни один код не является префиксом другого кода. Это позволяет однозначно декодировать сжатые данные. Кодирование Хаффмана широко используется в различных форматах файлов и инструментах сжатия, таких как JPEG, MP3 и ZIP.

Сжатие LZW

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

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

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

Пошаговое описание работы сжатия LZW:

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

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

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

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

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

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

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

Несмотря на эти ограничения...Вот перевод на русский язык:

Заключение

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

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

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

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

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

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

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

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

# Импортируем необходимые модули
import re
 
# Определяем функцию для поиска и замены подстрок
def replace_substrings(text, old_substring, new_substring):
    """
    Заменяет все вхождения старой подстроки на новую подстроку в тексте.
    """
    return text.replace(old_substring, new_substring)
 
# Определяем функцию для поиска и подсчета вхождений подстрок
def count_substrings(text, substring):
    """
    Подсчитывает количество вхождений подстроки в тексте.
    """
    return text.count(substring)
 
# Определяем функцию для поиска и замены с использованием регулярных выражений
def replace_with_regex(text, pattern, replacement):
    """
    Заменяет все вхождения, соответствующие регулярному выражению, на новую подстроку в тексте.
    """
    return re.sub(pattern, replacement, text)
 
# Определяем функцию для разбиения текста на слова
def split_text(text, delimiter=None):
    """
    Разбивает текст на список слов, используя указанный разделитель (по умолчанию - пробельные символы).
    """
    return text.split(delimiter)
 
# Определяем функцию для объединения списка слов в строку
def join_words(words, separator=' '):
    """
    Объединяет список слов в строку, используя указанный разделитель.
    """
    return separator.join(words)

Chapter 5 Graphs Chapter 7 Context