Поиск в глубину

Поиск в глубину

Что общего у алгоритмов сжатия и хранения информации в базе данных? В их основе часто лежит дерево, выполняющее всю работу. Деревья составляют подмножество графов. Деревья стоит рассматривать отдельно, так как у них есть много специализированных разновидностей. Например, в коде Хаффмана применяются бинарные деревья. Многие базы данных используют сбалансированные деревья(например B-деревья). Видов деревьев довольно много. Чтобы вам легче было разобраться в них далее будет описаны некоторые из них с необходимой терминологией и концепциями.

Дерево

Дерево — это разновидность графа. Более подробное определение дадим позже, а пока рассмотрим пример.

Как и граф, дерево состоит из узлов и рёбер.

Мы будем работать с однокоренными деревьями. Это означает, что у корневого дерева имеется один узел, от которого можно перейти к любому другому узлу. Так что говоря о дереве, я имею в виду корневое дерево. У узлов могут быть дочерние узлы, а у дочерних узлов может быть родительский узел. В дереве узлы имеют по крайней мере одного родителя. Существует только один узел без родителя — это корневой узел. Узлы, не имеющие дочерних узлов, называются листовыми узлами (листьями). Если вы поняли, что такое корень, лист, родительский и дочерний узел, значит, можно читать дальше!

Каталоги файлов

Так как дерево является разновидностью графа, к нему можно применить алгоритм работающий с графом. В предыдущей статье был рассмотрен алгоритм поиска в ширину. Поиск в ширину можно использовать и с деревом. Например, каталог файлов представляет собой дерево, с которым каждый кто работает за ПК сталкивается. Представьте, что у вас есть некий каталог и по нему требуется вывести имена всех файлов в каталоге, включая все его подкаталоги. В данном случае существует только один подкаталог. Тогда такую задачу можно решить поиск в ширину. эАлгоритм поиска в ширину можно использовать не только как инструмент собственно поиска. Поиск в ширину является также алгоритмом обхода: он посещает каждый узел дерева("обходит" его). В случае с выводом всех имён файлов в подкаталогах — это то что нужно! Нам нужен алгоритм, который перейдёт до каждого файла в дереве и выведет его имя. Логика такая:

1. Посетить каждый узел в дереве.
2. Если узел является файлом, вывести его имя.
3. Если узел является каталогом, добавить его в очередь, чтобы затем поискать находящиеся в нём файлы.

Ниже приведён код реализации такой программы(он похож на код для поиска "продавца яблок" из прошлой статьи):

from os import listdir
from os.path import isfile, join
from collection import deque

def print_file_names(dir):
    # Очередь используется для отслеживания каталогов, в которых потом производится поиск
    s_deque = deque()
    s_deque.append(dir) 
    while s_deque: # Пока очередь не пуста нужно извлекать из неё каталог для проверки
      dr = s_deque.popleft() # Извлечь каталог из очереди
      for file in sorted(listdir(dr)): # Перебрать все файлы и каталоги в извлечённом каталоге
        f_path = join(dr, file) # Формируем полный путь к файлу
        if isfile(f_path): # Если файл значит выводим его имя 
          print(file)
        else:
          s_deque.append(f_path) # Если каталог то добавляем её в конец очереди для обхода

print_file_names("docs") # Запуск в качестве примера для некоторого каталога docs

В очереди хранится информация о том, в каких ещё каталогах нужно провести "обход" и найти имена файлов. В этом примере присутствует отличие от примера поиска в ширину из прошлой статьи. В примере из статьи про поиск в ширину про "продавца яблок" необходимо было следить, проводился ли уже поиск с конкретным человеком(элементом поиска). Здесь этого делать не нужно. В деревьях нет циклов, и в данном случае у каждого узла только один родитель в виде каталога. Мы здесь не рассматриваем и не сможем случайно ввести программу в бесконечный цикл при обходе подкаталогов, поэтому и нет необходимости отслеживать, в каких каталогах уже был поиск. Это важный вывод который стоит использовать: в деревьях не бывает циклов.

О символических ссылках. Пару слов для тех, кто не знает. Создание символических ссылок открывает возможность создания циклов в каталогах. Символическую ссылку можно создать двумя известными способами в Linux или macOS командой: ln -s <путь каталога> <путь каталога> Для Windows это команда: mklink /d <путь каталога> <путь каталога> Получается, что с помощью символической ссылки можно по двум путям попадать фактически в один каталог с файлами. Когда система или приложение обращается к символической ссылке, она автоматически перенаправляет запрос к целевому файлу или директории, указанному в ссылке. При представлении такого каталога в виде дерева — каталог уже не будет являться деревом! В примере выше мы такую ситуацию не рассматриваем. К слову Python достаточно сообразителен поэтому в бесконечный цикл мы с символическими ссылками не попадаем а получаем в программе ошибку: OSError: Errno 62 Too many levels of symbolic links — т.е. слишком много уровней символических ссылок.

