Индекс поиска в памяти для приложения занимает слишком много памяти - какие-либо предложения?

Question

В нашем настольном приложении мы реализовали простую поисковую систему, использующую инвертированный индекс .

К сожалению, некоторые из наборов данных наших пользователей могут стать очень большими, например, занимает ~ 1 ГБ памяти до создания инвертированного индекса. Инвертированный индекс сам по себе занимает много памяти, почти столько же, сколько индексируемые данные (еще 1 ГБ ОЗУ).

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

Наш инвертированный индекс хранится как:

Dictionary<string, List<ApplicationObject>>

И это создается во время загрузки данных, когда каждый объект обрабатывается таким образом, что строка ключа applicationObject и слова описания сохраняются в инвертированном индексе.

Итак, мой вопрос: возможно ли более эффективно хранить индекс поиска в пространстве? Возможно, нужно использовать другую структуру или стратегию? В качестве альтернативы возможно ли создать вид CompressedDictionary? Поскольку он хранит много строк, я ожидал бы, что он будет очень сжимаемым.

Answer 1

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

Я предлагаю вам примерно узнать, какова частота - сколько из ваших словарных статей имеют списки из одного элемента, сколько из двух списков элементов и т. Д. Вы можете потенциально хранить несколько отдельных словарей - один для "У меня есть только один элемент »(прямое сопоставление), затем« у меня есть два элемента »(сопоставление со структурой Pair с двумя ссылками в) и т. д. до тех пор, пока он не станет глупым - вполне возможно, примерно с 3 записями - в этот момент вы вернетесь к обычным спискам , Инкапсулируйте весь лот за простым интерфейсом (добавьте записи / извлекайте записи). Таким образом у вас будет гораздо меньше потраченного впустую пространства (в основном пустые буферы, счетчики и т. Д.).

Если ничего из этого не имеет особого смысла, дайте мне знать, и я постараюсь придумать какой-нибудь код.

Answer 2

Я вижу несколько решений:

1. Если у вас есть объекты ApplicationObject в массиве, храните только индекс - может быть меньше.
2. Вы можете использовать немного C ++ / CLI для хранения словаря, используя UTF-8.
3. Не беспокойтесь о хранении всех различных строк, используйте Trie

Answer 3

Если это будет 1 ГБ ... поместите его на диск. Используйте что-то вроде Беркли DB. Это все еще будет очень быстро.

Вот проект с интерфейсом .net:

http://sourceforge.net/projects/libdb-dotnet

Answer 4

Как насчет использования Memory Mapped File Win32 API для прозрачного восстановления структуры вашей памяти?

http://www.eggheadcafe.com/articles/20050116.asp имеет PInvokes, необходимые для его включения.

Answer 5

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

В сценарии сопоставления файлов. Если вы откроете Reflector и отразите класс Dictionary, вы увидите, что он состоит из сегментов. Вероятно, вы можете использовать каждый из этих блоков в качестве страницы и физического файла (таким образом, вставка выполняется быстрее). Затем вы можете также свободно удалять значения, просто вставляя значение «элемент x удалено» в файл, и время от времени очищайте файл.

Кстати, в контейнерах хранятся значения с одинаковыми хэшами. Очень важно, чтобы ваши значения, которые вы храните, переопределяли метод GetHashCode () (и компилятор предупредит вас о Equals (), так что переопределяйте и это). Если вы сделаете это, вы значительно увеличите скорость поиска.

Answer 6

Я согласен с bobwienholt, но если вы индексируете наборы данных, я предполагаю, что они откуда-то взяты из базы данных. Имеет ли смысл просто искать это с помощью поисковой системы, такой как DTSearch или Lucene.net ?

Answer 7

Индекс только добавлен или вы тоже удаляете ключи от него?