Implementación de Aho-Corasick C ++ 17
Recientemente implementé el algoritmo, que puede encontrar todos los patrones que pueden contener "?" como "cualquier personaje". Por ejemplo, si el texto es "abracadabra" y el patrón es "a? A", entonces mi algoritmo encuentra patrones como "aca" y "ada". Para ese propósito, estaba usando el algoritmo Aho-Corasick para la detección de "subplantillas" y funcionó. Sin embargo, quería usar algunas técnicas de C ++ 17 para hacer mi código moderno. Pero me temo que podría hacer un mal uso de algunos de ellos. ¿Podrías darme algunas sugerencias sobre mi código?
PD: intento ceñirme al estilo de código de 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;
}
```
Respuestas
Tipos de devoluciones finales
Su uso de tipos de retorno finales parece muy inconsistente. Al mirar la Guía de estilo de Google C ++, parece que recomiendan usarlos si los tipos de retorno principales son "poco prácticos o mucho menos legibles". Eso es, por supuesto, una cuestión de gustos, pero recomendaría ser lo más coherente posible: primero, use el mismo tipo de retorno inicial / final en la declaración de una función que en la definición de la función. En segundo lugar, si el tipo de retorno es tan difícil de manejar que tiene que usar el estilo final, quizás sea mejor crear un alias de tipo para él. Por ejemplo:
using SubTemplateList = std::pair<std::vector<std::string>, std::vector<size_t>>;
static SubTemplateList Split(const std::string& text, char splitter);
Par de vectores frente a vector de pares
TemplateFinder::Split()devuelve un par de vectores, pero las entradas de cada vector siempre coinciden. Entonces tiene más sentido devolver un vector 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;
}
Esto también simplificará a algunos usuarios de este vector.
Evite el almacenamiento temporal innecesario
Split()solo se llama una vez en el constructor, y los resultados se utilizan para llamar AddSubtemplate(). Esto desperdiciará memoria creando primero el vector temporal. Puede resolver esto de varias maneras. Primero, podría fusionarse Split()en el constructor, ya que además de asignar el nodo raíz, eso es básicamente lo único que hace el constructor. Si desea mantener Split()una función separada, haga que tome un parámetro de devolución de llamada que se llame para cada subplantilla que encuentre, algo así como cómo FindEntries()toma un iterador de salida como argumento.
Punteros inteligentes
Veo que solo usas std::shared_ptren tu código. Sin embargo, esto está haciendo un recuento de referencias, lo que tiene un impacto en el rendimiento. Solo debe usarlo si realmente lo necesita. Debe usar en std::unique_ptrlugar de que solo necesita un puntero propietario, y puede usar punteros simples para punteros no propietarios para objetos que sabe que no se eliminarán antes del último uso de ese puntero no propietario.
Por ejemplo, a Nodetiene punteros secundarios que le pertenecen, por lo que debería usarlos std::unique_ptr, pero el padre de a Nodesiempre sobrevivirá a sus hijos, por lo que puede usar un puntero simple 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_;
};
La variable miembro root_ni siquiera tiene que ser un puntero en absoluto, podría ser simplemente un Nodevalor. Pero para mantener la coherencia con los otros nodos asignados, puede usar un std::unique_ptrhere. Tenga en cuenta que puede usar la inicialización de valor de miembro:
std::unique_ptr<Node> root_ = std::make_unique<Node>();
Tenga en cuenta que una vez que lo use std::unique_ptr, ya no debería escribir código como este:
auto p_current = root_;
Esto realmente le robará la memoria root_. Como solo desea obtener el puntero, escriba:
auto p_current = root_.get();
Prácticamente todos los usos de std::shared_ptren su código se pueden reemplazar con punteros desnudos, excepto los punteros propietarios root_y Node::transitions_.
Considere agregar funciones miembro a struct Node
Hay operaciones que realiza en Nodes de las que se podrían convertir en funciones miembros struct Node. Por ejemplo:
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();
}
};
Y luego úsalo así:
void TemplateFinder::AddSubTemplate(const std::string &subtemplate, size_t word_bias) {
...
for (char c : subtemplate) {
p_current = p_current->GetTransition(c);
}
...
}
Tenga cuidado al convertir números enteros entre firmados y no firmados
Veo 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())) {
...
}
Esto funcionará correctamente en arquitecturas de 64 bits, pero ¿qué pasa con las de 32 bits, donde size_thay realmente un uint32_t? Podrías usar ssize_to ptrdiff_taquí, pero quizás sea mejor simplemente evitar la necesidad de lanzar por completo:
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()) {
...
}
}