Россия+7 (495) 960-65-87

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

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

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

Аннотация

Запросы в текстовые коллекции выполняются путем ранжирования документов в коллекции, пользователю предоставляются документы с наивысшей оценкой. Альтернативным поисковым методом является ранжирования пассажей (небольших фрагментов документа). Данный метод рассчитан улучшать эффективность выдачи и определять релевантность материала документов больших размеров. Однако метод ранжирования пассажей может значительно увеличить затраты на поиск. В данной работе будут рассмотрены альтернативные и разработаны новые способы оценки запросов. Экспериментально будет показано, что правильно выбранный способ поиска пассажей представляет собой конструктивное решение для ПК с ограниченным объемом памяти. Сравнив поиск пассажей с известными алгоритмами ранжирования документов, было определено, что новому алгоритму ранжирования пассажей \DO-TOS" необходима лишь часть источников.

Введение

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

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

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

Способ, который учитывает эти проблемы, называется «поиск по пассажам», где единицей поиска выступают блоки теста из накопленных документов. Пассажи могут основываться на логических компонентах документа, например, разделы, параграфы. Однако наиболее эффективной и надежной формой пассажей является определенная последовательность слов, встречающаяся в документе. В данной модели оценки запроса каждый документ рассматривается как большое количество пассажей, где каждый новый начинается с вхождения подходящего слова. Оценка запроса предполагает поиск в базе данных пассажа, наиболее релевантного запросу. Затем все документы, содержащие самые релевантные пассажи, выдаются пользователю, либо только пассажи с заголовком документа и информацией о его местонахождении в документе. Трудность использования метода пассажей в том, что для оценки запроса может понадобиться больше времени.

В данной работе, сначала рассматриваются базовые способы оценки запросов, включая document-ordered или DO processing, где инвертированные списки обрабатываются одновременно, term-ordered или TO processing, где каждый инвертированный список обрабатывается последовательно. А также skipping или TOS стратегии, предполагающие ограничение числа потенциальных документов, рассмотренных во время оценки запроса. Для ранжирования всего документа предыдущий анализ предполагает, что для ограниченного объема памяти DO оценка представляется более эффективной, чем TO. Используя MG прототип системы текстовой базы, экспериментально сравнили TO, TOS и DO. Результаты исследования показали, что для коротких запросов эффективнее DO, а не TO. Однако для других запросов предпочтительнее использовать способ DO, оценка запроса TO является более оперативной. Однако для ранжирования документов оба способа уступают способу оценки TOS.

В дальнейшем будет рассмотрено соответствие каждого способа оценки для поиска пассажей и предложены рекомендации по практическому поиску пассажей. На основе экспериментов, все способы будут оценены по степени результативности и степени экономичности. Результаты экспериментов докажут практическую полезность ранжирования пассажей для коротких запросов в больших коллекциях, оцененных в ограниченном объеме памяти за первые секунды. Для достаточной памяти, результативными представляются и TOS, и DO, для того, чтобы выполнить обычное поисковое задание – предоставить список из 10-20 документов, – объем памяти не должен быть большим. Также будет доказано, что для ранжирования всего документа и для длинных запросов затраты на оценку запроса способом DO увеличиваются быстрее, чем способом TOS. Для коротких запросов способ DO считается более эффективным. Мы рекомендуем использовать комбинированный метод DO-TOS, где DO processing используется для определения набора похожих документов, основанных на редких терминах запросов, а TOS processing упорядочивает заново данный набор документов.

Текстовый поиск

В поисковых системах документы ранжируются по функции эвристического подобия, определяющей степень релевантности документа запросу. Оценка осуществляется при помощи вычисления релевантности каждого документа запросу, после чего выдается k документов с наивысшей оценкой подобия. Было предложено много функций подобия, наиболее распространенной и эффективной является косинусная оценка:

C(q; d) = Pt2q^d(wq;t _ wd;t)
Wd
где q - запрос, d - документ,
Wd = pX
t2d
w2
d;t ;
wd;t = loge(fd;t + 1) ;
wq;t = loge(fq;t + 1) _ loge(N=ft + 1)

Показатель fx;t – это число вхождений термина t в x (запрос или документ в запросе); присутствует N документов; ft- число уникальных документов, содержащих t; уравнение (N=ft + 1) – «обратная частота документов», редкость нахождения t в коллекции. Сравнив с косинусными формулировками, где были сделаны такие улучшения как стандартизация длины сходных документов, было обнаружено, что в тестовых данных, представленных в данной работе, вышеуказанная формулировка достигает той же результативности.

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

