Ukkonen алгоритм В С++


Вот ниже-это реализация Ukkoken алгоритм в C++. Пожалуйста, проверьте правильность, надежность и производительность.

#include "suffix_tree.h"
#include <cassert>
#include <iostream>
using namespace std;

class node
{
public:
    node();
    ~node();
    int m_begin;
    int m_end;
    node* m_parent;
    node* m_first_child;
    node* m_sibling;
    node* m_suffix_link;
};

class suffix_tree_impl
{
public:
    suffix_tree_impl(string s);
    ~suffix_tree_impl();
private:
    char first_char(node* node);
    int length(node* node, int implicit_end);
    string m_s;
    node* m_root;
};

node::node() : m_begin(0), m_end(0), m_parent(nullptr), m_first_child(nullptr), m_sibling(nullptr), m_suffix_link(nullptr)
{

}

node::~node()
{
    if (this->m_first_child != nullptr)
    {
        delete this->m_first_child;
    }
    if (this->m_sibling != nullptr)
    {
        delete this->m_sibling;
    }
}

suffix_tree_impl::suffix_tree_impl(string s) : m_s(s)
{
    node* node_cursor;
    int edge_cursor;
    node* next_node_cursor;
    int next_text_cursor;
    int implicit_end;
    node* last_internal_node;

    this->m_root = new node();
    node_cursor = nullptr;
    next_node_cursor = nullptr;
    last_internal_node = nullptr;
    int start = 0;
    for (int end = 1; end <= s.length(); end++)
    {
        next_node_cursor = this->m_root;
        next_text_cursor = start;
        implicit_end = end;
        for (; start < end; start++)
        {
            bool no_op_applied = false;

            node_cursor = next_node_cursor;
            start = next_text_cursor;
            edge_cursor = 0;

            int text_cursor = start;
            next_node_cursor = this->m_root;
            next_text_cursor = start + 1;
            while (text_cursor < end - 1)
            {
                int node_length = length(node_cursor, implicit_end);
                if (edge_cursor == node_length)
                {
                    if (node_cursor->m_suffix_link != nullptr)
                    {
                        next_node_cursor = node_cursor->m_suffix_link;
                        next_text_cursor = text_cursor - 1;
                    }

                    char next_char = this->m_s[text_cursor];
                    node* child_cursor = node_cursor->m_first_child;
                    while (true)
                    {
                        assert(child_cursor != nullptr);
                        if (this->first_char(child_cursor) == next_char)
                        {
                            node_cursor = child_cursor;
                            edge_cursor = 0;
                            break;
                        }
                        else
                        {
                            child_cursor = child_cursor->m_sibling;
                        }
                    }
                }
                else
                {
                    int text_move = end - 1 - text_cursor;
                    int edge_move = node_length - edge_cursor;
                    int move = text_move > edge_move ? edge_move : text_move;
                    edge_cursor += move;
                    text_cursor += move;
                }
            }

            char next_text_char = this->m_s[end - 1];
            node* search_end = nullptr;
            node* new_internal_node = nullptr;
            if (edge_cursor == length(node_cursor, implicit_end))
            {
                if (node_cursor != this->m_root && node_cursor->m_first_child == nullptr)
                {
                }
                else
                {
                    node* search = node_cursor->m_first_child;
                    bool found = false;
                    while (search != nullptr)
                    {
                        if (first_char(search) == next_text_char)
                        {
                            found = true;
                            break;
                        }
                        else
                        {
                            search = search->m_sibling;
                        }
                    }
                    if (found)
                    {
                        no_op_applied = true;
                    }
                    else
                    {
                        node* new_leaf = new node();
                        new_leaf->m_begin = end - 1;
                        new_leaf->m_parent = node_cursor;
                        new_leaf->m_sibling = node_cursor->m_first_child;
                        node_cursor->m_first_child = new_leaf;
                    }
                }
                search_end = node_cursor;
            }
            else
            {
                char next_tree_char = this->m_s[node_cursor->m_begin + edge_cursor];
                if (next_text_char == next_tree_char)
                {
                    no_op_applied = true;
                }
                else
                {
                    node* new_node = new node();
                    node* new_leaf = new node();
                    new_leaf->m_begin = end - 1;
                    new_node->m_begin = node_cursor->m_begin;
                    new_node->m_end = node_cursor->m_begin + edge_cursor;
                    node_cursor->m_begin = node_cursor->m_begin + edge_cursor;

                    new_node->m_parent = node_cursor->m_parent;
                    new_leaf->m_parent = new_node;
                    node_cursor->m_parent = new_node;

                    new_node->m_sibling = new_node->m_parent->m_first_child;
                    new_node->m_parent->m_first_child = new_node;

                    node* search = new_node;
                    while (search != nullptr)
                    {
                        if (search->m_sibling == node_cursor)
                        {
                            search->m_sibling = search->m_sibling->m_sibling;
                            break;
                        }
                        search = search->m_sibling;
                    }

                    new_node->m_first_child = new_leaf;
                    new_leaf->m_sibling = node_cursor;
                    node_cursor->m_sibling = nullptr;

                    new_internal_node = search_end = new_node;
                }
            }

            if (last_internal_node != nullptr)
            {
                assert(last_internal_node->m_suffix_link == nullptr);
                assert(search_end != nullptr);
                last_internal_node->m_suffix_link = search_end;
                last_internal_node = nullptr;
            }

            if (new_internal_node != nullptr)
            {
                last_internal_node = new_internal_node;
            }

            if (no_op_applied)
            {
                break;
            }
        }
    }
}

