Aho-Corasick C++17实现

Question

最近我实现了这个算法，它可以找到所有可能包含"?“的模式。作为“任何角色”。例如，如果文本是"abracadabra“而模式是"a?a"，那么我的算法就会找到"aca”和"ada“这样的模式。为此，我使用Aho-Corasick算法进行“子模板”检测，并得到了结果。尽管如此，我还是想使用一些c++17技术来使我的代码更加现代化。但我担心我可能会滥用其中一些。你能就我的密码给我一些建议吗？

我试着坚持谷歌的代码

#include <algorithm>
#include <iostream>
#include <iterator>
#include <unordered_map>
#include <vector>
#include <memory>

class TemplateFinder {
private:
    /* Trie node */
    struct Node {
        bool terminal_ = false;
        size_t word_size_ = 0;
        char parent_char_ = 0;

        std::shared_ptr<Node> parent_;
        std::shared_ptr<Node> suffix_;
        std::shared_ptr<Node> shrink_suffix_;

        std::vector<size_t> word_bias_; //Subtemplate bias. Subtemplates can be repeated -> several biases
        std::unordered_map<char, std::shared_ptr<Node>> transitions_;
        std::unordered_map<char, std::shared_ptr<Node>> delta_function_;
    };

    size_t subpattern_count_ = 0;
    size_t pattern_size_;

    std::shared_ptr<Node> root_;
    char splitter_;

    void AddSubTemplate(const std::string& subtemplate, size_t word_bias);
    void ProcessShrunk(const std::shared_ptr<Node>& current_p, size_t char_pos, std::vector<size_t>& pattern_entries);

    std::shared_ptr<Node> GetSuffix(const std::shared_ptr<Node>& current_p);
    std::shared_ptr<Node> GoDelta(const std::shared_ptr<Node>& current_p, char c);
    std::shared_ptr<Node> GetShrunkSuffix(const std::shared_ptr<Node>& current_p);

    static void UpdateEntries(const std::shared_ptr<Node>& current_p, size_t char_position,
                              std::vector<size_t>& pattern_entries);

    static auto Split(const std::string& text, char splitter)
        -> std::pair<std::vector<std::string>, std::vector<size_t>>;
public:
    explicit TemplateFinder(const std::string& pattern, char splitter);

    template<typename OutputIterator>
    void FindEntries(const std::string& text, OutputIterator& out);
};

/* Adding subtemplate to trie */
void TemplateFinder::AddSubTemplate(const std::string &subtemplate, size_t word_bias) {
    auto p_current = root_;
    for (char c : subtemplate) {
        if (p_current->transitions_.find(c) == p_current->transitions_.end()) {
            p_current->transitions_[c] = std::make_shared<Node>();
            p_current->transitions_[c]->parent_ = p_current;
            p_current->transitions_[c]->parent_char_ = c;
        }
        p_current = p_current->transitions_[c];
    }
    p_current->terminal_ = true;
    p_current->word_bias_.push_back(word_bias);
    p_current->word_size_ = subtemplate.size();
    ++subpattern_count_;
}

TemplateFinder::TemplateFinder(const std::string& pattern, char splitter) : pattern_size_(pattern.size()),
                                                                            splitter_(splitter) {
    root_ = std::make_shared<Node>();
    auto [split_text, bias] = Split(pattern, splitter_);
    for (size_t i = 0; i < split_text.size(); ++i) {
        AddSubTemplate(split_text[i], bias[i]);
    }
}

/* Splitting the template to subtemplates */
auto TemplateFinder::Split(const std::string &text, char splitter)
    -> std::pair<std::vector<std::string>, std::vector<size_t>>
{
    std::vector<std::string> split_text;
    std::vector<size_t> bias; //Position of subtemplates in the template
    std::string buffer;

    size_t counter = 0;
    for (char c : text) {
        if (c == splitter && !buffer.empty()) {
            bias.push_back(counter - buffer.size());
            split_text.push_back(buffer);
            buffer = "";
        } else if (c != splitter) {
            buffer += c;
        }
        ++counter;
    }
    if (!buffer.empty()) {
        bias.push_back(counter - buffer.size());
        split_text.push_back(buffer);
    }
    return std::make_pair(split_text, bias);
}

