Данная лабораторная работа является продолжением работ 10 и 11. Цель — использование частотных словарей и вычисления косинусного коэффициента для определения языковой принадлежности текста.
Итак, дано:
Требуется определить язык, к которому принадлежит текст.
Метод:
Пусть даны два частотных словаря A и B в виде отображения слово → частота, где под частотой понимается количество повторений слова (целое число). В C++ такое отображение можно хранить как объект map.
Пусть задано некое преобразование f: ℕ → ℝ+ (“поправка”). Тогда косинусным коэффициентом назовём число
cosf(A, B) = A·fB / (sqrt(A·fA) sqrt(B·fB)),
где
A·fB = Σ { f(x) f(y) | s — слово и (s → x)∈A, (s → y)∈B }.
Иными словами, требуется перебрать все слова одного словаря (например, A или, лучше, того из A и B, который имеет меньший размер) и для слов, которые есть в другом словаре, добавить к сумме произведение “поправленных” частот. Поправку разумно применять сразу при считывании словаря, получая map<string, double>.
В качестве поправки рекомендуется взять функцию
f(x) = 1 + log10(x).
Предлагаемая программа уже не опирается на средства локализации Стандартной библиотеки C++. В качестве кодировки текстов (и словарей) используется UTF-8. Для внутренней обработки — UTF-32. Преобразование между кодировками выполняется с помощью простенькой сторонней библиотеки UTF8-CPP. Данная библиотека не требует установки, достаточно распаковать архив рядом с исходником использующей её программы.
Задача классификации “буква”-“небуква”, а также замены заглавных букв на соответствующие им маленькие буквы решается с помощью таблицы описания символов Юникод, доступной на Unicode.org. Программа считывает таблицу из локально размещённого файла Categories.txt.
Смотрим main. Все описанные функции определены в исходнике, ссылка на который дана в конце раздела:
// Читаем информацию о символах Юникод из файла Categories.txt.
ifstream categories_desc("Categories.txt");
const auto unicode_info = read_unicode_info(categories_desc);Функция read_unicode_info строит описание символов Юникод (в виде vector<Codepoint_entry>, где Codepoint_entry — структура, поля которой отвечают колонкам таблицы Categories.txt).
const auto letter = select_category(unicode_info, "L");Функция select_category генерирует булевскую таблицу (vector<bool>), индексируемую кодом символа и возвращающую истину, если символ принадлежит заданной категории и ложь в противном случае. Здесь мы создаём таблицу принадлежности символа категории L (буквы).
const auto up2lo = upper_to_lower_mapping(unicode_info, letter);Функция upper_to_lower_mapping создаёт отображение заглавная буква → маленькая буква, отображающее коды символов Юникод. Таблица принадлежности буквам letter передаётся с целью ускорения работы: поиск соответствий осуществляется только среди букв, а не среди всех символов.
// Читаем исходный файл в строку и транскодируем в UTF-32.
auto text = unchecked_utf8_to_utf32(file_to_string(input));Функция file_to_string читает содержимое потока ввода (здесь — input) целиком и возвращает его в виде объекта string. Функция unchecked_utf8_to_utf32 конвертирует строку в кодировке UTF-8 (средствами библиотеки UTF8-CPP) в последовательность (vector) кодов Юникод (т.е. в кодировку UTF-32).
// Приводим к нижнему регистру и считаем слова.
const auto sf = count_words(apply_map(text, up2lo), letter);Функция apply_map применяет отображение (словарь замен кодов, здесь — up2lo) к контейнеру (здесь — text) на месте и возвращает ссылку на свой первый аргумент. Функция count_words принимает UTF-32 и булевскую таблицу, которая определяет, какие символы считать буквами, и возвращает отображение слово → частота.
Итак, sf — частотный словарь исходного текста, считанного из input, но в кодировке UTF-32. Словари (точнее, слова из них), считываемые из файлов, также требуется приводить к кодировке UTF-32 — для этой цели предусмотрена функция unchecked_utf8_to_utf32.
Исходный код целиком:
Код, расположенный в main между строчками
const auto sf = count_words(apply_map(text, up2lo), letter);и
return 0;выполняет сортировку слов по частотам и сохранение частотного словаря в файл. Для выполнения лабораторной это не требуется.
Предлагается вычислять косинусный коэффициент не для исходных значений частот, а для их логарифмов (сдвинутых на единицу). Можно сразу строить словарь с расчётом на это.
Требуется:
#include <cmath>.Word_frequencies) с uint64_t на double.count_words добавить цикл, проходящий result и заменяющий всякое значение в нём на 1 + log10(значение).
Написать функцию
double cos(const Word_frequencies &a, const Word_frequencies &b)
{
if (b.size() < a.size())
return cos(b, a);
// Пройтись по словарю a, вычислив скалярное произведение a на b и a на a.
// Пройтись по словарю b, вычислив скалярное произведение b на b.
// Вычислить и вернуть косинусный коэффициент.
}
Написать функцию
Word_frequencies read_dictionary(istream &from)
{
Word_frequencies result;
// ...
return result;
}Файл со словарём состоит из строк, каждая из которых содержит слово (кодировка UTF-8) и частоту. Таким образом, следует в цикле читать из потока from пары строк (string) и чисел (double).
Строку следует преобразовать в кодировку UTF-32 вызовом функции unchecked_utf8_to_utf32. Число прологарифмировать (заменить на 1 + log10). Каждая пара полученных значений должна быть вставлена в result.
В main на месте удалённого кода:
string: название языка и название файла частотного словаря этого языка.
read_dictionary).sf.Кувшинов Д.Р. © 2017