Эффективность ранжирования пассажей как одного из способов поиска информации в текстовых коллекциях. Часть II

Первая часть статьи опубликована здесь

Оценка ранжированных запросов

Оценивать запрос, сравнивая его с каждым документом, задача нереальная; для эффективной оценки запроса требуется специальная форма индекса. Большинство исследований продемонстрировали, что эффективный поиск требует рассмотрения всех терминов, встречающихся в документе, за исключением стоп слов (не несущих смысловой нагрузки терминов, например: «the», «и», к тому же). Попытки сократить объем индексных терминов до меньшего количества дескрипторов ( лексических единиц (слов, словосочетаний) информационно-поискового языка, служащих для описания основного смыслового содержания документов) не оказались успешными. Стандартная структурная единица индексируемых документов для ранжирования – это инвертированный файл (структура данных, в которой хранится информация о том, в каких документах и на каких позициях встречаются термины). Это единственно правильная структура индекса, состоящая из двух компонентов: словаря с определенными терминами и инвертированного списка для каждого термина.

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

Создать массив аккумуляторов (array of accumulators), один для каждого документа коллекции.
Обработать инвертированный список для каждого термина запроса t по очереди. Каждый список должен быть полностью обработан до начала обработки следующего. Идентификатор для каждого документа – d, частота вхождения термина в документе – fd;t в инвертированном списке для t, обновление аккумуляторов d посредствам добавления
wq;t * wd;t = loge(fd;t + 1) * loge(fq;t + 1) * loge(N=ft + 1) к его существующему значению.
3. Нормировать векторы аккумуляторов, поделив на Wd и определив наивысшую оценку k; добавятся и будут представлены пользователю соответствующие k документы.

Рис. 1. Term-order or TO обработка для ранжирования документов

Для инвертированного списка существует две стандартные стратегии для оценки ранжированного запроса: TO и DO. Далее рассмотрим данные стратегии, определяя плюсы и минусы каждой.

Оценка запроса с помощью TO (term-ordered) стратегии

TO обработка (term-ordered) является самой популярной стратегией оценки запросов. Здесь инвертированный список для каждого термина выбирается, обрабатывается и отбрасывается перед рассмотрением следующего списка.

Списки должны быть рассмотрены в порядке уменьшения редкости, т.е. информация о самом редком термине полностью обрабатывается, до тех пор, пока не добавляется информация о следующем термине. Входные данные в списке содержат информацию о вхождении термина в документе. Чтобы использовать данную информацию для оценки подобия, необходимы аккумуляторы (accumulators), содержащие данные о частичном подобии каждого документа. ТО обработка представлена на рис.1, данное множество (set) представлено как массив данных (array) с одним элементом в документе текстовой коллекции. Заметим, что даже для запросов, состоящих из нескольких терминов, большое количество документов в коллекции может иметь ненулевые значения аккумуляторов (non-zero accumula F^D_TO tors).

Затраты ресурсов на оценку запроса включают дисковое пространство (disk), память и процессы CPU в зависимости от запроса и статистики базы данных. Данные затраты не представляются в совокупности: любая модель, интегрирующая их в единую оценку была бы основана на жестком ограничении в параметрах, таких как затраты на выбор части дискового пространства, затраты на дополнительную обработку, размер коллекции, длинны стандартного запроса, распределение терминов запроса. Значимыми характеристиками данных затрат являются их асимптотический характер поведения и изменения, связанные с особенностями запроса и состоянием базы данных. Анализ данных характеристик позволяет прогнозировать относительные результаты различных методов оценки запросов.

Для ТО оценки основные источники затрат следующие:

Выбор инвертированных списков на диске

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

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

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

Обработка инвертированных списков

P^D_TO
Эта потеря времени состоит из двух компонентов: во-первых, время на полную декомпрессию каждого списка, во-вторых, Время на обработку каждого идентификатора для каждого документа, частоту вхождения термина в документ, вычисление wq;t wd;t, обновление соответствующего аккумулятора. Потери могут быть сокращены по средствам предвычислений для каждого документа значения wq;t wd;t, соответствующего небольшой частоте вхождения термина в документе, которая рассчитывается для большинства вхождений инвертированного списка.
Данные потери линейны по отношению к числу документов в коллекции и числу терминов в запросе.

