Задание на весь модуль

Общая цель: написать программу, выравнивающую параллельные тексты.

Точная постановка задачи:

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

• Программа строит выравнивание с помощью алгоритма Нидельмана-Вунша. Весовая функция программы основана на сравнении количества частей речи в разных предложениях. Например, (N₁*N₂+V₁*V₂+A₁*A₂)²/((N₁²+V₁²+A₁²)*(N₂²+V₂²+A₂²)), то есть, если представить описание предложения как вектор S, то вес есть ничто иное, как (S1S2 / (|S1||S2|))² - скалярное произведение, делённое на произведение длин (и всё вместе в квардрате).

• Программа выдаёт выравнивание в виде таблицы (в формате CSV с табулятором в качестве разделителя), в котором в каждой строчке выведена одна пара выровненных предложений или одно предложение и пустота напротив него.
• В программе настраивается штраф за indel (пропуск предложения в одном из текстов).
• Исходный текст программы должен быть читаемым. Программа не должна содержать строк длиннее 75 символов, и определения функций длиннее 15 строк (включая все let и where). Имена функций и переменных в программе должны быть содержательными там, где это возможно. Текст программы и история его изменений должен храниться в репозитории.

Свобода творчества:

• Вы сами определяете, в каком формате читать морфологическую разметку. Можете, например, потребовать файл в виде таблицы с двумя столбцами: слово и часть речи. (Но вы должны уметь сами такие файлы создавать для тестирования)
• Вы вольны выбирать набор признаков, которые вы сравниваете. Андрей Кутузов в магистерской курсовой работе показал, что при некоторой весовой функции количество существительных и количество глаголов работает лучше, чем если добавить к признакам другие части речи. Из этого не следует, что такой набор признаков лучше всегда.
• Вы вольны выбирать весовую функцию на свой вкус.
• Вы вольны выбрать другой выходной формат, если вдруг вы можете придумать что-то проще такой таблицы
• От вас не требуется, чтобы программа работала быстро (достаточно, если она может выровнять пару текстов из пяти предложений), однако, если она у вас работает очень медленно, а вы хотите заставить её работать быстро, то стоит погуглить слова "haskell memoization".

Алгоритм Нидельмана-Вунша

Если отказаться от сложностей википедии, то алгоритм состоит в том, что мы считаем вес выравнивания для разных ситуаций и выбираем ситуацию с наилучшим весом.

• вес([],[]) = 0
• вес(a:as,b:bs) = максимум (вес1, вес2, вес3)
• где:
  • вес1 = весовая функция(а,b) + вес(as,bs)
  • вес2 = штраф + вес(a:as, b)
  • вес3 = штраф + вес(as, b:bs)

И соответствующим образом в зависимости от веса выдаётся и ответ выравнивания.