Implementacja Aho-Corasick C ++ 17

Oct 13 2020

Niedawno zaimplementowałem algorytm, który potrafi znaleźć wszystkie wzorce, które mogą zawierać "?" jako „dowolny znak”. Na przykład, jeśli tekst to „abrakadabra”, a wzorzec to „a? A”, wówczas mój algorytm znajdzie wzorce takie jak „aca” i „ada”. W tym celu użyłem algorytmu Aho-Corasick do wykrywania „szablonów podrzędnych” i udało się. Niemniej jednak chciałem użyć technik C ++ 17, aby uczynić mój kod nowoczesnym. Ale obawiam się, że niektóre z nich mógłbym nadużyć. Czy możesz podać mi kilka sugestii dotyczących mojego kodu?

PS Staram się trzymać stylu kodowania Google

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

Odpowiedzi

3 G.Sliepen Oct 14 2020 at 04:03

Końcowe typy zwrotne

Twoje użycie końcowych typów zwracanych wygląda bardzo niespójnie. Patrząc na przewodnik Google C ++ Style Guide, wydaje się, że zalecają ich używanie, jeśli wiodące typy zwrotów są „niepraktyczne lub znacznie mniej czytelne”. Jest to oczywiście kwestia gustu, ale radziłbym być tak konsekwentnym, jak to tylko możliwe: najpierw użyj tego samego typu wiodącego / końcowego zwracanego typu w deklaracji funkcji, jak w definicji funkcji. Po drugie, jeśli typ zwracany jest tak nieporęczny, że musisz użyć stylu końcowego, być może lepiej jest utworzyć dla niego alias typu. Na przykład:

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

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

Para wektorów a wektor par

TemplateFinder::Split()zwraca parę wektorów, ale wpisy w każdym wektorze są zawsze zgodne. Więc bardziej sensowne jest zwrócenie wektora par:

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

Uprości to również niektórych użytkowników tego wektora.

Unikaj niepotrzebnego tymczasowego przechowywania

Split()jest wywoływana tylko raz w konstruktorze, a wyniki są używane do wywołania AddSubtemplate(). Spowoduje to zmarnowanie pamięci, tworząc najpierw tymczasowy wektor. Możesz rozwiązać ten problem na kilka sposobów. Po pierwsze, możesz połączyć Split()się z konstruktorem, ponieważ oprócz przydzielenia węzła głównego jest to w zasadzie jedyna rzecz, którą robi konstruktor. Jeśli chcesz zachować Split()oddzielną funkcję, poproś ją, aby pobierała parametr wywołania zwrotnego, który jest wywoływany dla każdego znalezionego podszablonu, tak jak FindEntries()przyjmuje iterator wyjścia jako argument.

Inteligentne wskazówki

Widzę, że używasz tylko std::shared_ptrw swoim kodzie. Jest to jednak zliczanie referencji, co ma wpływ na wydajność. Powinieneś go używać tylko wtedy, gdy naprawdę tego potrzebujesz. Powinieneś std::unique_ptrzamiast tego używać tylko wskaźnika będącego właścicielem, i możesz używać pustych wskaźników dla wskaźników nie będących właścicielami, aby obiekt, o którym wiesz, nie zostanie usunięty przed ostatnim użyciem wskaźnika, który nie jest właścicielem.

Na przykład a Nodema wskaźniki potomne, które jest jego właścicielem, więc powinien std::unique_ptrdo nich używać , ale rodzic Nodebędzie zawsze żył dłużej niż jego dzieci, więc możesz użyć gołego wskaźnika do 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_;
};

Zmienna składowa root_wcale nie musi być wskaźnikiem, może to być po prostu Nodewartość. Ale aby zachować spójność z innymi przydzielonymi węzłami, możesz użyć std::unique_ptrtutaj. Zauważ, że możesz użyć inicjalizacji wartości składowej:

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

Zwróć uwagę, że po użyciu std::unique_ptrnie powinieneś już pisać takiego kodu:

auto p_current = root_;

To faktycznie ukradnie pamięć root_. Ponieważ chcesz tylko uzyskać wskaźnik, napisz:

auto p_current = root_.get();

Praktycznie wszystkie zastosowania std::shared_ptrw kodzie można zastąpić zwykłymi wskaźnikami, z wyjątkiem wskaźników do właściciela root_i Node::transitions_.

Rozważ dodanie funkcji składowych do `struct Node`

Istnieją operacje, które wykonujesz na Nodeelementach, które mogą być funkcjami składowymi struct Node. Na przykład:

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

A potem użyj tego w ten sposób:

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

Zachowaj ostrożność podczas rzutowania liczb całkowitych między znakiem i bez znaku

Widzę ten kod:

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

Będzie to działać poprawnie na architekturach 64-bitowych, ale co z architekturami 32-bitowymi, gdzie size_ttak naprawdę jest uint32_t? Możesz użyć ssize_tlub ptrdiff_ttutaj, ale być może lepiej jest po prostu całkowicie uniknąć konieczności rzucania: