Программы для строк

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

Мы предполагаем, что читатель знаком с языком программирования Си; его "библией" является книжка Кернигана и Ричи [10]. В Си символы представляются кодами - целыми числами, которые легко сравнивать. Строки представляются векторами из символов. Структуры и теоремы, приведенные ранее, применяются непосредственно к множествам строк фиксированной длины. Стандарт Си, однако, предусматривает и строки с нефиксированной длиной: конец такой строки обозначается специальным null-символом, код которого - целое число нуль.

Построим функцию на Си для быстрой сортировки строк (см. приложение А). Главная сортирующая функция имеет следующий прототип:

   void ssort1main(char *x[], int n);

В нее передается массив x из n указателей на символьные строки; она должна переставить указатели таким образом, чтобы строки были расположены в лексикографическом порядке. Мы введем вторую функцию, параметрами которой будут оба этих аргумента плюс дополнительный аргумент целого типа h, отвечающий за "глубину" сравнений - номера сравниваемых символов. Алгоритм останавливается, когда входной вектор содержит не более одной строки, либо когда текущая глубина выйдет за границы имеющихся строк.

В сортирующей функции используется следующий вспомогательный макрос.

   #define swap(a, b) { char *t=x[a]; 
        x[a]=x[b]; x[b]=t; }
   #define i2c(i) x[i][dept h]

Макрос swap переставляет два указателя в массиве, а макрос i2c («целое в символ») возвращает символ "глубины" h строки x[i]. Функция vecswap перемещает последовательности одинаковых элементов из их временных положений в концах массива на нужные места в середине.

   void vecswap(int i, int j, int n, char *x[])
   {
      do {
         swap(i, j);
         i++;
         j++;
      } while(--n);
   }

Полный алгоритм сортировки вы найдете в программе 1; он близок к коду, представленному Бентли и Макилроем [2]. Вызывающая функция алгоритма:

   void ssort1main(char *x[], int n)
   {
      ssort 1(x, n, 0);
   }

После разбиения мы рекурсивно сортируем сегменты больших и меньших, а сегмент равных сортируем, если соответствующий символ не равен нулю.

