5
\$\begingroup\$

Recently I implemented the algorithm, that can find all the patterns which may contain "?" as "any character". For example, if the text is "abracadabra" and the pattern is "a?a", then my algorithm finds patterns like "aca" and "ada". For that purpose, I was using the Aho-Corasick algorithm for "subtemplates" detection, and it worked out. Nevertheless, I wanted to use some c++17 techniques to make my code modern. But I am afraid that I could kind of misuse some of them. Could you give me some suggestions on my code?

P.S. I try to stick to Google codestyle

#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> &current_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;
}
```
\$\endgroup\$
  • \$\begingroup\$ Please don't vandalize your post by removing most of the code after receiving answers. \$\endgroup\$ – Mast Oct 18 at 8:25
3
\$\begingroup\$

Trailing return types

Your use of trailing return types looks very inconsistent. Looking at the Google C++ Style Guide, it seems that they recommend using them if leading return types are "impractical or much less readable". That is of course a matter of taste then, but I would recommend being as consistent as possible: first, use the same type of leading/trailing return type in the declaration of a function as in the definition of the function. Second, if the return type is so unwieldly you have to use the trailing style, perhaps it is better to create a type alias for it. For example:

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

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

Pair of vectors vs. vector of pairs

TemplateFinder::Split() returns a pair of vectors, but the entries in each vector always match up. So it makes more sense to return a vector of pairs:

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;
}

This will simplify some users of this vector as well.

Avoid unnecessary temporary storage

Split() is only called once in the constructor, and the results are used to call AddSubtemplate(). This will waste memory by first creating the temporary vector. You could solve this in several ways. First, you could merge Split() into the constructor, since apart from allocating the root node, that's basically the only thing the constructor does. If you want to keep Split() a separate function, then have it take a callback parameter that is called for each subtemplate it finds, kind of like how FindEntries() takes an output iterator as an argument.

Smart pointers

I see you only use std::shared_ptr in your code. However, this is doing reference counting, which has an impact on performance. You should only use it if you are really need it. You should use std::unique_ptr instead of you only need an owning pointer, and you can use bare pointers for non-owning pointers to object you know will not be deleted before the last use of that non-owning pointer.

For example, a Node has child pointers that it owns, so it should use std::unique_ptr for those, but the parent of a Node will always outlive its children, so you can use a bare pointer for 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_;
};

The member variable root_ doesn't even have to be a pointer at all, it could just be a Node value. But for consistency with the other allocated nodes, you could use a std::unique_ptr here. Note that you can use member value initialization:

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

Note that once you use std::unique_ptr, you shouldn't write code like this anymore:

auto p_current = root_;

This will actually steal the memory from root_. Since you just want to get the pointer, write:

auto p_current = root_.get();

Virtually all uses of std::shared_ptr in your code can be replaced with bare pointers, except for the owning pointers root_ and Node::transitions_.

Consider adding member functions to struct Node

There are operations you do on Nodes that could be made member functions of struct Node. For example:

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();
    }
};

And then use it like this:

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

Be careful when casting integers between signed and unsigned

I see this code:

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())) {
    ...
}

This will work correctly on 64-bit architectures, but what about 32-bit ones where size_t is actually a uint32_t? You could use ssize_t or ptrdiff_t here, but perhaps better is to just avoid the need to cast altogether:

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()) {
        ...
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Wow, really great suggestions, thanks so much for your help! \$\endgroup\$ – mamamialogic Oct 14 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.