Лучший способ хранить, загружать и использовать инвертированный индекс в C++ (~ 500 мес.)

Я разрабатываю крошечную поисковую систему, используя TF-IDF и косинусное сходство. Когда страницы добавляются, я строю инвертированный индекс, чтобы сохранить частоту слов на разных страницах. Я удаляю стоп-слова и более распространенные слова, а также множественное число/глагол/и т. д. сдержаны.

Мой перевернутый индекс выглядит так:

map< string, map<int, float> > index

[
    word_a => [ id_doc=>frequency, id_doc2=>frequency2, ... ],
    word_b => [ id_doc->frequency, id_doc2=>frequency2, ... ],
    ...
]

С этой структурой данных я могу получить вес idf с помощью word_a.size(). Получив запрос, программа перебирает ключевые слова и оценивает документы.

Я плохо знаю структуры данных, и мои вопросы:

  1. Как сохранить инвертированный индекс 500 Mo, чтобы загрузить его во время поиска? В настоящее время я использую boost для сериализации индекса:

    ofstream ofs_index("index.sr", ios::binary);
boost::archive::bynary_oarchive oa(ofs_index);
oa << index;

    И затем я загружаю его во время поиска:

    ifstream ifs_index("index.sr", ios::binary);
boost::archive::bynary_iarchive ia(ifs_index);
ia >> index;

    Но он очень медленный, для загрузки требуется около 10 секунд.

  2. Я не знаю, достаточно ли map эффективны для инвертированного индекса.

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

Спасибо заранее за любую помощь!


c++ performance data-structures inverted-index
person Pwoet    schedule 23.03.2014    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

Если вы уверены, что ваши данные поместятся в памяти вашего компьютера, вы можете попытаться оптимизировать структуру на основе карты, которую вы используете сейчас. Хранение ваших данных на карте должно обеспечить довольно быстрый доступ, но всегда будут некоторые начальные накладные расходы, когда вы загружаете данные с диска в память. Кроме того, если вы используете только небольшую часть индекса, этот подход может быть довольно расточительным, поскольку вы всегда читаете и записываете весь индекс и сохраняете его в памяти.

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

  • map реализован в виде дерева (обычно черно-красное дерево). Во многих случаях hash_map может дать вам лучшую производительность, а также лучшее использование памяти (например, меньше выделений и меньше фрагментации).
  • Попробуйте уменьшить размер данных — меньше данных означает, что их будет быстрее считывать с диска, потенциально будет меньше выделяемой памяти, а иногда и лучше производительность в памяти из-за лучшей локальности. Вы можете, например, считать, что вы используете float для хранения частоты, но, возможно, вы могли бы хранить только количество вхождений как unsigned short в значениях карты, а в отдельной карте хранить количество всех слов для каждого документа (также как короткий ). Используя два числа, вы можете пересчитать частоту, но использовать меньше места на диске при сохранении данных на диск, что может привести к ускорению загрузки.
  • Ваша карта имеет довольно много записей, и иногда использование настраиваемых распределителей памяти помогает повысить производительность в таком случае.

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

person Michał Kosmulski    schedule 23.03.2014
comment
Спасибо за ваш ответ, мне удалось резко уменьшить размер индекса с помощью unsigned short int вместо float для частот. - person Pwoet; 30.03.2014