在文本中搜索25000个单词
https://stackoverflow.com/questions/154365
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我需要在文本中找到~25 000个单词的出现次数。为此目的，最合适的算法/库是什么？
目标语言是C ++
解决方案
使用单词构建哈希表，并扫描文本，为单词表中的每个单词查找填充所需信息（增量计数，添加到位置列表，等等）。
其他提示
我曾经使用过Boyer-Moore算法而且速度非常快。
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;
Bloom Filter 可能是您最好的选择。您使用搜索字词初始化过滤器，然后在阅读语料库时可以快速检查每项工作是否在过滤器中。
它非常节省空间，比简单地对每个单词进行散列要好得多：误报率为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!");
如果语料库太大，请尝试以这种方式对其进行优化：
计算需要检查的每个单词的散列，为每个char分配一个整数素数，然后将每个数字相乘;将每个数字 - ＆gt;单词存储在多重映射中（您需要在单个键上允许多个值） ）
在扫描wordlist时，以相同的方式为每个单词计算散列，然后在hashmap上获取与计算出的键相关联的单词。使用整数作为键，您可以检索O（1）;通过这种方式，如果处理后的单词在地图内部有一些字谜（您乘以字符），您可以快速找到。
记住：你在multimap中存储了具有相同哈希值的单词集，所以你现在需要在这个大大减少的集合中找到一个匹配项。你需要这个额外的检查，因为地图上整数的简单存在并不等于相关集合中单词的存在：我们在这里使用散列来减少问题的计算空间，但是这引入了需要的碰撞消除每个识别出的字谜的歧义。
使用 Aho-Corasick算法。它是为这个应用程序而制作的。您只需要阅读一次搜索文本中的每个字母。我最近实施并使用了它，效果很好。
正如Javier所说，最简单的解决方案可能是哈希表。
在C ++中，这可以使用STL集来实现。首先将25,000个测试单词添加到集合中，然后使用set.find（current_word）扫描文本中的每个单词，以评估该单词是否在25,000个测试单词中。
set.find以对数方式快速，因此25,000个测试词不应该太大。该算法在文本中的单词数量上显然是线性的。
如果您正在搜索的文本很大，那么可能值得进行一些预处理：将25,000个单词组合成一个TRIE。
扫描到文本中第一个单词的开头，然后在浏览单词的字母时开始走TRIE。如果您的TRIE中没有转换，请跳到下一个单词的开头并返回TRIE的根目录。如果到达单词的末尾，并且您在TRIE中的单词结尾节点，则表示您找到了匹配项。对文本中的每个单词重复。
如果您的文本只是大（而不是巨大），那么只需在哈希表中查找每个单词就足够了。
我曾经使用过Boyer-Moore算法 它很快。
对于Boyer-Moore，您通常不会在文本块中搜索单个字符串吗？
对于一个简单的实现解决方案，请使用Javier建议的哈希表方法。 FatCat1111建议的Bloom过滤器也应该起作用......取决于目标。
可能将您的初始词典（25000字）存储在磁盘上的berkeley db哈希表中，您可以直接从c / c ++中使用（我知道您可以从perl中使用），并且可以在text，查询它是否存在于数据库中。
您也可以按字母顺序对文本和单词列表进行排序。如果您有两个已排序的数组，则可以在线性时间内轻松找到匹配项。
Aho-Corasick算法专门为此目的而构建：一次搜索多个单词。
