11 Часть I. Компоненты 14 Глава Компьютерная
жүктеу/скачать 4,29 Mb.
|
nikolaev is mitrenina ov lando tm red prikladnaia i kompiute
- Бұл бет үшін навигация:
- Индекс
- В идеальном мире
- Тем временем в реальности
Как ищем?Проблемы разработчика поисковой машины можно разделить на тех- нические и содержательные. Технические проблемы связаны прежде всего с масштабом задачи: в случае с интернетом это миллиарды документов, тысячи запросов в секунду, распределенные системы из тысяч компьюте- ров и т. д. Все это само по себе очень увлекательно и порождает массу тем для книг, статей и конференций. Но в этой главе мы рассмотрим содержательные проблемы. В основ- ном они вызваны тем, что документы и запросы написаны на естествен- ном языке. А естественный язык обладает разными неудобными для авто- матического анализа свойствами вроде избыточности и неоднозначности. Но если мы хотим найти для пользователя документы, соответствующие запросу, то необходимо проанализировать (в идеале — понять) и запрос, и документы. Здесь возникает техническая проблема, которую невозможно не упо- мянуть. Что должна делать машина, получившая поисковый запрос? Она должна просмотреть целиком каждый документ в коллекции и решить, подходит он или нет? Например, понять, содержит ли он все слова из за- проса? В принципе можно именно так сделать, но из-за размеров коллек- ции и неизбежно ограниченной скорости обработки данных это займет столько времени, что даже самый терпеливый пользователь заскучает и уйдет. Очевидно, нужно уметь выбирать документы, не читая их полно- стью. ИндексОдин удобный способ поиска хорошо известен. Представьте себе тол- стую сложную книгу, хотя бы такую, как эта. В конце нее наверняка будет алфавитный указатель использованных терминов. Такой указатель позво- ляет читателю быстро понять, на какой странице (почти что «в каком до- кументе») встречается тот или иной термин, что очень упрощает поиск. Ровно эта же идея лежит в основе инвертированного индекса (inverted index). Можно заранее один раз пройтись по каждому документу, выде- лить из него все слова и дописать номер этого документа1 к общему спи- ску всех слов. Результат будет выглядеть примерно так: 1 Для технических целей удобнее хранить не названия документов, а их номера, чтобы иметь дело с числами, а не с цепочками букв. При этом таблица «номер—название» хранится отдельно.
Если в качестве первого приближения считать, что для ответа на по- исковый запрос подходят документы, в которых содержатся все слова за- проса, то теперь нам не нужно перебирать всю коллекцию, а достаточно лишь найти в индексе слова запроса (которых обычно немного) и выбрать пересечение соответствующих списков документов. Разумно предположить, что, например, по запросу [глаголы]1 пользо- ватель хотел бы найти в том числе и документ, где упоминается «спряже- ние глаголов». Это, конечно, должно навести нас на мысль о морфологии. И действительно, в индексе обычно хранят уже нормализованные формы слов: вместо отдельных элементов для «глаголы», «глаголов» и «глагола- ми» — всего один индекс «глагол». В данном примере используется лем- матизация, хотя для некоторых языков, включая английский, эффективнее использовать стемминг. Такое уменьшение элементов за счет приведения близких слов к оди- наковой форме называют нормализацией (normalization). Иногда требу- ются и менее сложные способы нормализации, связанные, например, с регистром символов или со слитным/раздельным написанием слов. Ко- нечно, слова запроса тоже проходят те же этапы нормализации, прежде чем мы начинаем искать их в индексе. Я намеренно привел сейчас крайне упрощенное описание индекса. На самом деле его правая часть (называемая списком словопозиций, или posting list) устроена сложнее и содержит список не просто номеров доку- ментов, а довольно сложных структур, хранящих, например, следующую информацию: в каких конкретно местах документа встретилось слово (иногда по- лезно искать слова в нужном порядке или подряд); сколько всего раз оно там встретилось (частота слова вообще очень важна); в какой именно форме находилось слово в каждой позиции (это помо- гает искать, например, точные цитаты). 1 Будем придерживаться распространенной практики и заключать примеры запросов в квадратные скобки. В идеальном миреПредлагаю сейчас остановиться и попробовать представить, как дол- жен был бы выглядеть «идеально» устроенный поиск с точки зрения клас- сической компьютерной лингвистики. Итак, у нас есть текст документа. Мы пропускаем его через морфоло- гический анализатор, затем через синтаксический и получаем набор неко- торых графов — например, деревьев зависимостей, — соответствующих предложениям в документе. После этого к работе приступает семантиче- ский анализатор, который на основе этих структур строит некоторое се- мантическое представление. Остается только придумать, как построить индекс на основе таких представлений. Затем при поступлении поисково- го запроса мы с помощью тех же операций строим семантическое пред- ставление запроса, отправляем это представление в наш семантический индекс и, вероятно, с большой точностью находим то, что хотел пользова- тель. Нет каких-то фундаментальных причин считать, что такой подход не будет работать. Некоторые шаги в этом направлении делает компания IBM, создавшая специализированную вопросно-ответную систему по имени Watson. В 2011 году она прославилась тем, что победила лучших в США игроков в «Jeopardy!» (аналог отечественной интеллектуальной «Своей игры»). В последнее время эта система испытывается в области анализа медицинских данных. Тем временем в реальностиЕсли мы начнем разрабатывать полноценную поисковую машину по описанной выше схеме, то очень быстро столкнемся с весьма серьезными проблемами. Во-первых, нужен качественный синтактико-семантический анализа- тор, который более или менее правильно разберет любое предложение, в том числе верно обработает анафору, не откажется работать на безграмот- ном тексте из блога, опознает эллипсис, избежит комбинаторного взрыва на предложении длиной в абзац и т. д. Делать такой анализатор очень дол- го и дорого, хотя, по-видимому, и возможно, как показывает ABBYY Compreno [Анисимович и др. 2012]. Предположим, нам все же удалось как-то заполучить такой анализа- тор и придумать, как строить семантический индекс. Теперь заметим, что нам постоянно нужно индексировать терабайты документов, а синтакси- ческий и семантический анализ — очень трудоемкие операции с точки зрения количества вычислений. Даже без них текущее обновление поис- ковых индексов требует громадных ресурсов. Есть и содержательные проблемы. Тексты документов, как уже упо- миналось, разнородны и часто содержат ошибки, так что для их правиль- ной обработки требуется очень изощренный парсер. Но это полбеды, а беда в том, что в запросах все совсем не так, как в документах. Синтакси- са как такового нет, заглавные буквы никто не пишет, да и вообще, как правило, современный пользователь, в отличие от ученых из 1960-х, не очень заботится о точности и ясности формулировок. Скажем, под запро- сом [дорога владимир николаев] может иметься в виду как маршрут из города Владимира в город Николаев, так и какая-нибудь книга, песня или клип «Дорога» некоего Владимира Николаева. Или что-нибудь еще. Полу- чается, для запросов нужен какой-то совсем другой анализатор. Существует не вполне четкая, но распространенная классификация запросов: жүктеу/скачать 4,29 Mb. Достарыңызбен бөлісу:
|