Мне нужно найти в нем ~ 25 000 слов. Каков наиболее подходящий алгоритм/библиотека для этой цели?
целевой язык - С++
Поиск 25 000 слов в тексте
Ответ 1
постройте хэш-таблицу со словами и просмотрите текст, для каждого поиска слов в текстовом столе и всю необходимую информацию (количество приращений, добавить в список позиций, что угодно).
Ответ 2
Я когда-то использовал алгоритм Бойера-Мура, и это было довольно быстро.
Бойер-Мур не склонен к эффективному поиску многих слов. На самом деле существует очень эффективный алгоритм для этого, называемый алгоритмом У-Манбера. Я отправлю ссылочную реализацию. Обратите внимание, однако, что я сделал это некоторое время назад только для образовательной цели. Следовательно, реализация не очень подходит для прямого использования, а также может быть более эффективной.
Он также использует stdext::hash_map из Dinkumware STL. Подпишитесь на std::tr1::unordered_map или соответствующую реализацию.
Там объяснение алгоритма в лекции script из лекции в Университете 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;
Ответ 3
A Bloom Filter может быть вашим лучшим выбором. Вы инициализируете свой фильтр своими поисковыми запросами, а затем, читая свой корпус, можете быстро проверить, работает ли каждая работа в фильтре.
Это очень эффективное пространство, намного лучше, чем просто хэширование каждого слова: с 1% ложноположительной скоростью он должен требовать всего 9,6 бит на элемент. Ложноположительная скорость уменьшается в 10 раз для каждого дополнительного 4,8 бит на элемент. Сравните это с простым хешированием, которое обычно требует sizeof (int) == 32 бит на элемент.
У меня есть реализация на С# здесь: 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!");
Ответ 4
если корпус настолько велик, попробуйте его оптимизировать следующим образом:
вычислить хэш каждого слова, которое нужно проверить, присваивая каждому char целочисленное простое число, а затем умножая каждое число вместе, сохраняя каждое число- > слово в мультимаре (вам нужно разрешить множественное значение в одном ключ)
при сканировании словарного списка, вычислите хэш таким же образом для каждого слова, затем получите слово (и), связанное с вычисленным ключом на хэш-карте. используя целые числа в качестве ключа, вы получаете выбор O (1); таким образом, вы могли бы найти очень быстрый способ, если обработанное слово имеет некоторую анаграмму (вы умножаете символы) внутри карты.
помните: вы сохранили в мультимаге набор слова, имеющего тот же самый хэш, поэтому теперь вам нужно найти совпадение в этом значительно уменьшенном наборе. вам нужна эта дополнительная проверка, поскольку простое существование целого числа на карте не приравнивается к существованию слова в ассоциированном множестве: мы используем хеширование здесь, чтобы уменьшить вычислительное пространство проблемы, но это вводит столкновение, которое необходимо быть неоднозначно проверять каждую идентифицированную анаграмму.
Ответ 5
Используйте алгоритм Aho-Corasick. Это было сделано для этого приложения. Вам нужно будет только прочитать каждое письмо в тексте поиска один раз. Я недавно реализовал и использовал его с отличными результатами.
Ответ 6
Как говорит Хавьер, самым простым решением, вероятно, является хеш-таблица.
В С++ это может быть реализовано с использованием набора STL. Сначала добавьте 25 000 тестовых слов к набору, а затем сканируйте каждое слово в тексте, используя set.find(current_word), чтобы оценить, является ли это слово среди 25 000 тестовых слов.
set.find логарифмически быстро, поэтому 25 000 тестовых слов не должны быть слишком большими. Алгоритм, очевидно, является линейным по числу слов в тексте.
Ответ 7
Если текст, который вы ищете, огромен, то, возможно, стоит выполнить некоторую предварительную обработку: собрать ваши 25 000 слов в TRIE.
Сканируйте до начала первого слова в тексте и начните ходить по TRIE, когда будете ходить по буквам слова. Если в TRIE нет перехода, перейдите к началу следующего слова и вернитесь к корню TRIE. Если вы дойдете до конца слова, и вы в конце слова node в TRIE, вы нашли совпадение. Повторите для каждого слова в тексте.
Если ваш текст просто большой (а не огромный), то просто поиск каждого слова в хеш-таблице, вероятно, достаточно.
Ответ 8
ViceBerg говорит:
Я когда-то использовал алгоритм Бойера-Мура и это было довольно быстро.
С Boyer-Moore, вы обычно не ищете блок текста для строки single?
Для простого внедрения решения перейдите к подходу хеш-таблицы, предложенному Хавьером. Фильтр Bloom, предложенный FatCat1111, должен также работать... в зависимости от целей.
Ответ 9
Возможно, вы сохраните свой исходный dictionnary (25000 слов) в хеш-таблице berkeley db на диске, который вы, вероятно, можете использовать непосредственно из c/С++ (я знаю, что вы можете сделать это с perl), и для каждого слова в текст, запрос, если он присутствует в базе данных.
Ответ 10
Вы также можете сортировать текст и список слов в алфавитном порядке. Когда у вас есть два сортированных массива, вы можете легко найти совпадения в линейном времени.
Ответ 11
Вы хотите Тройное дерево поиска. Хорошую реализацию можно найти здесь.
Ответ 12
Алгоритм Aho-Corasick построен специально для этой цели: поиск нескольких слов сразу.