МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
ВОСТОЧНО-СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Курсовой проект
по дисциплине «Системное программирование»
Тема: Разработка приложения «Парсер текста»
Выполнил: Андреев Д.А.
Руководитель кафедры СИ Веселов А.В.
Улан-Удэ
2019
Задание на курсовой проект
Дисциплина: Системное программирование
Тема: Разработка приложения «Парсер текста»
Краткое содержание проекта: Необходимо разработать программу "Парсер текста" выполняющую основные текстовые операции в среде программирования Python.
1.Теоретическая часть: словесная постановка задачи, анализ предметной области задачи, основные понятия, краткое описание существующих методов и алгоритмов, описание выбранного метода
2. Практическая часть:
Сроки выполнения проекта по графику:
1. Теоретический раздел - 25% к 3 неделе.
2. Основной раздел. Проектирование. - 50% к 4 неделе.
3. Основной раздел. Кодирование. - 80% к 6 неделе.
4. Экспериментальный раздел. - 95% к 7 неделе.
5. Защита. - 100% к 8 неделе.
Требования к оформлению:
1. Расчетно-пояснительная записка курсового проекта должна быть представлена в электронной и твердой копиях.
2. Объем РПЗ должен быть не менее 20 машинописных страниц без учета приложений.
Аннотация
Данный курсовой проект посвящен разработке приложения «Парсер текста».
Целью данного курсового проекта является создание программы "Парсер текста", которая и будет являться объектом исследования. Приобретение и закрепление навыков в организации вычислительных процессов и программирования на алгоритмическом языке.
Содержание
Введение
В общем смысле, парсинг - это линейное сопоставление последовательности слов с правилами языка. Парсинг сайтов - последовательный синтаксический анализ информации, размещённой на интернет-страницах. Текст интернет-страниц представляет собой иерархичный набор данных, структурированный с помощью человеческих и компьютерных языков. На человеческом языке предоставлена информация, знания, ради которых, собственно, люди и пользуются Интернетом. Компьютерные языки (html, JavaScript, css) определяют, как информация выглядит на мониторе.
Парсинг сайтов является эффективным решением для автоматизации сбора и изменения информации.
По сравнению с человеком, компьютерная программа-парсер:
- быстро обойдёт тысячи веб-страниц;
- аккуратно отделит техническую информацию от «человеческой»;
- безошибочно отберёт нужное и отбросит лишнее;
- эффективно упакует конечные данные в необходимом виде.
Цель: приобретение и закрепление навыков в организации вычислительных процессов и программирования на алгоритмическом языке.
Для достижения поставленной цели необходимо выполнить следующие задачи:
- программа должна работать в графическом режиме;
- в программе должны использоваться кнопки для ввода данных (операций) и графическое меню;
- программа должна содержать поле для ввода данных и вывода результата.
- программа должна выводить результат парсинга.
1. Аналитический раздел
1.1 Словесная постановка задачи
В этой задаче нам нужно создать парсер текста.
1.2 Анализ предметной области
Парсинг (Parsing) - это принятое в информатике определение синтаксического анализа. Для этого создается математическая модель сравнения лексем с формальной грамматикой, описанная одним из языков программирования. Например, PHP, Perl, Ruby, Python.
Когда человек читает, то, с точки зрения науки филологии, он совершает синтаксический анализ, сравнивая увиденные на бумаге слова (лексемы) с теми, что есть в его словарном запасе (формальной грамматикой).
Как работает парсинг, что это такое? Алгоритм работы парсера.
Независимо от того на каком формальном языке программирования написан парсер, алгоритм его действия остается одинаковым:
1) выход в интернет, получение доступа к коду веб-ресурса и его скачивание;
2) чтение, извлечение и обработка данных;
3) представление извлеченных данных в удобоваримом виде - файлы.txt,.sql,.xml,.html и других форматах.
В интернете часто встречаются выражения, из которых следует, будто парсер (поисковый робот, бот) путешествует по Всемирной сети. Но зачастую эта программа никогда не покидает компьютера, на котором она инсталлирована.
Сбор информации в интернете - трудоемкая, рутинная, отнимающая много времени работа. Парсеры, способные в течение суток перебрать большую часть веб-ресурсов в поисках нужной информации, автоматизируют ее. Наиболее активно «парсят» всемирную сеть роботы поисковых систем. Но информация собирается парсерами и в частных интересах. На ее основе, например, можно написать диссертацию. Парсинг используют программы автоматической проверки уникальности текстовой информации, быстро сравнивая содержимое сотен веб-страниц с предложенным текстом. Без программ парсинга владельцам интернет-магазинов, которым требуются сотни однотипных описаний товаров, технических характеристик и другого контента, не являющегося интеллектуальной собственностью, было бы трудно вручную заполнять характеристики товаров.
Возможностью «спарсить» чужой контент для наполнения своего сайта пользуются многие веб-мастера и администраторы сайтов. Это оправдано, если требуется часто изменять контент для представления текущих новостей или другой, быстро меняющейся информации.
Разновидности парсинга
Parsing позволяет осуществлять работу с данными любой тематики. Среди основных сфер применения такой технологии можно выделить:
- поиск и наполнение ресурсов текстовым и мультимедийным контентом;
- товары и цены в интернет-магазинах;
- данные из объявлений, размещенных на специальных ресурсах;
- поиск и сбор контактных данных пользователей;
- в рамках социальных сетей (например, отзывы и комментарии);
- сайты, специализирующиеся на публикации спортивных результатов.
Основа работы парсера.
Конечно же, парсеры не читают текста, они всего лишь сравнивают предложенный набор слов с тем, что обнаружили в интернете и действуют по заданной программе. То, как поисковый робот должен поступить с найденным контентом, написано в командной строке, содержащей набор букв, слов, выражений и знаков программного синтаксиса. Такая командная строка называется «регулярное выражение». Русские программисты используют жаргонные слова «маска» и «шаблон».
Чтобы парсер понимал регулярные выражения, он должен быть написан на языке, поддерживающем их в работе со строками. Такая возможность есть в РНР, Perl. Регулярные выражения описываются синтаксисом Unix, который хотя и считается устаревшим, но широко применяется благодаря свойству обратной совместимости.
Синтаксис Unix позволяет регулировать активность парсинга, делая его «ленивым», «жадным» и даже «сверхжадным». От этого параметра зависит длина строки, которую парсер копирует с веб-ресурса. Сверхжадный парсинг получает весь контент страницы, её HTML-код и внешнюю таблицу CSS.
Парсеры и PHP.
Этот серверный язык удобен для создания парсеров:
- У него есть встроенная библиотека libcurl, с помощью которой скрипт подключается к любым типам серверов, в том числе работающих по протоколам https (зашифрованное соеди-нение), ftp, telnet.
- PHP поддерживает регулярные выражения, с помощью которых парсер обрабатывает данные.
- У него есть библиотека DOM для работы с XML - расширяемым языком разметки текста, на котором обычно представляются результаты работы парсера.
- Он отлично ладит с HTML, поскольку создавался для его автоматической генерации.
Этические и технические сложности парсинга
Вопрос о том, является ли парсинг воровством контента, активно обсуждается во Всемирной сети. Большинство оппонентов считают, что заимствование части контента, не являющегося интеллектуальной собственностью, например, технических описаний, допустимо. Ссылка на первоисточник контента рассматривается как способ частичной легитимации. В то же время, наглое копирование, включая грамматические ошибки, осуждается интернет-сообществом, а поисковыми системами рассматривается как повод для блокировки ресурса.
Парсер можно написать самому или заказать на бирже фриланса, если вам требуются конкретные условия для поиска и чтения информации. Или купить эту программу в готовом виде с усредненным функционалом на специализированном веб-ресурсе.
1.3 Обзор и анализ существующих программных решений
Для этого необходимо изучить следующие существующие решения. Сегодня повсеместное использование парсеров существенно облегчает работу человека в самых различных сферах.
При парсинге исходный текст преобразуется в структуру данных, обычно - в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки.
Для того чтобы определить происхождение парсинга придется обратиться в недалекое прошлое.
1960 - Выпущена спецификация ALGOL 60, в которой впервые описан язык с блочной структурой. Комитету ALGOL хорошо известно, что никто не знает, как парсить такой язык. Но они считают, что, если они детально описали язык с блочной структурой, то для него будет изобретен анализатор/парсер. Рискованный подход, который впоследствии окупился.
1961 - Нед Айронс выпускает свой парсер ALGOL. Фактически, алгоритм Айронса является первым подобным анализатором, который был описан в печати. Парсер Неда является лево-рекурсивным (форма рекурсивного спуска) парсером. В отличие от современного рекурсивного спуска, алгоритм Айронса носит общий характер и является синтаксически-управляемым. «Общий» означает, что они могут разобрать что написано в БНФ (форма Бэкуса - Наура - формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории). «Синтаксически-управляемый» (декларативный) означает, что анализатор фактически создается из БНФ - парсер не нужно создавать самому.
Почти одновременно, появляются самокодируемые (т.е. с возможностью внесения изменений в исходный код) подходы к реализации леворекурсивных алгоритмов. Сейчас их рассматривают как рекурсивный спуск. В течение следующих лет самокодируемые подходы становятся все более популярными для леворекурсивных анализаторов, чем синтаксически-управляемые алгоритмы. Важную роль сыграли следующие три фактора:
- В 1960-х память и CPU очень ограничены. Ручное кодирование (hand-coding) окупается даже тогда, когда выигрыш от его применения мал.
- Чистый леворекурсивный анализ - очень слабый метод синтаксического анализа. Ручному кодированию часто приходится преодолевать эти ограничения. Это утверждение верно, как в 1961, так и в наши дни.
- Леворекурсивный анализ хорошо работает в сочетании с ручным кодированием - они дополняют друг друга.
1965 - Дональд Кнут (Don Knuth) изобретает алгоритм LR. Ученый в первую очередь заинтересован в математической стороне задачи. Кнут описывает алгоритм анализа, но его подход считается непрактичным.
1968 - Джей Эрли (Jay Earley) изобретает алгоритм, названный в его честь. Как и алгоритм Irons, алгоритм Эрли является синтаксически-управляемым и носит общий характер. В отличие от алгоритма Irons, не использует метод поиска с возвратом. Основная идея Эрли состоит в том, чтобы отслеживать этапы работы алгоритма в таблицах. Алгоритм Эрли заманчив, но имеет три основных недостатка:
- Во-первых, есть ошибка в обработке правил нулевой длины.
- Во-вторых, при право-сторонней рекурсии необходимо применять алгоритм дважды.
- В-третьих, чтобы создать таблицы, необходимо вести учёт системных ресурсов, что, по меркам аппаратных средств 1968 года, является довольно сложной задачей.
1969 - Фрэнк ДеРемер (Frank DeRemer) описывает новый вариант LR Кнута. Для алгоритма LALR ДеРемера необходим только стек и таблица состояний, размер которой можно легко изменить.