Как посчитать количество уникальных слов?

Question

есть задача подсчитать количество уникальных слов в тексте и сохранить их в вектор (составить словарь), но с ограничением, что слова между собой нельзя сравнивать. Как это можно сделать?

Answer 1

Например так :)

string str;
getline(cin, str);

//Разделители слов
string delims = "!?. ";
//Набор уникальных слов
set<string> unique_words;
//Позиция предыдущего слова
size_t prev = 0;
//Позиция следующего слова
size_t next;
do {
    //Получаем позицию начала нового слова
    next = str.find_first_of(delims, prev);
    //Обрезаем строку добавляя слово в набор
    if(next != prev)
        unique_words.insert(str.substr(prev, next - prev));
    prev = next + 1;
} while (next != string::npos);

cout << "Кол-во уникальных слов: " << unique_words.size() << endl;
for (set<string>::iterator it = unique_words.begin(); it != unique_words.end(); ++it)
    cout << *it << endl;

Answer 2

Написал небольшую программу, которая выводит число уникальных слов и сами слова. Использует std::unordered_set который не сравнивает слова на равенство, а определяет уникальность вычислением хеш функции от слов, плюс изредка сравнивает на равенство при совпадении хеша для перестраховки.

Такой алгоритм должен работать быстро для больших данных и его время выполнения растёт линейно с ростом размера текста.

Для разбиения текста на слова используется модуль std::regex, т.е. регулярные выражения, регулярное выражение у меня определяет разделитель слов, другими словами знаки пунктуации и пробелы, отредактируйте sepre выражение чтобы добавить новые знаки разделения.

Попробовать онлайн!

#include <string>
#include <regex>
#include <iostream>
#include <unordered_set>

int main() {
    std::string text = "Hello, world! world again.";
    std::unordered_set<std::string> words;
    std::regex sepre(R"([\s,\.\!\-]+)");
    std::sregex_token_iterator iter(text.begin(), text.end(), sepre, -1), end;
    for (; iter != end; ++iter)
        words.insert(*iter);
    std::cout << "Number of unique words: " << words.size() << std::endl;
    for (auto const & w: words)
        std::cout << w << "|";
}

Вывод:

Number of unique words: 3
again|Hello|world|

Предыдущий вариант решения отличается тем, что он всё таки делает сравнение строк на равенство, но редко. Т.е. если вопрос в скорости то он идеальный алгоритм. Но если задача стоит именно никогда не сравнивать строки, то предлагаю второй вариант. Он использует только равенство хешей для определения совпадения строк, т.е. строки никогда не сравнивает. Для этого я использовал std::unordered_map и std::hash. Единственный недостаток этого алгоритма в том что очень-очень редко при коллизии хешей (совпадении хешей) он может пропустить некоторые слова, но эту ошибку он допускает супер редко (раз на триллион слов на 64-битных машинах, при условии что компилятор реализовал качественную хеш функцию), так что можно считать что алгоритм идеальный в практических условиях.

Попробовать онлайн!

#include <string>
#include <regex>
#include <iostream>
#include <unordered_map>
#include <functional>

int main() {
    std::string text = "Hello, world! world again.";
    std::unordered_map<size_t, std::string> words;
    std::hash<std::string> hasher;
    std::regex sepre(R"([\s,\.\!\-]+)");
    std::sregex_token_iterator iter(text.begin(), text.end(), sepre, -1), end;
    for (; iter != end; ++iter)
        words[hasher(*iter)] = *iter;
    std::cout << "Number of unique words: " << words.size() << std::endl;
    for (auto const & p: words)
        std::cout << p.second << "|";
}

Также в последнем алгоритме выше можно заметить, что используется лишняя операция и память для хранения самих слов. Если нам нужно вывести только число уникальных слов, но не нужно выводить сами уникальные слова, то алгоритм можно упростить и ускорить и сэкономить память, убрав хранение самих слов и используя std::unordered_set. Также в этом финальном алгоритме можно заметить, что раз мы не храним слов вообще, то очевидно что мы их не сравниваем и даже не можем сравнить на равенство никак.

Попробовать онлайн!

#include <string>
#include <regex>
#include <iostream>
#include <unordered_set>
#include <functional>

int main() {
    std::string text = "Hello, world! world again.";
    std::unordered_set<size_t> words;
    std::hash<std::string> hasher;
    std::regex sepre(R"([\s,\.\!\-]+)");
    std::sregex_token_iterator iter(text.begin(), text.end(), sepre, -1), end;
    for (; iter != end; ++iter)
        words.insert(hasher(*iter));
    std::cout << "Number of unique words: " << words.size() << std::endl;
}

Замечание!!! Я в коде использовал стандартные хеш-функции предоставленные в STL компилятором. На самом деле компилятор может их реализовать как стойкими к коллизиям, так и нет, стандартом это не оговаривается. От этого будет зависеть качество алгоритма. Если необходимо очень точное решение, то нужно взять SHA-512 функцию в интернете (есть много авторов GitHub кто предоставляет компактную реализацию этой функции в одно-файловой библиотеке). Если стоит вопрос скорости, то лучше взять xxhash, он необычайно быстрый и при этом имеет очень мало коллизий.

БЛОГ НА HUSL

Как посчитать количество уникальных слов?

Ответы (2 шт):