Лабораторная работа 7: си-строки и префиксное дерево

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

Примеры

Очень простой

Тогда сгенерированный исходный код может выглядеть так (–1 в качестве результата означает ситуацию “строка не найдена”):

size_t token(const char *p)
{
    switch (*p++)
    {
    case 'a':
        switch (*p++)
        {
        case 'b': if (*p == '\0') return 0;
        case 'd': if (*p == '\0') return 1;
        default: return -1;
        }
    default: return -1;
    }
}

Простой

Более сложный пример. Пусть дан набор строк:

{ "a", "ab", "abc", "ad", "ada", "adc" }

size_t token(const char *p)
{
    switch (*p++)
    {
    case 'a': if (*p == '\0') return 0;

        switch (*p++)
        {
        case 'b': if (*p == '\0') return 1;

            switch (*p++)
            {
            case 'c': if (*p == '\0') return 2;
            default: return -1;
            }
        case 'd': if (*p == '\0') return 3;

            switch (*p++)
            {
            case 'a': if (*p == '\0') return 4;
            case 'c': if (*p == '\0') return 5;
            default: return -1;
            }
        default: return -1;
        }
    default: return -1;
    }
}

Средний

{ "why", "when", "then", "to", "there", "the" }

size_t token(const char *p)
{
    switch (*p++)
    {
    case 'w':
        switch (*p++)
        {
        case 'h':
            switch (*p++)
            {
            case 'y': if (*p == '\0') return 0;
            case 'e':
                switch (*p++)
                {
                case 'n': if (*p == '\0') return 1;
                default: return -1;
                }
            default: return -1;
            }
        default: return -1;
        }
    case 't':
        switch (*p++)
        {
        case 'h':
            switch (*p++)
            {
            case 'e': if (*p == '\0') return 5;

                switch (*p++)
                {
                case 'n': if (*p == '\0') return 2;
                case 'r':
                    switch (*p++)
                    {
                    case 'e': if (*p == '\0') return 4;
                    default: return -1;
                    }
                default: return -1;
                }
            default: return -1;
            }
        case 'o': if (*p == '\0') return 3;
        default: return -1;
        }
    default: return -1;
    }
}

Сложный

{
    "was",
    "water",
    "what",
    "when",
    "where",
    "while",
    "whilst",
    "why",
    "the",
    "then",
    "there",
    "these",
    "to",
    "tod",
    "today",
    "tone"
}

size_t token(const char *p)
{
    switch (*p++)
    {
    case 'w':
        switch (*p++)
        {
        case 'a':
            switch (*p++)
            {
            case 's': if (*p == '\0') return 0;
            case 't':
                switch (*p++)
                {
                case 'e':
                    switch (*p++)
                    {
                    case 'r': if (*p == '\0') return 1;
                    default: return -1;
                    }
                default: return -1;
                }
            default: return -1;
            }
        case 'h':
            switch (*p++)
            {
            case 'a':
                switch (*p++)
                {
                case 't': if (*p == '\0') return 2;
                default: return -1;
                }
            case 'e':
                switch (*p++)
                {
                case 'n': if (*p == '\0') return 3;
                case 'r':
                    switch (*p++)
                    {
                    case 'e': if (*p == '\0') return 4;
                    default: return -1;
                    }
                default: return -1;
                }
            case 'i':
                switch (*p++)
                {
                case 'l':
                    switch (*p++)
                    {
                    case 'e': if (*p == '\0') return 5;
                    case 's':
                        switch (*p++)
                        {
                        case 't': if (*p == '\0') return 6;
                        default: return -1;
                        }
                    default: return -1;
                    }
                default: return -1;
                }
            case 'y': if (*p == '\0') return 7;
            default: return -1;
            }
        default: return -1;
        }
    case 't':
        switch (*p++)
        {
        case 'h':
            switch (*p++)
            {
            case 'e': if (*p == '\0') return 8;

                switch (*p++)
                {
                case 'n': if (*p == '\0') return 9;
                case 'r':
                    switch (*p++)
                    {
                    case 'e': if (*p == '\0') return 10;
                    default: return -1;
                    }
                case 's':
                    switch (*p++)
                    {
                    case 'e': if (*p == '\0') return 11;
                    default: return -1;
                    }
                default: return -1;
                }
            default: return -1;
            }
        case 'o': if (*p == '\0') return 12;

            switch (*p++)
            {
            case 'd': if (*p == '\0') return 13;

                switch (*p++)
                {
                case 'a':
                    switch (*p++)
                    {
                    case 'y': if (*p == '\0') return 14;
                    default: return -1;
                    }
                default: return -1;
                }
            case 'n':
                switch (*p++)
                {
                case 'e': if (*p == '\0') return 15;
                default: return -1;
                }
            default: return -1;
            }
        default: return -1;
        }
    default: return -1;
    }
}

Подход к решению

В качестве средства решения данной задачи будем использовать префиксное дерево trie.

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

/// Максимально возможное число потомков одного узла префиксного дерева.
const size_t MAX_TRIE_CHILDREN = 8;
/// Узел префиксного дерева.
struct Trie_node
{
  Trie_node *children[MAX_TRIE_CHILDREN];
  size_t label[MAX_TRIE_CHILDREN];
  char prefix[MAX_TRIE_CHILDREN];

Метка используется для хранения номеров исходных строк. Значение метки “по умолчанию” задано константой NOT_FOUND и заменяется на реальный номер только в том случае, если символ prefix[i] является последним символом строки.

Если потомков меньше, чем MAX_TRIE_CHILDREN, то занята только начальная часть массивов. За последним занятым элементом prefix записан нулевой символ (код 0), который служит признаком конца массива. В начале нулевой символ записывается в первый элемент массива prefix, т.е. узел “пуст”. Это делает “конструктор по умолчанию” — специальная функция, которая автоматически вызывается при создании нового узла.

