rechercher 25 000 mots dans un texte
https://stackoverflow.com/questions/154365
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je dois trouver des occurrences d'environ 25 000 mots dans un texte. Quel est l’algorithme / la bibliothèque le mieux adapté à cet usage?
la langue cible est C ++
La solution
construisez une table de hachage avec les mots et parcourez le texte pour chaque recherche de mots dans la table des mondes, puis remplissez les informations nécessaires (nombre d'incréments, ajout à une liste de positions, peu importe).
Autres conseils
J'ai déjà utilisé l'algorithme de Boyer-Moore et c'était assez rapide.
Boyer-Moore n’est pas apte à rechercher efficacement plusieurs mots. Il existe en fait un algorithme très efficace pour cela, appelé algorithme Wu-Manber. Je posterai une implémentation de référence. Notez cependant que je l’ai fait il ya quelque temps à des fins éducatives uniquement. Par conséquent, la mise en œuvre n'est pas vraiment adaptée à une utilisation directe et peut également être rendue plus efficace.
Il utilise également le stdext :: hash_map du STL Dinkumware. Remplacez avec std :: tr1 :: unordered_map ou une implémentation appropriée.
Il existe une explication de l'algorithme dans un script de conférence d'une conférence donnée à la Freie Universität Berlin par Knut Reinert.
Le document original est également en ligne (vient de le retrouver) mais je ne le fais pas. t particulièrement comme le pseudocode présenté ici.
#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
Exemple d'utilisation:
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 Filtre Bloom peut être votre meilleur choix. Vous initialisez votre filtre avec vos termes de recherche, puis, tout en lisant votre corpus, vous pouvez rapidement vérifier si chaque travail est dans le filtre.
C’est très efficace en termes d’espace, beaucoup mieux que le simple hachage de chaque mot: avec un taux de faux positifs de 1%, il ne devrait nécessiter que 9,6 bits par élément. Le taux de faux positifs est réduit d'un facteur 10 pour chaque 4,8 bits supplémentaires par élément. Cela contraste avec le hachage simple, qui nécessite généralement sizeof (int) == 32 bits par élément.
J'ai une implémentation en C # ici: http://www.codeplex.com/bloomfilter
Voici un exemple illustrant son utilisation avec des chaînes:
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!");
si le corpus est si volumineux, essayez de l'optimiser de la manière suivante:
calculez le hachage de chaque mot à vérifier, attribuez à chaque caractère un nombre premier entier, puis multipliez chaque nombre; stockez chaque nombre - > mot dans une carte multiple (vous devez autoriser plusieurs valeurs sur une clé )
lors du balayage de la liste de mots, calculez le hachage de la même manière pour chaque mot, puis récupérez le (s) mot (s) associé (s) à la clé calculée sur la table de hachage. en utilisant des nombres entiers comme clé, vous obtenez une récupération de O (1); De cette façon, vous pourriez trouver très rapidement si le mot traité contient des anagrammes (vous multipliez les caractères) dans la carte.
rappelez-vous: vous avez stocké dans la carte multiple l'ensemble du mot ayant le même hachage, vous devez donc trouver une correspondance dans cet ensemble considérablement réduit. vous avez besoin de cette vérification supplémentaire car la simple existence de l'entier sur la carte n'équivaut pas à l'existence du mot dans l'ensemble associé: nous utilisons ici le hachage pour réduire l'espace de calcul du problème, mais cela introduit une collision qui doit être désambiguïsé en vérifiant chaque anagramme identifié.
Utilisez l'algorithme Aho-Corasick . C'était fait pour cette application. Il vous suffira de lire chaque lettre du texte de votre recherche une fois. Je l'ai récemment mis en œuvre et utilisé avec d'excellents résultats.
Comme le dit Javier, la solution la plus simple est probablement une table de hachage.
En C ++, cela peut être implémenté à l'aide d'un jeu STL. Ajoutez d’abord les 25 000 mots de test à l’ensemble, puis parcourez chaque mot du texte à l’aide de set.find (mot_de_passe) pour déterminer s’il fait partie des 25 000 mots de test.
set.find est logarithmiquement rapide, donc 25 000 mots de test ne doivent pas être trop grands. L'algorithme est évidemment linéaire dans le nombre de mots du texte.
Si le texte que vous recherchez est énorme, il peut être intéressant de procéder à un prétraitement: assemblez vos 25 000 mots dans un TRIE.
Balayez jusqu'au début du premier mot du texte et commencez à parcourir le TRIE en parcourant les lettres du mot. S'il n'y a pas de transition dans votre TRIE, passez au début du mot suivant et retournez à la racine du TRIE. Si vous atteignez la fin du mot et que vous vous trouvez à un nœud de fin de mot dans le TRIE, vous avez trouvé une correspondance. Répétez l'opération pour chaque mot du texte.
Si votre texte est simplement grand (plutôt qu'énorme), il suffit probablement de rechercher chaque mot dans une table de hachage.
viceBerg dit:
J'ai déjà utilisé l'algorithme de Boyer-Moore et c'était assez rapide.
Avec Boyer-Moore, vous ne recherchez généralement pas dans un bloc de texte une chaîne à single ?
Pour une solution simple à mettre en œuvre, utilisez l’approche par table de hachage proposée par Javier. Le filtre Bloom proposé par FatCat1111 devrait également fonctionner ... en fonction des objectifs.
Peut-être stockez-vous votre dictionnaire initial (les 25 000 mots) dans une table de hachage berkeley db sur disque, que vous pouvez probablement utiliser directement à partir de c / c ++ (je sais que vous pouvez le faire à partir de perl), et pour chaque mot du texte, demande s'il est présent dans la base de données.
Vous pouvez également trier le texte et la liste de mots par ordre alphabétique. Lorsque vous avez deux tableaux triés, vous pouvez facilement trouver les correspondances en temps linéaire.
Vous voulez un un arbre de recherche ternaire . Une bonne implémentation peut être trouvée ici .
L’algorithme Aho-Corasick est spécialement conçu à cet effet: rechercher plusieurs mots à la fois.