Мы можем увеличить эффективность программы 1 стандартными методами, они описаны, например, у Седжвика [21]. Алгоритмические ускорения включают сортировку вставкой маленьких подмассивов и разбиение вокруг медиан трех элементов (а в больших массивах - медианы трех медиан трех элементов), используя теорему 7. В стандартные приемы языка Си входит замена индексов массива указателями. Вот таблица, где содержится число секунд, требуемых для сортировки файла words из 72275 слов и 696436 символов (файл можно найти на сайте авторов статьи http://www.cs.princeton.edu/~rs/strings - прим. перев.).

В третьем столбце содержится время работы системной функции qsort, а в четвертом - время программы 1. Наш простой код во всех случаях не медленнее, а иногда и заметно быстрее, чем системные функции (предназначенные для общих целей, однако предположительно сильно оптимизированные). Пятый столбец рапортует о времени работы нашей улучшенной сортировки, которая всегда существенно быстрее простой версии. В качестве контрольной в последнем столбце приводятся времена для сильно оптимизированной сортировки, коды которой можно найти у Макилроя, Бостика и Макилроя [15]; это самая быстрая из известных нам сортировок строк.

   void ssort1(char *x[], int n, int depth)
   {
       int    a, b, c, d, r, v;
       if (n <= 1)
          return;
       a = rand() % N;
       swap(0, a);
       v = i2c(0);
       a = b = 1;
       c = d = n-1;
       for (;;) {
          while (b <= c && (r = i2c(b)-v) <= 0) {
             if (r == 0) {
                swap(a, b); a++;
             }
             b++;
          }
          while (b <= c && (r = i2c(c)-v) >= 0) {
             if (r == 0) { swap(c, d); d--; }
                c--;
          }
          if (b > c) break;
          swap(b, c);
          b++;
          c--;
       }
       r = min(a, b-a);     vecswap(0, b-r, r, x);
       r = min(d-c, n-d-1); vecswap(b, n-r, r, x);
       r = b-a; ssort1(x, r, depth);
       if (i2c(r) != 0)
          ssort1(x + r, a + n-d-1, depth+1);
       r = d-c; ssort1(x + n-r, r, depth);
   }

Мы также запустили четыре сортировки на двух наборах данных библиотечных номеров, используемых в DIMACS Implementation Challenge (файл dictcalls также можно найти на сайте http://www.cs.princeton.edu/~rs/strings - прим. перев.). Мы извлекли из каждого файла множество уникальных ключей (около 86,000 в каждом файле), каждый из который является номером карточки (например, ), ключи в среднем имеют длину 22.5 символов. На машинах MIPS, наша оптимизированная сортировка оказалась на 20 процентов быстрее поразрядной сортировки; на машинах Intel, она на несколько процентов медленнее. Быстрая сортировка с составными ключами может оказаться быстрее поразрядной сортировки и в других ситуациях.

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

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

   typedef struct tnode *Tptr;
   typedef struct tnode {
      char splitchar;
      Tptr lokid, eqkid, hikid;
   } Tnode;

В узле хранится расщепляющее значение splitchar и три указателя на поддеревья. Корень дерева объявлен как Tptr root;.

   int search1(char *s)
   {
      Tptr p;
      p = root;
      while (p) {
         if (*s < p->splitchar)
            p = p->lokid;
         else if (*s == p->splitchar) {
            if (*s++ == 0)
               return 1;
            p = p->eqkid;
         } else
            p = p->hikid;
      }
      return 0;
   }

Tptr insert1(Tptr p, char *s)
{
   if (p == 0) {
      p = (Tptr) malloc(sizeof(Tnode));
      p->splitchar = *s;
      p->lokid = p->eqkid = p->hikid = 0;
   }
   if (*s < p->splitchar)
      p->lokid = insert1(p->lokid, s);
   else if (*s == p->splitchar) {
      if (*s != 0)
         p->eqkid = insert1(p->eqkid, ++s);
   } else
      p->hikid = insert1(p->hikid, s);
   return p;
}

Программа 2 возвращает 1, если строка s присутствует в дереве, и 0 в противном случае. Она начинает с корня, и спускается вниз по дереву. Ветви lokid и hikid очевидны. Перед тем, как пойти по ветви eqkid, программа смотрит на текущий символ и возвращает 1, если он является символом конца строки 0. По завершении цикла мы знаем, что прошли дерево, но все еще находимся в пределах строки, так что возвращаем 0.

Программа 3 вставляет в дерево новую строку (и ничего не делает, если она там уже есть). Оператор root = insert (root, s) вставляет строку s. Первая ветвь if срабатывает, когда встречен конец дерева. В этом случае создается новый узел, он инициализируется, после чего работает регулярная часть. В последующем коде берется подходящая ветвь, но ветвь к eqkid срабатывает, только если строка еще не кончилась.

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

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

Теорема 11. Количество узлов в троичном дереве поиска определяется совокупностью узлов и не зависит от порядка, в котором узлы вставляются.

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

Обратите внимание, что у стандартного бора поиска (без уплотнения узлов) будет ровно то же количество узлов. В использованном для экспериментов множестве данных число узлов составляет только около 41 процента от количества символов.

Средняя длина слова (включая разделители) составляет 696436/72275 9.64 символов. Среднее число ветвей "равно" при успешно завершившемся (успешном) поиске равно примерно 9.64, так как каждый вводимый символ сравнивается с равным элементом один раз. Сбалансированное дерево в качестве корня поддерева всегда выбирает медиану этого набора. В таком дереве число избыточных ("меньше" и "больше") сравнений равно всего лишь 8.30 (около половины границы для худшего случая, равной 16, согласно теореме 5), так что общее число сравнений составляет как раз 17.94.

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

Четвертая строка таблицы описывает вставку слов в словарном порядке (без упорядочения по заглавным буквам и специальным символам). Две последние строки описывают вставку строк в порядке сортировки и в обратном сортировке порядке. При этом поиск замедляется не больше, чем в четыре раза; в бинарном дереве поиска они поиск замедляется более, чем в 2000 раз. Троичные деревья поиска оказались вполне устойчивыми.

Мы провели простые эксперименты, сравнивая троичное дерево поиска с другими описанными Кнутом [11] структурами, предназначенными для ведения таблиц имен. Мы сначала исследовали бинарный поиск, который можно рассматривать как реализацию сбалансированных двоичных деревьев. Для того же самого входного множества бинарный поиск в среднем использует 15.19 сравнений строк, и исследует 51.74 символа (в среднем при каждом сравнении строк требовалось проверить 3.41 символов). На всех компьютерах, на которых мы проводили эксперименты, высоко оптимизированный бинарный поиск требовал примерно вдвое больше времени, чем программа 2 (на турнирном дереве).

Хеширование является типичной реализацией таблиц имен. Чтобы представить n строк, мы использовали хеш-таблицы размера tablesize = n с списком для разрешения коллизий. Нижеследующая хеш-функция взята из раздела 6.6 "библии" Кернигана и Ричи [10]; она довольно эффективна и дает хороший разброс.

   int hashfunc(char *s)
   {
      unsigned n = 0;
      for ( ; *s; s++)
      n = 31 * n + *s;
      return n % tablesize;
   }

Вот тело функции поиска:

   for (p = tab[hashfunc(s)]; p; p = p->next)
      if(strcnp(s, p->str) = = 0)
         return 1;
   return 0;

Для более честного измерения времени мы заменили функцию, сравнивающую строки, на inline-код (так что и хеширование, и поиск по дереву используют один стиль кодирования).

На том же словаре средний успешный хеш-поиск требует 1.50 сравнений строк (вызовов функции strcnp) и 10.17 сравниваемых символов (успешный поиск требует одного сравнения с хранимой строкой, и половины сравнения со строкой перед ней, которое почти всегда кончается на первом символе). Кроме того, в каждом поиске надо вычислить хеш-функцию, которой обычно приходится "потрогать" каждый символ входной строки.

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

Числа означают количество секунд, требуемых для выполнения поиска каждого слова в словаре. Для успешных поисков обе структуры дают сравнимые времена. Безуспешные поиски мы генерировали увеличением на 1 кода первого символа в слове (так, слово bat превращалось в cat, а слово cat - в несуществующее слово dat). Троичные деревья поиска оказались быстрее хеширования как для этой простой модели, так и для других. Модели для безуспешного поиска зависят от приложения, однако похоже, что троичные деревья поиска при безуспешном поиске окажутся быстрее хеширования, так как они могут обнаружить несовпадения после проверки нескольких первых символов, в то время как в хешировании участвует весь ключ.

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

Функция insert в программе 3 оставляет большой простор для улучшения. Вставка с помощью турнирного дерева (сначала вставляется медианный элемент, а затем рекурсивно вставляются меньший и больший элементы) представляет разумный компромисс между временами построения и поиска. Заменив вызовы функции malloc статическим буфером для размещения узлов, мы сведем практически к нулю время, затрачиваемое на распределение памяти. Ускорить программу помогают также другие обычные методы: преобразование рекурсии в итерацию, работа с указателями на указатели, переупорядочивание проверок, сохранение разности при сравнении, и расщепление одного цикла на два. Объединение этих методов ускорило программу 3 вдвое на всех рассмотренных нами машинах, и гораздо сильнее на оборудовании с медленным malloc. В наших экспериментах цена вставки всех слов никогда не превышала цену поиска всех слов с помощью программы 2 более, чем на пятьдесят процентов. Эффективная программа вставки занимает 35 строк на Си, ее можно найти на упоминавшейся ранее Web-странице.

Основной недостаток троичных деревьев поиска по сравнению с хешированием заключается в их требованиях к памяти. Наше троичное дерево поиска использует 285807 16-байтовых узлов, что в сумме составляет 4.573 мегабайта. Хеширование использует хеш-таблицу из 72275 указателей, 72275 8-байтовых узлов, и 696436 байтов текста, что дает 1564 мегабайтов. Другое представление троичных деревьев поиска более эффективно расходует память: когда поддерево содержит строку, мы храним только указатель на нее (и в каждом узле тратится три бита, сообщающие, на указывают его потомки - на узлы или на строки). Это приводит к более медленному и сложному коду, однако сокращает количество узлов в дереве с 285807 до 94952, что ближе к памяти, требуемой при хешировании.

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

Итак, похоже, что троичные деревья поиска сочетают в себе лучшие стороны двух методов: низкие накладные расходы бинарных деревьев поиска (расход памяти и время работы) и эффективность боров при работе с символами. Основная проблема при применении боров на практике состоит в том, чтобы избежать расхода памяти на почти пустые узлы. Троичные деревья поиска можно рассматривать как реализацию боров, элегантно адаптированную для этого случая за счет небольшого увеличения работы с полными узлами. Кроме того, троичные деревья поиска легко реализовывать; например, сравните наш код с реализацией «хешированных боров» у Кнута [3].

Троичные деревья поиска больше года используются для представления английских словарей в коммерческой системе Optical Character Recognition (OCR), созданной в Bell Labs. Деревья оказались быстрее хеширования, и они элегантно справляются с 34000-символьным множеством Unicode Standard. Кроме того, разработчики экспериментировали с использованием частичных совпадений при поиске слов: оказалось, что следует заменять символы с низкой вероятностью распознавания символом «не имеет значения», «любой».