  /// "Конструктор по умолчанию": вызывается при создании узла.
  Trie_node() { prefix[0] = '\0'; }

Для добавления элемента надо найти первый нулевой символ в prefix — это будет номер свободной позиции среди потомков узла.

  /// Поиск свободной позиции в массиве потомков.
  size_t find_empty_slot()
  {
    return find_null(prefix, MAX_TRIE_CHILDREN);
  }
  
// где find_null -- свободная функция, определённая как (аналог std::strlen):
/// Найти позицию нулевого символа в массиве символов.
size_t find_null(const char *word, size_t word_len)
{
  for (size_t i = 0; i < word_len; ++i)
    if (word[i] == '\0')
      return i;
  return NOT_FOUND;
}

Для перехода к очередному потомку по заданному символу следует найти этот символ в массиве prefix, что даст номер потомка.

  /// Поиск номера потомка, отвечающего очередному символу.
  size_t find_char(char ch) const
  {
    return ::find_char(prefix, MAX_TRIE_CHILDREN, ch);
  }
  
// где find_char -- свободная функция, определённая как (аналог std::strchr):
/// Найти позицию заданного символ в массиве символов.
size_t find_char(const char *word, size_t word_len, char ch)
{
  for (size_t i = 0; i < word_len && word[i] != '\0'; ++i)
    if (word[i] == ch)
      return i;
  return NOT_FOUND;
}

Извлечь метку из узла, на котором заканчивается посимвольный поиск заданной строки можно с помощью функции find_word (для выполнения задания данной лабораторной эта функция, строго говоря, не требуется, но она несколько проще следующей функции add_word и демонстрирует “идеологию” работы с префиксным деревом):

  /// Извлечение метки, отвечающей заданному слову
  /// (с которой оно было ранее вставлено add_word).
  size_t find_word(const char *word) const
  {
    if (*word == '\0')
      return NOT_FOUND;

    auto index = find_char(*word);
    if (index == NOT_FOUND)
      return NOT_FOUND;

    // Это был последний ненулевой символ слова
    // (== последний символ си-строки)?
    if (word[1] == '\0')
      return label[index];

    // Нет -- продолжим с "хвостом" слова (рекурсия -- хвостовой вызов).
    // (Как заменить этот вызов на цикл?)
    return children[index]->find_word(word + 1);
  }

Добавить строку и отвечающую ей метку можно с помощью функции add_word:

  /// Рекурсивная операция вставки распознаваемой строки с заданной меткой lbl.
  void add_word(const char *word, size_t lbl)
  {
    if (*word == '\0')
      return;

    auto index = find_char(*word);
    if (index == NOT_FOUND)
    {
      index = find_empty_slot();
      if (index == NOT_FOUND)
      {
        assert(!"Trie: impossible to insert the next child: the node is full.");
        return;
      }

      prefix[index] = *word;
      if (index + 1 < MAX_TRIE_CHILDREN)
        prefix[index + 1] = '\0'; // The next empty slot.

      children[index] = new Trie_node;
      label[index] = NOT_FOUND; // Unassigned label at first.
    }

    if (word[1] == '\0')
      label[index] = lbl;
    else
      children[index]->add_word(word + 1, lbl);
    // Аналогично find_word: рекурсия -- хвостовой вызов,
    // как здесь заменить рекурсию на цикл?
  }

Наконец, обход дерева “сверху-вниз” “слева-направо” можно выполнить с помощью рекурсивной функции inorder:

  /// Обход поддерева слева-направо.
  void inorder(
    void (*open)(),
    void (*visit)(char, size_t),
    void (*close)())
  {
    if (prefix[0] == '\0')
      return;

    open();
    for (size_t i = 0; i < MAX_TRIE_CHILDREN && prefix[i] != '\0'; ++i)
    {
      visit(prefix[i], label[i]);
      children[i]->inorder(open, visit, close);
    }
    close();
  }

Эта функция принимает сразу три указателя на другие функции:

Задача данной лабораторной состоит в написании функций, которые можно передать в качестве параметров в inorder. В качестве примера представлены следующие функции — можно изменять их содержимое:

ofstream file("test.cpp"); // Файл для вывода результата.
char tab[7]; // Строка текущих отступов.
bool start;  // Флаг "ожидается первый потомок".

void print_open()
{
  file << '\n' << tab << "(\n";
  auto pos = find_null(tab, sizeof(tab) - 1);
  if (pos != NOT_FOUND)
    tab[pos] = '\t';
  start = true;
}

void print_visit(char ch, size_t label)
{
  file << (start? tab: ", ") << ch;
  if (label != NOT_FOUND)
    file << " [" << label << ']';
  start = false;
}

void print_close()
{
  auto pos = find_null(tab, sizeof(tab));
  if (pos != 0)
    tab[pos-1] = '\0';
  file << '\n' << tab << ")\n";
  start = true;
}

  const auto label = trie.find_word(word.c_str());

  const auto label = token(word.c_str());

(Здесь предполагается, что генерируемая функция имеет название token как в примерах.)