Методы сжатия

Методы сжатия Методы сжатия, описываемые в оставшейся части главы, являются методами сжатия информации без потерь (lossless compression), т.е. вся информация сохраняется. Сжатие информации с потерями (lossy compression) позволяет достичь более высокой степени сжатия за счет отбрасывания некоторых данных. Примерами сжатия информации с потерями являются свертывание регистра, стемминг и исключение стоп-слов. Аналогично, модель векторного пространства (глава 6) и методы уменьшения размерности, такие как латентно-семантическое индексирование, позволяют создать компактное представление, по которому невозможно восстановить исходную коллекцию.2 Сжатие с потерей информации целесообразно, когда “потерянная” информация не используется системой поиска. Например, для веб-поиска характерны огромное количество документов, короткие запросы и пользователи, просматривающие лишь несколько первых страниц результата. Вследствие этого можно отбросить словопозиции для документов, расположенных в списке результатов слишком далеко. Таким образом, существуют сценарии поиска, в которых методы сжатия информации с потерями можно использовать без риска снижения эффективности.

Перед тем как описать методы сжатия словаря, оценим количество разных терминов М в коллекции. Иногда говорят, что языки имеют словарь определенного размера. Во втором издании словаря Oxford English Dictionary (OED) содержится более 600 тысяч С ’ов. Однако словари большинства крупных коллекций намного больше, чем словарь OED. Он не содержит фамилий большинства людей, географических названий, наименований продуктов или научных понятий, например названий генов. Эти имена необходимо включить в инвертированный индекс, чтобы пользователь мог их найти.

33.Сжатие словаря

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

Одежда для маленьких собак тут.

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

tel-icq