Разработка и тестирование компьютерной программы для сравнительного анализа алгоритмов бинарного и последовательного поиска

Разработка и тестирование компьютерной программы для сравнительного анализа алгоритмов бинарного и последовательного поиска

Содержание

Введение

1. Методы автоматического поиска данных

1.1 Этапы веб парсинга

1.2 Методы парсинга контента

1.3 Метод копирования / вставки

1.4 Регулярные выражения и совпадение в тексте

1.5 HTTP-запросы

1.6 Методы с использованием искусственного интеллекта

2. Сравнение алгоритмов бинарного и последовательного поиска

2.1 Особенности алгоритма последовательного поиска

2.2 Особенности алгоритма бинарного (двоичного) поиска

3. Реализация алгоритмов поиска

1. Методы автоматического поиска данных

Данные в сети Интернет часто имеют смешанный характер и для определения их структуры и анализа приходится применять различные алгоритмы поиска данных и синтаксического анализа (парсинга).

1.1 Этапы веб парсинга

Процесс парсинга веб-страницы делится на несколько этапов, которые следуют по определенному алгоритму:

1. Получение и анализ исходного кода веб-страницы. Исходный код в виде html-файла захватывается программой для дальнейшей обработки. Ключевыми метками в нем служат текстовая информация и html-теги, по которым осуществляется анализ информации в дальнейшем.
2. Извлечение данных из исходного кода страницы. Разбор html-страниц начинается с построения иерархического дерева из html-тегов и текста веб-страницы. Для этого применяются различные библиотеки и фреймворки для парсинга, а также регулярные выражения. В языке Python для веб-скроулинга предусмотрен фреймворк Scrapy и HTML-парсер Beautiful Soap.
3. Обработка результата. Обработанные данные заносятся в базу данных для дальнейшего анализа.

Процесс обхода страниц сайта также может следовать по определенному алгоритму:

• Иерархический обход сайта. При обходе парсером гиперссылки каждой страницы заносятся в базу данных. Затем парсер последовательно обходит страницы страницы сайта в иерархической последовательности.
• Обход сайта исходя из закономерностей формирования веб-страниц. Парсер последовательно обходит страницы url-адрес которых сформирован по определенными правилам.

1.2 Методы парсинга контента

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

Как правило, есть два способа получения доступа к интересующему вас контенту:

1. Использование API. В этом случае владельцы предоставляют доступ к сайту пользователям, поскольку они заинтересованы в подписках, новостях и т. д.
2. Доступ к сайту без использования API. В этом случае используется парсинг контента.

Метод использования API удобен для пользователя, так как вся полученная информация будет хорошо структурирована. Например, она может быть в формате XML или JSON.

Второй метод заключается в использовании парсинг системы. Это трудоемкий метод для разработчиков. Полученные данные с сайта автоматически обрабатываются с использованием как искусственного интеллекта, так и семантического анализа. Такие программы включают в себя сложные алгоритмы поиска и анализа. [5]

1.3 Метод копирования / вставки

Этот метод, вероятно, является одним из самых простых. Вы вручную находите необходимую информацию и копируете ее (для локализации вашего документа, публикации в вашем ресурсе или в базе данных и т. Д.). Такой метод применяется при поиске информации вручную и не включает в себя автоматизацию. Плюсы:

• Качественный поиск
• Высокоскоростной поиск, за счет отсеивания ненужной информации.

Минусы:

• Необходимость наличия определенных знаний и навыков для поиска в Интернете, а также понимания целевой области.
• Люди уязвимы для психологического и физического воздействия. Это может негативно повлиять на стабильность и качественность работы.
• Такой метод ручного поиска позволяет обеспечить ограниченное количество результатов (до нескольких сотен в день).

1.4 Регулярные выражения и совпадение в тексте

Это простой, но в то же время высокоэффективный метод извлечения информации из Интернета. Он становится еще более эффективным в сочетании с инструментами командной строки UNIX-системы (например, «curl»). Регулярные выражения присутствуют во многих языках программирования. В нашем случае регулярные выражения реализованы на языке Python.