сервис аналитики звонков и оптимизации
бизнес-процессов
Войти как пользователь
Вы можете войти на сайт, если вы зарегистрированы на одном из этих сервисов:

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

Россия +7 (495) 960-65-87
Шрифт:
0 2024


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.2. Средние время затраты на запрос

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Параллелизм

В информационно-поисковых системах существует две формы параллелизма: использование разнообразных процессоров и технологий параллельного считывания с диска (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, Мельбурн, Австралия.

Перевод под редакцией Анны Макаровой, Сергея Стружкова

P.S. Вы также можете ознакомиться с отечественными разработками на эту тему.

«Оценка тематического подобия текстового документа». В.Ю.Добрынин, В.В. Клюев, И.С.Некрестьянов, Санкт-Петербургский Государственный Университет.

«Обнаружение структурного подобия HTML-документов». И.С.Некрестьянов, Е.В.Павлова, Санкт-Петербургский Государственный Университет.

Есть о чем рассказать? Тогда присылайте свои материалы в редакцию.


Новые 
Новые
Лучшие
Старые
Сообщество
Подписаться 
Подписаться на дискуссию:
E-mail:
ОК
Вы подписаны на комментарии
Ошибка. Пожалуйста, попробуйте ещё раз.
Поделиться 
Поделиться дискуссией:
Отправить отзыв
ПОПУЛЯРНЫЕ ОБСУЖДЕНИЯ НА SEONEWS
Как построить качественную ссылочную массу сайта
Айрат Рахимзянов
38
комментариев
0
читателей
Полный профиль
Айрат Рахимзянов - Спасибо Кирилл. Сейчас восстановилась работа сервиса: take.ms/ttXrw
Анализ ссылок: сравнение многофункциональных платформ по размеру их баз
Андрей Ольшевский - Очень неточная статистика, объясню почему. Довольно часто делаю анализ сайтов на качество и объём ссылочной массы. Всегда делаю выгрузку из трех источников – Вебмастера Яндекса, сервиса Мегаиндекс, сервиса Линкпад. Потом с помощи алгоритмов и функции Excel отсеиваются много дублей, битых ссылок, несуществующих урл и тп. Как показала практика, вебмастера Яндекса вполне достаточно, там вся информация и она самая актуальная, в других сервисах куча мусора, а нового, чтоб было найдено и проиндексировано ПС - очень мало. Поэтому мирятся количеством в данном анализе не профессионально.
Как создать интернет-магазин: сколько стоит открытие?
Пришел посмеяться
1
комментарий
0
читателей
Полный профиль
Пришел посмеяться - Я просто посмеюсь :D Даже не хочу ничего особо говорить :D Смех, а не статья.
ТОП-10 автоматизированных сервисов контекстной рекламы
Гость - Действительно, очень плохая статья. А у редактора Блондинки видимо слишком много свободного времени.
Кому и зачем нужен маркетплейс от Яндекса
Дарья Калинская
212
комментария
0
читателей
Полный профиль
Дарья Калинская - Максим, спасибо, рада, что статья оказалась полезной )
Конкурс: угадай победителя рейтинга «Известность бренда SEO-компаний»
Андрей
1
комментарий
0
читателей
Полный профиль
Андрей - Оптимизм Дэмис Кокос Ашманов и Партнеры Раш эдженси
Инструкция по применению: обзор сервиса обратного звонка Callbackhunter
Полина Ковальчук
1
комментарий
0
читателей
Полный профиль
Полина Ковальчук - Возможно, но не советую экономить на этом сервисе, функционал то тоже круче, чем у аналогов. Вы создаете сайт для получения денег и чем качественнее Вы выстроите продвижение, тем больше лидов Вы получите!
Тест: Какой ты интернет-маркетолог?
Петр - Мда уж, есть ряд очень и очень субъективных вопросов, например с картинками и ctr или с несколькими вариантами ответа, когда из 5 пунктов надо выбрать 4, что несерьезно. Поэтому, как минимум, к этому тесту нельзя относиться серьезно. Его надо очень серьезно дотягивать, а не вываливать отсебятину.
SEO-тренды на 2017 год: мнение специалистов
Olga Inventor
1
комментарий
0
читателей
Полный профиль
Olga Inventor - Хорошая статья. То, что SEO - антитренд, уже давно говорят. Нужен комплексный подход.
Чек-лист: SEO для B2B-бизнеса
Антон Зозуля
8
комментариев
0
читателей
Полный профиль
Антон Зозуля - Ваша цель вывести страницу, на которой будет только ваш товар (обычно это фильтр бренд/производитель в нужном каталоге) по СЧ запросам в ТОП. Например, вы продаете "велосипеды Елочка". В каталоге дилера велосипеды, вы выбираете Бренд - "Елочка" и должны получить страницу "велосипеды Елочка". Она должна быть на уникальном урл, иметь уникальные метатеги, лучше, чтобы был SEO-текст. После этого ваша задача получить на нее трафик по запросам: идеально: купить велосипед, цена велосипед хуже: велосипед дешево, китайский велосипед еще хуже (меньше трафика и ниже конверсия, но они есть): велосипед + [регион], велосипед + [фильтр другой]. Тут трудно без прямого влияния на содержимое страницы (метатеги и текст). ПС бренд елочка выдуман. :)
ТОП КОММЕНТАТОРОВ
Комментариев
910
Комментариев
834
Комментариев
554
Комментариев
540
Комментариев
483
Комментариев
373
Комментариев
285
Комментариев
262
Комментариев
212
Комментариев
171
Комментариев
156
Комментариев
137
Комментариев
123
Комментариев
97
Комментариев
97
Комментариев
95
Комментариев
80
Комментариев
71
Комментариев
67
Комментариев
60
Комментариев
55
Комментариев
52
Комментариев
50
Комментариев
45
Комментариев
44

Отправьте отзыв!
Отправьте отзыв!