Как сжать многие строки в структуре данных?

Question

У меня есть коллекция документов XML объемом 500 ГБ, которые я индексирую. В настоящее время я могу только индексировать 6 ГБ этой коллекции с 32 ГБ ОЗУ.

Моя индексная структура представляет собой HashMap<String, PatriciaTrie<String, Integer>>, где первая строка представляет собой термин, а вторая строка имеет формат filepath+XPath с конечным целым числом, представляющим количество вхождений.

Я использовал trie для сокращения общего префикса и потому, что мне нужны отсортированные данные. Это немного помогло с компрессией, но этого было недостаточно.

Общая коллекция строк filepath+XPath находится между 1 ТБ и 4 ТБ в пределах этой структуры данных. Мне нужно иметь возможность полностью сжимать эту структуру данных в памяти. Целевая машина имеет 256 ГБ оперативной памяти и 16 ядер процессора. Меньше памяти имеет несколько дополнительных преимуществ (например, сокращение времени холодного запуска). Индексное время не такое уж большое дело.

XPaths представляют около 250 общих типов узлов.

Подход, над которым я сейчас работаю, построит таблицу Хаффмана для каждой серии из 2 тегов на основе тегов, которые могут произойти следующим образом. Часто это сокращает параметры до примерно 4 или 5, что позволяет кодировать XPath в гораздо более короткую битовую строку, которая затем может быть закодирована как байты.

Строки, как правило, 40-600 байт (UTF-8), и я считаю, что это должно уменьшить все после префикса пути к файлу (первые 40 символов, которые сжимаются trie) до max 12 байт (самый глубокий точка на дереве составляет около 12 узлов, а каждый узел в худшем случае представляет 1 символ) для структуры и 12 байтов для индексов (переменная байтовая кодировка с очень небольшим количеством элементов, содержащих индексы выше 256), производя строки, которые обычно в диапазоне 40-64 байта.

Я думаю, что это хороший подход, но я думаю, что мне что-то не хватает.

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

Answer 1

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

Скажем, у вас 200 000 уникальных терминов в 200 различных файлах. Таким образом, каждый уникальный термин переносит вес по меньшей мере одного пути к файлу или 40 байтов. И это прежде, чем вы начнете индексировать что-нибудь.

Вы должны иметь возможность сжать эти данные в таблицу из строк filepath+Xpath и список терминов, каждый из которых содержит ссылки на записи в этой таблице.Так, например, вы можете иметь:

Путь таблицы:

index Path 
    1 file+xpath1 
    2 file+xpath2 
    3 file+xpath3 
    ... 
999 file+xpath999 

Условия

term references 
foo 1, 19, 27, 33, 297 
bar 99, 864, 865 
... 

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

Файлы

1 file1.xml 
    2 file2.xml 
... 
999 file999.xml 

И тогда ваши пути станут:

1 1,xpathA 
    2 1,xpathB 
    3 2,xpathQ 
    ... 

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

Слова

1 the 
2 quick 
3 brown 
4 fox 

Дорожки

index path 
0  1(index of file),2(quick),4(fox),-1(terminator) 
4  3(index of file),3(brown),-1(terminator) 
7  etc . . . 

В таблице трактов просто большой массив, который будет выглядеть следующим образом:

1,2,4,-1,3,3,-1,... 

Это минимизирует стоимость хранения данных, поскольку нет строки хранится не один раз. Все, что у вас есть, это строковые таблицы и ссылки на эти строки. Объем занимаемой площади будет примерно таким:

Combined length of all file names 
Combined length of all path segment terms 
(number of paths) * (average path length) * (size of integer index) 
(number of terms) * (average number of references per term) * (size of integer index) 

Построение этого в памяти возможно. Трудно сказать, не зная, сколько у вас индивидуальных терминов. Вам нужны словари для имен файлов, путей и отдельных сегментов пути, если вы используете список слов. Но все это можно сделать за один проход, если у вас есть память.

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

term, path reference 
term, path reference 
... 

Используйте внешнюю программу сортировки для сортировки по срокам, а затем пройти и объединить дубликаты. Когда вы закончите, вы получите файл, который содержит:

File names table 
Path segments table 
Paths 
terms 

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

Я использовал что-то вроде этого несколько лет назад, и это сработало достаточно хорошо. Вы должны иметь возможность написать программу, которая анализирует ваши данные, чтобы придумать цифры (уникальные пути, количество имен файлов, среднее число ссылок за семестр и т. Д.). Оттуда вы можете легко определить, будет ли использование этой техники работать для вас.