Лабораторная работа 12: классификация текстового файла

Кувшинов Д.Р.

2017


Общее оглавление


Задача

Данная лабораторная работа является продолжением работ 10 и 11. Цель — использование частотных словарей и вычисления косинусного коэффициента для определения языковой принадлежности текста.

Итак, дано:

Требуется определить язык, к которому принадлежит текст.

Метод:

  1. Построить частотный словарь текста.
  2. Вычислить косинусный коэффициент построенного словаря с каждым из словарей, перечисленных в fdicts.txt.
  3. Указать название языка, для которого косинусный коэффициент получился максимальным.

Вычисление косинусного коэффициента частотных словарей

Пусть даны два частотных словаря A и B в виде отображения словочастота, где под частотой понимается количество повторений слова (целое число). В C++ такое отображение можно хранить как объект map.

Пусть задано некое преобразование f: ℕ → ℝ+ (“поправка”). Тогда косинусным коэффициентом назовём число

cosf(A, B) = A·fB / (sqrt(A·fA) sqrt(B·fB)),

где

A·fB = Σ { f(x) f(y) | s — слово и (sx)∈A, (sy)∈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.

Исходный код целиком:

C++, HTML


Алгоритм модификации программы построения частотного словаря

Убрать лишнее

Код, расположенный в main между строчками

const auto sf = count_words(apply_map(text, up2lo), letter);

и

return 0;

выполняет сортировку слов по частотам и сохранение частотного словаря в файл. Для выполнения лабораторной это не требуется.


Модифицировать словарь

Предлагается вычислять косинусный коэффициент не для исходных значений частот, а для их логарифмов (сдвинутых на единицу). Можно сразу строить словарь с расчётом на это.

Требуется:


Написать функцию, вычисляющую косинусный коэффициент пары словарей

Написать функцию

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 на месте удалённого кода:


Общее оглавление

Кувшинов Д.Р. © 2017