advanced-ds.tex

\chapter{Сложные структуры данных}
\label{ch:advanced-ds}

\section{Красно-чёрные деревья}
\label{sec:rb-tree}
\emph{Красно-чёрное дерево} представляет собой бинарное дерево поиска с одним дополнительным битом \emph{цвета}. Цвет узла может быть либо красным, либо чёрным. Возможное определение типа на языке \emph{Haskell} следующее:
\begin{hslst}{}{}
data Color = R
           | B
           deriving Show

data Tree e = E
            | T Color (Tree e) e (Tree e)
            deriving Show
\end{hslst}

В соответствии с накладываемыми на узлы дерева ограничениями, ни один путь в красно-чёрном дереве не отличается от другого по длине более чем в два раза, что делает его сбалансированным. Вот эти ограничения:
\begin{enumerate}
  \item Корень дерева является чёрным.
  \item Красный узел может быть потомком только чёрного узла.
  \item Все пути от корня к пустым узлам содержат одинаковое количество чёрных узлов.
  \item Пустой узел — чёрный.
\end{enumerate}

\subsection{Реализация}
Определение типа уже было представлено выше. Напишем функции для создания пустого дерева и для проверки, присутствует ли элемент в дереве или нет:
\begin{hslst}{}{}
empty :: Tree e
empty = E

member :: Ord e => e -> Tree e -> Bool
member x E = False
member x (T _ a y b) | x <  y = member x a
                     | x == y = True
                     | x >  y = member x b
\end{hslst}

При вставке нового узла в дерево может возникнуть одна из четырёх ситуаций, представленных на рисунке~\ref{fig:rb-tree-transforms}, когда красный узел является потомком тоже красного узла. На этом же рисунке~\ref{fig:rb-tree-transforms} показаны необходимые преобразования, чтобы дерево вновь стало сбалансированным.

