我需要在文本中找到约 25 000 个单词的出现。为此目的最合适的算法/库是什么？
目标语言是 C++
问问题
3725 次
12 回答
15
我曾经使用过 Boyer-Moore 算法，它非常快。
Boyer-Moore 不适合有效地搜索许多单词。实际上有一种非常有效的算法可以做到这一点，称为 Wu-Manber 算法。我将发布一个参考实现。但是请注意，我前段时间这样做只是为了教育目的。因此，该实现并不适合直接使用，也可以提高效率。
它还使用stdext::hash_map来自 Dinkumware STL 的。替换为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;
于 2008-09-30T18:47:29.813 回答
12
用单词构建一个哈希表，并扫描文本，为单词表中的每个单词查找并填充所需的信息（增加计数，添加到位置列表等）。
于 2008-09-30T18:39:09.633 回答
11
布隆过滤器可能是您最好的选择。你用你的搜索词初始化你的过滤器，然后在阅读你的语料库时可以快速检查每件作品是否在过滤器中。
它非常节省空间，比简单地散列每个单词要好得多：误报率为 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<string> filter = new Filter<string>(capacity);
filter.Add("Lorem");
filter.Add("Ipsum");
if (filter.Contains("Lorem"))
Console.WriteLine("Match!");
于 2008-09-30T18:40:17.460 回答
5
如果语料库这么大，尝试这样优化：
计算您需要检查的每个单词的哈希值，为每个字符分配一个整数素数，然后将每个数字相乘；将每个数字-> 单词存储在多重映射中（您需要在单个键上允许多个值）
在扫描单词列表时，以相同的方式计算每个单词的哈希值，然后获取与哈希图上的计算键关联的单词。使用整数作为键，您可以检索 O(1)；这样，如果处理后的单词在地图中有一些字谜（您将字符相乘），您就可以非常快速地找到它。
请记住：您在多重映射中存储了具有相同哈希的单词集合，因此您现在需要在这个大大减少的集合中找到匹配项。你需要这个额外的检查，因为地图上整数的简单存在并不等同于相关集合中单词的存在：我们在这里使用散列来减少问题的计算空间，但这会引入冲突，需要对每个已识别的字谜进行消歧义检查。
于 2008-09-30T19:09:56.330 回答
3
使用Aho-Corasick 算法。它是为这个应用程序制作的。您只需阅读搜索文本中的每个字母一次。我最近实施并使用了它，效果很好。
于 2009-05-01T18:03:56.340 回答
2
正如 Javier 所说，最简单的解决方案可能是哈希表。
在 C++ 中，这可以使用 STL 集来实现。首先将 25,000 个测试词添加到集合中，然后扫描文本中的每个单词，使用 set.find(current_word) 评估该单词是否在 25,000 个测试词中。
set.find 的对数速度很快，所以 25,000 个测试词不应该太大。该算法在文本中的单词数量上显然是线性的。
于 2008-09-30T18:50:25.143 回答
2
如果您要搜索的文本很大，那么可能值得进行一些预处理：将您的 25,000 个单词组合成一个 TRIE。
扫描到文本中第一个单词的开头，并在遍历单词的字母时开始走 TRIE。如果您的 TRIE 中没有转换，请跳到下一个单词的开头并返回到 TRIE 的根。如果您到达单词的结尾，并且您位于 TRIE 中的单词结尾节点，则您找到了匹配项。对文本中的每个单词重复。
如果您的文本只是很大（而不是很大），那么只需在哈希表中查找每个单词就足够了。
于 2009-05-01T17:50:49.540 回答
0
副伯格 说：
我曾经使用过 Boyer-Moore 算法，它非常快。
使用 Boyer-Moore，您通常不是在文本块中搜索单个字符串吗？
对于一个简单的实现解决方案，请使用 Javier 建议的哈希表方法。FatCat1111 建议的布隆过滤器也应该可以工作......取决于目标。
于 2008-09-30T18:43:55.330 回答
0
可能将您的初始字典（25000 个单词）存储在磁盘上的 berkeley db 哈希表中，您可能可以直接从 c/c++ 使用（我知道您可以从 perl 中使用），对于文本中的每个单词，查询如果它存在于数据库中。
于 2008-09-30T18:51:08.417 回答
0
您还可以按字母顺序对文本和单词列表进行排序。当您有两个排序数组时，您可以轻松地在线性时间内找到匹配项。
于 2008-09-30T20:16:43.937 回答
0
Aho-Corasick 算法是专门为此目的而构建的：一次搜索多个单词。
于 2009-11-10T21:35:22.983 回答