텍스트 내에서 25,000 단어를 검색하십시오
https://stackoverflow.com/questions/154365
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
텍스트 내에서 ~ 25,000 단어의 발생을 찾아야합니다. 이 목적에 가장 적합한 알고리즘/라이브러리는 무엇입니까?
대상 언어는 C ++입니다
해결책
단어와 함께 해시 테이블을 만들고 텍스트를 스캔하고 WordTable의 각 단어 조회에 대해 필요한 정보를 작성하십시오 (증분 수, 위치 목록에 추가).
다른 팁
나는 한때 Boyer-Moore 알고리즘을 사용했고 그것은 매우 빠릅니다.
Boyer-Mooore는 많은 단어를 효율적으로 검색하기에 적합하지 않습니다. Wu-Manber 알고리즘이라고하는 것을 실제로 수행하기위한 매우 효율적인 알고리즘이 있습니다. 참조 구현을 게시하겠습니다. 그러나 교육 목적으로만이 일을했음을 알 수 있습니다. 따라서 구현은 직접 사용에 적합하지 않으며 더 효율적일 수도 있습니다.
또한 사용합니다 stdext::hash_map dinkumware stl에서. 함께 std::tr1::unordered_map 또는 적절한 구현.
알고리즘에 대한 설명이 있습니다 강의 대본 Knut Reinert가 보유한 Freie Universität Berlin의 강의에서.
그만큼 원본 종이 또한 온라인이지만 (다시 찾았습니다) 나는 그곳에 제시된 의사 코드가 특히 좋아하지 않습니다.
#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;
ㅏ 블룸 필터 최선의 방법 일 수 있습니다. 검색어로 필터를 초기화 한 다음 코퍼스를 읽는 동안 각 작업이 필터에 있는지 빠르게 확인할 수 있습니다.
그것은 매우 공간 효율적이며 단순히 각 단어를 해시하는 것보다 훨씬 낫습니다. 1% 오 탐 양성 속도로 요소 당 9.6 비트 만 필요합니다. 오 탐 양성 속도는 요소 당 추가 4.8 비트마다 10 배로 감소합니다. 이것을 일반 해싱과 대조하십시오. 일반적으로 요소 당 (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!");
코퍼스가 너무 커지면 이런 식으로 최적화하십시오.
확인 해야하는 각 단어의 해시를 계산하고 각 숯에 정수 소수를 할당 한 다음 각 숫자를 함께 곱하십시오. 각 숫자-> 단어를 멀티 맵에 저장하십시오 (단일 키에서 여러 값을 허용해야 함).
WordList를 스캔하는 동안 각 단어에 대해 동일한 방식으로 해시를 계산 한 다음 해시 맵에서 계산 된 키와 관련된 단어를 가져옵니다. 정수를 키로 사용하면 O (1)을 검색합니다. 이 방법으로 처리 된 단어에지도 내부에 아나그램 (곱한 문자)이 있으면 정말 빠른 방식으로 찾을 수 있습니다.
기억하십시오 : 당신은 동일한 해시를 갖는 단어의 세트를 멀티 맵에 저장 했으므로 이제이 크게 줄어드는 세트에서 일치를 찾아야합니다. 지도에 정수의 단순히 존재하는 것이 관련 세트의 단어의 존재와 동일하지 않으므로이 추가 점검이 필요합니다. 우리는 여기에 해싱을 사용하여 문제의 계산 공간을 줄입니다. 그러나 이것은 필요한 충돌을 소개합니다. 식별 된 각 아나그램을 확인하십시오.
사용 AHO-CORASICK 알고리즘. 이 응용 프로그램을 위해 만들어졌습니다. 검색 텍스트의 각 문자 만 읽어야합니다. 나는 최근에 훌륭한 결과와 함께 구현하고 사용했습니다.
Javier가 말했듯이 가장 간단한 솔루션은 아마도 해시 테이블 일 것입니다.
C ++에서는 STL 세트를 사용하여 구현할 수 있습니다. 먼저 세트에 25,000 테스트 단어를 추가 한 다음 텍스트의 각 단어를 스캔하여 Set.Find (current_word)를 사용하여 단어가 25,000 테스트 단어 중 하나인지 평가하십시오.
Set.Find는 로그가 빠르므로 25,000 개의 테스트 단어가 너무 크지 않아야합니다. 알고리즘은 텍스트의 단어 수에서 분명히 선형입니다.
검색하는 텍스트가 크면 전처리를 수행하는 것이 좋습니다. 25,000 단어를 트리로 조립하십시오.
텍스트에서 첫 번째 단어의 시작 부분을 스캔하고 단어의 글자를 걸을 때 트리를 걷기 시작하십시오. 트리에 전환이 없으면 다음 단어의 시작으로 건너 뛰고 트리의 뿌리로 돌아갑니다. 단어의 끝에 도달하고 트리의 단어 종단 노드에 있다면 일치를 찾았습니다. 텍스트의 각 단어에 대해 반복하십시오.
텍스트가 단지 크고 (거대하지 않고), 해시 테이블에서 각 단어를 찾는 것만으로는 충분할 것입니다.
부사장은 말한다 :
나는 한때 Boyer-Moore 알고리즘을 사용했고 그것은 매우 빠릅니다.
Boyer-Mooore를 사용하면 일반적으로 텍스트 블록을 검색하지 않습니까? 하나의 끈?
구현하는 솔루션을 간단하게하려면 Javier가 제안한 해시 테이블 접근 방식을 사용하십시오. FatCat1111이 제안한 블룸 필터는 목표에 따라 작동해야합니다.
디스크의 버클리 DB 해시 테이블에 초기 사전 (25000 단어)을 저장할 수 있습니다. C/C ++에서 직접 사용할 수 있으며 (Perl에서 할 수 있다는 것을 알고 있습니다) 텍스트의 각 단어에 대해 쿼리. 데이터베이스에있는 경우.
텍스트와 단어 목록을 알파벳순으로 정렬 할 수도 있습니다. 두 개의 정렬 된 배열이 있으면 선형 시간에 일치를 쉽게 찾을 수 있습니다.
AHO-CORASICK 알고리즘은 그 목적을 위해 특별히 구축되었습니다. 한 번에 많은 단어를 검색합니다.
