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

Question

производительность — лучший способ хранить, загружать и использовать инвертированный индекс в 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(), По запросу программа перебирает ключевые слова и оценивает документы.

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

Как сохранить инвертированный индекс 500 Мо, чтобы загрузить его во время поиска? В настоящее время я использую 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 секунд.
Я не знаю, если map достаточно эффективны для инвертированного индекса.
Для кластеризации документов я получаю все ключевые слова из каждого документа и перебираю эти ключевые слова, чтобы оценить одинаковые документы, но я бы хотел избежать повторного чтения каждого документа и использовать только этот инвертированный индекс. Но я думаю, что эта структура данных будет дорогостоящей.

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

2

c++data-structures inverted-index performance

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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

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

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

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

3