buscar 25 000 palabras dentro de un texto
https://stackoverflow.com/questions/154365
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Necesito encontrar ocurrencias de ~ 25 000 palabras dentro de un texto. ¿Cuál es el algoritmo / biblioteca más adecuado para este propósito?
el idioma de destino es C ++
Solución
cree una tabla hash con las palabras y escanee a través del texto, para cada búsqueda de palabras en la tabla mundial y rellene la información necesaria (recuento de incrementos, agregar a una lista de posiciones, lo que sea).
Otros consejos
Una vez usé el algoritmo de Boyer-Moore y fue bastante rápido.
Boyer-Moore no es apto para buscar de manera eficiente muchas palabras. En realidad, existe un algoritmo muy eficiente para hacer precisamente eso, llamado el algoritmo de Wu-Manber. Voy a publicar una implementación de referencia. Tenga en cuenta, sin embargo, que hice esto hace un tiempo solo con fines educativos. Por lo tanto, la implementación no es realmente apta para el uso directo y también puede hacerse más eficiente.
También utiliza el stdext :: hash_map de la STL de Dinkumware. Subsitute con std :: tr1 :: unordered_map o una implementación apropiada.
Hay una explicación del algoritmo en guión de la conferencia de una conferencia en la Freie Universit & # 228; t Berlin, organizada por Knut Reinert.
El documento original también está en línea (simplemente lo encontré nuevamente) pero no lo hago. Particularmente me gusta el pseudocódigo presentado allí.
#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
Ejemplo de uso:
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 Bloom puede ser su mejor apuesta. Inicializa su filtro con sus términos de búsqueda, luego, al leer su corpus, puede verificar rápidamente si cada trabajo está en el filtro.
Es muy eficiente en cuanto al espacio, mucho mejor que simplemente escribir cada palabra: con una tasa de falsos positivos del 1%, debería requerir solo 9.6 bits por elemento. La tasa de falsos positivos se reduce en un factor de 10 por cada 4.8 bits adicionales por elemento. Contraste esto con el hashing simple, que generalmente requiere sizeof (int) == 32 bits por elemento.
Tengo una implementación en C # aquí: http://www.codeplex.com/bloomfilter
Aquí hay un ejemplo que demuestra su uso con cadenas:
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 el corpus es tan grande, intente optimizarlo de esta manera:
calcule un hash de cada palabra que necesita verificar, asignando a cada carácter un número primo entero y luego multiplicando cada número; almacene cada palabra de número y > en un multimapa (debe permitir múltiples valores en una sola tecla )
mientras escanea la lista de palabras, calcule el hash de la misma manera para cada palabra, luego obtenga la (s) palabra (s) asociada (s) con la clave calculada en el hashmap. utilizando enteros como clave, tiene una recuperación de O (1); De esta manera, podría encontrar de manera muy rápida si la palabra procesada tiene algún anagrama (multiplicó los caracteres) dentro del mapa.
recuerda: guardaste en el multimapa el conjunto de la palabra que tiene ese mismo hash, por lo que ahora necesitas encontrar una coincidencia en este conjunto enormemente reducido. necesita esta comprobación adicional, ya que la simple existencia del número entero en el mapa no equivale a la existencia de la palabra en el conjunto asociado: estamos utilizando el hashing aquí para reducir el espacio de cálculo del problema, pero esto introduce una colisión que es necesario Se puede desambiguar la comprobación de cada anagrama identificado.
Utilice el algoritmo de Aho-Corasick . Fue hecho para esta aplicación. Solo necesitarás leer cada letra en tu texto de búsqueda una vez. Recientemente lo he implementado y lo he usado con excelentes resultados.
Como dice Javier, la solución más sencilla es probablemente una tabla hash.
En C ++, esto se puede implementar utilizando un conjunto de STL. Primero agregue las 25,000 palabras de prueba al conjunto, y luego escanee cada palabra en el texto, usando set.find (current_word) para evaluar si la palabra está entre las 25,000 palabras de prueba.
set.find es logarítmicamente rápido, por lo que 25,000 palabras de prueba no deberían ser demasiado grandes. El algoritmo es obviamente lineal en el número de palabras en el texto.
Si el texto que estás buscando es enorme, entonces podría valer la pena hacer un poco de procesamiento previo: reúne tus 25,000 palabras en una TRIE.
Escanee hasta el comienzo de la primera palabra en el texto y comience a recorrer TRIE a medida que avanza por las letras de la palabra. Si no hay transición en su TRIE, salte al comienzo de la siguiente palabra y regrese a la raíz de la TRIE. Si llega al final de la palabra y se encuentra en un nodo de final de palabra en el TRIE, ha encontrado una coincidencia. Repita para cada palabra en el texto.
Si su texto es simplemente grande (en lugar de enorme), entonces basta con buscar cada palabra en una tabla hash.
viceBerg dice:
Una vez utilicé el algoritmo de Boyer-Moore y fue bastante rápido.
Con Boyer-Moore, ¿no suele buscar en un bloque de texto una cadena única ?
Para una solución simple de implementar, vaya con el enfoque de tabla hash sugerido por Javier. El filtro Bloom sugerido por FatCat1111 también debería funcionar ... dependiendo de los objetivos.
Puede estar almacenando su diccionario inicial (las 25000 palabras) en una tabla hash de berkeley db en el disco, que probablemente pueda usar directamente desde c / c ++ (sé que puede hacerlo desde perl), y para cada palabra en el texto, consulta si está presente en la base de datos.
También puede ordenar el texto y la lista de palabras alfabéticamente. Cuando tienes dos arreglos ordenados, puedes encontrar fácilmente las coincidencias en tiempo lineal.
Desea un Árbol de búsqueda ternaria . Puede encontrar una buena implementación en aquí .
El algoritmo Aho-Corasick está diseñado específicamente para ese propósito: buscar muchas palabras a la vez.
