Дипломная (вкр): Информационно-поисковые и информационно-справочные системы в обучении информатике

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

Вероятность = Частота вхождения слова / Число слов

Зипф установил закономерность: если умножить вероятность обнаружения слова в тексте на ранг частоты, то получившаяся величина (С) приблизительно постоянна. [рис 1]

С = (Частота вхождения слова х Ранг частоты) / Число слов

Если мы незначительно преобразуем формулу, а на следующем этапе, используем данные математического справочника, станет очевидным, что это функция типа y=k/x и ее график -равносторонняя гипербола.

Рис 1. Первый закон Зипфа.

Следовательно, по первому закону Зипфа, если самое распространенное слово встречается в тексте, например, 100 раз, то следующее по частоте слово вряд ли встретится 99 раз. Частота вхождения второго по популярности слова, с высокой долей вероятности, окажется на уровне 50. Значение константы в разных языках различно, но внутри одной языковой группы остается неизменно, какой бы текст мы ни взяли. Так, например, для английских текстов константа Зипфа равна приблизительно 0,1. Для русского языка коэффициент Зипфа получился равным 0,06-0,07. Хотя эти исследования не претендуют на полноту, универсальность законов Зипфа позволяет предположить, что полученные данные вполне достоверны.

2.3.2 Второй закон Зипфа "количество - частота"

Рассматривая первый закон, Зипф установил, что разные слова входят в текст с одинаковой частотой и что частота и количество слов, входящих в текст с этой частотой, тоже связаны между собой. Если построить график, отложив по одной оси (оси Х) частоту вхождения слова, а по другой (оси Y) -количество слов в данной частоте, то получившаяся кривая будет сохранять свои параметры для всех без исключения созданных человеком текстов. Как и в предыдущем случае, это утверждение верно в пределах одного языка.

Рис. 2 Второй закон Зипфа

Однако и межъязыковые различия невелики. На каком бы языке текст ни был написан, форма кривой Зипфа останется неизменной и коэффициенты, отвечающие за наклон кривой отличаются незначительно [рис. 2]. Законы Зипфа универсальны, они применимы не только к текстам, аналогичный эффект наблюдается при рассмотрении зависимости количества городов от числа проживающих в них жителей. Характеристики популярности узлов в сети Интернет - тоже отвечают законам Зипфа. Исследования показывают, что наиболее значимые слова лежат в средней части диаграммы. Слова, которые попадаются слишком часто, в основном оказываются предлогами, местоимениями, в английском - артиклями и т.п. Редко встречающиеся слова тоже, в большинстве случаев, не имеют решающего смыслового значения.

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

В качестве примера возьмем один из предыдущих абзацев (абзац, начинающийся словами "Законы Зипфа универсальны"). Посмотрим, какие слова попали в область значимых слов, а какие нет. В таблице 1 приведены все слова абзаца и указана частота их вхождения. Как видите, слова с частотой 2 и 3 наиболее точно отражают смысл абзаца. Слово с наибольшей частотой вхождения оказалось предлогом, а слова с меньшей - общими словами.

Выделим зону значимых слов. Пусть это будут слова с рангом 2, 3 и частотой 3, 2 соответственно. (Обратите внимание, как смещение или расширение зоны значимых слов влияет на их состав.)

Давайте теперь проанализируем выделенную нами область значимых слов. Не все слова, которые попали в нее, отражают смысл текста. Смысл абзаца очень точно выражают слова: «зипфа», «манускриптов», «войнича», «законам». Запрос типа: + "закон* зипфа" + "манускрипт* войнича" непременно найдет нам этот документ. Однако в область попали и слова: «на», «не», «для», «например», «это». Эти слова являются "шумом", помехой, которая затрудняет правильный выбор. "Шум" можно уменьшить путем предварительного исключения из исследуемого текста некоторых слов. Для этого создается словарь ненужных стоп-слов (словарь называется стоп-лист). Например, для английского текста стоп-словами станут термины: «the», «a», «an», «in», «to», «of», «and», «that»... и так далее. Для русского текста в стоп-лист могли бы быть включены все предлоги, частицы, личные местоимения и т. п. Наверняка попали бы и слова из нашего "шума": «на», «не», «для», «это». Есть и другие способы повысить точность оценки значимости терминов.

До сих пор мы рассматривали отдельно взятый документ, не принимая во внимание, что он входит в базу данных наряду с множеством других документов. Если представить всю базу данных как единый документ, к ней можно будет применить те же законы, что и к единичному документу. Посмотрите на список терминов в нашем примере. В одной группе находятся слова-термины «зипфа» и «не» - они входят в документ равное количество раз. Исследовав остальные документы базы данных на предмет вхождения в них этих терминов, мы, обнаружим, что «не» встречается очень часто, в то время как «зипфа» довольно редко. Вышеизложенное позволяет сделать вывод: слово «зипфа» должно стать термином, в то время как «не» следует отбросить, как ненужное слово. Чтобы избавиться от лишних слов и в тоже время поднять рейтинг значимых слов, вводят инверсную частоту термина. Значение этого параметра тем меньше, чем чаще слово встречается в документах базы данных. Вычисляют его по формуле:

