Implementierung von Aho-Corasick C ++ 17
Kürzlich habe ich den Algorithmus implementiert, der alle Muster finden kann, die "?" als "irgendein Zeichen". Wenn der Text beispielsweise "Abrakadabra" und das Muster "a? A" ist, findet mein Algorithmus Muster wie "aca" und "ada". Zu diesem Zweck habe ich den Aho-Corasick-Algorithmus für die Erkennung von "Subtemplates" verwendet, und es hat funktioniert. Trotzdem wollte ich einige C ++ 17-Techniken verwenden, um meinen Code modern zu machen. Aber ich habe Angst, dass ich einige von ihnen irgendwie missbrauchen könnte. Könnten Sie mir einige Vorschläge zu meinem Code geben?
PS Ich versuche, mich an Google Codestyle zu halten
#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;
}
```
Antworten
Nachfolgende Rückgabetypen
Ihre Verwendung von nachfolgenden Rückgabetypen sieht sehr inkonsistent aus. Im Google C ++ Style Guide wird empfohlen, sie zu verwenden, wenn führende Rückgabetypen "unpraktisch oder viel weniger lesbar" sind. Das ist dann natürlich Geschmackssache, aber ich würde empfehlen, so konsistent wie möglich zu sein: Verwenden Sie in der Deklaration einer Funktion zunächst den gleichen Typ des führenden / nachfolgenden Rückgabetyps wie in der Definition der Funktion. Zweitens, wenn der Rückgabetyp so unhandlich ist, dass Sie den nachgestellten Stil verwenden müssen, ist es möglicherweise besser, einen Typalias dafür zu erstellen. Beispielsweise:
using SubTemplateList = std::pair<std::vector<std::string>, std::vector<size_t>>;
static SubTemplateList Split(const std::string& text, char splitter);
Paar von Vektoren gegen Vektor von Paaren
TemplateFinder::Split()gibt ein Paar von Vektoren zurück, aber die Einträge in jedem Vektor stimmen immer überein. Es ist also sinnvoller, einen Vektor von Paaren zurückzugeben:
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;
}
Dies vereinfacht auch einige Benutzer dieses Vektors.
Vermeiden Sie unnötigen temporären Speicher
Split()wird im Konstruktor nur einmal aufgerufen und die Ergebnisse werden zum Aufrufen verwendet AddSubtemplate(). Dies verschwendet Speicher, indem zuerst der temporäre Vektor erstellt wird. Sie können dies auf verschiedene Arten lösen. Erstens könnten Sie Split()in den Konstruktor einbinden , da dies neben der Zuweisung des Stammknotens im Grunde das einzige ist, was der Konstruktor tut. Wenn Sie Split()eine separate Funktion beibehalten möchten, lassen Sie sie einen Rückrufparameter verwenden, der für jede gefundene Untervorlage aufgerufen wird, ähnlich wie FindEntries()ein Ausgabe-Iterator als Argument verwendet wird.
Intelligente Zeiger
Ich sehe, dass Sie nur std::shared_ptrin Ihrem Code verwenden. Hierbei handelt es sich jedoch um eine Referenzzählung, die sich auf die Leistung auswirkt. Sie sollten es nur verwenden, wenn Sie es wirklich brauchen. Sie sollten verwenden, std::unique_ptranstatt nur einen Besitzzeiger zu benötigen, und Sie können bloße Zeiger für nicht besitzende Zeiger auf Objekte verwenden, von denen Sie wissen, dass sie vor der letzten Verwendung dieses nicht besitzenden Zeigers nicht gelöscht werden.
Zum Beispiel hat a untergeordnete NodeZeiger, die es besitzt, daher sollte es std::unique_ptrfür diese verwendet werden, aber das übergeordnete NodeElement eines wird seine untergeordneten Zeiger immer überleben, sodass Sie einen bloßen Zeiger verwenden können für 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_;
};
Die Mitgliedsvariable root_muss nicht einmal ein Zeiger sein, sondern kann nur ein NodeWert sein. Aus Gründen der Konsistenz mit den anderen zugewiesenen Knoten können Sie std::unique_ptrhier ein verwenden. Beachten Sie, dass Sie die Elementwertinitialisierung verwenden können:
std::unique_ptr<Node> root_ = std::make_unique<Node>();
Beachten Sie std::unique_ptr, dass Sie nach der Verwendung keinen Code mehr wie folgt schreiben sollten:
auto p_current = root_;
Dies wird tatsächlich die Erinnerung stehlen root_. Da Sie nur den Zeiger erhalten möchten, schreiben Sie:
auto p_current = root_.get();
Nahezu alle Verwendungen std::shared_ptrin Ihrem Code können durch bloße Zeiger ersetzt werden, mit Ausnahme der Zeiger root_und Node::transitions_.
Erwägen Sie das Hinzufügen von Elementfunktionen zu struct Node
Es gibt Operationen, die Sie an Nodes ausführen , die zu Mitgliedsfunktionen von gemacht werden könnten struct Node. Beispielsweise:
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();
}
};
Und dann benutze es so:
void TemplateFinder::AddSubTemplate(const std::string &subtemplate, size_t word_bias) {
...
for (char c : subtemplate) {
p_current = p_current->GetTransition(c);
}
...
}
Seien Sie vorsichtig, wenn Sie Ganzzahlen zwischen vorzeichenbehafteten und vorzeichenlosen Zahlen umwandeln
Ich sehe diesen 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())) {
...
}
Dies funktioniert auf 64-Bit-Architekturen korrekt, aber was ist mit 32-Bit-Architekturen, bei denen size_tes sich tatsächlich um eine handelt uint32_t? Sie könnten ssize_toder ptrdiff_thier verwenden, aber vielleicht ist es besser, die Notwendigkeit zu vermeiden, insgesamt zu gießen:
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()) {
...
}
}