Суть патента
Система получения информации использует фразы для индексирования, получения, структурирования и описания документов. Фразы определяются с тем, чтобы предсказать появление в документе других фраз. Документы индексируются на основании фраз, которые они включают. Спам-документы определяются на основании количества соответствующих фраз, встречающихся в документе.
1. Компьютерный метод определения спам-документов в системе получения информации включает в себя:
поддержку списка фраз, причем каждая фраза содержит ассоциативные связи с набором соотнесенных с ней фраз;
определение количества соотнесенных фраз, которые могут содержаться в документе
для каждой фразы из списка фраз;
определение для документа, и, по крайней мере, для одной фразы в документе, - фактического количества соотнесенных фраз, содержащихся в документе;
определение документа в качестве спам-документа путем сравнения фактического количества соотнесенных фраз, содержащихся в документе, с ожидаемым количеством соотнесенных фраз
2. Метод, описанный в п.1, в процессе определения количества соотнесенных фраз, ожидаемых в документе по каждой фразе из списка фраз, включает также в себя:
анализ индекса документов;
для каждого документа – определение набора фраз в документе из списка фраз, и для каждой фразы в документе – определение количества соотнесенных фраз, также содержащихся в документе;
определение ожидаемого количества соотнесенных фраз, как усредненной величины количества соотнесенных фраз в проанализированных документах
3. Метод, описанный в п.1, в процессе определения «спамовости» документа, включает в себя:
отслеживание фактического количества соотнесенных фраз, содержащихся в документе, для хотя бы одной фразы, по которой количество соотнесенных фраз значительно превосходит ожидаемый показатель.
4. Метод, описанный в п.1, в процессе определения «спамовости» документа, включает в себя:
отслеживание фактического количества соотнесенных фраз, содержащихся в документе, для хотя бы одной фразы, по которой количество соотнесенных фраз хотя бы в несколько раз превосходит показатель стандартной девиации ожидаемого количества соотнесенных фраз.
5. Метод, описанный в п.1, в процессе определения «спамовости» документа, включает в себя:
отслеживание фактического количества соотнесенных фраз, содержащихся в документе, для хотя бы одной фразы, по которой количество соотнесенных фраз хотя бы в несколько раз превосходит показатель ожидаемого количества соотнесенных фраз.
6. Метод, описанный в п.1, в процессе определения «спамовости» документа, включает в себя:
идентификацию документа в качестве спама, если для каждого минимального разнообразия фраз в документе фактическое количество соотнесенных фраз, присутствующих в документе, значительно превосходит ожидаемое количество соотнесенных фраз.
7. Метод, описанный в п.1, в процессе определения «спамовости» документа, включает в себя:
идентификацию документа в качестве спама, если фактическое количество соотнесенных фраз в документе, по хотя бы одной фразе, превосходит предопределенный максимум ожидаемого количества соотнесенных фраз.
8. Метод, описанный в п.1, в процессе определения «спамовости» документа, включает в себя:
определение для документа набора наиболее значимых фраз, содержащихся в этом документе;
для каждой из наиболее значимых фраз, определение фактического количества соотнесенных фраз, содержащихся в документе;
а также отслеживание случаев значительного превышения фактического количества соотнесенных фраз, по сравнению с ожидаемым показателем – в таком случае документ будет идентифицирован как спам по этой отдельной фразе
9.Метод, описанный в п.1, включает в себя:
отслеживание случаев идентификации документа в качестве спама и помещение документа в список спамовых документов.
10. Метод, описанный в п.9, включает в себя:
получение поискового запроса;
выборку набора документов, релевантных поисковому запросу, при этом каждый документ имеет определенный коэффициент релевантности;
определение (для каждого документа из набора) того, был ли идентифицирован документ в качестве спама;
переоценку коэффициента релевантности документа на основании того, был ли документ идентифицирован в качестве спама;
перераспределение документов в наборе, в соответствии с их коэффициентами релевантности
|
11. Метод, описанный в п.8, включает в себя: добавление документа в список спамовых документов, ассоциированных с наиболее значимой фразой; а по каждой фразе, соотнесенной с наиболее значимой фразой, добавление документа в список спамовых документов, ассоциированных с соотнесенной фразой.
Описание патента
Область применения изобретения
Настоящее изобретение относится к системе получения информации в целях индексирования, поиска и классификации документов в широкомасштабных хранилищах данных, подобных сети Интернет.
Предыстория изобретения
Системы получения информации, обычно называемые поисковыми системами, стали основным инструментом для поиска информации в широкомасштабных, разнородных и развивающихся хранилищах данных, подобных сети Интернет.
Поисковые системы, обычно, создают индекс, в котором хранятся данные о соответствии документов (или «страниц») отдельным словам, находящимся в каждом документе. Документ выдается в ответ на запрос, содержащий поисковые термины – в основном, если в документе содержится некоторое количество этих терминов. Затем полученные документы ранжируются, в соответствии с другими статистическими величинами, например, частота появления поисковых терминов, домен, состав ссылок на документ, и т.д. Полученные документы предоставляются пользователю, обычно в порядке ранжирования и без группировки или иерархии. Иногда предоставляется отдельный участок текста документа, чтобы пользователь мог получить представление о содержании документа.
Непосредственное «булево» соответствие поисковых терминов имеет хорошо известные ограничения, и в отдельных случаях не идентифицирует документы, которые не содержат поисковых терминов, однако обладают соотнесенными словами. К примеру, в стандартной булевой системе, поиск по «Australian Shepherds» («Австралийские овчарки») не возвратит документы о других пастушьих собаках, подобных бордер-колли - если в этих документах не будет содержаться именно этих поисковых терминов. Более того, подобная система, скорее всего, возвратит с высоким ранкингом документы об Австралии (в которых нет ничего о собаках) и документы о «пастухах» в целом (shepherd – пастух).
Проблема состоит в том, что общепринятые системы индексируют документы на основании отдельных терминов, но не концепций. Концепции зачастую могут быть выражены фразами, подобными «Australian Shepherd», «President of the United States», или «Sundance Film Festival». В лучшем случае, некоторые системы могут индексировать документы с учетом предопределенного и весьма ограниченного набора «известных» фраз – которые обычно выбираются оператором-человеком. Индексирование фраз обычно не проводится, в силу повышенных требований к вычислительным мощностям, необходимым для идентификации всех возможных фраз, состоящих из трех, четырех, пяти и более слов. К примеру, если предположить, что любые пять слов могут составить фразу, а собрание терминов будет содержать 200 000 уникальных записей, то в результате получится около 3,2*1026 фраз – намного больше, чем может храниться в современной памяти или обрабатываться программными средствами. Следующая проблема состоит в том, что фразы постоянно обновляют лексикон и выходят из обихода (в разрезе частоты их использования) – намного чаще, чем появляются отдельные новые слова. Новые фразы генерируются постоянно, из разных источников – технология, искусство, мировые события, право. Популярность других фраз может уменьшаться с течением времени.
Другая проблема, которая возникает в существующих системах получения информации, состоит в появлении «спам»-документов. Некоторые спам-страницы являются документами, которые содержат малую толику, либо не содержат вовсе, значимого контента. Вместо этого, в них содержатся коллекции популярных слов и фраз, зачастую сотни и даже тысячи – такие документы иногда называют «страницами, фаршированными кейвордами». Другие содержат специфичные слова и фразы, которые могут быть интересны рекламодателям. Эти типы документов (называемые «медовыми бочонками») создаются для показа в поисковых запросах вместе с платными объявлениями. Однако для конечного пользователя, который ищет значимый контент, просмотр подобных документов означает ненужную потерю времени и расстройство.
Поэтому, появилась необходимость в системе получения информации и методологии, которые смогли бы наиболее полно идентифицировать фразы в широкомасштабных коллекциях, индексировать документы в соответствии с фразами. Кроме того, подобная система получения информации нужна для обнаружения спам-документов и фильтрации этих документов из поисковых результатов.
Краткое описание изобретения
Система получения информации и методология используют фразы для индексирования, поиска, ранжирования и описания документов в коллекции документов. Система адаптирована для идентификации фраз, которые обладают достаточно частым и/или выдающимся использованием в коллекции документов – для индикации того, что они являются «действующими» или «хорошими» фразами. Подобным образом могут быть идентифицированы фразы, состоящие из нескольких слов – к примеру, фразы из четырех, пяти, и более слов. Это позволяет избежать проблемы идентификации и индексирования всех возможных фраз, получаемых в результате всех возможных комбинаций данного количества слов.
истема адаптирована для идентификации фраз, которые соотносятся друг с другом – на основании способности фразы предвосхищать появление в документе других фраз. Используется предсказательное сравнение фактического совместного появления двух фраз и ожидаемого совместного появления этих двух фраз. Полученная информация, в виде коэффициента фактического совместного появления к ожидаемому появлению, составляет предсказательную шкалу. Две фразы соотносятся, если на предсказательной шкале они превышают некоторый порог. В таком случае, вторая фраза имеет существенное информационное значение по отношению к первой фразе. Семантически, соотнесенные фразы обычно используются для обсуждения или описания данной темы или концепции, наподобие «Президент Соединенных Штатов» и «Белый Дом». Для данной фразы, соотнесенные фразы могут быть упорядочены согласно их релевантности или значимости, на основании их предсказательных параметров.
Система получения информации адаптирована для определения спам-документов, на основании появления повышенного количества соотнесенных фраз в документе.
Краткое описание чертежей
Рис 1. – блок-диаграмма программной архитектуры настоящего изобретения
Рис 2. – иллюстрирует метод идентификации фраз в документах
Рис 3 – иллюстрирует документ с окном фраз и вторичным окном
Рис 4- иллюстрирует метод идентификации соотнесенных фраз
Рис 5– иллюстрирует метод индексирования документов для соотнесенных фраз
Рис 6– иллюстрирует метод получения документов, основанный на фразах
Чертежи описывают предпочтительный вариант реализации настоящего изобретения и служат только для иллюстрации. Для разбирающегося в теме из последующего обсуждения будет понятно, что могут быть использованы альтернативные воплощения продемонстрированных структур и методов, с соблюдением принципов описанного здесь изобретения.
Детальное описание изобретения.
I. Обзор системы
На Рис 1 представлена организация программной архитектуры поисковой системы 100, в соответствии с одной из реализаций данного изобретения. В этой реализации система включает в себя систему индексирования 110, поисковую систему 120, презентационную систему 130 и сервер 140, отвечающий за связь с внешним миром.
Система индексирования 110 отвечает за идентификацию фраз в документах, и за индексирование документов в соответствии с их фразами – путем доступа к различным веб-сайтам 190 и другим коллекциям документов. Сервер 140, отвечающий за связь с внешним миром, получает запросы от пользователя или клиента 170, и предоставляет эти запросы поисковой системе 120. Поисковая система 120 отвечает за поиск документов, релевантных поисковому запросу (результаты поиска), включая идентификацию любых фраз в поисковом запросе, и дальнейшее ранжирование документов в результатах поиска с учетом наличия фраз в документах. Поисковая система 120 предоставляет поисковые результаты презентационной системе 130. Презентационная система 130 отвечает за модификацию поисковых результатов, включающую в себя удаление дублированных документов, генерацию тематических описаний документов и предоставление модифицированных результатов обратно серверу 140, который предоставляет результаты клиенту 170. Далее, система 100 включает в себя первичный индекс 150 и вторичный индекс 152, которые хранят проиндексированную информацию, относящуюся к документам, а также хранилище данных по фразам 160 - которое хранит фразы и соответствующую статистическую информацию. Первичный индекс 150 распределен между некоторым количеством первичных серверов 1 . . . М1, а вторичный индекс 152, подобным образом, распределен между вторичными серверами 1 . . .М2.
В контексте данного патента, под «документами» понимается любой вид носителя информации, который может быть получен и проиндексирован поисковой системой, включая веб-документы, изображения, файлы мультимедиа, текстовые документы, PDF или другие файлы с отформатированными изображениями, и т.д. Документ может содержать одну или более страниц, разделов, сегментов или других компонентов, в соответствии с его типом и контентом. Документ может с тем же успехом называться «страницей» - этот термин часто используется для обозначения документов в Интернете. Поисковая система 100 оперирует большим собранием документов, подобным Интернету и World Wide Web, однако с таким же успехом может быть использована и для ограниченных коллекций – наподобие библиотечных собраний документов или частных коллекций. Независимо от контекста, документы могут распространяться через множество различных компьютерных систем и сайтов. Без ущерба для общей картины, документы в целом, независимо от их формата или местонахождения (т.е. вебсайта или базы данных) будут упоминаться в качестве собрания или коллекции документов. Каждый документ имеет соответствующий идентификатор, который уникальным образом определяет документ; идентификатор – это преимущественно URL, однако другие типы идентификаторов (т.е., номера документов) тоже могут быть использованы. В данном материале в качестве идентификатора документов принимается URL. 
II. Система индексирования
В одном из возможных воплощений, система индексирования 110 обеспечивает три основные функциональные операции:
идентификацию фраз и соотнесенных фраз
индексирование документов в соответствии с фразами
генерацию и поддержку таксономии (Taxonomy - наука о классификации), основанной на фразах
Система индексирования может выполнять и другие функции, которые не будут рассматриваться в настоящем документе. Система индексирования 110 оперирует с первичным индексом 150 и со вторичным индексом 152, а также с хранилищем данных по фразам 160. Хранилища данных будут описаны ниже.
1. Идентификация фразы
Система индексирования 110, во время операции по идентификации фразы, определяет «хорошие» и «плохие» фразы в коллекции документов – те фразы, которые помогут в индексировании и поиске документов. С одной стороны, хорошими можно назвать фразы, которые имеют тенденцию встречаться в документах коллекции чаще некоторой определенной процентной величины, и/или отмечены особым образом в этих документах (выделены тэгами HTML, форматированием, другими морфологическими или грамматическими маркерами). С другой стороны, хорошие фразы предсказывают появление других хороших фраз, а не только являются последовательностью слов из лексикона. К примеру, фраза «Президент Соединенных Штатов» предсказывает другие фразы, такие как «Джордж Буш» и «Билл Клинтон». Однако другие фразы не могут быть предсказательными, такие как «убей себя об стену» или «в разгар дня», «среди ясного неба» - поскольку подобные идиомы и разговорные штампы могут появляться с самыми различными и несвязанными между собой фразами. Таким образом, фаза идентификации фразы определяет, какие фразы являются хорошими, а какие – плохими (то есть, не обладают предсказательной силой).
В соответствии с Рис 2, процесс идентификации фраз состоит из следующих функциональных стадий:
200 Сбор возможных и хороших фраз, наряду со статистикой частоты и совместного употребления фраз
202 Классификация возможных фраз на хорошие и плохие, на основании частотной статистики
204 Чистка списка хороших фраз, на основании предсказательных показателей, выведенных из статистики совместного употребления.
Каждая из этих стадий будет описана более детально.
Первая стадия 200 – это процесс кроулинга поисковой системой 110 набора документов в коллекции документов, с созданием разделов коллекции документов через определенные промежутки времени. За один проход обрабатывается один раздел. Количество документов, подвергающихся кроулингу за один проход, может варьироваться, наиболее предпочтительным является 1000000 на раздел. Желательно, чтобы в каждом разделе обрабатывались документы, которые ранее не подвергались кроулингу - пока не будут обработаны все документы, или пока не будет выполнен другой критерий для завершения операции. На практике, кроулинг продолжается, по мере того, как новые документы добавляются в коллекцию документов. Система индексирования 110 предпринимает следующие шаги при кроулинге каждого документа:
Траверсирование слов документа с окном для фраз длиной n, где n – предпочтительный максимум длины фразы. Длина окна, обычно, составляет по меньшей мере 2, а в оптимальном раскладе – 4 или 5 терминов (слов). Лучше, чтобы фразы включали в себя все слова из окна фраз, вместе с теми словами, которые обычно характеризуются как стоп-термины (“a”, “the”, и т.д.). Окно фразы может заканчиваться концом строки, знаком конца параграфа, тэгом разметки или другим индикатором смены в контенте или формате.
Рис 3 иллюстрирует часть документа 300 в течение траверсирования, когда окно фраз 302 начинается со слова «stock» и продолжается на 5 слов вправо. Первое слово в окне 302 – это кандидат на фразу I, а каждое последующее слово i+1, i+2, i+3, i+4, i+5 – это тоже кандидаты на фразу. Итак, в данном примере, кандидатами на фразу являются "stock", "stock dogs", "stock dogs for", "stock dogs for the", "stock dogs for the Basque", и "stock dogs for the Basque shepherds".
В каждом окне фразы 302, каждый кандидат на фразу по очереди проходит проверку, чтобы определить, представлен ли он в списке хороших фраз 208, или в списке возможных фраз 206. Если фраза-кандидат не присутствует ни в списке хороших фраз 208, ни в списке возможных фраз 206, то кандидат определяется как «плохой» и пропускается.
Если фраза-кандидат присутствует в списке хороших фраз 208, в качестве записи gj, то запись в индексе 150 по фразе gj обновляется, чтобы включить документ (то есть, URL или другой идентификатор документа), как индикатор того, что эта фраза-кандидат gj появляется в настоящем документе. Запись в индексе 150 по фразе gj (или термину) называется постинг-списком фразы gj. Постинг-список включает в себя список документов, (по их идентификаторам документа, таким как номер документа или URL), в которых встречается фраза. В данной структурной организации, номер документа получается односторонним хэшированием URL, с использованием, например, MD5.
|
Кроме того, обновляется матрица совместного появления 212, этот процесс объясняется ниже. В самый первый проход, хороший и плохой списки будут пустыми, поэтому большинство фраз будут иметь тенденцию попадания в список возможных фраз 206.
Если фраза-кандидат не находится в списке хороших фраз 208, то она добавляется в список возможных фраз 206, если она там еще не находится. Каждая запись p в списке возможных фраз 206 обладает тремя ассоциированными характеристиками.
P(p): Количество документов, в которых появлялась возможная фраза
S(p): Количество всех появлений возможной фразы, и
M(p): Количество интересных появлений возможной фразы. Появление возможной фразы считается «интересным», если возможная фраза выделена из окружающего контента в документе грамматическими маркерами или форматированием, например, жирным шрифтом, подчеркиванием, анкор-текстом гиперссылки, или в кавычках. Эти (и другие) случаи выделения определяются по различным HTML-тэгам и грамматическими маркерами. Эта статистика для фразы сохранится, если она будет перемещена в список хороших фраз 208.
Кроме различных списков, поддерживается также матрица совместного появления 212 (G) для хороших фраз. Матрица G имеет размерность m * m, где m - количество хороших фраз. Каждая запись G (j,k) в матрице представляет собой пару хороших фраз (gj, gk). Матрица совместного появления 212 логически (но не обязательно физически) поддерживает три отдельных параметра для каждой пары (gj, gk) хороших фраз, в соответствии со вторичным окном 304, которое отцентрировано по текущему слову I, и распространяется на +/- h слов. В данной реализации, которая показана на Рис 3, вторичное окно 304 состоит из 30 слов. Матрица совместного появления, таким образом, поддерживает:
R(j,k): Обычный подсчет количества совместных появлений. Количество раз, когда фраза gj или фраза gj появлялась в качестве отдельного текста во вторичном окне,
D(j,k): Подсчет совместного «интересного» появления: количество раз, когда обе фразы gj и gk появлялись совместно в качестве выделенного текста во вторичном окне. Использование подсчета совместного интересного появления особенно ценно для того, чтобы избежать тех случаев, когда фраза (напр., знак копирайта) часто появляется на полях, в верхней или нижней части страницы, и фактически не является предсказательной для какого-то другого текста.
По отношению к примеру на Рис 3 предполагается, что "stock dogs" находится в списке хороших фраз 208, равно как и фразы "Australian Shepherd" и "Australian Shepard Club of America". Обе последние фразы появляются во вторичном окне 304, с привязкой к текущей фразе "stock dogs". Однако фраза "Australian Shepherd Club of America" является анкор-текстом для гиперссылки на сайт (отмечена подчеркиванием). Таким образом, показатель совместного появления пары {"stock dogs", "Australian Shepherd"} увеличивается, равно как и показатели появления фраз {"stock dogs", "Australian Shepherd Club of America"}и их раздельные показатели интереса – поскольку последняя фраза появляется в качестве выделенного текста.
Процесс траверсирования документа окном 302 и вторичным окном 304 повторяется для каждого документа в разделе.
После того, как документы в разделе прошли траверсирование, наступает следующая стадия операции индексирования – обновление 202 списка хороших фраз 208 из списка возможных фраз 206. Возможная фраза p из списка возможных фраз 206 перемещается в список хороших фраз 208, если частота появления фразы и количество документов, в которых появляется фраза, свидетельствуют о ее достаточно частом использовании в качестве семантически значимой фразы.
В данной реализации, это тестируется следующим образом. Возможная фраза p удаляется из списка возможных фраз 206, и помещается в список хороших фраз 208, если:
а) P(p) > 10 и S(p) > 20 (количество документов, содержащих фразу p больше 10, а количество появлений фразы p больше 20), или
б) M(p) > 5 (количество интересных появлений фразы p больше 5)
Эти параметры определяются количеством документов в разделе. К примеру, если в разделе содержится 2000000 документов, эти параметры увеличиваются примерно вдвое. Мастера жанра, конечно же, оценят, что определенные значения параметров могут изменяться, наряду с адаптивной логикой их тестирования.
Если фраза не попадает в список хороших фраз 208, то она проверяется как потенциальная плохая. Фраза p считается плохой, если:
а) количество документов, содержащих фразу P(p) < 2, и
б) количество интересных появлений фразы M(p) = 0
Эти условия свидетельствуют, что фраза является нечастой, и не используется в качестве индикатора значимого контента. Как и прежде, приведенные параметры могут изменяться, в зависимости от количества документов в разделе.
Нужно отметить, что список хороших фраз 208 будет естественным образом включать отдельные слова в качестве фраз, в дополнение к фразам из нескольких слов. Это происходит потому, что каждое первое слово в окне фраз 302 – всегда кандидат на фразу, соответственно будет накапливаться количество появлений. Таким образом, система индексирования 110 может автоматически индексировать как отдельные слова (то есть, фразы из одного слова), так и мульти-словесные фразы. Список хороших фраз 208 будет значительно короче, чем теоретический максимум, рассчитанный из максимального количества возможных комбинаций m фраз. При стандартной реализации, список хороших фраз будет включать в себя около 6,5 * 105 фраз. Список плохих фраз хранить необязательно, поскольку система должна отслеживать только возможные и хорошие фразы.
К последнему проходу по коллекции документов, список возможных фраз будет достаточно коротким, в силу ожидаемого распространения используемых фраз в большом собрании документов. Если, к примеру, при десятом проходе (т.е., около 10000000 документов), фраза встречается первый раз, крайне маловероятно, что она будет хорошей фразой на момент проведения анализа. Она может оказаться новой фразой, которая только входит в употребление, и тогда в течение последующих проходов она будет приобретать популярность. В таком случае, ее относительное количество появлений будет увеличиваться и в результате превысит порог, требуемый для попадания в список хороших фраз.
Третья стадия операции индексирования – чистка 204 списка хороших фраз 208, с использованием предсказательной величины, получаемой из матрицы совместного появления 212. Без подобной чистки, список хороших фраз 208 будет включать в себя множество фраз, которые, хотя и входят в лексикон, но не предвосхищают появление других фраз, или сами являются производными от более длинных фраз. Удаление этих слабых хороших фраз приводит к созданию довольно качественной подборки из хороших фраз. Для идентификации хороших фраз, используется предсказательная величина, которая отражает зависимость появления в документе одной фразы, при условии, что в нем присутствует другая фраза. В данной реализации это сделано следующим образом:
Как упоминалось ранее, матрица совместного появления представляет собой матрицу размером m * m, в которой хранятся данные, связанные с хорошими фразами. Каждый ряд j в матрице представляет собой хорошую фразу gj, рассчитывается величина ожидания Е ( gj). Величина ожидания Е – это процентное содержание документов в коллекции, в которых ожидается появление gj. Эта величина рассчитывается, к примеру, как отношение количества документов, содержащих gj, к общему количеству Т документов в коллекции, которые подверглись кроулингу – P(j)/T .
Как отмечалось ранее, количество документов, содержащих gj, обновляется каждый раз, когда gj появляется в документе. Значение для Е(gj) может обновляться каждый раз, когда увеличивается значение gj, или в течение данной третьей стадии.
Далее, для каждой из оставшихся хороших фраз gk (т.е., колонок матрицы), определяется – предсказывает ли gj появление gk. Предсказательный коэффициент для gj определяется следующим образом:
рассчитывается величина ожидания E (gk). Ожидаемый коэффициент совместного появления E(j,k) для gj и gk, если они не являются несвязанными фразами, составит в таком случае E(gj) * E (gk).
рассчитывается фактический коэффициент совместного появления A (j,k) для gj и gk. Это исходное значение совместных появлений R (j,k), деленное на T, общее количество документов;
gj считается предсказательным по отношению к gk, если фактический уровень совместного появления A(j,k) превосходит ожидаемый уровень совместного появления E(j,k) на некоторое пороговое значение.
В данной реализации, предсказательной величиной является получение информации. Таким образом, фраза gj предвосхищает другую фразу gk, если полученная информация I по фразе gk, в присутствии фразы gj, превосходит некоторую установленную величину. Рассчитывается это по формуле I(j,k)=A(j,k)/E(j,k)
А хорошая фраза gj предвосхищает хорошую фразу gk, если:
|
I(j,k) больше установленного порога информационного качества
В данной реализации, порог информационного качества установлен на уровне 1,5 , но его предпочтительные значения могут варьироваться от 1,1 до 1,7. Повышение порога над 1,0 служит уменьшению возможности того, что две, в целом несвязанные фразы, появятся вместе чаще, чем это предсказано статистически.
Как отмечалось ранее, расчет информационного качества повторяется для каждой колонки k матрицы G, с учетом данного ряда j. По окончании ряда, если информационное качество ни по одной из хороших фраз gk не превосходит порога информационного качества, это значит – фраза gj не предвосхищает ни одну другую хорошую фразу.
Этот шаг считается завершенным, когда будут пройдены все ряды матрицы совместного появления 212 .
Финальный шаг этой стадии – чистка списка хороших фраз 208, чтобы удалить незаконченные фразы. Незаконченной считается фраза, которая только предсказывает собственные расширения, и которая начинается в левой крайней части фразы (то есть, в начале фразы). «Расширение фразы» p - это супер-последовательность, которая начинается с фразы p. К примеру, фраза "President of" предвосхищает фразы "President of the United States", "President of Mexico", "President of AT&T", и т.д. Все последующие фразы являются расширениями фразы "President of", поскольку они начинаются с "President of" и поэтому являются супер-последовательностями.
Каждая фраза gj, оставшаяся в списке хороших фраз 208, будет предвосхищать некоторое количество других фраз, исходя из порога информационного качества, обсуждавшегося ранее. Для каждой фразы gj, система индексирования 110 проводит проверку на совпадение строк с каждой из фраз gk, которые она предвосхищает. Проверка на построчное совпадение показывает, не является ли фраза gk расширением фразы gj. Если все предвосхищенные фразы gk являются расширением фразы gj, то фраза gj неполная - она удаляется из списка хороших фраз 208 и добавляется в список незаконченных фраз 216. Таким образом, если существует хоть одна фраза gk, которая не является расширением фразы gj, тогда gj считается полной и остается в списке хороших фраз. Пример: "President of the United" – неполная фраза, поскольку единственная фраза, которую она предвосхищает, - "President of the United States", - является расширением исходной фразы.
Список неполных фраз 216 довольно полезен сам по себе, когда речь идет о фактическом поиске. После получения поискового запроса, его можно сравнить со списком неполных фраз 216. Если запрос (или его часть) совпадает с записью в списке, то поисковая система 120 может просмотреть наиболее возможное расширение этой неполной фразы (расширение фразы, которое получило наибольший коэффициент информативности относительно неполной фразы), и предложить это расширение фразы пользователю, или автоматически выполнить поиск по выбранному расширению. К примеру, если запрос был сформулирован как "President of the United", поисковая система 120 может автоматически предложить пользователю в качестве поискового запроса вариант "President of the United States".
После того, как закончится последняя стадия индексирования, список хороших фраз 208 будет содержать большое количество хороших фраз, обнаруженных в собрании. Каждая из этих хороших фраз будет предвосхищать, по крайней мере, одну фразу, которая не является ее расширением. Таким образом, каждая хорошая фраза используется с достаточной частотой и независимостью, чтобы отражать осмысленные концепции или идеи, содержащиеся в собрании документов. В отличие от существующих систем, которые используют предопределенные или отобранные вручную фразы, список хороших фраз отражает фразы, которые фактически используются в собрании. Далее, поскольку описанный процесс кроулинга и индексирования периодически повторяется, по мере добавления в коллекцию новых документов, система индексирования 110 автоматически определяет новые фразы, по мере их поступления в лексикон.
--------
|
|
vita73
|
Коментарии:
