ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САНКТ-ПЕТЕРБУРГСКИЙ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М. А. БОНЧ-БРУЕВИЧА»

К.В. БЕЛОУС

Методические указания к выполнению курсового проекта по дисциплине «Основы Интернет технологий»

Санкт-Петербург

2014

Задание на курсовой проект

Курсовой проект по дисциплине «Основы Интернет технологий» направлен на первоначальное знакомство студентов с алгоритмами и методами работы поис-

ковых систем.

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

ство, оригинальность и происхождение («машинный» или человеческий). Кроме того, статистический анализ текстов позволяет предположить происхождение ли-

тературного произведения, в случае, если автор его не известен.

Для выполнения курсового проекта студенту предлагается выбрать некото-

рый литературный текст объѐмом 2 — 2,5 машинописных листа. После выбора текста необходимо подсчитать общее количество слов в тексте и составить табли-

цу, отражающую число вхождений некоторого слова в текст.

При использовании информационных источников (книги, электронные из-

дания), а так же использования входящих в них схем, таблиц, рисунков, графиков и диаграмм необходимо творчески подходить к использованию информации, со-

держащейся в данных информационных источниках. При использовании источ-

ников информации, в конце лабораторной работы необходимо указать их выход-

ные данные (автор, название, издательство, год издания, ISBN (при наличии),

ссылка на сайт (при использовании электронного издания)).

Теоретическое введение Работа поисковых систем основана на анализе текста, поэтому при разра-

ботке алгоритма поисковых систем и при поисковой оптимизации сайта исполь-

зуется статистический анализ текстов. Важную роль в статистическом анализе текстов играют законы Зипфа.

Изучением закономерностей составления текстовых документов занимался,

американский лингвист и философ Джордж Зипф (1902 – 1950), профессор Гар-

вардского университета. К эмпирическим законам Джорджа Зипфа обычно обра-

щаются для иллюстрации частоты повторения тех или иных явлений. Эти законы выведены на основе исследования частоты использования слов в тексте.

Наблюдения показали, что слова с большим количеством букв встречаются в тексте реже коротких слов. В каждом языке есть слова, которые встречаются чаще, чем остальные, но не имеют значения. Есть слова, которые встречаются ре-

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

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

нами Зипфа.

Первый закон Зипфа представляет эмпирическую закономерность распре-

деления частоты слов естественного языка: если все слова некоторого языка (или просто достаточно длинного текста) упорядочить по убыванию частоты их ис-

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

Выберем любое слово и посчитаем, сколько раз оно встречается в тексте.

Эта величина называется частотой вхождения слова в текст. Обозначим еѐ f. Под-

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

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

ковый номер частоты называется рангом частоты . Так, наиболее часто встреча-

ющиеся слова будут иметь ранг , следующие за ними — и т. д. В вы-

бранной странице текста определим вероятность р встретить определенное слово.

Вероятность будет равна отношению частоты вхождения этого слова к общему числу слов в тексте:

(1)

где количество слов в тексте.

Первый закон Зипфа состоит в том, что произведение вероятности р обна-

ружения слова в тексте на его ранг частоты r (ранг частоты наиболее частого сло-

ва равен 1) является константой для определенной языковой группы. Обозначим

еѐ .

(2)

В честь ученого назвали «константой Зипфа». Значение константы в

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

какой бы текст мы ни взяли. Так, например, для английских текстов константа Зипфа равна приблизительно 0,1. Для русского языка константа Зипфа получи-

лась равной 0,06-0,07. Приведем примеры подсчета частот некоторых русских слов, для которых вычислены следующие значения коэффициентов Зипфа для

Таблица 3

Для текста с избыточным употреблением слова «новости»

Как видно из таблицы неестественность текста может быть определена ал-

горитмически — значение коэффициента Зипфа для слова «новости» (табл. 3) по-

чти в три раза выше, чем ожидаемое для естественных текстов (табл. 2). Алгорит-

мы ранжирования реальных поисковых машин намного сложнее, но все факторы,

которые поисковики используют в качестве значимых параметров для ранжиро-

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

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