Инверсная частота термина i = log (количество документов в базе данных / количество документов с термином i).

Теперь каждому термину можно присвоить весовой коэффициент, отражающий его значимость:

Вес термина i в документе j = частота термина i в документе j х инверсная частота термина i.

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

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

В качестве терминов могут выступать не только отдельные слова, но и словосочетания. Джорж Зипф (George K. Zipf) опубликовал свои законы в 1949 году. Пять лет спустя знаменитый математик Беноит Мандлеброт (Benoit Mandlebrot) внес небольшие изменения в формулы Зипфа, добившись более точного соответствия теории практике. Без этих законов сегодня не обходится ни одна система автоматического поиска информации. Как следует из законов, математический анализ позволяет машине с хорошей точностью, без участия человека распознать суть текста. [16, с 30]

.4 Механизм работы поисковых систем

Каждая поисковая система - это комплекс программ.

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

Основные части программного комплекса:

2.      Робот crawler (“путешествующий” паук). Его задача - собирать все ссылки на исследуемой странице, находить среди них новые, неизвестные поисковой системе, и добавлять их в список ожидающих индексации.

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

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

.        Система обработки запросов и выдачи результатов.

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

Каждый результат поиска содержит:

1.      Заголовок найденной страницы.

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

.        Полный URL (УРЛ) (“Universal Resource Locator” - адрес в сети Интернет) страницы.

.        Размер страницы, дата последнего изменения (если поисковая машина в состоянии ее определить).

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

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

.        Рубрику каталога или рейтинга поисковой машины (если сайт участвует в каталоге или рейтинге).

Чем же различаются поисковые машины, если у них одинаковая форма запроса и примерно одинаковый формат выдачи результатов?

-    Релевантностью результатов;

-        величиной и частотой обновления баз данных;

-        скоростью выдачи результатов;

-        удобством работы.

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

.5 Основные параметры поисковых систем

Работа поискового указателя происходит в три этапа, из которых два первых являются подготовительными и незаметны для пользователя. Сначала поисковый указатель собирает информацию из World Wide Web. Для этого используют специальные программы, аналогичные браузерам. Они способны скопировать заданную Web-страницу на сервер поискового указателя, просмотреть ее, найти все гиперссылки, имеющиеся на странице, снова разыскать находящиеся в них гиперссылки и т. д. Подобные программы называют червяками, пауками, гусеницами, краулерами, спайдерами и другими подобными именами. Каждый поисковый указатель эксплуатирует для этой цели свою уникальную программу, которую нередко сам и разрабатывает. Многие современные поисковые системы родились из экспериментальных проектов, связанных с разработкой и внедрением автоматических программ, занимающихся мониторингом Сети. Теоретически, при удачном входе спайдер способен «просмотреть» все Web-пространство за одно погружение, но на это надо много времени, а ему еще необходимо периодически возвращаться к ранее посещенным ресурсам, чтобы контролировать происходящие там изменения и выявлять «мертвые» ссылки, т. е. потерявшие актуальность.

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

На третьем этапе происходит обработка запроса клиента и выдача ему результатов поиска в виде списка гиперссылок. Допустим, клиент хочет узнать, где в Интернете имеются Web-страницы, на которых упоминается известный голландский механик, оптик и математик Христиан Гюйгенс. Он вводит слово Гюйгенс в поле набора ключевых слов и нажимает кнопку. Найти (Search). По своим базам указателей поисковая система в доли секунды разыскивает подходящие Web-ресурсы и формирует страницу результатов поиска, на которой рекомендации представлены в виде гиперссылок. Далее клиент может пользоваться этими ссылками для перехода к интересующим его ресурсам. [8, с380]

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

.6 Классификация поисковых систем по авторитетности

Классификация поисковых систем по авторитетности:

-        Alta Vista (#"863513.files/image001.gif">: «выборки, представленные в таблице 1, однородны (распределение учащихся по баллам существенно не различается)» при конкурирующей гипотезе : «выборки, представленные в таблице 1, неоднородны (распределение учащихся по баллам различается существенно)». Гипотеза  проверена по критерию б . Найдена числовая характеристика по формуле (1)

б =n₁n₂* (H₁-H₀)/ (H₁*H₀)       (1),

где H_1, и H₀ - число учащихся контрольная группа и экспериментальная группа соответственно, получивших определенный балл k=(1;4), , n₁=11, n₂=11 - число учащихся в контрольной группе и экспериментальной группе соответственно.

Таким образом,

б =6*(1/6-1/6) /2+(2/6-2/6) /4+(3/6-2/6) /5+(0/6-1/6) /1

б =0,127

По таблице критических точек распределения б для уровня значимости в=0,05 и числа степеней свободы l₁= 3 найдено критическое значение б_кр вј= б_кр/0,05; 3ј=5,3.

Так как б_набл= б_кр, то гипотеза  принимается на уровне значимости 0,05. Поэтому можно утверждать, что на начало эксперимента качество знаний учащихся в контрольной и экспериментальной группах существенно не различается.