c++ - tagxedo - buscar 25 000 palabras dentro de un texto

nube de tags descargar

Question

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 ++

Answer 1

Una vez usé el algoritmo Boyer-Moore y fue bastante rápido.

Boyer-Moore no es apto para buscar de manera eficiente muchas palabras. En realidad, hay un algoritmo muy eficiente para hacer exactamente eso, llamado algoritmo Wu-Manber. Publicaré una implementación de referencia. Sin embargo, tenga en cuenta que hice esto hace algún 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 stdext::hash_map de Dinkumware STL. Subsistencia con std::tr1::unordered_map o una implementación apropiada.

Hay una explicación del algoritmo en un guión de conferencia de una conferencia en la Freie Universität Berlin, realizada por Knut Reinert.

El documento original también está en línea (lo encontré de nuevo) pero no me gusta particularmente el pseudocódigo que se presenta 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;

Answer 2

Como dice Javier, la solución más simple es probablemente una tabla hash.

En C ++, esto puede implementarse 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 se encuentra 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.

Answer 3

Puede estar almacenando su dictionnary inicial (las 25000 palabras) en una tabla berkeley db hash en el disco, que probablemente pueda usar directamente de c / c ++ (sé que puede hacerlo desde perl), y para cada palabra en el texto, consulta si está presente en la base de datos.

Answer 4

Quieres un árbol de búsqueda ternario . Una buena implementación se puede encontrar aquí .

Answer 5

También puede ordenar el texto y la lista de palabras alfabéticamente. Cuando tiene dos matrices ordenadas, puede encontrar fácilmente las coincidencias en tiempo lineal.

Answer 6

construya una tabla hash con las palabras y escanee el texto, para cada búsqueda de palabras en la tabla de palabras y rellene la información necesaria (recuento de incrementos, agregar a una lista de posiciones, lo que sea).

Answer 7

si el corpus es tan grande, intente optimizarlo de esta manera:

calcule un hash de cada palabra que necesita verificar, asignando a cada char un número primo entero y luego multiplicando cada número, almacena cada número-> palabra en un multimapa (necesita permitir el valor múltiple 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 tecla calculada en el hashmap. usando números enteros como clave, tiene una recuperación de O (1); de esta forma, podrías encontrar de una manera realmente rápida si la palabra procesada tiene algún anagrama (caracteres multiplicados) dentro del mapa.

recuerde: usted almacenó en el multimapa el conjunto de la palabra que tiene el mismo hash, por lo que ahora necesita encontrar una coincidencia en este conjunto muy reducido. necesita esta verificació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 computacional del problema, pero esto introduce la colisión que necesita se desambigó la comprobación de cada anagrama identificado.

Answer 8

viceBerg dice:

Una vez usé el algoritmo Boyer-Moore y fue bastante rápido.

Con Boyer-Moore, ¿no estás generalmente buscando un bloque de texto para una sola cadena?

Para una solución simple de implementar, vaya al enfoque de tabla hash sugerido por Javier. El filtro Bloom sugerido por FatCat1111 debería funcionar también ... según los objetivos.

Answer 9

Si el texto que está buscando es enorme, entonces puede valer la pena realizar un preprocesamiento: ensamble sus 25,000 palabras en un TRIE.

Escanee hasta el comienzo de la primera palabra del texto y comience a caminar el TRIE mientras recorre las letras de la palabra. Si no hay transición en su TRIE, salte al comienzo de la siguiente palabra y vuelva a la raíz del TRIE. Si llegas al final de la palabra y estás en un nodo de fin de palabra en el TRIE, has encontrado una coincidencia. Repita para cada palabra en el texto.

Si su texto es meramente grande (en lugar de enorme), basta con buscar cada palabra en una tabla hash.

Answer 10

Usa el algoritmo Aho-Corasick . Fue hecho para esta aplicación. Solo necesitará leer cada letra del texto de búsqueda una vez. Recientemente lo implementé y lo utilicé con excelentes resultados.

Answer 11

El algoritmo Aho-Corasick está creado específicamente para ese propósito: buscar muchas palabras a la vez.

Answer 12

Un Bloom Filter puede ser su mejor opción. Inicializa su filtro con sus términos de búsqueda, luego, mientras lee su corpus, puede verificar rápidamente si cada trabajo está en el filtro.

Es muy eficiente en el uso del espacio, mucho mejor que simplemente aplicar hash a 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 a hash 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, demostrando 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!");