что чем больше текст, тем достовернее определяется его «естественность».

Второй закон Зипфа «количество — частота»

Выразим из (2) зависимость частоты встречаемости слова в тексте от его ранга r.

(2)

Второй закон Зипфа состоит в том, что форма кривой зависимости частоты и количества слов, входящих в текст с этой частотой, одинакова для всех текстов.

Функция f(r) для текста достаточно большого фиксированного объема п (напри-

мер в 5000 слов) в графическом представлении является равносторонней гипербо-

лой.

В каждом языке есть слова, которые встречаются чаще, чем остальные, но не имеют значения. Есть слова, которые встречаются реже, но имеют намного большее смысловое значение.

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

части диаграммы. Зависимость частоты от ранга для английских текстов отражает тот общепонятный факт, что некоторые немногие английские слова (в первую очередь — THE, OF, ТО, A, AND. IN. THAT. FOR, WAS, WITH, HIS, IS встреча-

ются очень часто, подавляющее большинство слов встречается со средней часто-

той, и есть небольшое количество слов (очень длинных), которые встречаются очень редко.

Закон применим и к русскому языку, который оказался несвободным от за-

кономерностей, как и иностранные языки. В русском языке первую по рангу ше-

ренгу образуют слова: И, В, НЕ, НА, ЧТО, Я, С, МЫ, У, ОН, ПО, БЫЛО — и из всего этого следует, что при встрече с каким-то закодированным текстом про-

стейший способ выяснить, осмысленный это текст или просто набор случайно ис-

пользуемых значков, — это проверить частотность знаков этого текста на закон Зипфа,

Еще одно следствие: наиболее часто употребляемые слова языка, суще-

ствующего длительное время, короче остальных. Частое употребление ―истерло‖ их... Воспользовавшись законами Зипфа, можно извлечь из текста слова, отража-

ющие его смысл (ключевые слова). Это слова с рангом r = 3 ÷ 1 0 .

От того, как будет выставлен диапазон значимых слов, зависит многое. Если поставить широко — то в ключевые слова будут попадать вспомогательные сло-

ва; если установить узкий диапазон — то можно потерять смысловые термины.

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

го текста некоторых слов, которые не могут являться значимыми и поэтому явля-

ются «шумом».

Пример расчѐта

Шесть миль каждый вечер. Двадцать лет подряд. Джэнис Кэпшоу считала,что выглядит лет на десять моложе в свои трид-

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

десять часов и пробежала четыре квартала по Оушн-авеню, глав-

ной улице городка Мунлайт-Ков. Дальше она, как всегда, свер-

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

ний, где никогда не запирали двери, - таверны "Рыцарский

мост" и костела Девы Марии. Городок Мунлайт-Ков в отличие от многих других не делал ставку на туристов. Когда-то размерен-

ность здешней жизни даже привлекала внимание Джэнис, но затем ей иногда стало казаться, что город не просто дремлет, а впа-

дает в летаргию. Янтарь фонарей, оправленный в тень кипари-

сов и сосен на главной улице, неподвижный воздух и туман,

струящийся над мостовой, - больше никого и ничего. Джэнис ка-

залось, что она - последний человек на Земле и только звуки ее шагов и дыхание нарушают тишину, наступившую после Страш-

ного Суда.

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

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

мраке наступающей ночи небо поднималось высоко над землей,

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

Теперь путь ее лежал по берегу моря. Лунный свет,

переливающийся то золотом, то серебром, в этот вечер почти не заслоняли ни облака, ни туман; она могла видеть все перед со-

бой. Таинственные огоньки плясали на волнах,

полоса песка, казалось, сама светилась лунным светом, и

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

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

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

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

отвечала: "Во всяком случае, я буду сосать не твою кровь". Видит Бог, она любила его. Сначала, правда, опаса-

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

минает его каждый день. И каждую ночь. Он был...

Внезапно Джэнис почувствовала, что она не одна на пустынном пляже. Это случилось в тот момент, когда она мино-

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

она не заметила, только инстинкт подсказал ей - кто-то нару-

шил ее одиночество.

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

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

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