在文本中搜索25000个单词

我需要在文本中找到约25 000个单词的出现次数.为此目的,最合适的算法/库是什么？

目标语言是C++

1> Konrad Rudol..：

---

我曾经使用过Boyer-Moore算法而且速度非常快.

Boyer-Moore不适合有效地搜索很多单词.实际上有一种非常有效的算法,称为Wu-Manber算法.我将发布一个参考实现.但请注意,我之前做过这个只是为了教育目的.因此,实现并不适合直接使用,也可以提高效率.

它还使用stdext::hash_map了Dinkumware STL.合并std::tr1::unordered_map或适当实施.

在Knut Reinert举办的柏林自由大学(FreieUniversitätBerlin)讲座的讲座中,对算法进行了解释.

该原纸也在线(刚发现它再次),但我并不特别喜欢那里呈现的伪代码.

#ifndef FINDER_HPP
#define FINDER_HPP

#include 

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(static_cast(c));
    }
};

inline Finder::~Finder() { }

} } // namespace thru::matching

#endif // !defined(FINDER_HPP)

---

#include 
#include 

#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 const& patterns);

    bool find();

    std::size_t position() const;

    std::size_t pattern_index() const;

private:

    template 
    struct HashMap {
        typedef stdext::hash_map Type;
    };

    typedef HashMap::Type shift_type;
    typedef HashMap >::Type hash_type;

    std::string const& m_text;
    std::vector 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 
#include 

#include "wumanber.hpp"

using namespace std;

namespace thru { namespace matching {

WuManberFinder::WuManberFinder(string const& text, vector 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(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& 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 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;

---

不构造一个简单的搜索词前缀 - trie会为你提供O(n)-O(1)时空复杂度吗？为什么当简单有效的解决方案已存在数十年时,人们会迅速跳过这些愚蠢的复杂解决方案......

---

@sonicoder:O(n)-O(1)是什么意思？构造长度为*m*的*k*字符串的trie具有运行时间O(k·m)并且在长度为*n*的文本中搜索每次出现的模式具有额外的运行时O(n).Wu和Manber算法的运行时在实践中的顺序相同.此外,你真的称它为"愚蠢而且过于复杂"并且想要被认真对待吗？Wu和Manber的算法是一种成熟的多模式搜索算法,它远非复杂.事实上,*高效*(即O(k·m))trie结构更难以实现.

2> Javier..：

---

使用单词构建哈希表,并扫描文本,为单词表中的每个单词查找填充所需的信息(增量计数,添加到位置列表,等等).

---

无论如何,你必须将所有25,000个单词存储在内存中; 将它们存储在哈希表中的开销不会超过一个小的常数因子.几百千字节与现代硬件无关.

3> Justin R...：

---

一个布隆过滤器可能是你最好的选择.您使用搜索字词初始化过滤器,然后在阅读语料库时可以快速检查每项工作是否在过滤器中.

它非常节省空间,比简单地对每个字进行散列要好得多:误报率为1%,每个元素只需要9.6位.每个元素每增加4.8位,误报率降低10倍.将此与普通散列进行对比,通常需要每个元素的sizeof(int)== 32位.

我在C#中有一个实现:http://www.codeplex.com/bloomfilter

这是一个示例,演示了它与字符串的使用:

int capacity = 2000000; // the number of items you expect to add to the filter
Filter filter = new Filter(capacity);
filter.Add("Lorem");
filter.Add("Ipsum");
if (filter.Contains("Lorem"))
    Console.WriteLine("Match!");

4> Lorenzo Bocc..：

---

如果语料库太大,请尝试以这种方式优化它:

计算你需要检查的每个单词的散列,为每个char分配一个整数素数,然后将每个数字相乘;将每个数字 - >单词存储在一个多重映射中(你需要在单个键上允许多个值)

在扫描字列表时,以相同的方式为每个字计算散列,然后在散列映射上获得与计算的密钥相关联的字.使用整数作为键,您可以检索O(1); 通过这种方式,如果处理后的单词在地图内部有一些字谜(您乘以字符),您可以快速找到.

记住:你在multimap中存储了具有相同哈希值的单词集,所以你现在需要在这个大大减少的集合中找到一个匹配项.你需要这个额外的检查,因为地图上整数的简单存在并不等于相关集合中单词的存在:我们在这里使用散列来减少问题的计算空间,但是这引入了需要的碰撞消除每个识别出的字谜的歧义.