Implementação de Aho-Corasick C ++ 17
Recentemente implementei o algoritmo, que pode encontrar todos os padrões que podem conter "?" como "qualquer personagem". Por exemplo, se o texto for "abracadabra" e o padrão for "a? A", meu algoritmo encontrará padrões como "aca" e "ada". Para isso, usei o algoritmo Aho-Corasick para detecção de "submodelos" e deu certo. No entanto, eu queria usar algumas técnicas de c ++ 17 para tornar meu código moderno. Mas eu temo que posso fazer uso indevido de alguns deles. Você poderia me dar algumas sugestões sobre o meu código?
PS Eu tento seguir o estilo de código do 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> ¤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;
}
```
Respostas
Tipos de retorno à direita
O uso de tipos de retorno à direita parece muito inconsistente. Olhando para o Guia de estilo C ++ do Google, parece que eles recomendam usá-los se os principais tipos de retorno forem "impraticáveis ou muito menos legíveis". É claro que isso é uma questão de gosto, mas eu recomendaria ser o mais consistente possível: primeiro, use o mesmo tipo de retorno inicial / final na declaração de uma função e na definição da função. Em segundo lugar, se o tipo de retorno for tão difícil de manejar, você terá que usar o estilo final, talvez seja melhor criar um alias de tipo para ele. Por exemplo:
using SubTemplateList = std::pair<std::vector<std::string>, std::vector<size_t>>;
static SubTemplateList Split(const std::string& text, char splitter);
Par de vetores vs. vetor de pares
TemplateFinder::Split()retorna um par de vetores, mas as entradas em cada vetor sempre correspondem. Portanto, faz mais sentido retornar um vetor de pares:
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;
}
Isso também simplificará alguns usuários desse vetor.
Evite armazenamento temporário desnecessário
Split()é chamado apenas uma vez no construtor e os resultados são usados para chamar AddSubtemplate(). Isso vai desperdiçar memória criando primeiro o vetor temporário. Você pode resolver isso de várias maneiras. Primeiro, você pode fundir Split()no construtor, já que, além de alocar o nó raiz, é basicamente a única coisa que o construtor faz. Se você quiser manter Split()uma função separada, faça com que ela receba um parâmetro de retorno de chamada que é chamado para cada submodelo que encontrar, algo semelhante a como FindEntries()usa um iterador de saída como um argumento.
Ponteiros inteligentes
Vejo que você só usa std::shared_ptrem seu código. No entanto, isso é uma contagem de referência, o que tem um impacto no desempenho. Você só deve usá-lo se realmente precisar dele. Você deve usar, em std::unique_ptrvez de você só precisa de um ponteiro proprietário, e pode usar ponteiros simples para ponteiros não-proprietários para objetos que você sabe que não serão excluídos antes do último uso desse ponteiro não-proprietário.
Por exemplo, a Nodetem ponteiros filhos de sua propriedade, então deve ser usado std::unique_ptrpara eles, mas o pai de a Nodesempre viverá mais que seus filhos, então você pode usar um ponteiro simples para 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_;
};
A variável de membro root_nem precisa ser um ponteiro, pode ser apenas um Nodevalor. Mas para consistência com os outros nós alocados, você pode usar um std::unique_ptraqui. Observe que você pode usar a inicialização de valor de membro:
std::unique_ptr<Node> root_ = std::make_unique<Node>();
Observe que, depois de usar std::unique_ptr, você não deve mais escrever código como este:
auto p_current = root_;
Isso realmente roubará a memória root_. Como você deseja apenas obter o ponteiro, escreva:
auto p_current = root_.get();
Praticamente todos os usos de std::shared_ptrem seu código podem ser substituídos por ponteiros vazios, exceto para os ponteiros proprietários root_e Node::transitions_.
Considere adicionar funções de membro a struct Node
Existem operações que você Noderealiza em s que podem ser transformadas em funções de membro struct Node. Por exemplo:
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();
}
};
E então use-o assim:
void TemplateFinder::AddSubTemplate(const std::string &subtemplate, size_t word_bias) {
...
for (char c : subtemplate) {
p_current = p_current->GetTransition(c);
}
...
}
Tenha cuidado ao lançar números inteiros entre assinados e não assinados
Eu vejo este código:
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())) {
...
}
Isso funcionará corretamente em arquiteturas de 64 bits, mas e as de 32 bits em que size_tna verdade existe um uint32_t? Você poderia usar ssize_tou ptrdiff_taqui, mas talvez seja melhor apenas evitar a necessidade de lançar completamente:
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()) {
...
}
}