Общая характеристика работы icon

Общая характеристика работы


Смотрите также:
1   2   3   4   5   6
вернуться в начало
^

1.2 Алгоритмы поиска. Законы Зипфа


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

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

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

Первый закон связывает частоту появления слова в тексте (она называется частота вхождения слова) с рангом этой частоты.

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


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

Формула 1

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


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

Формула 2

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

В математике такая зависимость отображается гиперболой. Отсюда, в частности, следует, что, если наиболее распространенное слово встречается в тексте 100 раз, то следующее по распространенности встретится не 99 и не 90, а примерно 50 раз.

Это также означает, что самое популярное слово в английском языке (the) употребляется в 10 раз чаще, чем слово, стоящее на десятом месте, в 100 раз чаще, чем сотое, и в 1000 раз чаще, чем тысячное.

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

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

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

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

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

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

Чтобы испытать свою разработку, ученый решил проанализировать тексты всех президентских докладов о положении в США (State of the Union addresses) начиная с 1790 года. В итоге получилось, что в период Войны за независимость американских колоний часто употреблялись слова militia («ополчение») и British («британский»), а в период с 1947 по 1959 годы наблюдался «скачок» в использовании слова atomic («атомный»). Таким образом, ученому удалось доказать работоспособность системы.

^

1.3 Как поисковые машины могут использовать законы Зипфа?


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

Можно предположить, что наиболее значимые для текста слова лежат в средней части представленного графика. Оно и понятно: слова, которые встречаются слишком часто, — это предлоги, местоимения и т.д. (в английском, немецком и некоторых других языках — еще и артикли). Редко встречающиеся слова также в большинстве случаев не несут особого смыслового значения, хотя иногда, наоборот, весьма важны для текста (об этом будет сказано чуть ниже). Каждая поисковая система решает, какие слова отнести к наиболее значимым, по-своему, руководствуясь общим объемом текста, частотными словарями и т.п. Если к числу значимых слов будут отнесены слишком многие, важные термины будут забиты «шумом» случайных слов. Если диапазон значимых слов будет установлен слишком узким, за его пределами окажутся термины, несущие основную смысловую нагрузку.

Для того чтобы безошибочно сузить диапазон значимых слов, создается словарь «бесполезных» слов, так называемых стоп-слов (а словарь, соответственно, называется стоп-лист). Например, для английского текста стоп-словами станут артикли и предлоги the, a, an, in, to, of, and, that... и др. Для русского текста в стоп-лист могли бы быть включены все предлоги, частицы и личные местоимения: на, не, для, это, я, ты, он, она и др.Исключение стоп-слов из индекса ведет к его существенному сокращению и повышению эффективности работы. Однако некоторые запросы, состоящие только из стоп-слов (типа «to be or not to be»), в этих случаях уже не пройдут. Неудобство вызывают и некоторые случаи полисемии (многозначности слова в зависимости от контекста). Например, в одних случаях английское слово «can» как вспомогательный глагол должно быть включено в список стоп-слов, однако как существительное оно часто несет большую содержательную нагрузку.

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

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

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

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

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

Пример индексирования см. в Приложении



Скачать 479,28 Kb.
оставить комментарий
страница2/6
Дата04.03.2012
Размер479,28 Kb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт
1   2   3   4   5   6
хорошо
  1
отлично
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com


База данных защищена авторским правом ©exdat 2000-2014
При копировании материала укажите ссылку
обратиться к администрации
Документы

Рейтинг@Mail.ru
наверх