Размещено на http://www.allbest.ru/

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное

учреждение высшего профессионального образования

"Национальный исследовательский университет

"Высшая школа экономики"

Разработка средств автоматизации поиска структурированной информации в гетерогенной среде

Работу выполнил студент

группы БИ-10-1, 4 курса

П. С. Крысанов

Научный руководитель:

к.ф.-м.н., доцент

Л.Н. Лядова

Пермь 2014



Введение

Объём информации в Интернет растёт c каждым днем, а соответственно и растут потребности пользователей в поиске информации, которая может быть представлена в разных форматах.

На данный момент в основных поисковых системах существует поиск только через строковый запрос, то есть пользователь вводит сроку для поиска, к примеру, на главную страницу поискового робота Яндекс и он выдаёт ему соответствующий этому запросу результат. С точки зрения пользователя, он вводит в поисковую машину только строковый запрос, но Яндекс на основе данной поисковой строки формирует целый запрос с такими параметрами как дата, язык, локализация и многое другое. С некоторыми параметрами есть возможность работать, так как они передаются через GET запрос. Один из таких параметров это строка запроса, а это в свое очередь означает, что программа в автоматическом режиме может подавать в Яндекс GET запросы различными поисковыми запросами. Более подробно механизм работы с поисковыми системами из приложения описан ниже. excel word парсинг интернет

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

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

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

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

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

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

Объектом исследования в данной работе будет информационный поиск, а предметом исследования методы и средства поиска структурированной информации.

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

Для достижения поставленной цели должны быть решены следующие задачи:

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

· Разработать алгоритм для программного поиска документов (Word, Excel, Html) на локальном компьютере.

· Рассмотреть возможности языка C# при обработке документов выбранных для поиска (Word, Excel, Html).

· Разработать алгоритм для определения схожести таблиц по структуре.

· Рассмотреть возможности языка C# в для решения задачи разбора html документов.

· Разработать алгоритм для поиска и выгрузки табличных данных в интернете в документах (Word, Excel, Html).

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

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

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



Глава 1. Аналитический обзор методов и средств для разработки необходимых алгоритмов и приложения в целом

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

Для решения поставленных задач необходимо найти средства для парсинга интернет страниц. Парсинг используется при автоматическом извлечении данных с интернет-страниц [1]. Решение задачи парсинга в данной работе необходимо для извлечения таблиц с данными с различных сайтов и извлечение ссылок со страницы с результатами поиска Яндекса. Также очень важно найти готовые решения в области нахождения основы от его исходного вида. Это решение необходимо для разработки алгоритма сравнения двух на соответствие друг другу, который описан в следующей главе.

1.1 Основные определения

Для того, чтобы можно было свободно ориентироваться по данной работе, необходимо дать определения нескольким понятиям. Под парсингом, с помощью которого будут извлекаться данные, понимается автоматизированный сбор контента или данных с какого-либо сайта или сервиса [2]. Также понадобится дать определение слову “релевантный”, так как оно будет использоваться много раз. Релевантность определяется как соответствие полученной информации информационному запросу [3]. В контекстах, предложенных в данной работе, оно будет может быть синонимом к слову “соответствующий”. Также в работе необходимо дать определение слову лемматизация, так как оно будет использовано в ключевом алгоритме этой работы. Под лемматизацией понимается процесс привода словоформы к её лемме - нормальной (словарной) форме[4]. Выражение “поисковый запрос” также имеет большое значение в данной работе. Данное словосочетание означает некоторую исходную информацию для осуществления поиска с помощью поисковой системы [4]. То есть, может быть не только строковый запрос, в него могут входить и другие параметры, как, например, процент допустимой релевантности и многие другие

1.2 DLL библиотека для парсинга интернет-страниц

Парсинг интернет страниц на сегодняшний день очень широко распространенная задача. Примером может являться ситуация, когда пользователю необходимо собирать данные о ценах в нескольких интернет магазинах и сравнивать их друг с другом или вести какую-нибудь другую аналитику. Если собирать необходимые данные вручную, то это займет уйму времени , а с помощью программных решений это займет несколько минут. Для решения этой задача для пользователей .NET разработана DLL библиотека, которая позволяет извлекать необходимые данные с интернет страниц [5].