Оценка подобия может быть улучшена несколькими способами. Одним из них является использование фраз наряду с отдельными терминами. Например, вместо поиска документов с терминами «нефть» и «скважина», система представит документы, где данные термины сопредельны. Таким образом, документы, где термины в запросе расположены близко друг к другу, представляются более релевантными.

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

Поиск пассажей

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

Использовать пассажи можно по-разному. Первый способ - предоставление только полных пассажей, что обеспечивает четкий ответ. Поиск пассажей может, например, стать основанием поиска информации в виде «вопросов-ответов». Следующий способ – использование пассажей как посредников документов, таким образом, документ оценивается в соответствии с оценкой его пассажей. Документ выбирается согласно запросу, а пассажи в нем расцениваются как ответы. На данный способ не влияют такие преимущества поиска пассажей, как механизм оценки запроса.

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

Для FR подраздела TREC (Text REtrieval Conference), которая состоит из документов различной длины (объема), было продемонстрировано, что использование совпадающих пассажей из 150-300 слов значительно улучшают эффективность. Для TREC были отмечены менее значительные, но последовательные улучшения. Как поисковый механизм первого уровня, данные результаты показывают, что пассажи являются лучшим способом оценки подобия целого документа. Доказано, что наивысшая эффективность достигается, если пассажи могут быть выбраны из любой части документа, если нет, то с интервалами в 25 слов, тогда ухудшения незначительные.

Подобный результат получается и для небольших запросов, если использовать способ разметки. Кларк (Clarke) использует булевые запросы для определения сегментов документов, которые удовлетворяют булевым условиям. Подобие документов основывается на самых коротких сегментах, подходящих булевому запросу, оценивающих сегменты текста по их абсолютной длине. Никаких статистических данных коллекции не требуется, однако на начальном этапе данного исследования был необходим ручной труд для введения булевых запросов. Все термины запроса обрабатывались эквивалентно. Способ, не предполагающий использование ручного труда, был представлен в 1998 на конференции TREC. Запросы на естественном языке использовались для генерации набора булевых запросов, выстроенных по уменьшению числа терминов: первый запрос – все слова, второй – все кроме слова с наивысшим IDF и т.д. Пока данный способ представляется эффективным для коротких запросов, и находится в стадии разработки.

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

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

Перевод под редакцией Анны Макаровой.

(Нет голосов)
Читайте нас в Telegram - digital_bar

Есть о чем рассказать? Тогда присылайте свои материалы Даше Калинской


Новые 
Новые
Лучшие
Старые
Сообщество
Подписаться 
Подписаться на дискуссию:
E-mail:
ОК
Вы подписаны на комментарии
Ошибка. Пожалуйста, попробуйте ещё раз.
Отправить отзыв
  • Анастасия Филатова
    0
    комментариев
    0
    читателей
    Анастасия Филатова
    больше года назад
    Из всей статьи я так и не поняла, что же такое пассаж?
    -
    0
    +
    Ответить
  • Денис Щеглов
    7
    комментариев
    0
    читателей
    Денис Щеглов
    больше года назад

    Пассаж представляет собой сообщение, которое отделено от других различными разделителями (.,!,? и т.д, теги <p>). В том случае, если разделителей нет, то пассаж это 63-64 слова.
    -
    0
    +
    Ответить
