Suche 25 000 Wörter in einem Text
https://stackoverflow.com/questions/154365
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich brauche Vorkommen von ~ 25 000 Wörter in einem Text zu finden. Was ist die am besten geeignete Algorithmus / Bibliothek für diesen Zweck?
Zielsprache C ++
Lösung
eine Hash-Tabelle mit den Worten bauen und scannen durch den Text, für jedes Wort Nachschlagen in der Welt Tisch und stopft die benötigten Informationen (Schrittzahl, fügen Sie zu einer Positionsliste, was auch immer).
Andere Tipps
Früher habe ich einmal den Boyer-Moore-Algorithmus und es war recht schnell.
Boyer-Moore ist nicht geeignet für viele Worte effizient zu suchen. Es ist eigentlich ein sehr effizienter Algorithmus für nur das zu tun, die so genannten Wu-Manber Algorithmus. Ich werde eine Referenzimplementierung posten. Beachten Sie jedoch, dass ich das vor einiger Zeit tat nur für Ausbildungszwecke. Daher ist die Umsetzung nicht wirklich geeignet für die direkte Nutzung und kann auch effizienter gemacht werden.
Es nutzt auch die stdext::hash_map vom Dinkumware STL. Subsitute mit std::tr1::unordered_map oder einer entsprechenden Implementierung.
Es ist eine Erklärung des Algorithmus in einem Vorlesungsskript aus einem Vortrag an der Freien Universität Berlin, gehalten von Knut Reinert.
Die Originalpapier auch online (fand es einfach wieder), aber ich don‘ t besonders wie der Pseudo-Code dort vorgestellt.
#ifndef FINDER_HPP
#define FINDER_HPP
#include <string>
namespace thru { namespace matching {
class Finder {
public:
virtual bool find() = 0;
virtual std::size_t position() const = 0;
virtual ~Finder() = 0;
protected:
static size_t code_from_chr(char c) {
return static_cast<size_t>(static_cast<unsigned char>(c));
}
};
inline Finder::~Finder() { }
} } // namespace thru::matching
#endif // !defined(FINDER_HPP)
#include <vector>
#include <hash_map>
#include "finder.hpp"
#ifndef WUMANBER_HPP
#define WUMANBER_HPP
namespace thru { namespace matching {
class WuManberFinder : public Finder {
public:
WuManberFinder(std::string const& text, std::vector<std::string> const& patterns);
bool find();
std::size_t position() const;
std::size_t pattern_index() const;
private:
template <typename K, typename V>
struct HashMap {
typedef stdext::hash_map<K, V> Type;
};
typedef HashMap<std::string, std::size_t>::Type shift_type;
typedef HashMap<std::string, std::vector<std::size_t> >::Type hash_type;
std::string const& m_text;
std::vector<std::string> const& m_patterns;
shift_type m_shift;
hash_type m_hash;
std::size_t m_pos;
std::size_t m_find_pos;
std::size_t m_find_pattern_index;
std::size_t m_lmin;
std::size_t m_lmax;
std::size_t m_B;
};
} } // namespace thru::matching
#endif // !defined(WUMANBER_HPP)
#include <cmath>
#include <iostream>
#include "wumanber.hpp"
using namespace std;
namespace thru { namespace matching {
WuManberFinder::WuManberFinder(string const& text, vector<string> const& patterns)
: m_text(text)
, m_patterns(patterns)
, m_shift()
, m_hash()
, m_pos()
, m_find_pos(0)
, m_find_pattern_index(0)
, m_lmin(m_patterns[0].size())
, m_lmax(m_patterns[0].size())
, m_B()
{
for (size_t i = 0; i < m_patterns.size(); ++i) {
if (m_patterns[i].size() < m_lmin)
m_lmin = m_patterns[i].size();
else if (m_patterns[i].size() > m_lmax)
m_lmax = m_patterns[i].size();
}
m_pos = m_lmin;
m_B = static_cast<size_t>(ceil(log(2.0 * m_lmin * m_patterns.size()) / log(256.0)));
for (size_t i = 0; i < m_patterns.size(); ++i)
m_hash[m_patterns[i].substr(m_patterns[i].size() - m_B)].push_back(i);
for (size_t i = 0; i < m_patterns.size(); ++i) {
for (size_t j = 0; j < m_patterns[i].size() - m_B + 1; ++j) {
string bgram = m_patterns[i].substr(j, m_B);
size_t pos = m_patterns[i].size() - j - m_B;
shift_type::iterator old = m_shift.find(bgram);
if (old == m_shift.end())
m_shift[bgram] = pos;
else
old->second = min(old->second, pos);
}
}
}
bool WuManberFinder::find() {
while (m_pos <= m_text.size()) {
string bgram = m_text.substr(m_pos - m_B, m_B);
shift_type::iterator i = m_shift.find(bgram);
if (i == m_shift.end())
m_pos += m_lmin - m_B + 1;
else {
if (i->second == 0) {
vector<size_t>& list = m_hash[bgram];
// Verify all patterns in list against the text.
++m_pos;
for (size_t j = 0; j < list.size(); ++j) {
string const& str = m_patterns[list[j]];
m_find_pos = m_pos - str.size() - 1;
size_t k = 0;
for (; k < str.size(); ++k)
if (str[k] != m_text[m_find_pos + k])
break;
if (k == str.size()) {
m_find_pattern_index = list[j];
return true;
}
}
}
else
m_pos += i->second;
}
}
return false;
}
size_t WuManberFinder::position() const {
return m_find_pos;
}
size_t WuManberFinder::pattern_index() const {
return m_find_pattern_index;
}
} } // namespace thru::matching
Beispiel für die Verwendung:
vector<string> patterns;
patterns.push_back("announce");
patterns.push_back("annual");
patterns.push_back("annually");
WuManberFinder wmf("CPM_annual_conference_announce", patterns);
while (wmf.find())
cout << "Pattern \"" << patterns[wmf.pattern_index()] <<
"\" found at position " << wmf.position() << endl;
Bloom Filter kann die beste Wahl sein. Sie initialisieren Sie einen Filter, mit Ihren Suchbegriffen, dann während corpus lesen können schnell überprüfen, ob jede Arbeit im Filter ist.
Es ist sehr platzsparende, viel besser als einfach jedes Wort Hashing: mit einer 1% falsch-positiven Rate sollte es nur 9,6 Bits pro Element erfordern. Die falsch-positive Rate wird um einen Faktor von 10 für jede zusätzlichen 4,8 Bits pro Element reduziert. Man vergleiche dies in einfachem Hashing, die üblicherweise sizeof (int) == 32 Bits pro Element benötigt.
Ich habe eine Implementierung in C # hier: http://www.codeplex.com/bloomfilter
Hier ist ein Beispiel, demonstriert seine Verwendung mit Strings:
int capacity = 2000000; // the number of items you expect to add to the filter
Filter<string> filter = new Filter<string>(capacity);
filter.Add("Lorem");
filter.Add("Ipsum");
if (filter.Contains("Lorem"))
Console.WriteLine("Match!");
, wenn der Korpus so groß ist, versuchen Sie es auf diese Weise zu optimieren:
Berechnen eines Hash von jedem Wort Sie überprüfen müssen, um jede Zuordnung eines ganzzahligen Primzahl verkohlen und dann jede Zahl Multiplizieren, speichere jeden Nummer-> Wort in einem multimap (Sie für mehrere Wert auf einzelne Taste ermöglichen, müssen)
, während die Wortliste Abtastung berechnet den Hash in die gleichen Art und Weise für jedes Wort, dann das Wort erhalten, (e) in Verbindung mit der berechneten Taste auf der hashmap. mit ganzen Zahlen als Schlüssel, haben Sie eine Abfrage von O (1); So kann man in einem wirklich schnellen Weg, wenn das verarbeitete Wort etwas Anagramm hat (Sie Zeichen multipliziert) in der Karte finden.
erinnern: Sie sind im multimap die Menge des Wortes gespeichert, dass gleichen Hash mit, so dass Sie jetzt ein Spiel in diesem stark reduzierten Satz benötigen. Sie brauchen diese zusätzliche Prüfung als einfach Existenz der ganzen Zahl auf der Karte nicht in dem zugehörigen Satz auf die Existenz des Wortes zu: Wir verwenden hier Hashing den Rechenraum des Problems zu reduzieren, aber dies führt Kollision, die müssen vereindeutigt Überprüfung auf jedem identifizierten Anagramme werden.
Mit dem Aho-Corasick Algorithmus . Es wurde für diese Anwendung hergestellt. Sie müssen nur einmal jeden Buchstaben in Ihrem Suchtext lesen. Ich habe vor kurzem eingeführt und verwendet es mit sehr guten Ergebnissen.
Wie Javier sagt, ist die einfachste Lösung ist wahrscheinlich eine Hash-Tabelle.
In C ++ kann dies einen STL-Satz implementiert werden. Zuerst fügen Sie die 25.000 Testworte zu dem Satz, und dann im Text durch jedes Wort scannen, mit set.find (current_word) zu beurteilen, ob das Wort unter den 25.000 Testworten ist.
set.find ist logarithmisch schnell, also 25.000 Testwörter sollte nicht zu groß sein. Der Algorithmus ist offensichtlich in der Anzahl der Wörter im Text linear ist.
Wenn der Text Sie suchen, sehr groß ist, dann könnte es sich lohnen, eine Vorverarbeitung tun. Montieren Ihre 25.000 Wörter in eine TRIE
Scannenan den Anfang des ersten Wortes im Text, und starten Sie den TRIE zu Fuß, wie Sie durch den Buchstaben des Wortes gehen. Wenn es kein Übergang in Ihrem TRIE ist, zu Beginn des nächsten Wortes überspringt und mit der Wurzel des TRIE zurück. Wenn Sie das Ende des Wortes zu erreichen, und du bist auf einem Wort-Endknoten in der TRIE, haben Sie eine Übereinstimmung gefunden. Wiederholen Sie für jedes Wort im Text.
Wenn der Text nur groß ist (und nicht sehr groß), dann einfach jedes Wort in einer Hash-Tabelle aufzublicken ist wahrscheinlich ausreichend.
viceBerg sagt:
Früher habe ich einmal den Boyer-Moore-Algorithmus und es war recht schnell.
Mit Boyer-Moore, nicht Sie in der Regel einen Textblock für eine einzigen string gesucht?
Für eine einfache Lösung zu implementieren, mit der Hash-Tabelle Ansatz von Javier vorgeschlagen gehen. Die Bloom Filter vorgeschlagen von FatCat1111 sollte auch funktionieren ... je nach den Zielen.
sein kann Ihre erste Dictionnary (die 25.000 Worte) in einer Berkeley-DB-Hash-Tabelle auf der Festplatte zu speichern, dass Sie wahrscheinlich direkt von c verwenden können / c ++ (ich weiß, Sie es von Perl tun können), und für jedes Wort in der Text, abfragen, wenn es in der Datenbank vorhanden ist.
Sie können auch den Text sortieren und die Wortliste alphabetisch. Wenn Sie zwei sortierten arraysyou leicht die Spiele in linearer Zeit finden kann.
Sie möchten einen Ternary Search Baum . Eine gute Implementierung kann hier .
Aho-Corasick Algorithmus speziell für diesen Zweck gebaut. Sofort für viele Wörter suchen