К примеру, с помощью строки на языке C# “HtmlNodeCollection c = doc.DocumentNode.SelectNodes ("//a[@class=data']");” можно получить коллекцию всех ссылок у который атрибут class=”data.” Это очень быстрый способ работы с HTML документами, так как позволяют получить необходимые данные с помощью ввода 1-2 строк кода [6].



1.3 Проблема сравнения двух основ слов на равенство

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

Решением данной проблемы будет алгоритм приведения этих 2 слов к их основам и уже после приведения сравнивать их на равенство. Название у данного алгоритма приведения к основе - “Стемминг” [7].

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

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

Первый опубликованный стеммер был написан Джули Бет Ловинс в 1968 году.

Позже стеммер был написан Мартином Портером и опубликован в 1980 году. Этот стеммер очень широко использовался и стал де-факто стандартным алгоритмом для текстов на английском языке. Доктор Портер получил премию Стрикса в 2000 году за работы по стеммингу и поиску информации.

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

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

Стеммер был найден в интернете в виде консольного приложения и далее, используя Visual Studio, была создана DLL библиотека на основе этого приложения. Стеммер разработан компанией Ивеоник Системс. Результаты работы стеммера на нескольких языках. Слева входная строка, справа то, что получилось в результате работы стеммера.

И вот что получаем:

Stemmer: Iveonik.Stemmers.RussianStemmer

краcОта --> краcот

красоту --> красот

красоте --> красот

КрАсОтОй --> красот

Stemmer: Iveonik.Stemmers.EnglishStemmer

jump --> jump

jumping --> jump

jumps --> jump

jumped --> jump

Stemmer: Iveonik.Stemmers.GermanStemmer

mochte --> mocht

mochtest --> mocht

mochten --> mocht

mochtet --> mochtet [8]

В данной работе была протестирована вышеописанная библиотека на примере 250 русских слов. В результате получилось 227 удовлетворительных вариантов, 23 неудовлетворительных. Процент удовлетворительности 90%, что вполне приемлемо для данной работы.

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

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



Глава 2. Алгоритмы для поиска структурированных данных

В данной главе будут рассматриваться алгоритмы, которые необходимо разработать для решения задач, поставленных в данной работе. Во-первых, как уже было сказано в предыдущей главе, это алгоритм сопоставления двух таблиц на соответствие друг другу. Это один из ключевых алгоритмов данной работы. Он будет использоваться для сравнения найденных таблиц с эталонной таблицей. Об эталонной таблице речь пойдет ниже. На вход данному алгоритму подается две таблицы, а на выходе получается ответ на вопрос: “Имеют ли данные таблицы схожий смысл?” в виде “Да/Нет”. По аналогичной схеме будет строится алгоритм сравнения двух заголовков на соответствие. На вход данному алгоритму будет подаваться две строки(два заголовка), а на выходе будет получен ответ “Да или Нет”. Параметрами при сравнении двух таблиц на соответствие друг другу будет процент схожести заголовков этих таблиц, при котором алгоритм даст положительный ответ на вопрос о соответствии таблиц и процент схожести двух заголовков друг другу, при котором при сравнении двух заголовков на релевантность будет положительный ответ. Более подробно об этом при описании алгоритма. Далее обязательно необходимы алгоритмы извлечения таблиц из документов Word, Excel и Html, для того, чтобы сопоставлять данные из них с эталонной таблицей.

Эталонная таблица - это таблица созданная пользователем, с которой будет происходить сравнение найденных таблиц на соответствие. Эталонная таблица в данной работе будет означать поисковый запрос пользователя.

2.1 Создание модели таблицы в программе

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

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

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

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

Алгоритм создания модели таблицы на основе заголовков представлен ниже.

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

2.2 Алгоритм сравнения двух заголовков на соответствие друг другу

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

bool CompareHeaders(List<string> lstMin, List<string> lstMax)

{

int countrelevant=0;

foreach (string str1 in lstMin)

{

foreach (string str2 in lstMax)

{

if (CompareWords(str1, str2))

{

countrelevant++;

break;

}

}

}

if (lstMin.Count > 0)

if ((countrelevant / lstMin.Count)*100 >= percentage_of_relevancyHeaders) return true;

return false;

}