/* Getting suffix link of the node */
auto TemplateFinder::GetSuffix(const std::shared_ptr<Node>& current_p)
    -> std::shared_ptr<Node>
{
    if (!current_p->suffix_) {
        if (current_p == root_ || current_p->parent_ == root_) {
            current_p->suffix_ = root_;
        } else {
            current_p->suffix_ = GoDelta(GetSuffix(current_p->parent_), current_p->parent_char_);
        }
    }
    return current_p->suffix_;
}

/* Delta function of automata */
auto TemplateFinder::GoDelta(const std::shared_ptr<Node>& current_p, char c)
    -> std::shared_ptr<Node>
{
    if (current_p->delta_function_.find(c) == current_p->delta_function_.end()) {
        if (current_p->transitions_.find(c) != current_p->transitions_.end()) {
            current_p->delta_function_[c] = current_p->transitions_[c];
        } else if (current_p == root_) {
            current_p->delta_function_[c] = root_;
        } else {
            current_p->delta_function_[c] = GoDelta(GetSuffix(current_p), c);
        }
    }
    return current_p->delta_function_[c];
}

/* Getting shrunk suffix link of the node */
auto TemplateFinder::GetShrunkSuffix(const std::shared_ptr<Node>& current_p)
    -> std::shared_ptr<Node>
{
    if (!current_p->shrink_suffix_) {
        std::shared_ptr<Node> suffix_link = GetSuffix(current_p);
        if (suffix_link->terminal_) {
            current_p->shrink_suffix_ = suffix_link;
        } else if (suffix_link == root_) {
            current_p->shrink_suffix_ = root_;
        } else {
            current_p->shrink_suffix_ = GetShrunkSuffix(suffix_link);
        }
    }
    return current_p->shrink_suffix_;
}

/* Main algorithm function - finding pattern in the text  */
template<typename OutputIterator>
void TemplateFinder::FindEntries(const std::string &text, OutputIterator& out) {
    std::shared_ptr<Node> current_p = root_;
    std::vector<size_t> pattern_entries(text.size());
    
    for (size_t char_pos = 0; char_pos < text.size(); ++char_pos) {
        current_p = GoDelta(current_p, text[char_pos]);
        ProcessShrunk(current_p, char_pos, pattern_entries);

        if (current_p->terminal_) {
            UpdateEntries(current_p, char_pos, pattern_entries);
        }
    }

    for (size_t char_pos = 0; char_pos < pattern_entries.size(); ++char_pos) {
        if (pattern_entries[char_pos] == subpattern_count_ && char_pos + pattern_size_ < text.size() + 1) {
            *out = char_pos;
            ++out;
        }
    }
}

/* Shrunk suffix traversal */
auto TemplateFinder::ProcessShrunk(const std::shared_ptr<Node>& current_p, size_t char_pos,
                                   std::vector<size_t> &pattern_entries) -> void
{
    for (auto shrunk_p = GetShrunkSuffix(current_p); shrunk_p != root_; shrunk_p = GetShrunkSuffix(shrunk_p)) {
        UpdateEntries(shrunk_p, char_pos, pattern_entries);
    }
}

auto TemplateFinder::UpdateEntries(const std::shared_ptr<Node> ¤t_p, size_t char_pos,
                                   std::vector<size_t> &pattern_entries) -> void
{
    auto update_entries = [current_p, char_pos, &pattern_entries](size_t bias) {
        auto pattern_pos = static_cast<int64_t>(char_pos - bias - current_p->word_size_ + 1);
        if (pattern_pos >= 0 && pattern_pos < static_cast<int64_t>(pattern_entries.size())) {
            ++pattern_entries[static_cast<size_t>(pattern_pos)];
        }
    };
    std::for_each(current_p->word_bias_.begin(), current_p->word_bias_.end(), update_entries);
}