Реализация алгоритма

Обойдём каталог файлов на этот раз рекурсивно:

from os import listdir
from os.path import isfile, join

def print_file_names(dir):
    # Перебрать все файлы и подкаталоги
    for file in sorted(listdir(dir)):
        f_path = join(dir, file) # Формируем полный путь к файлу
        if isfile(f_path): 
            # Если файл значит выводим его имя 
            print(file)
        else:
            # Если каталог то вызываем функцию рекурсивно
            # Чтобы снова провести обход файлов в подкаталоге как в основном каталоге поиска
            print_file_names(fullpath)

print_file_names("pics")

Обратите внимание на этот раз очередь не используется. Вместо этого алгоритм при обнаружении подкаталога сразу же заходит в него. Естественно что этот второй способ поиска в глубину будет выводить имена файлов в другом порядке, нежели алгоритм с поиском в ширину. Поиск в глубину тоже работает с графом и представляет собой алгоритм обхода дерева. Отличие от поиска в ширину то что алгоритм поиска в глубину не добавляет подкаталог поиска в очередь, а сразу же заходит в него и ищет в нём файлы. Поиск в ширину и поиск в глубину тесно связаны друг с другом. Однако между ними существует важное различие. Поиск в глубину не может использоваться для нахождения кратчайшего пути! Именно потому что поиск в глубину сразу заходит на максимально возможную глубину по дереву. Оба алгоритма могут быть использованы для обхода деревьев, но для поиска кратчайшего пути подходит только алгоритм поиска в ширину. У алгоритма поиска в глубину больше применений в топологической сортировке(о ней также было упомянуто в прошлой статье).

Определение дерева

После рассмотрения примера можно привести более точное определение дерева. Дерево представляет собой связанный ациклический граф. Работа алгоритма поиск в глубину идёт исключительно с корневыми деревьями и связанными графами. Главное, что следует помнить — не должно быть циклов в деревьях которые "обходит" алгоритм.

Бинарные деревья

Существует множество разных типов деревьев. Бинарные деревья используются исключительно часто. Бинарное дерево представляет собой особую разновидность дерева, узлы которого могут иметь не более двух дочерних узлов (отсюда и название бинарные или двоичные деревья). Дочерние узлы традиционно называют левым и правым узлами. Пример бинарного дерева — генеалогическое древо, так как у каждого узла имеются два биологических родителя. В таком дереве между узлами существует чёткая связь — все они составляют одну семью. Однако данные могут быть произвольными. Важно то, что ни у одного узла не может быть больше двух дочерних узлов. Иногда встречаются термины "левое поддерево" и "правое поддерево". Далее рассмотрен пример,в котором используется бинарное дерево.

Код Хаффмана

Код Хаффмана — хороший пример использования бинарных деревьев. Он лежит в основе алгоритмов сжатия текста. Разберём как он работает и как в нём применяются деревья. Прежде необходимо понять как работает сжатие, и знать, сколько места занимает текстовый файл. Представим файл, содержащий всего одно слово: dart. Сколько места он занимает? Чтобы узнать это, можно воспользоваться командой stat в Unix системах. Сохраните слово в файле с именем test.txt, а затем воспользуемся командой stat:

$ cat test.txt

dart

$ stat -c %s test.txt

4

Итак, файл занимает 4 байта: по 1 байту на символ. Выглядит логично. Если предположить, что мы используем кодировку ISO-8859-1. Каждая буква в ней занимает ровно 1 байт. Например, буква t в ISO-8859-1 соответствует код 116, который в двоичной системе записывается в виде 01110100, — итого 8 бит. Коды ISO-8859-1 содержатся в интервале от 00000000, что соответствует нуль-символу, до 11111111, что соответствует символу ÿ(латинская буква y в нижнем регистре с тремой). Всего существует 256 возможных 8-битовых комбинаций из 0 и 1, так что кодировка ISO-8859-1 способна представить до 256 букв.

Кодировки. Существует множество способов кодирования символов. Можно букву записать в двоичной форме разными способами. Всё началось с кодировки ASCII, которая была создана ещё в 1960-х годах в США. ASCII является 7-битной кодировкой. К сожалению в неё не вошли многие символы и распространённые обозначения, например, обозначения валют. Позже была создана 8 битная кодировка ISO-8859-1, а в дальнейшем выделилось целое семейство ISO-8859. В этой кодировке уже было вдвое больше символов чем в ASCII! Вместо 7 битной из 128 символов стало доступно 256! Тем не менее этого было недостаточно, и многие страны стали создавать собственные кодировки. Так как ISO-8859-1 и ASCII были ориентированы на европейские языки. Хаос с кодировками при прочтении и отправке текстовых файлов и писем по электронной почте нарастал, пока не появился Юникод! Юникод — стандарт кодирования символов который поддерживает символы всех языков. Юникод версии 16 по данным на сентябрь 2024 года включает 154 998 символов — большой шаг вперёд по сравнению с 256! Более 1000 это так называемые символы эмодзи. В настоящее время самой популярной кодировкой такого рода считается UTF-8. Эта кодировка с переменной длиной кодирования символов; представление одного символа может занимать от 1 до 4 байт(8-32 бит).