bool CompareWords(string str1, string str2)

{

str1 = Stem(str1);

str2 = Stem(str2);

if (str1 == str2) return true;

else return false;

}

В псевдокоде, описанном выше, присутствуют две функции: CompareHeaders и CompareWords. В функции CompareРeaders происходит непосредственно сравнение двух заголовков на соответствие друг другу. Для реализации этой функции необходимо было выделить функцию сравнения двух слов на релевантность. В функции CompareWords используется стемминг, который вызывается посредством функции Stem.

На вход алгоритму поступают два набора слов ( один из первого заголовка, второй из второго). Для каждого слова из заголовка, в котором количество слов меньше, проводится сравнение с каждым словом, где количество слов больше. Под сравнение слов понимается сравнение основ слов, который реализуется посредством стемминга. Если слово из набора слов, в котором меньше слов, находит равное себе во втором наборе слов, то переменная-счетчик countrelevant увеличивается на единицу и происходит переход к следующему слову из заголовка, в котором меньше слов. В итоге, если countrelevant разделить на количество слов в наборе, в котором меньше слов, и это значение будет больше или равно параметру - необходимое количество процентов схожести двух заголовков для признания этих заголовков релевантными, то это означает, что заголовки имеют схожий смысл.

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

Рассмотрим пример сравнения двух заголовков. Есть два заголовка : “Результаты экзамена” и “Итоговый экзамен по программированию”. Эти два заголовка будут разделены на следующие наборы слов : (Результаты, экзамена) и (Итоговый, экзамен, программированию). Предлоги и союзы не входят в набор слов так как не несут на себе смысловой нагрузки.

Красная линия означает, что данные слова не соответствуют друг другу, а зеленая если соответствуют. В итоге получается, что из двух слов первого набора, только одно нашло себе соответствующее слово во втором наборе. Теперь необходимо найти процент соответствия заголовков. Для этого нужно разделить количество слов, из набора, в котором меньше слов, которые нашли себе соответствие в другом наборе на количество слов в этом наборе. То есть, в данном случае это будет Ѕ =50%. Если в параметрах соответствия заголовков, стоит значение 50 или менее, то приложение вернет ответ true на вопрос: ” Соответствуют ли эти заголовки друг другу?”



2.3 Алгоритм сравнения двух уровней заголовков на соответствие друг другу

Данный алгоритм будет использоваться в алгоритме сопоставления двух таблиц. На вход алгоритму подается два набора заголовков, которые взяты из уровней заголовков - по одному из каждой таблицы. Они будут передаваться виде двухуровневого списка, у которого одно измерение это заголовки, второе измерение это слова, которые входят в заголовки. Первым подается тот список, в котором меньше заголовков. Описание алгоритма приведено ниже.

bool compareLevel(List<List<string>> minTbl, List<List<string>> maxTbl)

{

int countRelevant = 0;

foreach (List<string> lstMin in minTbl)

{

foreach (List<string> lstMax in maxTbl) //Можно добавить глубину поиска

{

if (lstMin.Count <= lstMax.Count)

{

if (CompareHeaders(lstMin, lstMax))

{

countRelevant++;

break;

}

}

else

{

if (CompareHeaders(lstMax,lstMin))

{

countRelevant++;

break;

}

}

}

}

decimal dblCountRelevant = decimal.Parse(countRelevant.ToString());

if (minTbl.Count > 0)

{

decimal value = dblCountRelevant / minTbl.Count;

if (value * 100 >= percentage_of_relevancyTables) return true;

}

return false;

}

В псевдокоде, описанном выше, присутствуют две функции: compareLevel и CompareHeaders. В функции compareLevel происходит непосредственно сравнение двух наборов заголовков на соответствие друг другу. Для реализации этой функции использоваласб функция CompareHeaders, алгоритм работы которой описан в предыдущем пункте.

На вход алгоритму поступают два набора заголовков (один из первого уровня заголовков, второй из второго). Для каждого заголовка из набора, в котором количество заголовков меньше, проводится сравнение с каждым заголовком, где количество заголовков больше. Под сравнением заголовков понимается сравнение применение алгоритма описанного в предыдущем пункте. Если заголовок из набора, в котором меньше заголовков, находит релевантный себе заголовок во втором наборе, то переменная-счетчик countrelevant увеличивается на единицу и происходит переход к следующему заголовку из первого набора. В итоге, если countrelevant разделить на количество заголовков в наборе, в котором меньше заголовков, и это значение будет больше или равно параметру - необходимое количество процентов схожести двух наборов заголовков для признания этих наборов релевантными, то это означает, что наборы заголовков имеют схожий смысл.

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