int main() {
    std::string text_template;
    std::string text;
    std::cin >> text_template >> text;

    TemplateFinder finder(text_template, '?');

    auto out_iter = std::ostream_iterator<size_t>(std::cout, " ");
    finder.FindEntries(text, out_iter);

    std::cout << std::endl;
    return 0;
}
```

Answer 1

尾随返回类型

尾随返回类型的使用看起来非常不一致。看看Google C++样式指南，如果引导返回类型“不切实际或可读性差得多”，他们似乎建议使用它们。这当然是一个品味问题，但我建议尽可能保持一致:首先，在函数的声明中使用与函数定义相同的引导/尾随返回类型。其次，如果返回类型非常笨拙，您必须使用尾随样式，那么最好为其创建一个类型别名。例如：

using SubTemplateList = std::pair<std::vector<std::string>, std::vector<size_t>>;

static SubTemplateList Split(const std::string& text, char splitter);

对向量与

对向量

TemplateFinder::Split()返回一对向量，但是每个向量中的条目总是匹配的。因此，返回成对的向量更有意义：

using SubTemplateList = std::vector<std::pair<std::string, size_t>>;
...
SubTemplateList TemplateFinder::Split(const std::string &text, char splitter)
{
    SubTemplateList result;
    ...
        result.push_back({buffer, counter - buffer.size()});
    ...
    return result;
}

这也将简化这个向量的一些用户。

避免不必要的临时存储

在构造函数中只调用一次Split()，结果用于调用AddSubtemplate()。这将通过首先创建临时向量来浪费内存。你可以用几种方法解决这个问题。首先，您可以将Split()合并到构造函数中，因为除了分配根节点之外，这基本上是构造函数所做的唯一事情。如果您想让Split()保持一个单独的函数，那么让它为它找到的每个子模板调用一个回调参数，这有点像FindEntries()如何将输出迭代器作为参数。

智能指针

我看到您只在代码中使用std::shared_ptr。然而，这是在做引用计数，这对性能有影响。只有当你真的需要它时，你才应该使用它。您应该使用std::unique_ptr，而不是只需要一个拥有指针，并且您可以对非拥有指针使用空指针，您知道在上次使用该非拥有指针之前不会删除对象的指针。

例如，一个Node拥有它拥有的子指针，所以它应该对这些指针使用std::unique_ptr，但是Node的父指针总是比它的子指针更长，所以您可以为parent_使用一个裸指针：

struct Node {
    ...
    Node *parent_;
    Node *suffix_;
    Node *shrink_suffix_;

    std::unordered_map<char, std::unique_ptr<Node>> transitions_;
    std::unordered_map<char, Node *> delta_function_;
};

成员变量root_甚至根本不需要是指针，它可能只是一个Node值。但是为了与其他分配的节点保持一致，您可以在这里使用一个std::unique_ptr。请注意，可以使用成员值初始化：

std::unique_ptr<Node> root_ = std::make_unique<Node>();

请注意，一旦使用了std::unique_ptr，就不应该再编写这样的代码了：

auto p_current = root_;

这实际上将从root_中窃取内存。既然你只想得到指针，就写：

auto p_current = root_.get();

代码中几乎所有std::shared_ptr的使用都可以替换为裸指针，除了拥有的指针root_和Node::transitions_。

考虑向struct Node

添加成员函数

您在Nodes上做的一些操作可以成为struct Node的成员函数。例如：

struct Node
{
    ...
    Node(Node *parent, char parent_char): parent_(parent), parent_char_(parent_char) {}

    Node *GetTransition(char c) {
        if (transitions_.find(c) == transitions_.end()) {
            transitions_[c] = std::make_unique<Node>(this, c);
        }

        return transitions_[c].get();
    }
};

然后像这样使用它：

void TemplateFinder::AddSubTemplate(const std::string &subtemplate, size_t word_bias) {
    ...
    for (char c : subtemplate) {
        p_current = p_current->GetTransition(c);
    }
    ...
}

在有符号和无符号

之间转换整数时要小心

我看到这个代码：

auto pattern_pos = static_cast<int64_t>(char_pos - bias - current_p->word_size_ + 1);
if (pattern_pos >= 0 && pattern_pos < static_cast<int64_t>(pattern_entries.size())) {
    ...
}

这将在64位架构上正确工作，但是32位架构( size_t实际上是uint32_t )呢？您可以在这里使用ssize_t或ptrdiff_t，但也许更好的方法是完全避免强制转换：

if (char_pos > bias + current_p->word_size) {
    size_t pattern_pos = char_pos - bias - current_p->word_size_ + 1;
    if (pattern_pos < pattern_entries.size()) {
        ...
    }
}