procurar 25 000 palavras dentro de um texto
https://stackoverflow.com/questions/154365
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu preciso encontrar ocorrências de ~ 25 000 palavras dentro de um texto. Qual é o algoritmo / biblioteca mais adequado para este fim?
língua de destino é C ++
Solução
construir uma tabela hash com as palavras, e de digitalização através do texto, para cada pesquisa palavra na tabela do mundo e encher as informações necessárias (contagem de incremento, adicionar a uma lista posição, qualquer que seja).
Outras dicas
Uma vez eu utilizado o algoritmo Boyer-Moore e foi bastante rápido.
Boyer-Moore não está apto para pesquisar de forma eficiente muitas palavras. Há realmente um algoritmo muito eficiente para fazer exatamente isso, o chamado algoritmo de Wu-Manber. Vou postar uma implementação de referência. Note, no entanto, que eu fiz isso há algum tempo apenas para educacional. Assim, a implementação não é realmente apto para uso direto e também pode ser mais eficiente.
Ele também usa o stdext::hash_map do STL Dinkumware. Subsitute com std::tr1::unordered_map ou uma implementação adequada.
Há uma explicação do algoritmo em uma palestra script a partir de uma palestra na Freie Universität Berlin, realizada por Knut Reinert.
O artigo original também está on-line (só descobri-lo novamente), mas eu don' t particularmente como o pseudocódigo apresentado 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
Exemplo de utilização:
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;
A Bloom Filtro pode ser sua melhor aposta. Que iniciar o filtro com os termos de pesquisa, em seguida, ao ler o seu corpus pode verificar rapidamente se cada trabalho é no filtro.
É muito eficiente do espaço, muito melhor do que simplesmente hash cada palavra: com uma taxa de falso-positivo de 1% deve exigir apenas 9,6 bits por elemento. A taxa de falsos positivos é reduzida por um factor de 10 para cada um adicional de 4,8 bits por elemento. Compare-se isto para hash simples, o que geralmente requer sizeof (int) == 32 bits por elemento.
Eu tenho uma implementação em C # aqui: http://www.codeplex.com/bloomfilter
Aqui está um exemplo, demonstrando a sua utilização com 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!");
Se o corpus é tão grande, tentar otimizá-lo desta maneira:
computar um hash de cada palavra que você precisa verificar, atribuindo a cada caractere um número primo inteiro e, em seguida, multiplicando cada número juntos, armazenar cada número-> palavra em um multimap (você precisa para permitir vários valores em uma única tecla)
durante a digitalização da lista de palavras, calcular o hash da mesma forma para cada palavra, em seguida, passar a palavra (s) associado à chave computadorizada na hashmap. usando números inteiros como chave, você tem uma recuperação de O (1); Desta forma, você poderia encontrar em uma maneira muito rápida, se a palavra processada tem alguma anagrama (você multiplicado caracteres) dentro do mapa.
lembre-se: você armazenados no multimap o conjunto da palavra ter que mesmo hash, então agora você precisa encontrar um jogo neste conjunto bastante reduzido. você precisa esta verificação adicional como o simples existência do inteiro no mapa não equivale à existência da palavra no conjunto de associados: nós estamos usando hashing aqui para reduzir o espaço computacional do problema, mas isto introduz colisão que necessidade de ser disambiguated verificando em cada anagrama identificado.
Use a Aho-Corasick algoritmo . Ela foi feita para esta aplicação. Você só vai precisar ler cada letra em sua pesquisa de texto uma vez. Eu recentemente implementado e é usado com excelentes resultados.
Como Javier diz, a solução mais simples é provavelmente uma tabela hash.
Em C ++, isso pode ser implementado usando um conjunto STL. Primeiro adicione as palavras de teste 25.000 para o conjunto, e depois digitalizar através de cada palavra no texto, usando set.find (current_word) para avaliar se a palavra está entre as palavras de teste 25.000.
set.find é logarítmica rápido, então palavras 25.000 de teste não deve ser muito grande. O algoritmo é obviamente linear no número de palavras no texto.
Se você o texto está a procura é enorme, então pode valer a pena fazer alguns pré-processamento:. Montar seus 25.000 palavras em uma TRIE
Digitalizar para o início da primeira palavra no texto, e começar a andar o TRIE como você anda através das letras da palavra. Se não há nenhuma transição em sua TRIE, pular para o início da próxima palavra e voltar para a raiz do TRIE. Se você chegar ao final da palavra, e você está em um nó-ending palavra no TRIE, você encontrou uma partida. Repita para cada palavra no texto.
Se o texto é apenas grande (em vez de enorme), em seguida, basta olhar para cima cada palavra em uma tabela hash é provavelmente suficiente.
viceBerg diz:
Uma vez eu utilizado o algoritmo Boyer-Moore e foi bastante rápido.
Com Boyer-Moore, não é tipicamente procurando um bloco de texto para um única string?
Para um simples de implementar solução de ir com a abordagem tabela hash sugerido por Javier. O filtro Bloom sugerido por FatCat1111 deve funcionar também ... dependendo dos objetivos.
Pode ser armazenar sua Dictionnary inicial (as 25000 palavras) em uma tabela do Berkeley DB de hash no disco, que você provavelmente pode usar diretamente do c / c ++ (eu sei que você pode fazê-lo a partir de perl), e para cada palavra no texto, consulta se ele está presente no banco de dados.
Você também pode classificar o texto ea lista de palavras em ordem alfabética. Quando você tem dois ordenados arraysyou pode facilmente encontrar os jogos em tempo linear.
Você quer um ternário Pesquisa Árvore . A boa implementação pode ser encontrada aqui .
Aho-Corasick é construído especificamente para esse fim:. à procura de muitas palavras de uma só vez
