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, в качестве записи g_j, то запись в индексе 150 по фразе g_j обновляется, чтобы включить документ (то есть, URL или другой идентификатор документа), как индикатор того, что эта фраза-кандидат g_j появляется в настоящем документе. Запись в индексе 150 по фразе g_j (или термину) называется постинг-списком фразы g_j. Постинг-список включает в себя список документов, (по их идентификаторам документа, таким как номер документа или URL), в которых встречается фраза. В данной структурной организации, номер документа получается односторонним хэшированием URL, с использованием, например, MD5.