cerca 25000 parole in un testo
https://stackoverflow.com/questions/154365
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Devo trovare occorrenze di ~ 25000 parole in un testo. Qual è l'algoritmo / libreria più adatto a questo scopo?
la lingua di destinazione è C ++
Soluzione
crea una tabella hash con le parole ed esegui la scansione del testo, per ogni ricerca di parole nella tabella del mondo e riempi le informazioni necessarie (conteggio degli incrementi, aggiungi a un elenco di posizioni, qualunque cosa).
Altri suggerimenti
Una volta ho usato l'algoritmo Boyer-Moore ed è stato abbastanza veloce.
Boyer-Moore non è adatto per la ricerca efficiente di molte parole. In realtà esiste un algoritmo molto efficiente per fare proprio questo, chiamato algoritmo Wu-Manber. Pubblicherò un'implementazione di riferimento. Si noti, tuttavia, che l'ho fatto qualche tempo fa solo a scopo educativo. Pertanto, l'implementazione non è davvero adatta all'uso diretto e può anche essere resa più efficiente.
Utilizza anche lo stdext :: hash_map da Dinkumware STL. Sottoscrivi con std :: tr1 :: unordered_map o un'implementazione appropriata.
C'è una spiegazione dell'algoritmo in un copione della lezione da una conferenza alla Freie Universität di Berlino, tenuta da Knut Reinert.
Il documento originale è anche online (appena trovato di nuovo) ma io non Mi piace particolarmente lo pseudocodice presentato lì.
#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
Esempio di utilizzo:
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;
Un Filtro fioritura potrebbe essere la soluzione migliore. Inizializzi il filtro con i termini di ricerca, quindi durante la lettura del tuo corpus puoi verificare rapidamente se ogni opera è nel filtro.
È molto efficiente in termini di spazio, molto meglio del semplice hashing di ogni parola: con una percentuale di falsi positivi dell'1% dovrebbe richiedere solo 9,6 bit per elemento. Il tasso di falsi positivi viene ridotto di un fattore 10 per ogni 4,8 bit aggiuntivi per elemento. Confrontalo con il semplice hashing, che di solito richiede sizeof (int) == 32 bit per elemento.
Ho un'implementazione in C # qui: http://www.codeplex.com/bloomfilter
Ecco un esempio, dimostrando il suo utilizzo con le stringhe:
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!");
se il corpus è così grande, prova a ottimizzarlo in questo modo:
calcola un hash di ogni parola che devi controllare, assegnando a ciascun carattere un numero primo intero e quindi moltiplicando ogni numero insieme; memorizza ogni numero- > parola in una multimappa (devi consentire il valore multiplo su una singola chiave )
durante la scansione dell'elenco di parole, calcola l'hash nello stesso modo per ogni parola, quindi ottieni le parole associate alla chiave calcolata sull'hashmap. usando numeri interi come chiave, si ottiene un recupero di O (1); in questo modo potresti scoprire in modo molto rapido se la parola elaborata ha qualche anagramma (moltiplicati i caratteri) all'interno della mappa.
ricorda: hai memorizzato nella multimap l'insieme della parola con lo stesso hash, quindi ora devi trovare una corrispondenza in questo set notevolmente ridotto. hai bisogno di questo controllo aggiuntivo poiché la semplice esistenza dell'intero sulla mappa non equivale all'esistenza della parola nell'insieme associato: stiamo usando l'hash qui per ridurre lo spazio computazionale del problema, ma questo introduce una collisione che deve essere inequivocabile controllando ogni anagramma identificato.
Utilizza Algoritmo Aho-Corasick . È stato creato per questa applicazione. Dovrai leggere ogni lettera nel testo di ricerca una sola volta. Di recente l'ho implementato e usato con grandi risultati.
Come dice Javier, la soluzione più semplice è probabilmente una tabella hash.
In C ++, questo può essere implementato usando un set STL. Prima aggiungi le 25.000 parole di prova al set, quindi esegui la scansione di ogni parola nel testo, usando set.find (current_word) per valutare se la parola è tra le 25.000 parole di test.
set.find è logaritmicamente veloce, quindi 25.000 parole di prova non dovrebbero essere troppo grandi. L'algoritmo è ovviamente lineare nel numero di parole nel testo.
Se il testo che stai cercando è enorme, potrebbe valere la pena fare un po 'di preelaborazione: assembla le tue 25.000 parole in un TRIE.
Scansiona fino all'inizio della prima parola nel testo e inizia a camminare su TRIE mentre cammini tra le lettere della parola. Se non ci sono transizioni nel tuo TRIE, salta all'inizio della parola successiva e torna alla radice del TRIE. Se raggiungi la fine della parola e ti trovi in ??un nodo che termina la parola nel TRIE, hai trovato una corrispondenza. Ripeti l'operazione per ogni parola nel testo.
Se il tuo testo è semplicemente grande (piuttosto che enorme), probabilmente è sufficiente cercare ogni parola in una tabella hash.
viceBerg dice:
Una volta ho usato l'algoritmo Boyer-Moore ed è stato abbastanza veloce.
Con Boyer-Moore, in genere non stai cercando in un blocco di testo una singola stringa?
Per una soluzione semplice da implementare, seguire l'approccio con la tabella hash suggerito da Javier. Anche il filtro Bloom suggerito da FatCat1111 dovrebbe funzionare ... a seconda degli obiettivi.
Potrebbe essere la memorizzazione della tua dizione iniziale (le 25000 parole) in una tabella hash berkeley db su disco, che puoi probabilmente usare direttamente da c / c ++ (so che puoi farlo da perl), e per ogni parola nella testo, interroga se è presente nel database.
È inoltre possibile ordinare alfabeticamente il testo e l'elenco di parole. Quando hai due array ordinati, puoi facilmente trovare le corrispondenze in tempo lineare.
Desideri un Albero di ricerca ternaria . Una buona implementazione può essere trovata qui .
L'algoritmo Aho-Corasick è stato creato appositamente per questo scopo: cercare molte parole contemporaneamente.
