テキスト内で ~ 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 分の 1 に減少します。これを通常のハッシュと比較してください。通常、要素ごとに 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アルゴリズムを使用します。このアプリケーションのために作られました。検索テキストの各文字を1回だけ読む必要があります。私は最近それを実装して使用し、素晴らしい結果をもたらしました。
于 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 に答える
0
バイスバーグは次のように述べています。
Boyer-Moore アルゴリズムを使用したことがありますが、非常に高速でした。
Boyer-Moore の場合、テキストのブロックから1 つの文字列を検索するのが一般的ではありませんか?
実装が簡単なソリューションについては、Javier によって提案されたハッシュ テーブル アプローチを使用します。FatCat1111 によって提案されたブルーム フィルターも機能するはずです...目標によっては。
于 2008-09-30T18:43:55.330 に答える
0
最初の辞書 (25000 語) をディスク上の berkeley db ハッシュ テーブルに格納し、おそらく c/c++ から直接使用でき (perl から実行できることはわかっています)、テキスト内の各単語に対してクエリを実行する可能性があります。データベースに存在する場合。
于 2008-09-30T18:51:08.417 に答える
0
テキストと単語リストをアルファベット順に並べ替えることもできます。2 つの並べ替えられた配列がある場合、線形時間で一致を簡単に見つけることができます。
于 2008-09-30T20:16:43.937 に答える