ищите 25 000 слов в рамках текста

Фильтр Цветка может быть Вашим лучшим выбором. Вы инициализируете свой фильтр с Вашими критериями поиска, затем в то время как чтение Вашего корпуса может быстро проверить, находится ли каждая работа в фильтре.

Это - очень эффективное пространство, намного лучше, чем простое хеширование каждого слова: с 1%-м ложно-положительным уровнем должно требоваться только 9,6 битов за элемент. Ложно-положительный уровень уменьшается фактором 10 для каждого дополнительные 4,8 бита за элемент. Контрастируйте это с простым хешированием, которое обычно требует sizeof (интервал) == 32 бита за элемент.

у меня есть реализация в C# здесь: http://www.codeplex.com/bloomfilter

Вот пример, демонстрируя его использование со строками:

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!");

я когда-то использовал алгоритм Boyer-Moore, и это было довольно быстро.

Boyer-Moore не склонен для того, чтобы эффективно искать много слов. Существует на самом деле очень эффективный алгоритм для того, чтобы сделать просто что, названный алгоритмом Wu-Manber. Я отправлю ссылочную реализацию. Заметьте, однако, что я сделал это некоторое время назад для образовательной цели только. Следовательно, реализация не действительно склонна для прямого использования и может также быть сделана более эффективной.

Это также использует stdext::hash_map от STL Dinkumware. Subsitute с std::tr1::unordered_map или соответствующая реализация.

существует объяснение алгоритма в сценарий лекции от лекции в Freie UniversitГ¤t Берлин, сохраненном Knut Reinert.

исходная бумага также онлайн (просто нашел его снова), но мне особенно не нравится псевдокод, представленный там.

#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

Пример использования:

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;

если корпус является настолько большим, попытайтесь оптимизировать его таким образом:

вычисляют хеш каждого слова, которое необходимо проверить, присвоив каждому символу целочисленное простое число и затем умножив каждое число вместе; сохраните каждое число-> слово в мультикарте (необходимо допускать, несколько оценивают единственным ключом)

при сканировании списка слов вычислите хеш таким же образом для каждого слова, затем свяжите слово (слова) с вычисленным, включают hashmap. использование целых чисел как ключ, у Вас есть извлечение O (1); этим путем Вы могли найти действительно быстрым способом, если обработанное слово имеет некоторую анаграмму (Вы умножили символы) в карте.

помните: Вы сохранили в мультикарте набор слова, имеющего тот же самый хеш, таким образом, теперь необходимо найти соответствие в этом значительно уменьшенном наборе. Вам нужна эта дополнительная проверка как, просто существование целого числа на карте не приравнивается к существованию слова в связанном наборе: мы используем хеширование здесь для сокращения вычислительного пространства проблемы, но это представляет коллизию, которая должна быть снята неоднозначность, проверив каждую определенную анаграмму.

вице-айсберг говорит:

я когда-то использовал алгоритм Boyer-Moore, и это было довольно быстро.

С Boyer-Moore, не Вы обычно поиск блока текста для единственный строка?

Для простого для реализации решения идут с подходом хеш-таблицы, предложенным Javier. Фильтр Цветка, предложенный FatCat1111, должен работать также... в зависимости от целей.

Как Javier говорит, простое решение является, вероятно, хеш-таблицей.

В C++, это может быть реализовано с помощью набора STL. Сначала добавьте 25 000 тестовых слов к набору и затем просканируйте через каждое слово в тексте, с помощью set.find (current_word), чтобы оценить, является ли слово среди 25 000 тестовых слов.

set.find логарифмически быстр, таким образом, 25 000 тестовых слов не должны быть слишком большими. Алгоритм очевидно линеен в количестве слов в тексте.

Можно также отсортировать текст и список слов в алфавитном порядке. То, когда Вы имеете два, отсортировало arraysyou, может легко найти соответствия в линейное время.

Может хранить Ваш первоначальный словарь (эти 25 000 слов) в хеш-таблице дб Беркли на диске, который можно, вероятно, использовать непосредственно от c/c ++ (я знаю, что можно сделать это от жемчуга), и для каждого слова в тексте, запрос, если это присутствует в базе данных.

Вы хотите Троичное Дерево поиска . Хорошая реализация может быть найдена здесь .

Используйте алгоритм Aho-Corasick . Это было сделано для этого приложения. Вам нужно будет прочитать каждую букву в тексте поиска только один раз. Я недавно внедрил и использовал его с отличными результатами.

Если текст, который вы ищете, огромен, то, возможно, стоит выполнить некоторую предварительную обработку: собрать 25 000 слов в TRIE.

Сканирование до начала первого слова в текст, и начните ходить TRIE, проходя по буквам слова. Если в вашем TRIE нет перехода, перейдите к началу следующего слова и вернитесь к корню TRIE. Если вы достигли конца слова и оказались в конце слова в TRIE, вы нашли совпадение. Повторите эти действия для каждого слова в тексте.

Если ваш текст просто большой (а не огромный), тогда достаточно просто найти каждое слово в хеш-таблице.

Алгоритм Ахо-Корасика создан специально для этой цели: поиск нескольких слов одновременно.