Хранение и обработка массива аккумуляторов (array of accumulators)

A^D_TO
Аккумуляторы потребляют память для хранения, процессов CPU, нормализации, поиска сходных величин. Данные потери линейны по отношению к числу документов в коллекции, но независимы от длины запроса.

В условиях ограниченной памяти, может возникнуть необходимость хранить аккумуляторы компактно, по средствам структуры фиксированной длинны, в том случае, если структура будет заполнена, запись следует осуществлять на диск. В конце обработки инвертированных списков, временные структуры (temporary structures) должны быть выбраны и объединены. Такой способ обработки предполагает значительные затраты; намного эффективнее просто ограничить число аккумуляторов.

Чтобы сократить число аккумуляторов, можно использовать квази-нулевую стратегию запоминания (almost-zero memory strategy): выбираются первые два инвертированных списка, объединяются, записывается промежуточный результат на диск, затем итерационно (пошагово) этот результат объединяется с каждым результатом по последующим спискам, каждый раз записывая новые результаты на диск. Если пространство буфера ограничено, инвертированный список может быть представлен в виде небольших блоков. Данная стратегия имеет свой недостаток для длинных запросов: промежуточный список будет содержать только один входной элемент (entry) для каждого документа в базе данных.

Дальнейшие потери связаны с издержками выбора ответных документов (answer documents), которые не зависят от способа оценки запроса. Для небольшого количества ответов затраты не велики, их можно не учитывать.

Улучшение ТО оценки

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

Другим улучшением является ограничение числа аккумуляторов. Т.к. большинство аккумуляторов обычно ненулевые (non-zero), то большинство показателей аккумуляторов заведомо малы, за исключением значительных терминов. Предлагается несколько эвристических правил для ограничения числа аккумуляторов. Одним их наиболее эффективных способов – выбор абсолютных границ (absolute bound) аккумуляторов. В данном подходе, предполагающем TOS, обработаны первые инвертированные списки (в соответствии с более редкими терминами в запросе), каждая ссылка на новый документ провоцирует создание аккумулятора. Когда аккумулятор заполнен, начинается обработка часто встречающихся терминов, существующие аккумуляторы могут быть обновлены, но создание новых уже невозможно. По данным экспериментов TREC, ограничение числа аккумуляторов до 5% от количества имеющихся документов не повлияет на результативность. Метод с использованием ограниченного числа аккумуляторов может иметь значение в том случае, если количество терминов запроса велико. Основным поводом для подобных изменений является сокращение затрат на хранение аккумуляторовБольшие затраты могут потребоваться для их поддержания – массивы данных (array) должны быть заменены определенной структурой поиска, такие как хеш-таблица, которая представляется в виде карты идентификаторов документа для аккумуляторов.

A^D_TOS составляет почти 1/10 от A^D_TO
Затраты на подключение аккумуляторов возрастают, т.о. поиск не совсем прямой.Идентификаторы документов и частота термина в документе не используются для инвертированных списков, соответствующих часто встречающимся терминам , потому что эти данные соответствуют документам, которых нет в аккумуляторе. Путем изменений каждого инвертированному списку, таких как, разделение списка на блоки и др., можно избежать обработки ненужной информации. Для очень больших списков достаточно дешифровать лишь небольшой процент всего контента.

Т.о. пропуская TO или TOS обработки, можно значительно сократить общие затраты. По аналогии с ТО обработкой, затраты – F^D_TO для выбора списков, для обработки списков, и A^D_TOS для обработки аккумуляторов. Использование команд пропуска немного увеличит затраты на выбор термина, т.к. списки увеличатся из-за включения дополнительных указателей (pointers), возможно F^D_TOS 1:25F^D_TO.

