Дано имя текстового файла, требуется определить частоты слов, содержащихся в этом файле.
“Дефис” (минус -) считать буквой, остальные небуквенные символы считать пробелами. Большие буквы отождествлять с маленькими (всё приводить к маленьким). Результат вывести в другой файл в виде последовательности пар слово частота, по одному слову в строке, в порядке убывания частот.
Для решения данной задачи требуется уметь решать следующие подзадачи:
Всё это в целом — слишком большое задание для одной лабораторной. Поэтому для данных подзадач ниже предложены заготовки решений, из которых требуется собрать решение исходной задачи.
Если итоговый результат для достаточно большого текста на естественном языке изобразить в виде графика (можно, например, открыть в MS Excel и построить диаграмму), то получится характерная картина. Такие заранее сгенерированные файлы (эталоны) можно использовать для определения языка произвольного текста (например, определяя эталон, дающий наибольший косинусный коэффициент).
Прочитать содержимое потока ввода (в частности, файла) “пословно”, если слова разделены пробельными символами, можно следующим циклом (с прочитанными словами пока ничего не делаем):
void read_words(istream &is)
{
for (string word; is >> word;)
{ /* word -- очередное слово */ }
}Например, мы могли бы возвращать массив прочитанных слов:
vector<string> read_words(istream &is)
{
vector<string> words;
for (string word; is >> word;)
words.push_back(word);
return words;
}Чтобы подобный код работал в нашем случае, надо как-то сообщить потоку ввода, что мы хотим приравнять символ “-” к букве, а прочие небуквенные символы к пробелу. (Альтернатива для трудолюбивых: читать по одному символу из потока и выполнять классификацию и отделение слов вручную.)
Воспользуемся средствами, предусмотренными в Стандартной библиотеке для решения вопросов поддержки многоязычных сред (“локализации” — std::locale).
Итак, объекты std::locale (далее называемые локали) содержат в себе набор определений — фасеты facets, задающие ту или иную сторону поведения при обработке строк. Объект locale может быть “подключен” к объекту потока ввода или вывода для модификации его поведения.
Сейчас нас интересует фасет std::ctype, определяющий классификацию символов. В случае 8-битных кодировок можно переопределить классификацию символов, создав новый объект ctype с собственной таблицей классификации. Пример создания и использования такой таблицы:
#include <locale> // locale, ctype, ctype_base
#include <iostream>
#include <string>
#include <climits> // CHAR_BIT
using namespace std;
ctype_base::mask*
my_ctype_table(const locale &base_loc)
{
static const auto table_size = 1u << CHAR_BIT;
auto table = new ctype_base::mask[table_size];
for (unsigned i = 0; i < table_size; ++i)
table[i] = isalpha((char)i, base_loc) ?
ctype_base::alpha
: ctype_base::space;
table['-'] = ctype_base::alpha; // "дефис" у нас тоже буква.
return table;
}
int main()
{
// Вариант, работающий для русского языка в консоли при использовании Visual C++.
// При работе с файлами в кодировке Windows-1251 надо заменить 866 на 1251.
// К сожалению, имена локалей не стандартизированы (за исключением "C").
// Кроме того, Стандартом не предусмотрено средство извлечения списка имён поддерживаемых системой локалей.
locale base_loc("Russian_Russia.866");
cout.imbue(base_loc); // Задать локаль потоку вывода.
cout << "Base locale name: " << base_loc.name() << endl;
// Создать новую локаль, подставив фасет ctype с новой таблицей символов.
locale my_loc(base_loc, new ctype<char>(my_ctype_table(base_loc), true));
cout << "Changed locale name: " << my_loc.name() << endl;
cin.imbue(my_loc); // Задать локаль потоку ввода.
cout << "Enter the text, please:\n";
// Читать и выводить слова.
for (string word; cin >> word;)
cout << word << ' ';
return 0;
}При использовании сборок g++ под Windows может оказаться, что реализация Стандартной библиотеки поддерживает только кодировку ASCII. Соответственно, кириллические буквы не будут считаться буквами. На этот случай можно использовать “лобовое” решение с заранее зашитой таблицей для нужной кодировки:
#include <locale>
#include <iostream>
#include <string>
using namespace std;
// Вариант таблицы для кодировки OEM-866.
// Возвращаемый этой функцией объект удалять нельзя.
const ctype_base::mask*
my_ctype_table_866()
{
static const auto
o = ctype_base::space,
l = ctype_base::alpha;
static const ctype_base::mask table[256]
{
// ASCII.
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, o, o, o, o, o, o, o, o, o, o, o, o, l, o, o,
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, o, o, o, o, o,
o, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, o, o, o, o, o,
// Upper half.
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, o, o, o, o, o, o, o, o,
};
return table;
}
// Вариант таблицы для кодировки Windows-1251.
// Возвращаемый этой функцией объект удалять нельзя.
const ctype_base::mask*
my_ctype_table_1251()
{
static const auto
o = ctype_base::space,
l = ctype_base::alpha;
static const ctype_base::mask table[256]
{
// ASCII.
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, o, o, o, o, o, o, o, o, o, o, o, o, l, o, o,
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, o, o, o, o, o,
o, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, o, o, o, o, o,
// Upper half.
l, l, o, l, o, o, o, o, o, o, l, o, l, l, l, l,
l, o, o, o, o, o, o, o, o, o, l, o, l, l, l, l,
o, l, l, l, o, l, o, o, l, o, l, o, o, o, o, l,
o, o, l, l, l, o, o, o, l, o, l, o, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
};
return table;
}
int main()
{
// Возьмём локаль системы по умолчанию.
locale base_loc("");
cout << "Native locale name: " << base_loc.name() << endl;
// Создадим новую локаль, подставив фасет ctype с новой таблицей символов.
// Выбрана таблица OEM-866 для использования в консоли Windows (вариант "по умолчанию").
locale my_loc(base_loc, new ctype<char>(my_ctype_table_866()));
cout << "Changed locale name: " << my_loc.name() << endl;
// Зададим локаль потоку ввода.
cin.imbue(my_loc);
cout << "cin imbued, enter words, please: ";
// Прочитаем и выведем слова.
for (string word; cin >> word;)
cout << word << ' ';
return 0;
}
Для многобайтных кодировок (UTF-8) этот приём, увы, не доступен.
Следующий C++11-код конвертирует прочитанное “слово” в кодировке UTF-8 в кодировку UTF-32, удобную при внутреннем оперировании символами. В C++17 данная часть библиотеки объявлена устаревшей (deprecated), но никакой замены не предложено.
#include <locale>
#include <iostream>
#include <string>
#include <codecvt> // std string conversion
using namespace std;
int main()
{
wstring_convert<codecvt_utf8<char32_t>, char32_t> utf32;
string word;
cin >> word; // UTF-8
u32string word32 = utf32.from_bytes(word);
// Вывести код каждого символа в UTF-32.
for (auto code : word32)
cout << hex << (unsigned)code << endl;
return 0;
}
Локаль позволяет преобразовать строку, заменив все большие буквы (или соответствующие сочетания) на маленькие (tolower) или наоборот (toupper) с помощью того же фасета ctype.
// string word;
use_facet<ctype<char>>(base_loc).tolower(&word[0], &word[0] + word.size());
// Теперь word содержит только маленькие буквы.Если локаль не поддерживает ничего сверх кодировки ASCII, то проще написать конвертацию строки в виде отдельной функции. Для обычных 8-битных кодировок может быть достаточно замены по таблице (символ на символ), но такая операция не учитывает возможных языковых особенностей. Хрестоматийный пример сложности смены регистра из немецкой орфографии: ß ('\xDF' в кодировке Latin-1) может заменяться на SS или SZ и наоборот, на практике эту проблему std::locale не решает. В стандарте Unicode в качестве соответствующей ß большой буквы предусмотрен символ ẞ.
Для конкретной кодировки вместо таблицы можно использовать набор правил, как сделано для кодировок 866 и 1251 в примере ниже.
// Кодировка DOS-866.
string& tolower_866(string &s)
{
for (auto &c: s)
{
unsigned char code = c;
if ((0x41 <= code && code < 0x5B) // ASCII
|| (0x80 <= code && code < 0x90))
c += 32;
else if (0x90 <= code && code < 0xA0)
c += 80;
else switch (code)
{
case 0xF0: case 0xF2: case 0xF4: case 0xF6:
++c;
}
}
return s;
}
// Кодировка Windows-1251.
string& tolower_1251(string &s)
{
for (auto &c: s)
{
unsigned char code = c;
if ((0x41 <= code && code < 0x5B) // ASCII
|| (0xC0 <= code && code < 0xE0))
c += 32;
else switch (code)
{
case 0x80: case 0x8A: case 0x8C:
case 0x8D: case 0x8E: case 0x8F:
case 0xA8: case 0xAA: case 0xAF:
c += 16; break;
case 0xA1: case 0xB2: case 0xBD:
++c; break;
case 0x81: c = '\x83'; break;
case 0xA3: c = '\xBC'; break;
case 0xA5: c = '\xB4'; break;
}
}
return s;
}
Для решения данной задачи требуется реализовать отображение строка → счётчик и увеличивать для каждого прочитанного слова соответствующий счётчик на единицу. Данную задачу можно решить многими способами. Например, с помощью vector (uint64_t — 64-битный целочисленный тип):
void count_words(istream &source, vector<string> &words, vector<uint64_t> &counters)
{
words.reserve(128);
counters.reserve(128);
// Считаем, что source содержит слова, разделённые пробелами.
for (string word; source >> word;)
{
size_t index = 0;
while (index != words.size() && word != words[index])
++index;
if (index != words.size()) // слово есть в words,
{
counters[index]++;
}
else // слова нет в words -- добавим его.
{
words.push_back(word);
counters.push_back(1);
}
}
}У данного метода есть весьма серьёзный недостаток: линейный поиск по всем словам для каждого следующего слова даёт общее квадратичное время по числу считанных слов.
Стандартная библиотека C++ предоставляет ряд средств, позволяющих решать данную и похожие задачи более эффективно. Здесь рассмотрим одно из них: контейнер std::map — “отображение” map. Для его использования необходимо подключить заголовочный файл <map>. См. также здесь.
Контейнер map можно использовать как массив, индексом которого служит аргумент отображения (ключ), а элементом — значение отображения для этого аргумента. На деле map хранит пары “ключ”-“значение” в сбалансированном двоичном дереве поиска, что позволяет находить ключ за логарифмическое время. Если значение ключа не найдено, то соответствующая пара (при использовании операции []) будет создана автоматически со значением по умолчанию (0 для чисел), что нам и требуется.
Итак, пример выше можно переписать с помощью map:
void count_words(istream &source, map<string, uint64_t> &counters)
{
// Считаем, что source содержит слова, разделённые пробельными символами.
for (string word; source >> word;)
counters[word]++;
}
Так как map использует двоичное дерево поиска (по требованию Стандарта C++), пары “ключ-значение” хранятся упорядоченно и могут быть извлечены симметричным обходом дерева в порядке возрастания ключа. Данный факт позволяет решить подзадачу 4 “обращением” словаря — надо обратить стрелку отображения. К сожалению, в нашем случае мы имеем дело с сюръективным отображением, обращение которого может быть неоднозначным: легко представить себе ситуацию, когда разные слова встречаются в тексте одинаковое число раз.
Стандартная библиотека C++ позволяет разрешить данную проблему по-разному. С одной стороны, помимо обычных “отображений” map есть “мультиотображения” multimap. С другой стороны, можно “выложить” пары “ключ-значение” (в порядке “значение-ключ”) в вектор и отсортировать его.
И для того, и для другого надо знать, как пройти по всем парам, хранящимся в map. Для этого предлагается следующий пример (“распечатка map”):
// Вывести в поток произвольный объект map.
template <class K, class V>
ostream& print(ostream &os, const map<K, V> &m)
{
for (auto &kv: m)
os << kv.first << ' ' << kv.second << '\n';
return os;
}Точно в такой же манере можно пройти и multimap (целиком в порядке неубывания ключа).
Если создать вектор пар (std::pair) “ключ-значение”, то заполнить его содержимым некоторого map можно с помощью простого цикла:
vector<pair<uint64_t, string>> vp;
vp.reserve(counters.size());
for (auto &kv: counters)
vp.emplace_back(kv.second, kv.first);Функция emplace_back добавляет в конец элемент, для которого вызывается конструктор, получающий аргументы функции emplace_back (в то время как функция push_back принимает уже созданный элемент, что в данном случае менее удобно).
Отсортировать вектор можно одним вызовом std::sort (из <algorithm>, также предполагается, что подключен <iterator>):
sort(begin(vp), end(vp));Так как multimap сам организует порядок своего содержимого, у него нет функции emplace_back, зато есть аналогичная функция emplace. Вставка осуществляется не в “конец”, а соответственно упорядочению уже имеющихся элементов, так что сортировать multimap не требуется — он всегда отсортирован.
multimap<uint64_t, string> mp;
for (auto &kv: counters)
mp.emplace(kv.second, kv.first);Поскольку нам нужны слова в порядке убывания частоты, идти надо с конца, а не с начала, поэтому for(:) не подходит. Впрочем, обратный порядок обхода предусмотрен в Стандартной библиотеке, хотя его организация и является более многословной (предполагается, что подключен <iterator>):
// Вывести mp в обратном порядке.
for (auto p = rbegin(mp), e = rend(mp); p != e; ++p)
cout << p->first << ' ' << p->second << '\n';Мелким недостатком данного решения является то, что слова с равными частотами будут идти в обратном алфавитному порядке.
Этот недостаток можно устранить, если заменить критерий сравнения ключей (компаратор) на > (std::greater; нужно подключить <functional>). Заодно можно будет проходить multimap в прямом порядке и не использовать rbegin и rend.
void print_map_reverse(const map<string, uint64_t> &counters)
{
multimap<uint64_t, string, greater<>> mp;
for (auto &kv: counters)
mp.emplace(kv.second, kv.first);
for (auto &kv: mp)
cout << kv.first << ' ' << kv.second << '\n';
}Кувшинов Д.Р. © 2017