Данный пример я специально упростил назвав кодировку ISO-8859-1 с 8-битным представлением символов, — это удобно за счёт постоянной длины кодирования. Выделим основное, что из выше изложенного нужно понимать:

• Алгоритмы сжатия сокращают количество бит, необходимых для представления символов;
• UTF-8 современный стандарт кодирования по умолчанию.

Декодируем наше слово dart в двоичное представление: 01100100 01100001 01110010 01110100. Можно воспользоваться таблицей кодировки ISO-8859-1 или преобразователем двоичной записи, чтобы упростить задачу. Также при декодировании мы знаем что одна буква занимает 8 бит, поэтому разделяем последовательность на 8-битные блоки, чтобы её проще было читать. Для просмотра двоичного кода текста можно воспользоваться утилитой Unix систем. Вызываем команду xxd для файла test.txt в котором сохранён текст python(предварительно пакет xxd должен быть установлен в системе). Вот так это выглядит:

$ xxd -b test.txt

00000000: 01100100 01100001 01110010 01110100 dart

Далее используется сжатие. Для слова dart не нужны все 256 возможных букв, достаточно четырёх. Таким образом, для представления буквы не требуется 8 бит, можно обойтись двумя. Можно определить собственную 2-битную кодировку для этих четырёх букв:

d = 00

a = 01

r = 10

t = 11

В таком случае можно записать слово dart в новой нашей кодировке: 00 01 10 11. Так работает алгоритм Хаффмана: он ищет все символы в тексте и использует для их представления менее 8 бит. В результате происходит сжатие данных. Код Хаффмана генерирует дерево и по этому дереву можно узнать код каждой буквы, начиная с корневого узла. Коды букв в кодировке Хаффмана не обязательно должны иметь одинаковую длину. Это важный момент, поэтому рассмотрим ещё один пример. Построим дерево, сгенерированное алгоритмом Хаффмана для фразы "android paranoid", будет выглядеть так:

Здесь мы видим что код для буквы p это 0001. А для буквы d это уже 10. В данном случае вообще используется три разные длины кодирования символов! Представьте, что вам нужно раскодировать данные: 000101010. В данном случае код может состоять из 2, 3 или 4 цифр! Так как длина кода постоянно может меняться, разбить его на равные фрагменты сразу невозможно. Чтобы декодировать, придётся перебирать каждую цифру по отдельности, словно нам их показывают по очереди. Вот как будем разбирать эту последовательность 000101010 по нашему дереву.

1. Первая цифра ноль, поэтому идём налево;
2. Вторая цифра снова ноль, снова идём налево;
3. Третья также ноль, налево;
4. Четвёртая цифра 1, мы пришли к букве p по нашему дереву.
5. Остались данные: 01010. Снова начинаем с корневого узла, чтобы найти остальные буквы.

Нашли закодированное слово? Да, это слова pad (с английского блокнот). Здесь мы видим принципиальное отличие кода Хаффмана от кодировки ISO-8859. Длины кодов могут изменяться, поэтому декодирование должно выполняться по-другому. У такой схемы есть своё преимущество. Те буквы которые чаще встречаются в тексте — имеют более короткие коды. Буква d встречается в тексте три раза, а буква p всего один раз. Вместо того чтобы кодировать все буквы 4 битами, алгоритм применяет повышенное сжатие или сокращение кодов для часто используемых в тексте букв! В длинном тексте это обеспечит большой выйгрыш в памяти!

С кодом Хаффмана нет проблемы "наложения кодов друг на друга", потому что буквы помещаются только в листовых узлах. И от корневого узла к каждому листовому существует только один уникальный путь — это одно из уникальных свойств деревьев! Это свойство также гарантирует, что каждой букве будет соответствовать только один код. Когда декодируются код по одной цифре, предполагается, что в конечном итоге получается буква. Если бы в графе присутствовал цикл, то такое предположение не работало бы из-за риска попасть в этот самый цикл. Но в дереве циклы заведомо отсутствуют, так что алгоритм гарантированно придёт к какой-нибудь букве. А также используется корневое дерево и всегда известно с чего начинать декодирование. С другой стороны не каждый граф будет иметь корневой узел. Наконец, дерево, используемое в алгоритме называется бинарным. Узлы в бинарных деревьях имеют не более двух дочерних узлов — левый и правый, так как в двоичной записи только две цифры 0 и 1.

В следующей статье будут рассматриваться сбалансированные деревья и их возможные применения.