\begin{figure}[t]
  \centering
  \begin{tikzpicture}[red/.style={circle,draw},
                      black/.style={circle,draw,fill=gray},
                      level distance=1cm,
                      font=\footnotesize]
    \node [black] at (0,0) {$z$}
      child { node [red] {$x$}
        child { node [] {$a$} }
        child { node [red] {$y$}
          child { node [] {$b$} }
          child { node [] {$c$} } } }
      child { node [] {$d$} };

    \node [black] at (-4,-4.5) {$z$}
      child { node [red] {$y$}
        child { node [red] {$x$}
          child { node [] {$a$} }
          child { node [] {$b$} } }
        child { node [] {$c$} } }
      child { node [] {$d$} };

    \node [black] at (4,-4.5) {$x$}
      child { node [] {$a$} }
      child { node [red] {$y$}
        child { node [] {$b$} }
        child { node [red] {$z$}
          child { node [] {$c$} }
          child { node [] {$d$} } } };

    \node [black] at (0,-8.5) {$x$}
      child { node [] {$a$} }
      child { node [red] {$z$}
        child { node [red] {$y$}
          child { node [] {$b$} }
          child { node [] {$c$} } }
        child { node [] {$d$} } };


    \begin{scope}[level/.style={sibling distance=11mm/#1}]
      \node [red] at (0,-4.5) {$y$}
        child { node [black] {$x$}
          child { node [] {$a$} }
          child { node [] {$b$} } }
        child { node [black] {$z$}
          child { node [] {$c$} }
          child { node [] {$d$} } };
    \end{scope}

    \draw [->,thick] (-2.5,-5.5) -- (-1.5,-5.5);
    \draw [->,thick] (2.5,-5.5) -- (1.5,-5.5);
    \draw [->,thick] (0,-3.2) -- (0,-4);
    \draw [->,thick] (0,-7.8) -- (0,-7);
  \end{tikzpicture}
  \caption{Балансировка дерева}
  \label{fig:rb-tree-transforms}
\end{figure}

Для этих преобразований напишем функции \lstinline{balance}. Для всех четырёх случаев она делает преобразование необходимое, в ином случае она возвращает узел, состоящий целиком и полностью из переданных ей аргументов.
\begin{hslst}{}{}
balance :: Color -> Tree e -> e -> Tree e -> Tree e
balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance color a x b = T color a x b
\end{hslst}

Функция вставки \lstinline{insert} работает следующим образом: она вставляет элемент в положенное место в дереве, после чего при раскрутке стека делает преобразование, если оно необходимо, для каждого пройденного узла функцией \lstinline{balance}, после чего делает корневой узел чёрным.
\begin{hslst}{}{}
insert :: Ord e => e -> Tree e -> Tree e
insert x t = makeBlack (insert' t)
  where insert' E = T R E x E
        insert' (T color a y b) | x <  y = balance color (insert' a) y b
                                | x == y = T color a y b
                                | x >  y = balance color a y (insert' b)
        makeBlack (T _ a x b) = T B a x b
\end{hslst}

Реализуем функцию для построения дерева из элементов списка — и посмотрим, правильно ли строится дерево вышепредставленными функциями.
\begin{hslst}{}{}
fromList :: Ord e => [e] -> Tree e
fromList = foldl (flip insert) E

main :: IO ()
main = do
  putStrLn $ show $ fromList [9, 8, 7, 4, 5, 6, 3, 2, 1, 0]
\end{hslst}

После выполнения этого кода, получим в консоли:
\begin{plainlst}{}{}
T B (T B (T R (T B E 0 E) 1 (T B E 2 E)) 3 (T B E 4 E)) 5 (T B (T B (T R E 6 E) 7 E) 8 (T B E 9 E))
\end{plainlst}

\section{Префиксные деревья}
\label{sec:trie}
\emph{Префиксное дерево} (\emph{trie}) — структура данных, позволяющая хранить ассоциативный массив, ключами которого являются, как правило, строки. В отличие от двоичных деревьев поиска не обязательно хранить ключ в узлах дерева, так как в префиксном дереве по позиции узла можно вычислить ключ, ассоциированный с ним. Все потомки узла имеют общий префикс, представленный этим самым узлом.

Ниже на рисунке представлено префиксное дерево с некоторыми английскими словами в качестве ключей.
\begin{center}
  \begin{tikzpicture}[minimum size=7mm,
                      circle,thick,
                      edge from parent/.style={->,draw,thick},
                      level/.style={sibling distance=50mm/#1}]
    \node [draw] {}
      child { node [draw] {$t$}
        child { node [draw] {$to$}
          edge from parent
            node[left] {$o$}
        }
        child { node [draw] {$te$}
          child { node [draw] {$tea$}
            edge from parent
              node[left] {$a$}
          }
          child { node [draw] {$ted$}
            edge from parent
              node[left] {$d$}
          }
          child { node [draw] {$ten$}
            edge from parent
              node[right] {$n$}
          }
          edge from parent
            node[right] {$e$}
        }
        edge from parent
          node[left] {$t$}
      }
      child { node [draw] {$i$}
        child { node [draw] {$in$}
          child { node [draw] {$inn$}
            edge from parent
              node[right] {$n$}
          }
          edge from parent
            node[right] {$n$}
        }
        edge from parent
          node[right] {$i$}
      };
  \end{tikzpicture}
\end{center}

В качестве ключей могут использоваться не только строки, но и любая последовательность. Время вставки, удаления и поиска в префиксном дереве равно $O(m)$, где $m$ — длина ключа.

\subsection{Реализация}
Для реализации нам понадобятся модули \lstinline{Data.Map}, который предоставляет реализацию словаря, и \lstinline{Data.Maybe}:
\begin{hslst}{}{}
import Prelude hiding (lookup, null)

import qualified Data.Map as Map
import qualified Data.Maybe as Maybe
\end{hslst}

Тип префиксного дерева определим следующим образом:
\begin{hslst}{}{}
data Trie k v = Trie (Maybe v) (Map.Map k (Trie k v))
                deriving Show
\end{hslst}

Определим пустое дерево и функцию для проверки, пусто ли дерево или нет:
\begin{hslst}{}{}
empty :: Ord k => Trie k v
empty = Trie Nothing Map.empty

null :: Ord k => Trie k v -> Bool
null (Trie Nothing children) = Map.null children
null _                       = False
\end{hslst}

Ниже приведены функция проверки на принадлежность элемента дереву \lstinline{member} и функция поиска элемента в дереве \lstinline{lookup}.
\begin{hslst}{}{}
lookup :: Ord k => [k] -> Trie k v -> Maybe v
lookup [] (Trie value _)          = value
lookup (k : ks) (Trie _ children) = do
  next <- Map.lookup k children
  lookup ks next

member :: Ord k => [k] -> Trie k v -> Bool
member k = Maybe.isJust . lookup k
\end{hslst}

Функция вставки значения по ключу-последовательности \lstinline{insert}:
\begin{hslst}{}{}
insert :: Ord k => [k] -> v -> Trie k v -> Trie k v
insert [] value (Trie _ children) = Trie (Just value) children
insert (k : ks) value (Trie v children) =
  let next = Map.findWithDefault empty k children
      node = insert ks value next in
  Trie v $ Map.insert k node children
\end{hslst}

Напишем функцию построения дерева из списка пар ключ-значение, и проверим, правильно ли работает наша функция вставки.
\begin{hslst}{}{}
fromList :: Ord k => [([k], v)] -> Trie k v
fromList = foldl (\t (k, v) -> insert k v t) empty

main :: IO ()
main = do
  let keys = ["tea", "ted", "ten", "inn", "te", ""]
  let trie = fromList [ (k, True) | k <- keys ]
  putStrLn $ show trie
\end{hslst}

После выполнения функции \lstinline{main} мы получим следующий вывод на консоль:
\begin{plainlst}{}{}
Trie (Just True) (fromList [('i',Trie Nothing (fromList [('n',Trie Nothing (fromList [('n',Trie (Just True) (fromList []))]))])),('t',Trie Nothing (fromList [('e',Trie (Just True) (fromList [('a',Trie (Just True) (fromList [])),('d',Trie (Just True) (fromList [])),('n',Trie (Just True) (fromList []))]))]))])
\end{plainlst}

Функция удаления элемента из дерева по ключу-последовательности может быть реализована так:
\begin{hslst}{}{}
delete :: Ord k => [k] -> Trie k v -> Trie k v
delete [] (Trie _ children) = Trie Nothing children
delete (k : ks) trie@(Trie value children) =
  case Map.lookup k children of
    Just next ->
      let node = delete ks next in
      if null node
      then Trie value $ Map.delete k children
      else Trie value $ Map.insert k node children
    Nothing   -> trie
\end{hslst}

Для проверки напишем функцию, которая удаляет элементы для всех ключей из переданного списка, и проверим работоспособность функции \lstinline{delete}.
\begin{hslst}{}{}
deleteAll :: Ord k => [[k]] -> Trie k v -> Trie k v
deleteAll keys trie = foldl (flip delete) trie keys

main :: IO ()
main = do
  let keys = ["tea", "ted", "ten", "inn", "te", ""]
  let trie = fromList [ (k, True) | k <- keys ]
  putStrLn $ show $ deleteAll keys trie
\end{hslst}

После чего на консоль распечатается пустое дерево, как и ожидается:
\begin{plainlst}{}{}
Trie Nothing (fromList [])
\end{plainlst}

\section{Фильтр Блума}
\label{sec:bloom-filter}
\emph{Фильтр Блума} (\emph{Bloom filter}) — вероятностная структура данных, позволяющая компактно хранить информацию о принадлежности элемента множеству. Но при этом возможно \emph{ложноположительное сработывание}, то есть элемент в множестве не присутствует действительно, но согласно фильтру он там есть.

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

Фильтр Блума состоит из битовой карты размером $m$ и хеш-функций $h_1,...,h_k$, которые задает пользователь. Изначально все биты равны нулю. Хеш-функции должны быть независимыми и распределены равномерно.

Для добавления элемента $e$ необходимо выставить биты в битовой карте в единицу на позициях $h_1(e),...,h_k(e)$.

Для проверки принадлежности элемента множеству, необходимо проверить биты на позициях $h_1(e),...,h_k(e)$. Если хотя бы один бит равен нулю, то элемент не принадлежит множеству. Если же все биты равны единице, то элемент \emph{возможно} принадлежит множеству.

\subsection{Вероятность ложноположительного срабатывания}
Пусть хеш-функции — незивисимы и распределены равномерно, то есть выбор любой позиции по значению хеш-функции — равновероятен, и $m$ — размер битовой карты. Тогда вероятность того, что какой-то определенный бит не будет установлен данной хеш-функцией, когда добавляется элемент в множество:
\[
1 - \frac{1}{m}.
\]

Вероятность, что этот бит не будет установлен ни одной хеш-функцией, равна:
\[
\left( 1 - \frac{1}{m} \right)^k.
\]

После вставки $n$ элементов, вероятность, что данный бит все ещё равен нулю:
\[
\left( 1 - \frac{1}{m} \right)^{nk}.
\]

В таком случае верояность, что он равен единице:
\[
1 - \left( 1 - \frac{1}{m} \right)^{nk}.
\]

Пусть мы теперь пробуем проверить принадлежность элемента, который мы не добавляли в фильтр. Тогда вероятность ложноположительного срабатывания будет равна:
\[
f= \left( 1 - \left[ 1 - \frac{1}{m} \right]^{nk} \right)^k =  \left( 1 - e^{-nk / m} \right)^k,
\]
используя второй замечательный предел\footnote{$\lim_{x \to \infty} \left( 1 + \frac{1}{x} \right)^x = e$}. Из этого следует, что при уменьшении размера $m$ и увеличинии $n$ увеличивается вероятность ложноположительного срабатывания. Для того, чтобы найти оптимальное количество $k$ хеш-функций, при котором вероятность ложноположительного срабатывания будет минимальной при фиксированных $m$ и $n$, следует взять производную $f$ по $k$. Для удобства взятия производной представим $f$ следующим образом:
\[
f = e^{k\ln(1 - e^{-nk / m})}.
\]

Пусть $g = k\ln(1 - e^{-nk / m})$. Тогда производная равна:
\[
\frac{\partial g}{\partial k} = ln(1 - e^{-nk / m}) + \frac{nk}{m} \frac{e^{-nk / m}}{1 - e^{-nk / m}}
\]

Производная $g$ равна нулю при $k = \ln 2 \cdot (m / n) \simeq 0.6931 \frac{m}{n}$. При этом вероятность ложноположительного срабатывания $f = (1 / 2)^k \simeq 0.6185^{m / n}$.

\subsection{Реализация}
\begin{pylst}{}{}
class BloomFilter(object):
    def __init__(self, size, hashers):
        assert size > 0,     "size must be greater than zero"
        assert len(hashers), "at least one hash function must be provided"

        self.size    = size
        self.hashers = tuple(hashers)
        self.bitset  = 0L

    def add(self, item):
        for hasher in self.hashers:
            position = hasher(item) % self.size
            self.bitset |= 1 << position

    def __contains__(self, item):
        for hasher in self.hashers:
            position = hasher(item) % self.size
            if not (self.bitset & (1 << position)):
                return False
        return True

    def __repr__(self):
        return self.__str__()

    def __str__(self):
        binary = bin(self.bitset)
        binary = binary[2:]
        binary = '0' * (self.size - len(binary)) + binary
        return binary
\end{pylst}

Ниже — пример использования фильтра Блума:
\begin{pylst}{}{}
>>> bf = BloomFilter(64, [hash])
>>> bf.add(20)
>>> bf
0000000000000000000000000000000000000000000100000000000000000000
>>> bf.add(34)
>>> bf
0000000000000000000000000000010000000000000100000000000000000000
>>> 34 in bf
True
>>> 20 in bf
True
>>> 21 in bf
False
\end{pylst}

\section{B-деревья}
\label{sec:b-tree}
B-дерево — это сбалансированное дерево поиска, созданное для систем, которые считывают и записывают информацию относительно большими блоками. Примерами таких систем являются база данных и файловая система.

B-деревья похожи на красно-чёрные деревья, но отличаются высокой оптимизацией дисковых операций ввода-вывода. Отличаются же тем, что B-деревья могут иметь много дочерних узлов — до тысяч, так что степерь ветвления B-дерева может быть очень большой. B-деревья, как и красно-чёрные деревья, имеют высоту $O(\lg n)$, но конкретное значение высоты существенно меньше, чем у красно-чёрных деревьев, за счет большего ветвления.

\subsection{Определение B-деревьев}
B-дерево \emph{минимальной степени} $t$ — дерево, которое имеет следующие свойства:
\begin{enumerate}
  \item Каждый узел имеет не более $2t$ дочерних узлов.
  \item Каждый узел, кроме корневого, имеет по крайней мере $t$ узлов.
  \item Если дерево не пустое, то корень имеет не меньше двух дочерних узлов.
  \item Все листья находятся на одном и том же уровне, который равен высоте дерева $h$.
  \item Внутренний узел с $k$ дочерними узлами имеет $k - 1$ ключей.
\end{enumerate}

Ключи хранятся в невозрастающем порядке. Ключи разделяют поддиапозоны ключей, хранящихся в поддеревьях. Узел \emph{заполнен}, если он содержит $2t - 1$ ключей.

\subsection{Реализация}
Для вставки ключа в заполненный лист вводится новая операция — \emph{разбиение} заполненного узла на два, каждый из которых содержит по $t - 1$ ключей. \emph{Медиана}, или средний ключ,  при этом перемещается в родительский узел, где становиться разделительной точкой для двух вновь образовавшихся поддеревьев.

\lstinputlisting[style=ocamlstyle]{src/advanced-ds/btree.ml}

\section {Расширяемое хеширование}
\label{sec:ext-hashing}
Хеш-таблица, содержащая настолько большое количество записей, что их приходится располагать преимущественно во вторичном хранилище, отличается от варианта хеш-таблицы, предназначенной для структурирования данных в оперативной памяти в нескольких важных аспектах. Прежде всего, массив сегментов должен состоять из блоков, а не отдельных указателей на заголовки связанных списков.

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

В предыдущем разделе по структурам данных речь шла о \emph{статических} хеш-таблицах (static hash tables), у которых количество сегментов, или её размер, остаётся неизменным. В данном разделе речь будем идти о \emph{динамических} хеш-таблицах, а именно о \emph{расширяемом хешировании} (extendible hashing).

Ниже перечислены основные отличия расширяемого хеширования от обычных хеш-таблиц:
\begin{enumerate}
  \item Массив указателей способен к расширению. Его длина всегда сохраняется равной степени числа 2, так что на очередном шаге величения массива количество сегментов таблицы удваивается.
  \item Каждому сегменту не обязательно ставится в соответствие отдельный блок: если суммарное количество записей в нескольких сегментах не превышает допустимого числа записей в блоке, то блоки могут быть объединены.
  \item Хеш-функция $h$ вычисляет для каждого ключа последовательность из $k$ битов, где $k$ — фиксированное целое число (например, 32). Однако для номеров сегментов будет использоваться некоторое меньшее количество битов $d$, выбираемых из начала последовательности. Таким образом, длина массива сегментов составит $n = 2^d$ для любого $d \leq k$.
\end{enumerate}

В каждом блоке хранится величина $m$, определящая, какое количество битов последовательности, возвращенной хеш-функцией, используется для определения принадлежности записи блоку $B$.

Рассмотрим операции поиска по ключу, вставки и удаления.

\subsubsection{Поиск по ключу $key$}
\begin{enumerate}
  \item Вычислить $seq = h(key)$.
  \item Получить $d$ массива сегментов.
  \item Взять $d$ бит из начала $seq$. Пусть $i$ будет числом, состоящим из этих бит.
  \item Получить блок $B$ по $i$-му указателю в массиве сегментов.
  \item Получить $bkey$, который представляет собой $m$ бит последовательности $seq$, начиная с позиции $(d + 1)$.
  \item Получить необходимую запись в блоке $B$ по ключу $bkey$, если таковая присутсвует там.
\end{enumerate}

\subsubsection{Вставка записи $(key, data)$}

\begin{enumerate}
  \item Получить блок $B$, предварительно вычислив $i$.
  \item Если в блоке $B$ свободного места достаточно, вставить запись $(key, data)$ в блок $B$. Останов.
  \item В ином случае, если $m < d$, массив сегментов модификации не требует. Достаточно выполнить следующее:
    \begin{enumerate}
      \item Создать новый блок.
      \item Распределить записи, принадлежащие блоку $B$, по двум блокам, руководствуясь значением $(d + m + 1)$-го бита хеш-кода. Записи с нулём в указанной позиции хеш-кода оставить в блоке $B$, а остальные переместить в новый блок.
      \item Для нового блока и блока $B$: $m = m + 1$.
      \item Исправить значения указателей в массиве сегментов так, чтобы указатели, ранее адресовавшие блок $B$, теперь ссылались на $B$ либо на новый блок — в зависимости от значения $d + m$-го бита хеш-кода.
    \end{enumerate}

  \item Если $m = d$, то надо увеличить на единицу значение $d$. При этом длина массива сегментов удваивается. Как обновлять при этом указатели — очевидно.
  \item Повторить вставку сначала.
\end{enumerate}

\subsubsection{Удаление по ключу $key$}
\begin{enumerate}
  \item Получить запись, используя ключ $key$.
  \item Если соответсвующей записи нет, то останов с извещением о неудаче.
  \item Удалить запись.
  \item Если сумма количества записей в текущем блоке и количества записей в соседнем блоке меньше либо равна $2^m$, то объединить эти два блока следующим образом:
    \begin{enumerate}
      \item Скопировать все записи из этих двух блоков во временную область $Q$.
      \item Освободить один из двух блоков. Сделать так, чтобы все указатели, ссылавшиеся на особождённый блок, ссылались на оставшийся блок.
      \item $m = m - 1$ для оставшегося блока.
      \item Удалить все записи из блока.
      \item Вставить все записи из $Q$.
    \end{enumerate}
  \item Если каждый указатель в директории равен соседнему, то:
    \begin{enumerate}
      \item Уменьшить глубину директории на один.
      \item Уменьшить вдвое размер директории и обновить указатели очевидным образом.
    \end{enumerate}
\end{enumerate}

\begin{thebibliography}{9}

\bibitem{advanced-ds:cormen05}
  Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн,
  \emph{Алгоритмы: построение и анализ}.
  Вильямс,
  2-е изд.,
  2005.

\bibitem{advanced-ds:ulman03}
  Г. Гарсиа-Молина, Дж. Д. Ульман, Дж. Уидом,
  \emph{Системы баз данных: полный курс}.
  Вильямс,
  2003.

\bibitem{advanced-ds:okasaki99}
  C. Okasaki,
  \emph{Purely functional data structures}.
  Cambridge University Press,
  1999.

\bibitem{advanced-ds:okasaki99rb}
  C. Okasaki,
  \emph{Red-black tree in a functional setting}.
  Journal of Functional Programming,
  Volume 9 Issue 4,
  July 1999.

\bibitem{advanced-ds:bloom05}
  A. Broder, M. Metzenmacher,
  \emph{Network applications of Bloom filters: a survey}.
  2005.

\bibitem{advanced-ds:fagin79}
  R. Fagin, J. Hievergelt, N. Peppenger, H. Raymond Strong,
  \emph{Extendible hashing — a fast access method for dynamic files}.
  ACM Transactions on Database Systems 4 (3): 315–344,
  1979.

\end{thebibliography}