Рассмотрим пример сравнения двух наборов заголовков. Есть два набора заголовков: (Студент, Результат) и (ФИО, рейтинг до экзамена, экзамен, результат).

Красная линия означает, что данные заголовки не соответствуют друг другу, а зеленая если соответствуют. В итоге получается, что из двух заголовков первого набора, только один нашел себе соответствующий заголовок во втором наборе. Теперь необходимо найти процент соответствия наборов. Для этого нужно разделить количество заголовков, из набора, в котором меньше заголовков, которые нашли себе соответствие в другом наборе на количество заголовков в этом наборе. То есть, в данном случае это будет Ѕ =50%. Если в параметрах соответствия наборов заголовков, стоит значение 50 или менее, то приложение вернет ответ true на вопрос: ” Соответствуют ли эти наборы заголовки друг другу?”

2.4 Алгоритм сравнения двух таблиц на соответствие друг другу

Как уже было написано во введении, одной главных задач данной работы является разработка алгоритма сравнения двух таблиц на их соответствие. На вход в алгоритм поступают две модели таблиц, которые имеют вид, подобный виду описанном на рис. 2.3. Данная модель будет реализована виде списка списков(List< List<string>>). На выходе будет ответ в виде “True/False”, где True означает, что таблицы соответствуют друг другу, а False означает, что не соответствуют. Псевдокод алгоритма описан ниже.

bool CompareTables(List<List<List<string>>> tbl1,

List<List<List<string>>> tbl2)

{

if (tbl1.Count == 0 || tbl2.Count == 0) return false;

foreach (List<List<string>> lst1 in tbl1)

{

foreach (List<List<string>> lst2 in tbl2)

{

if (lst1.Count == 0 || lst2.Count == 0)

{

continue;

}

if (lst1.Count < lst2.Count)

{

if (compareLevels(lst1, lst2))

{

return true;

}

}

else

{

if (compareLevels(lst2, lst1))

{

return true;

}

}

}

}

return false;

}

В данном алгоритме происходит сравнение каждого уровня заголовков с каждым уровнем заголовков из другой таблицы. Каждый уровень заголовков состоит из набора заголовков. Для того, чтобы результат сравнения двух таблиц был равен true достаточно, чтобы хотя бы одно сравнение уровней дало положительный ответ. В данном алгоритме применяется функция CompareLevels, алгоритм которой описан в предыдущей пункте.

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

Сравнение произведено в соответствии с алгоритмом описанным в предыдущим пункте. Зеленая стрелка означает, что данные уровни релевантные, красная - не релевантные. Так как для данного алгоритма достаточно всего одного совпадения, чтобы вернуть true, то результатом сравнения данных таблиц будет true. Если n - количество уровней в первой табле, а m - во второй, то сложность алгоритма будет стремится к выражению n*m.



2.5 Выделение табличной информации из файлов различных типов

В данной работе приложению необходимо извлекать таблицы из документов Word, Excel и HTML для дальнейшей обработки, поэтому встает задача создания алгоритмов для выделения табличных данных из соответствующих документов. Ниже описаны алгоритмы для работы с каждым из приведенных выше типов документов.

Выделение информации из таблиц в документах Excel

Для выделение табличных данных из документов Excel вначале необходимо выделить на листе часть с данными и далее выделить из нее заголовки.

Во-первых, необходимо проверить лист на пустоту. Для этого, используется стандартную функцию UsedRange объекта WorkSheet(Рабоичй лист) [9]. В случае, если UsedRange.Rows.Count и UsedRange.Columns.Count одновременно равны единице, то можно сделать вывод, что данный пустой. Ну, а далее, когда мы прошли проверку листа на пустоту, то необходимо выделить диапазон с данными.