int suffix_tree_impl::length(node* node, int implicit_end)
{
    if (node == this->m_root)
    {
        return 0;
    }
    else if (node->m_first_child == nullptr)
    {
        return implicit_end - node->m_begin;
    }
    else
    {
        return node->m_end - node->m_begin;
    }
}

char suffix_tree_impl::first_char(node* node)
{
    return this->m_s[node->m_begin];
}

suffix_tree_impl::~suffix_tree_impl()
{
    delete this->m_root;
}

suffix_tree::suffix_tree(string s) : m_impl(new suffix_tree_impl(s))
{

}

suffix_tree::~suffix_tree()
{
    delete this->m_impl;
}


240
1
задан 31 января 2018 в 05:01 Источник Поделиться
Комментарии
2 ответа

Пару заметок об идиоматических написания кода.


  1. Проверка, что указатель не null перед удалением он излишне многословен. Если параметр delete выражение имеет значение NULL, это будет пустой по определению.

  2. Вы используете оба именования Конвенции о том, с m_ для данных членов, и открыть их через this->. То есть опять излишне многословен, так как либо выделить их как члены. Я рекомендую вам выбрать один и придерживаться его.

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

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

    for(; start < end; start++) {
    bool found = find_existing_node_for_suffix(/* ... */);
    // More things
    }

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

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


7
ответ дан 31 января 2018 в 06:01 Источник Поделиться

Я сделаю частичный отзыв, просто класс node. Там есть уроки, которые будут полезны и применимы к остальной части кода:

class node
{
public:
node();
~node();
int m_begin;
int m_end;
node* m_parent;
node* m_first_child;
node* m_sibling;
node* m_suffix_link;
};

node::node() : m_begin(0), m_end(0), m_parent(nullptr), m_first_child(nullptr), m_sibling(nullptr), m_suffix_link(nullptr)
{

}

node::~node()
{
if (this->m_first_child != nullptr)
{
delete this->m_first_child;
}
if (this->m_sibling != nullptr)
{
delete this->m_sibling;
}
}

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

Мы можем обеспечить инициализаторов для членов, и избежать необходимости писать собственные конструктора:

struct node
{
~node();
int m_begin = 0;
int m_end = 0;
node* m_parent = {};
node* m_first_child = {};
node* m_sibling = {};
node* m_suffix_link = {};
};

Деструктор дает нам подсказку, что m_first_child и m_sibling есть владеющие указатели, и что m_parent и m_suffix_link не владея. Это сигнализирует нам, что сгенерированный компилятором по умолчанию, копировать/переместить конструкторы и операторы присваивания разобьет наши инварианты (в данном случае, вызывает двойной free).

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

#include <memory>
struct node
{
int m_begin = 0;
int m_end = 0;
node* m_parent = {};
std::unique_ptr<node> m_first_child = {};
std::unique_ptr<node> m_sibling = {};
node* m_suffix_link = {};
};

Посмотрите, нет методов!

3
ответ дан 2 февраля 2018 в 09:02 Источник Поделиться