Однако затраты обработки значительно сокращаются; наиболее точным утверждением об относительных затратах может быть P^D_TOS всегда меньше, чем P^D_TO, намного меньше для длинных запросов. Разница между A^D_TO и A^D_TOSне зависит от длинны запроса;
В тестовых данных принимается во внимание обычные запросы из 5 терминов. Используя ТО обработку на тестовой установке Sparc 20, выбор инвертированных списков произойдет за время F^D_TO = 0:2, время для обработки списков – это P^D_TO = 0:2, время необходимое для инициализации и конечной обработки аккумуляторов – это A^D_TO = 0:4 (всего 0.8 секунды). Для запроса из 30 терминов, время затраты – F^D_TO = 1:0, P^D_TO = 1:5,и A^D_TO = 0:5 соответственно (всего 3.0 секунды).

Для сравнения отметим, что, для TOS обработки, для того же запроса из 5 терминов время затраты составили F^D_TOS= 0:2, P^D_TOS = 0:2, и A^D_TOS = 0:1 (всего 0.5 секунды), иДля того же запроса из 30 терминов время затраты составили F^D_TOS = 0:9, P^D_TOS = 1:1, и A^D_TOS = 0:1 (всего 2.1секунды).

Средние время затраты на запрос показаны на рис. 2. Каждое k число представляет `000 аккумуляторов.

Альтернативная стратегия иерархического переупорядочивания списков в дальнейшем может сократить декодирование затрат, настолько, чтобы для длинных запросов значительными оставались лишь затраты на выбор инвертированного списка и на улучшение аккумулятора. Данная стратегия такова, что контент каждого списка превращается в сбалансированное бинарное дерево, которое сохраняется преимущественно для последующего поиска в ширину (stored breadth-first), линейная обработка списка осуществляется по дереву значений, построенному для поиска в ширину, это обеспечивает эффективность команд пропуска. Однако данная стратегия оказывается невыгодной практически, т.к. не известно будет ли информация о позиции слова полностью представлена в инвертированных списках. Но для ранжирования целого документа (whole-document ranking) данная стратегия предпочтительнее команд пропуска.

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

Оценка запроса с помощью DO (document-ordered) стратегии

Другой важной стратегией оценки запроса является document-ordered или DO обработка. В данной стратегии инвертированные списки всех терминов запроса обрабатываются параллельно. Информация о каждом документе используется со всех списков одновременно. DO обработка рассмотрена на рис.3.

Выбрать первый фрагмент каждого инвертировано списка и создать массив указателей (array of pointers), с одним в начале каждого списка. Упорядочить массив по самому малому указателю документа в каждом списке. Создать отдельный, пустой неупорядоченный массив данных (мощностью k) для высоко оцененных документов.
Используйте списки как показано далее. Для необработанного документа d с наименьшем определителем, определите каждый инвертированный список, относящийся к этому документу и вычислите Σ (wq;t* wd;t)
tєq^d
Нормированный на Wd; если результат больше, чем имеющаяся наименьшая оценка подобия, добавьте d к неупорядоченному массиву высоко оцененных документов. Обновите указатели (учитывая информацию о d), выберите следующие фрагменты инвертированного списка. Данная стратегия предполагает сортировку инвертированных списков, которые оказывают небольшое влияние на изменения затрат.
k документы среди высоко оцененных документов в неупорядоченном массиве данных представляются пользователю

Рис.3. Document-order или DO обработка для оценки документов

Основными источникам затрат для DO оценки являются:

Выбор инвертированных списков с диска

F^D_DO
Одновременное запоминание в буфер каждого инвертированного списка целиком может оказаться невозможным для всех терминов в запросе. Т.о. каждый список может быть выбран фрагментарно.

Такие затраты при выборе инвертированных списков линейны по отношению к размеру коллекции, учитывая, что редкость терминов запроса не изменяется. Если для одновременного запоминания всех инвертированных списков недостаточно пространства, то появляется потребность в многократном поиске каждого инвертированного списка, а это означает, что F^D_DO может оказаться больше, чем F^D_TO в большинстве случаев. В этом случае, данные потери линейны по отношению к числу терминов в запросе, но на практике затраты сильно возрастают, когда объем буферной памяти превышен.

Для хранения имеющихся фрагментов инвертированных списков требуется один буфер фиксированного объема.

Обработка инвертированных списков

F^D_DO
Затраты состоят из трех компонентов. Во-первых, время на полную декомпрессию каждого списка, во-вторых, вычисление wq,t * wd,t для каждого идентификатора документа и частоты вхождения термина в документе. В-третьих, затраты на поиск и перестройку неупорядоченного массива инвертированных списков для каждого документа.

Эти затраты линейны по отношению к числу документов в коллекции, но для m терминов запроса они равны O(mlogm).

Для DO обработки необходим только один аккумулятор предполагающий поиск по инвертированным спискам на каждом этапе; но без структуры аккумуляторов возможности сократить вычислительные затраты (computation cost) на объединение списков практически нет. Альтернативная стратегия заключается в размещении небольшого массива t аккумуляторов, представляющих следующие t документы. На каждом этапе оценка запроса будет осуществляться циклически по спискам терминов, обрабатывая информацию любого из данных документов. Такой поиск обеспечит самые высокие показатели подобия. Это избавит от поиска по спискам, однако представит затраты ТО обработки, по существу каждый документ представляется аккумулятором, в дополнение каждый инвертированный список должен быть выбран фрагментарно.

В продолжение предыдущего примера, для запроса из 5 терминов время затраты в секундах равны
F^D_DO= 0:2 и P^D_DO = 0:6 (всего 0, 8 секунды); для запроса из 30 терминов время затраты равны F^D_DO= 1:3 и P^D_DO= 4:8 (всего 6,1секунды).
Средние время затраты на запрос показаны на рис. 2.

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

Однако для больших коллекций и запроса, состоящего из небольшого числа терминов, DO обработка может быть предпочтительнее, чем TO или TOS обработки: пространство буфера позволяет каждому инвертированному списку быть выбранным целиком, затраты на обработку большого массива данных аккумуляторов отсутствуют, а команда пропуска представляет небольшое преимущество. С увеличением количества терминов в запросе, потери при мультидоступе DO становятся более значительными, тогда как команда пропуска представляет улучшения для TOS обработки. Точка пересечения двух схем зависит от: размера коллекции, вероятного распространения терминов запроса, работа диска.

Параллелизм

В информационно-поисковых системах umago.ru существует две формы параллелизма: использование разнообразных процессоров и технологий параллельного считывания с диска (parallel disk technologies), которые смогут улучшить эффективность системы (system performance) и технология, которая представляет возможность работать множеству пользователей одновременно (user parallelism).

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

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

С увеличение числа пользователей, сокращается объем памяти на каждого пользователя. Для ТО обработки: если не достаточно пространства для полного массива аккумуляторов, оценка запроса может быть произведена с использованием лишь временных аккумуляторных структур (temporary accumulator structures) на диске; это означает, если количество пользователей удвоится, потребуется большее дисковой мощности (disk accesses) для выполнения любого запроса.

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

Для DO обработки: если количество пользователей возрастает, буферное пространство для инвертированных списков должно быть сокращено. С одной стороны, сокращение пространства не повлияет на результативность. С другой стороны, увеличение пользователей вдвое, потребует вдвое больше дискового пространства для выполнения запросов. Увеличение пользователей вдвое вскоре может увеличить продолжительность загрузки в 4 раза. Стремительное сокращение пространства, может разрушить систему.

TOS оценка: аккумуляторные структуры не должны быть крупными. Вместо предложения абстрактной модели затрат, эффективность TO, TOS и DO оценок запроса были проверены экспериментально.

Марчин Казкиел (Marcin Kaszkiel), Джастин Зобель (Justin Zobel), Рон Сакс-Дэвис (Ron Sacks-Davis). Университет RMIT, Мельбурн, Австралия.

Источник: seonews.ru