Для решения данной задачи можно было бы использовать ту же самую функцию(UsedRange), которая выделяет диапазон используемых ячеек, но у нее есть один большой недостаток. Недостаток заключается в том, что используемой ячейкой считается не только заполненная ячейка, но и ячейка в которой когда-либо находились данные. К примеру, я ввел данные в ячейку А1, а далее удалил их из этой ячейки. Таким образом, данная функция вернет ячейку А1, несмотря на то, что на данный момент она пустая, так как ранее она использовалась. Таким образом, необходимо разработать собственный алгоритм для выделения данных с листа Excel.

Этапы выделения данных с листа Excel:

1. Найти одну непустую ячейку на листе.

2. От этой ячейки двигаться вверх, вниз, вправо, влево до тех пор, пока не встретится пустая ячейка(выделить диапазон ячеек).

3. Считать заголовки таблицы.

Ниже будет рассмотрен этап для выделения непустой ячейки. Во-первых, для выделения диапазона непустых ячеек необходимо вначале выделить одну непустую ячейку. Для этого будет использована стандартная функция в языке C# “UsedRange ”.

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

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

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

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

Ниже будет рассмотрен пример работы алгоритма.

Далее приложение начинает искать в нем первую непустую ячейку. С помощью функции “UsedCells” можно получить доступ к верхней левой заполненной ячейке или получить пустую ячейку, если лист пуст.

Далее из ячейки C4 программа начнет двигаться вверх, вниз, влево, вправо до тех пор пока не встретит пустую ячейку или не дойдет до конца листа.

Так как у нас количество заголовков в первой строке больше или равно ширине диапазона минус 4(14>14-4), то перехода к считыванию следующей строки не будет. Таким образом, модель таблицы будет состоять только из одного уровня заголовков, в который будут входить следующие заголовки:

· Хозяева.

· Гости.

· Тур.

· Месяц.

· Место.

· Id команды.

· Класс тренера.

· 1.

· Бюджет.

· Голов забито.

· Голов пропущено.

· Голов забито игру назад.

· Голов пропущено игру назад.

Выделение информации из таблиц в документах WORD

С WORD все обстоит проще. DLL для работы с документами WORD дает широкие возможности для различных действий на основе этих документов.

В данной библиотеке все таблицы документа хранятся в свойстве WordDocument.Tables и поэтому доступ к этой таблице сводится к тому, что необходимо просто указать индекс интересующей таблицы [10]. К примеру, строка WordDocument.Tables[1] в результате вернет ссылку на первую таблицу в документе.

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

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

Таким образом, результатом обработки таблицы 1 будет список заголовков таблицы:

· Хозяева.

· Гости.

· Работа.

· Id.

· Место в составе.

Выделение информации из таблиц в документах HTML

На входе в приложение мы получаем HTML файл или ссылку на документ формате HTML. Для его парсинга, а именно извлечения данных из тэгов будет использована dll библиотека “HtmlAgilityPack”, которая работает с языком Xpath.

Ниже приведены этапы работы данного алгоритма:

1. Выделить все таблицы из документа

2. Для каждой таблицы, проверить наличие внутренних таблиц в этих таблицах. Те, таблицы, которые имеют внутренние таблицы отбросить.

3. Из оставшихся от предыдущего этапа оставить только те таблицы, у которых количество ячеек больше 5 и, у которых хотя бы 50% содержат числовые данные.

Чтобы найти таблицы нужно странице обратиться с помощью языка Xpath. Запрос будет выглядеть следующим образом:

HtmlNodeCollection tables = d.DocumentNode.SelectNodes("//table");

Данный код означает, что из документа берутся все DOM-узлы с тэгом “table”, то есть таблицей. Итого у нас есть коллекция кодов всех таблиц, которые имеются на данной странице.

Таблицы на страницах могут быть 2 видов: информационные и те, которые используются для разметки страницы. Таким образом, необходимо оставить только те таблицы, которые несут информационную нагрузку.

Для этого в цикле обращаемся к каждой таблице из коллекции и начинаем определять ее тип.

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

Для реализации проверки таблицы - является она внутренней или нет - мы будем искать в коде таблицы фрагмент “<table”, открывающий тэг таблицы, который говорит о том, что внутри таблицы имеется еще одна таблица. Если мы обнаруживаем данный фрагмент, то это значит, что таблица не внутренняя, и мы ее отбрасываем.

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

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

