我需要查找一个文本中〜25 000个单词的出现。为此目的，最合适的算法/库是什么？

目标语言是C ++

解决方案

针对单词表中的每个单词查找，使用单词构建一个哈希表，并遍历文本，并填充所需的信息(增加计数，添加到位置列表等)。

布隆过滤器可能是我们最好的选择。我们可以使用搜索词初始化过滤器，然后在阅读语料库时可以快速检查每个工作是否在过滤器中。

它非常节省空间，比简单地对每个单词进行散列要好得多：假阳性率为1％时，每个元素仅需要9.6位。每个元素每增加4.8位，误报率就会降低10倍。将此与普通散列相反，普通散列通常需要每个元素的sizeof(int)== 32位。

我在Chere中有一个实现：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!");

ViceBerg说：

I once used the Boyer-Moore algorithm
  and it was quite fast.

使用Boyer-Moore，我们通常不是在文本块中搜索单个字符串吗？

对于简单实施的解决方案，请使用Javier建议的哈希表方法。 FatCat1111建议的布隆过滤器也应该起作用……取决于目标。

I once used the Boyer-Moore algorithm and it was quite fast.

Boyer-Moore不适合有效地搜索许多单词。实际上，有一种非常有效的算法可以做到这一点，称为Wu-Manber算法。我将发布参考实现。但是请注意，我前段时间仅出于教育目的进行了此操作。因此，该实现实际上并不适合直接使用，也可以提高效率。

它还使用了Dinkumware STL中的stdext :: hash_map。用std :: tr1 :: unordered_map或者适当的实现代替。

在由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;

正如哈维尔所说，最简单的解决方案可能是哈希表。

在C ++中，可以使用STL集来实现。首先将25,000个测试词添加到集合中，然后使用set.find(current_word)扫描文本中的每个词，以评估该词是否在25,000个测试词中。

set.find对数快速，因此25,000个测试词不应太大。该算法显然在文本中的单词数上是线性的。

可能会将初始字典(25000个单词)存储在磁盘上的berkeley db哈希表中，我们可能可以直接从c / c ++使用(我知道我们可以从perl进行操作)，对于文本中的每个单词，都可以查询如果它存在于数据库中。

如果语料库太大，请尝试通过以下方式对其进行优化：

计算需要检查的每个单词的哈希，为每个字符分配一个整数质数，然后将每个数字相乘；将每个数字->单词存储在多图中(我们需要在单个键上允许多个值)

在扫描单词列表时，以相同的方式为每个单词计算哈希，然后获取与哈希图上计算出的键关联的单词。使用整数作为键，我们可以检索O(1);这样，我们就可以非常快速地找到所处理的单词是否在地图中包含一些字谜(我们乘以字符)。

请记住：我们在多重映射中存储了具有相同哈希值的单词集合，因此现在我们需要在这个大大简化的集合中找到一个匹配项。我们需要进行此额外的检查，因为地图上整数的简单存在并不等于相关集中的单词的存在：我们在这里使用散列来减少问题的计算空间，但这会导致碰撞，消除歧义，检查每个已识别的字谜。

我们也可以按字母顺序对文本和单词列表进行排序。当我们有两个排序的数组时，我们可以轻松地在线性时间内找到匹配项。

我们需要三元搜索树。一个很好的实现可以在这里找到。

如果要搜索的文本很大，则可能需要进行一些预处理：将25,000个单词组合成TRIE。

扫描到文本中第一个单词的开头，然后在遍历单词字母时开始遍历TRIE。如果TRIE没有过渡，请跳到下一个单词的开头，然后返回TRIE的根。如果我们到达单词的结尾，并且我们位于TRIE中的单词结尾节点，那么我们已经找到了匹配项。对文本中的每个单词重复上述步骤。

如果文本只是很大(而不是很大)，那么只需在哈希表中查找每个单词就足够了。

使用Aho-Corasick算法。它是为此应用程序制作的。我们只需要阅读一次搜索文本中的每个字母。我最近实现并使用了它，并取得了很好的效果。

Aho-Corasick算法是专门为此目的而构建的：一次搜索许多单词。