Курсовой проект по дискретному анализу

Целью курсового проекта является самостоятельное решение жизненной задачи.

О выборе варианта и оценке

При оценивании решения будет учитываться:

  1. Производительность.
  2. Качество программного кода.
  3. Удобность использования.
  4. Анализ использованного метода или алгоритма.

Первый студент, сдающий работу некоторого варианта получает оценку в соответствии с выполненной работой. Каждому следующему чтобы получить оценку «хорошо» или «отлично» необходимо выполнить работу лучше, чем те, кто уже сдал и получил соответствующую оценку. Сравнительный анализ проводит сам сдающий.

Последнее требование введено для того, чтобы повысить разнообразие выполняемых вариантов.

Автоматическая классификация документов (nbk)

Реализовать наивный Байесовский классифкатор (НБК) с обучением для автоматической классфикации набора документов относительно двух категорий: C и ¬C.

НБК это один из самых простых алгоритмов автоматической классификации документов с обучением. Подразумевается, что необходимо разбить документы по двум катеориям, дополняющим друг друга и не пересекающимся. Примерами таких категорий могут быть: спам и не спам, статьи про астрофизику и статьи про все остальное и т. п.

При этом имеется некоторый набор документов, который был заранее вручную размечен таким образом, что про каждый документ известно, к какой категории он относится.

Перед классификацией документов НБК должен сначала пройти процесс обучения, т. е. обработки исходного размеченного набора документов, по которым собирается статистика использования слов и выделяются характерные для каждой из тематик свойства. После обучения НБК можно использовать для классификации любых других документов, которые не встречались в обучающем множестве.

На хорошую оценку нужно:

  • Реализовать систему обладающую интерфейсом для обучения и классификации.
  • Выбрать тематику классификации, подобрать обучающее множество.
  • Оценить качество работы системы (точность, полноту). Найти примеры ложных срабатываний, пояснить, почему они появились.
  • Предложить (и, возможно, реализовать) способы улучшения классификатора.

Подробнее про НБК можно прочитать в Википедии.

Генерация текста при помощи марковских цепей (mctg — markov chain text generation)

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

Создание подобной программы подробно описано в качестве примера в книге «Практика программирования» Кернигана и Пайка.

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

Исправление ошибок в поисковых запросах (spc)

Иногда пользователи ошибаются при вводе запроса в поисковую систему. Такие ошибки нужно находить, исправлять запрос или предлагать вариант для исправления.

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

Логи обычно бережно хранятся поисковыми системами. В открытом доступе можно найти только запросы поисковой системы AOL 2006 года: (скачать 43М логов).

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

Подробнее об исправлении ошибок в запросах:

Конкорданс (conc)

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

К примеру, если набор исходных документов содержит в себе полное собрание сочинений Ф.М. Достоевского, то запрос из одного слова «топор» должен вернуть, в частности, следующие контексты:

  • Боже! — воскликнул он, — да неужели ж, неужели ж я в самом деле возьму топор, стану бить по голове, размозжу ей череп. . . буду скользить в липкой, теплой крови, взламывать замок, красть и дрожать; прятаться, весь залитый кровью. . . с топором. . . Господи, неужели?

  • Что же касается петли, то это была очень ловкая его собственная выдумка: петля назначалась для топора. Нельзя же было по улице нести топор в руках. А если под пальто спрятать, то все- таки надо было рукой придерживать, что было бы приметно. Теперь же, с петлей, стоит только вложить в нее лезвие топора, и он будет висеть спокойно, подмышкой изнутри, всю дорогу.

  • Предстояло самое важное дело — украсть из кухни топор. О том, что дело надо сделать топором, решено им было уже давно.
  • и т.д.

При решении задачи нужно рассчитывать на то, что задача поиска слов в коллекции документов возникает значительно чаще, чем изменение самой коллекции. Тем самым, перед выполнением запросов нужно построить некоторые дополнительные индексы для ускорения выполнения запросов. Отдельно стоит обратить внимание на формат вывода контекстов употребления слов. В идеале это должны быть предложения или абзацы, количество которых может регулироваться в запросе. Однако, в силу сложности разбиения текста на предложения, можно выдавать только некоторое количество слов перед и после найденного слова.

Должны быть реализованы две утилиты:

  • Построения индекса, idx_builder.
  • Поиска, idx_searcher.

Утилита построения индекса запускается следующим образом:

$ ./idx_builder [flags] idx-path file1 file2 ...

Здесь idx-path — название подкаталога, в котором должны быть размещены файлы индекса, а последующие за ним аргументы указывают на текстовые файлы, подлежащие индексации. Вы можете задавать опциональные флаги (начинающиеся с дефиса) перед путём к индексу, но все аргументы после названия индекса должны трактоваться как имена файлов.

Программа должна напечтать как минимум следующие строки:

  • ! idx_builder started — сразу же при запуске.
  • ! processing file file1.txt — в начале обработки каждого файла.
  • ! file file1.txt processed: 20123 tokens, 1512 terms — по факту индексации каждого файла. Нужно вывести небольшую статистику: количество слов, на которые был разбит текст (tokens) и количество уникальных слов, содержащихся в тексте (terms).
  • ! idx_builder finished: total 112567 tokens, 20345 terms — перед завершением программы, с итоговой статистикой.
  • Никаких других строк, начинающихся с восклицательного знака, в выводе не допускается.
  • Строки без восклицательного знака в начале могут использоваться по своему усмотрению.

Утилита поиска запускается так:

$ ./idx_searcher [flags] idx-path

Обязательным параметром является путь к каталогу, в котором располагаются индексные файлы (созданные ранее idx_builder’ом). Среди флагов должны присутствовать флаги управления размером контекста:

  • -w N — N слов справа и слева.
  • -s N — N предложений справа и слева.
  • -p N — N абзацев справа и слева.

Каждая строка стандартного ввода является запросом вида

word1 word2 word3 ... wordN

Для каждого запроса программа должна вывести строку

! query 1 execution: word1 word2 word3 ... wordN

То есть, указать номер запроса и повторить его. Затем, для каждого вхождения, должен быть распечатана позиция первого слова в этом вхождении и конеткст употребления:

! File file1.txt, line 20, position 45:
context context word1 word2 word3 ... wordN context context

Контекст должен быть:

  • При ограничении в словах — на одной строке.
  • При ограничении в предложениях — по одному предложению на каждой строчке.
  • При ограничении в абзацах — каждый абзац разделяется пустой строкой.

Утилита diff (diff)

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

Решение этой задачи тесно связано с вычислением расстояния Левенштейна или нахождением наибольшей общей подпоследовательности двух строк (LCS).

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

Работа программы, процедура её запуска, формат ввода и вывода должны быть аналогична работе исходной утилиты diff.

Должны поддерживаться как мининмум следующие опции: -i, -E, -b, -w, -B, -c, -C, -u, -U, normal, -t.

Архиватор (arch)

Необходимо реализовать один из известных методов сжатия данных для сжатия одного файла.

Формат запуска должен быть аналогичен формату запуска программы gzip, должны быть поддержаны следующие ключи: -c, -d, -l, -t, -r, -1, -9. Должно поддерживаться указание символа дефиса в качестве стандартного ввода.

При выполнении этого задания важно получить адекватную производительность для выбранного уровня сжатия.

Собственное задание (self)

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