Самый эффективный способ создания наивного алгоритма суммирования текста

Я строю простой наивный текстовый алгоритм. Алгоритм работает так:

  • Первый шаг моего алгоритма — удалить все стоп-слова (остановить слова на английском).
  • После того, как мой текст содержит только слова с реальным значением, я собираюсь посмотреть, сколько раз каждое слово используется в тексте, чтобы найти частоту слова. Например, если слово «суперкомпьютер» используется 5 раз, оно будет иметь frequency = 5,
  • Затем я собираюсь рассчитать вес каждого предложения, разделив sum of the frequencies of all words in the sentence к number of the words in the sentence,
  • На последнем шаге я собираюсь отсортировать предложения по длине.

Мне нужно написать этот алгоритм на C ++ (как модуль V8 NodeJS), но проблема в том, что в последние несколько лет я работал в основном с высокоуровневыми языками сценариев, такими как Javascript, и я не настолько опытен в C ++. В javascript я мог бы просто использовать регулярные выражения, чтобы удалить все стоп-слова, а затем найти частоту, но в C ++ это выглядит намного сложнее.

Мне пришла в голову следующая идея:

struct words {
string word;
int freq;
}

std::vector<words> Words;
  • Стоп-слова будут предварительно загружены в локальный массив V8 или std :: vector.
  • Для каждого слова в тексте я собираюсь просмотреть все стоп-слова, если текущее слово не является стоп-словом, а затем проверить, есть ли оно в структуре, если нет -> добавить новый word к Words vector, если существует, увеличьте частоту на 1.
  • После того, как я нашел все частоты всех слов, я собираюсь снова пройтись по тексту, чтобы найти вес каждого предложения.

И с этой идеей у меня возникло несколько проблем:

  1. Мои тексты будут в основном более 1000 слов. И для каждого слова, проходящего через более 100 стоп-слов, будет выполнено 100000 итераций, просто чтобы определить стоп-слова. Это кажется действительно неэффективным.
  2. После того, как у меня будут частоты, мне нужно будет еще раз пройтись по тексту 1000+ слов с 300+ словами (в векторных частотах), чтобы вычислить вес каждого предложения.

Моя идея кажется неэффективной, но я не очень хорошо знаком с C ++.

Итак, мои вопросы: есть ли лучшие способы сделать это или оптимизировать мой алгоритм, особенно проблемы, которые я перечислил выше?

Я беспокоюсь о производительности моего алгоритма, и любые советы / предложения будут с благодарностью.

-1

Решение

Для стоп-слов, посмотрите на std::unordered_set. Вы можете хранить все свои строки стоп-слов в std::unordered_set<string>тогда, когда у вас есть строка, которую вы хотите сравнить, позвоните count(string) чтобы увидеть, если это существует.

Для пар слово / частота используйте std::unordered_map как в некоторых комментариях. Это будет быстрее, если вы выполните поиск и вставку в одном поиске карты. Попробуйте что-то вроде этого:

struct Frequency
{
int val;
Frequency() : val(0) {}
void increment()
{
++val;
}
};

std::unordered_map<std::string, Frequency> words;

void processWord(const std::string str)
{
words[str].increment();
}

words[str] ищет слово на карте, добавляя его, если оно не существует. Новые слова будут вызывать конструктор Frequency, который инициализируется нулем. Так что все, что вам нужно сделать, это позвонить processWord на каждое слово.

0

Другие решения


По вопросам рекламы [email protected]