Если эта проверка пройдена, то проверим таблицу на количество ячеек. В данной работе было определено, что если в таблице менее 6 ячеек, то мы их отсекаем.

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



Глава 3. Разработка приложения

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

3.1 Разработка приложения для поиска на локальном компьютере

3.1.1 Логика поиска на локальной машине

Для поиска на локальной машине необходимо получить список документов Excel и Word из папки, в которой будет произведен поиск, а также из всех внутренних папок. Далее все таблицы, которые будут извлечены из найденных файлов, будут проходить сравнение с эталонной таблицей.

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

3.1.2 Интерфейс

Форма для создания настроек для поиска на локальном компьютере выглядит следующим образом.

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

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

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

При нажатии на кнопку “Выбор поисковой таблицы” откроется диалоговое окно выбора с фильтрацией документов по типам (xls, xlsx, doc, docx), где пользователь сможет выбрать тот файл, из которого будет извлекаться таблица.

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

3.2 Разработка приложения для поиска в интернете

3.2.1 Логика поиска в интернете

Задача поиска табличных данных в интернете является более сложной нежели на локальной машине.

Для начала приложение извлекает список заголовков из таблицы, которая выбрана в качестве поисковой. Во-первых, необходимо из программы с помощью языка C# обращаться к поисковому работу Яндекс. На первом этапе - этапе работы с поисковыми системами необходимо на основе введенных ключевых слов сформировать массив ссылок на результаты, которые выдает Яндекс. По умолчанию, он выдает 10 ссылок на самые релевантные ресурсы. В данной работе мы будем исследовать только их. Вторая и следующие страницы поисковой выдаче затрагиваться не будут.

Для того чтобы сделать это, воспользуемся языком C# и с помощью стандартных средств платформы .NET возьмем код страницы и присвоим его некой строковой переменной. Реализация данной функции представлена в приложении. В Яндексе запрос обрабатывается следующим образом, например при вводе в форму строки: ”Поиск информации в интернете”, поисковый робот обрабатывает ее и создает следующий URL.

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

Таким образом, чтобы нам задать запрос к Яндексу с помощью приложения, разработанного на языке C# нам нужно взять код страницы:

http://yandex.ru/?text=Поиск+информации+в+интернете

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

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

При анализе кода страниц, которые выдает поисковая система, была замечена закономерность что ссылки на страницы в поисковой выдаче идут в тэгах “a” с классом:” b-serp-item__title-link" .

Таким образом, используя библиотеку “HtmlAgilityPack” и язык XPath, мы обработаем код полученный от Яндекса с помощью следующего Xpath запроса, который вернет тэги со ссылками на ответы Яндекса:



“HtmlNodeCollection c = doc.DocumentNode.SelectNodes("//a[@class='b-serp-item__title-link']");”.

В данной строке ключевым является запрос: "//a[@class='b-serp-item__title-link']". Он означает, что нужно из всего загруженного документа, взять все тэги “a”(ссылки), у которых класс равен “'b-serp-item__title-link”. Таким образом, Яндекс возвращает коллекцию узлов со ссылками.

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

В начале на каждой странице обрабатывается HTML информация. Происходит извлечение информационных таблиц на основе алгоритма описанного в пункте 2.3.3 “Выделение табличной информации из таблиц в документах HTML”. Эти таблицы сравниваются с исходной и в случае, если они соответствуют критериям релевантности, то данные таблицы выгружаются на компьютер и сохраняются в результатах поиска в формате xls.

После анализа HTML кода на наличие информационных таблиц, приложение проводит поиск по файлам в формате doc и xls на которые ссылается данная страница. Для этого с помощью языка Xpath извлекаются все ссылки (тэги <a>) и проверяются все атрибуты “href” и далее, если они ссылаются на файлы в форматах (doc, docx, xls, xlsx), то программа скачивает их в папку с результатами. И далее проводит анализ данных файлов на соответствие с исходной таблицей аналогично поиску на локальной машине. Если в файле присутствуют релевантные таблицы, то приложение оставляет его, и в список результатов добавляет ссылку на сохраненный файл на локальной машине, при этом указывая индекс таблицы и тип данных.