ПОПУЛЯРНЫЕ ОБСУЖДЕНИЯ НА SEONEWS
Рейтинг Известности 2018: старт народного голосования
Михаил Р
1
комментарий
0
читателей
Полный профиль
Михаил Р - 1. Demis 2. кокс 3. Ашманов 4. Скобеев 5. Digital Strategy
Сколько ссылок помогут продвинуть молодой сайт
Павел Андрейчук
33
комментария
0
читателей
Полный профиль
Павел Андрейчук - Дело в том, что вряд ли в ваших платных "качественных" кейсах найдётся хоть пару % действительно новой и полезной информации которой бы не было на общедоступных источниках.
Рейтинг Известности 2018: второй этап народного голосования
Константин Сокол
3
комментария
0
читателей
Полный профиль
Константин Сокол - Кто был ответственный за дизайн таблицы голосования? Копирайтер?
Сайт на WordPress: за и против
Мира Смурков
1
комментарий
0
читателей
Полный профиль
Мира Смурков - Людмила, я согласен с большинством комментаторов. Вы хоть один полноценный магазин сделали на этих движках? Woocommerce это система с супер возможностями. И к ней есть дополнительные модули, с функционалом, который вряд ли появиться на Битрикс. А самому это программировать - сотни тысяч рублей на разработку. А приведя в пример сложности с robots.txt и Sitemap вы ставите под вопрос вашу компетенцию в понимании Интернет-бизнеса и веб-разработки в целом. Во-первых это такие мелочи, а во-вторых это все делается на вордпресса за 2 минуты, и опять же с возможностями многократно превышающими Битрикс.
Обзор популярных CMS: плюсы и минусы
Гость
1
комментарий
0
читателей
Полный профиль
Гость - как по мне joomla! самая удобная и гибкая система из всех современных (я про wp раньше так думал, пока меня в Extrit не убедили в обратном). Раньше всегда оставался на техподдержке, потому что сам заполнять не мог, а теперь делаю это сам, потому что админка простая как палка. + на других цмсках при просьбе что-то добавить мне либо цену загибали овер 100500 либо говорили - нереально, делай новый сайт. А на joomla норм
Google обошел Яндекс по популярности в России в 2018 году: исследование SEO Auditor
Рамблер
1
комментарий
0
читателей
Полный профиль
Рамблер - Вот вроде отечественный - это сказано верно.. «Я́ндекс» — российская транснациональная компания, зарегистрированная в Нидерландах. Так говорится в Википедии. И с хрена ли ОТЕЧЕСТВЕННЫЙ поисковик зарегистрирован в Европе? И где платится основная часть налогов? Ну-ууу, точно не в России. И если запахнет жаренным, то был Яндекс и нет Яндекса!
8 методик в SEO, от которых давно пора отказаться
Евгений Сметанин
11
комментариев
0
читателей
Полный профиль
Евгений Сметанин - Факторов вообще очень много, согласитесь, вы будете использовать максимальное их количество, особенно, если в ТОПе засели агрегаторы с сумасшедшими ПФ. В таких случаях, вхождение ключа в домен для маленького профильного сайта, сыграет свою положительную роль. Конечно же, если контент на страницах хорошего качества. У меня есть несколько успешных кейсов на эту тему. На сайте продают несколько видов товаров, а выстреливает в ТОП тот, название которого присутствует в доменном имени. Как корабль назовешь, так он и поплывет, верно?))
Инструкция: настраиваем цели Яндекс.Метрики через Google Tag Manager
Roman Gorkunenko
1
комментарий
0
читателей
Полный профиль
Roman Gorkunenko - Здравствуйте. Подскажите, пожалуйста, можно с айпи метрики вытащить среднюю стоимость клика по утм меткам? В метрике есть такой шаблон tags_u_t_m, но он не совместим с меткой директа, у них разные префиксы.
Аудит структуры интернет-магазина мебели от «Ашманов и партнеры»
Дмитрий
11
комментариев
0
читателей
Полный профиль
Дмитрий - Сергей, а вы допускаете, что вся ваша жизнь - seo-миф?
Идеальный каталог для продвижения сайта: структура и функционал
Татьяна Ягутьева
6
комментариев
0
читателей
Полный профиль
Татьяна Ягутьева - Уважаемый Денис, сделайте сами напишите свою статью. Посоветуйте другую универсальную CMS, желательно идеальную по всем параметрам. Битрикс очень сильно зависит от разработчика. Если у него прямые руки - бардака не будет. А вообще, конечно, холивар на тему CMS/конструкторов/фреймворков - наверное, вечный. Давайте не будем начинать :)
ТОП КОММЕНТАТОРОВ
Комментариев
910
Комментариев
834
Комментариев
554
Комментариев
540
Комментариев
483
Комментариев
373
Комментариев
345
Комментариев
262
Комментариев
246
Комментариев
171
Комментариев
156
Комментариев
137
Комментариев
121
Комментариев
100
Комментариев
97
Комментариев
97
Комментариев
96
Комментариев
80
Комментариев
74
Комментариев
67
Комментариев
60
Комментариев
59
Комментариев
57
Комментариев
56
Комментариев
55

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