поиск по 25 000 слов в тексте
-
03-07-2019 - |
Вопрос
Мне нужно найти в тексте вхождения ~25 000 слов.Какой алгоритм/библиотека наиболее подходит для этой цели?
целевой язык — C++
Решение
создайте хеш-таблицу со словами и просканируйте текст для поиска каждого слова в таблице слов и заполните необходимую информацию (увеличьте количество приращений, добавьте в список позиций и т. д.).
Другие советы
Однажды я использовал алгоритм Бойера-Мура, и он оказался довольно быстрым.
Бойер-Мур не способен эффективно искать множество слов.На самом деле для этого существует очень эффективный алгоритм, называемый алгоритмом Ву-Манбера.Я опубликую эталонную реализацию.Однако обратите внимание, что некоторое время назад я сделал это только в образовательных целях.Следовательно, реализация на самом деле не пригодна для прямого использования, и ее также можно сделать более эффективной.
Он также использует stdext::hash_map
из Dinkumware STL.Заменить на std::tr1::unordered_map
или соответствующую реализацию.
Объяснение алгоритма есть в сценарий лекции из лекции Кнута Райнерта в Свободном университете Берлина.
А оригинальная бумага тоже есть в сети (только что снова нашел), но мне не особенно нравится представленный там псевдокод.
#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 бита на элемент.Частота ложноположительных результатов снижается в 10 раз на каждые дополнительные 4,8 бита на элемент.Сравните это с простым хешированием, для которого обычно требуется 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!");
если корпус такой большой, попробуйте оптимизировать его следующим образом:
вычислите хеш каждого слова, которое вам нужно проверить, назначив каждому символу целое простое число, а затем умножив каждое число вместе; сохраните каждое число->слово в мультикарте (вам необходимо разрешить несколько значений для одного ключа)
при сканировании списка слов вычислите хеш одинаковым образом для каждого слова, а затем получите слово(а), связанные с вычисленным ключом на хэш-карте.используя целые числа в качестве ключа, вы получаете O(1);таким образом вы сможете очень быстро найти, есть ли в обработанном слове какая-то анаграмма (вы умножили символы) внутри карты.
помнить:вы сохранили в мультикарте набор слов, имеющих тот же хэш, поэтому теперь вам нужно найти совпадение в этом значительно уменьшенном наборе.вам нужна эта дополнительная проверка, поскольку простое существование целого числа на карте не означает существование слова в связанном наборе:мы используем здесь хеширование, чтобы уменьшить вычислительное пространство задачи, но это приводит к коллизии, которую необходимо устранить, проверяя каждую идентифицированную анаграмму.
Использовать Алгоритм Ахо-Корасика.Это было сделано для этого приложения.Вам нужно будет прочитать каждую букву в тексте поиска только один раз.Недавно я внедрил и использовал его с отличными результатами.
Как говорит Хавьер, самое простое решение — это, вероятно, хеш-таблица.
В C++ это можно реализовать с помощью набора STL.Сначала добавьте в набор 25 000 тестовых слов, а затем просмотрите каждое слово в тексте, используя set.find(current_word), чтобы оценить, входит ли это слово в число 25 000 тестовых слов.
set.find работает логарифмически быстро, поэтому 25 000 тестовых слов не должны быть слишком большими.Алгоритм, очевидно, линеен по количеству слов в тексте.
Если текст, который вы ищете, огромен, возможно, стоит выполнить предварительную обработку:соберите свои 25 000 слов в TRIE.
Сканируйте до начала первого слова в тексте и начните проходить TRIE, проходя по буквам слова.Если в вашем TRIE нет перехода, перейдите к началу следующего слова и вернитесь к корню TRIE.Если вы достигли конца слова и находитесь в узле окончания слова в TRIE, вы нашли совпадение.Повторите для каждого слова в тексте.
Если ваш текст просто большой (а не огромный), то, вероятно, достаточно просто найти каждое слово в хеш-таблице.
вицеБерг говорит:
Однажды я использовал алгоритм Бойера-Мур, и это было довольно быстро.
С Бойером-Муром разве вы обычно не ищете в блоке текста одинокий нить?
Для простоты реализации решения используйте подход хэш-таблицы, предложенный Хавьером.Фильтр Блума, предложенный FatCat1111, тоже должен работать...в зависимости от целей.
Возможно, вы сохраните свой первоначальный словарь (25000 слов) в хеш-таблице Berkeley db на диске, которую вы, вероятно, сможете использовать непосредственно из C/С++ (я знаю, что вы можете сделать это из Perl), и для каждого слова в тексте запросите если он присутствует в базе данных.
Вы также можете сортировать текст и список слов в алфавитном порядке.Если у вас есть два отсортированных массива, вы можете легко найти совпадения за линейное время.
Вы хотите Троичное дерево поиска.Хорошую реализацию можно найти здесь.
Алгоритм Ахо-Корасика создан специально для этой цели:поиск многих слов одновременно.