При разработке данного алгоритма появилась небольшая проблема, связанная с тем, что для скачивания файла из интернета необходим полный путь к файлу(http://домен/....), а ссылки в интернете не всегда хранятся в абсолютном виде. Ссылка на ресурс может храниться в 3 вариантах:

· Абсолютном (пример : http://perm.hse.ru/).

· Относительный (пример images/1.gif).

· Полуотносительный (пример /images/1.gif).

Таким образом, необходимо относительные пути приводить к абсолютным. Для этого была реализована соответствующая функция, текст которой приведён в находится в приложении к работе.

3.2.2 Интерфейс

Форма для создания настроек для поиска таблиц в интернете выглядит следующим образом.

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

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

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

Далее слева находятся настройки глубины поиска данных в Яндексе и на сайтах, которые вернул Яндекс. Глубина поиска в Яндексе это количество станиц, которые будет обрабатывать система в результатах поиска (по умолчанию один, это значит, что только первая страница поисковой выдачи).

Глубина поиска на сайте, это максимальный уровень, на который приложение будет обрабатывать сайт(по умолчанию один, это значит, что поиск будет вестись только на той странице, на которую была получена ссылка из Яндекса. Остальные страницы обрабатываться не будут). Ниже располагаются настройки для сравнения 2 таблиц на соответствие. В первой из них находится процент соответствия заголовков, при котором мы считаем 2 заголовка имеющими одинаковый смысл. Во втором поле процент соответствия таблиц, при котором мы считаем их равными.

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

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



Заключение

В ходе преддипломной практики было разработано приложение для поиска на локальной машине и в интернете. Также разработаны алгоритмы извлечения необходимой табличной информации из документов WORD, EXCEL, HTML. Разработан алгоритм для сравнения 2 таблиц на соответствие друг другу. Таким образом, получилось готовое приложение, которое ведет поиск структурированной информации в сети интернет и на локальной машине.

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



Библиографический список

1. Парсинг (Parsing) // Словарь WestSEO [Электронный ресурс] [Режим доступа: http://westseo.ru/article/parsing] [Проверено: 15.04.2014].

2. Релевантный // Словари и энциклопедии на Академике [Электронный ресурс] [Режим доступа: http://dic.academic.ru/dic.nsf/maruso/релевантный] [Проверено: 16.04.2014].

3. Лемматизация - что это? // SEO блог: поисковые системы | создание, оптимизация и продвижение сайтов [Электронный ресурс] [Режим доступа: http://searchenginez.ru/lemmatizaciya-chto-eto/] [Проверено: 17.04.2014].

4. Поисковые запросы. Виды поисковых запросов. // Как создать свой сайт самому [Электронный ресурс] [Режим доступа: http://sites-builder.ru/view_post.php?id=191] [Проверено: 16.04.2014].

5. html agility pack | Дмитpий Hecтepук // Дмитpий Hecтepук [Электронный ресурс] [Режим доступа: http://nesteruk.wordpress.com/tag/html-agility-pack/] [Проверено: 16.04.2014].

6. Язык запросов XPath // Школа программирования Coding Craft [Электронный ресурс] [Режим доступа: http://codingcraft.ru/xpath.php] [Проверено: 16.04.2014].

7. Стемминг // Система автоматизированного продвижения сайтов [Электронный ресурс] [Режим доступа: http://wiki.rookee.ru/Stemming/] [Проверено: 17.04.2014].

8. Iveonik Systems|ALL #INCLUDE // Стеммеры Snowball на C# - free download [Электронный ресурс] [Режим доступа: www.iveonik.com/blog/2011/08/stemmery-snowball-na-csharp-free-download/] [Проверено: 17.04.2014].

9. WorksheetBase.UsedRange - свойство (Microsoft.Office.Tools.Excel)// Microsoft Developer network [Электронный ресурс] [Режим доступа: http://msdn.microsoft.com/ru-ru/library/microsoft.office.tools.excel.worksheetbase.usedrange.aspx] [Проверено: 17.04.2014].

10. Практическое руководство. Программное таблиц в Word// Microsoft Developer network [Электронный ресурс] [Режим доступа: http://msdn.microsoft.com/ru-ru/library/w1702h4a.aspx] [Проверено: 17.04.2014].

Размещено на Allbest.ru