есть задача подсчитать количество уникальных слов в тексте и сохранить их в вектор (составить словарь), но с ограничением, что слова между собой нельзя сравнивать. Как это можно сделать?
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, он необычайно быстрый и при этом имеет очень мало коллизий.
-
И все же, вы знаете какая именно хэш-функция (тут написано -- The actual hash functions are implementation-dependent) используется, чтобы утверждать, что коллизии происходят
"раз на триллион слов"
?– avp21 дек 2020 в 17:17 -
@avp В популярных компиляторах (MSVC, GCC, CLang) используют как раз очень сильные функции с хорошей устойчивостью к коллизиям. Т.е. там не просто сумма байт. Я смотрел реализации. Кроме того есть две возможности - либо использовать SHA-512 реализацию (простые одно-файловые реализации всюду доступны), либо можно вместо одной хеш функции использовать портфель функций, например просто добавив в начало каждой строки 5 различных фиксированных префиксов мы получаем 5 различных функций. Общую функцию мы получим как конкатенацию хешей этих 5 функций. Это сильно повысит качество общего хеша.– Arty21 дек 2020 в 17:22
-
@avp Т.е. тут вопрос в том, насколько идеально нужно решить задачу. Если нам действительно очень точно надо решить, то просто возьмём SHA-512. А если достаточно приблизительно очень качественного решения, то моё решение подойдёт для известных хороших компиляторов с хорошей реализацией хеша.– Arty21 дек 2020 в 17:23
-
Т.е. что именно стоит за
std::hash<std::string> hasher
(SHA-512 или Bernstein), скажем в g++ 7.5 вы не знаете? (Т.о. оценить время работы не удастся)– avp21 дек 2020 в 17:25 -
На практике SHA-512 для подобной задачи (64 байта для любого слова (сколько оно в среднем? байт 6, наверное)) брать в любом случае не стоит– avp21 дек 2020 в 17:27
Например так :)
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;
-
1Кстати говоря std::set как раз таки сравнивает на равенство слова, внутри своего кода, т.е. если строго делать то что просил автор вопроса, то думаю нужно std::unordered_set использовать.– Arty21 дек 2020 в 16:03
-
std::unordered_set никогда не даёт осечки, он разделяет объекты по хешу, но если хеш совпал то для перестраховки проверяет на равенство сами объекты, т.е. равенство строк всё таки делает. Но просто он делает это редко, т.к. хеш совпадёт редко. Более того он даже весь хеш не использует а только часть младших бит. Так что думаю с точки зрения "не-сравнения-на-равенство" unordered_set идеален, сравнивает редко, и никогда не промахивается.– Arty21 дек 2020 в 16:09
-
2@Arty мы не сравниваем слова явно, и я думаю в данной задаче
unordered_set
иset
на одном уровне. Я например в конец каждой строки могу добавлять какой нибудь один символ и уже использоватьset
т.к. я не сравниваю сами слова, а сравниваюмодифицированную
строку, как и хеши. Почему нет 21 дек 2020 в 16:10 -
1@Arty "сравнивает редко" хмм. А разве это не противоречие задаче? Сравнение ведь произойдет когда нибудь 21 дек 2020 в 16:11
-
1@Arty зная как точно работает
unordered_set
вы написали первый комментарий, где написали, что "если строго делать то что просил автор вопроса, то думаю нужно std::unordered_set использовать", а пришло все к тому, чтоunordered_set
так же сравнивает, но реже. Хмм... 21 дек 2020 в 16:15
set
.unorder*
которые работают именно через хэш функции