Пространственно-эффективная структура в памяти для сортированного текста, поддерживающего поиск префикса
У меня проблема: мне нужен пространственно-эффективный поиск данных файловой системы на основе префикса пути к файлу. Другими словами, поиск в отсортированном тексте. Вы говорите, что используете три, и я думал то же самое. Проблема в том, что попытки не достаточно эффективны в пространстве, не без других трюков.
У меня есть достаточное количество данных:
- около 450M в текстовом формате Unix-формата на диске
- около 8 миллионов строк
- gzip по умолчанию сжимает до 31M
- bzip2 по умолчанию сжимает до 21M
Я не хочу есть где-нибудь около 450M в памяти. На этом этапе я был бы счастлив использовать где-то около 100 М, так как там много избыточности в виде префиксов.
Я использую С# для этого задания, и для простой реализации trie по-прежнему потребуется один лист node для каждой строки в файле. Учитывая, что для каждого листа node потребуется некоторая ссылка на последний фрагмент текста (32 бита, скажем, индекс в массив строковых данных для минимизации дублирования строк), а накладные расходы CLR - 8 байтов (проверено с использованием windbg/SOS), Я буду тратить > 96 000 000 байт на структурные издержки без текстового хранения.
Посмотрим на некоторые статистические атрибуты данных. Когда набивается в trie:
- всего уникальных "кусков" текста около 1,1 миллиона.
- общее количество уникальных кусков около 16 М на диске в текстовом файле
- средняя длина блока составляет 5,5 символов, max 136
- если не учитывать дубликаты, около 52 миллионов символов в кусках
- Внутренние три-узлы в среднем составляют около 6,5 детей с макс. 44
- около 1,8 м внутренних узлов.
Превышение скорости создания листьев составляет около 15%, избыточное внутреннее создание node составляет 22% - избыточное создание, я имею в виду листья и внутренние узлы, созданные во время построения trie, но не в финальном trie как доля от конечного числа узлов каждого типа.
Здесь представлен анализ кучи из SOS, указывающий, где используется большая часть памяти:
[MT ]--[Count]----[ Size]-[Class ]
03563150 11 1584 System.Collections.Hashtable+bucket[]
03561630 24 4636 System.Char[]
03563470 8 6000 System.Byte[]
00193558 425 74788 Free
00984ac8 14457 462624 MiniList`1+<GetEnumerator>d__0[[StringTrie+Node]]
03562b9c 6 11573372 System.Int32[]
*009835a0 1456066 23297056 StringTrie+InteriorNode
035576dc 1 46292000 Dictionary`2+Entry[[String],[Int32]][]
*035341d0 1456085 69730164 System.Object[]
*03560a00 1747257 80435032 System.String
*00983a54 8052746 96632952 StringTrie+LeafNode
Dictionary<string,int> используется для сопоставления строковых фрагментов индексов в List<string> и может быть отброшен после построения trie, хотя GC, похоже, не удаляет его (было сделано несколько явных коллекций до этого дамп) - !gcroot в SOS не указывает никаких корней, но я ожидаю, что позднее GC освободит его.
MiniList<T> является заменой для List<T> с использованием точности (то есть линейного роста, производительности O(n^2)) T[], чтобы избежать потери пространства; это тип значения и используется InteriorNode для отслеживания дочерних элементов. Этот T[] добавляется в кучу System.Object[].
Итак, если я суммирую "интересные" элементы (помеченные *), я получаю около 270 М, что лучше, чем сырой текст на диске, но все еще недостаточно близко к моей цели. Я понял, что накладные расходы .NET слишком много, и создал новое "тонкое" trie, используя только массивы типа значений для хранения данных:
class SlimTrie
{
byte[] _stringData; // UTF8-encoded, 7-bit-encoded-length prefixed string data
// indexed by _interiorChildIndex[n].._interiorChildIndex[n]+_interiorChildCount[n]
// Indexes interior_node_index if negative (bitwise complement),
// leaf_node_group if positive.
int[] _interiorChildren;
// The interior_node_index group - all arrays use same index.
byte[] _interiorChildCount;
int[] _interiorChildIndex; // indexes _interiorChildren
int[] _interiorChunk; // indexes _stringData
// The leaf_node_index group.
int[] _leafNodes; // indexes _stringData
// ...
}
Эта структура уменьшила объем данных до 139M и по-прежнему является эффективно проходящим trie для операций только для чтения. И поскольку это так просто, я могу тривиально сохранить его на диск и восстановить его, чтобы избежать затрат на воссоздание trie каждый раз.
Итак, любые предложения для более эффективных структур для поиска префикса, чем trie? Альтернативные подходы, которые я должен рассмотреть?
Ответы
Ответ 1
Поскольку всего 1,1 миллиона кусков, вы можете индексировать кусок, используя 24 бита вместо 32 бит и экономя там место.
Вы также можете сжать куски. Возможно, кодирование Хаффмана - хороший выбор. Я также хотел бы попробовать следующую стратегию: вместо использования символа в качестве символа для кодирования вы должны кодировать переходы символов. Поэтому вместо того, чтобы смотреть на вероятность появления символа, посмотрите на вероятность перехода в цепочке Markov, где состояние является текущим символом.
Ответ 2
Вы можете найти научную статью, связанную с вашей проблемой здесь (цитирование авторов: "Эксперименты показывают, что наш индекс поддерживает быстрые запросы в пределах занимаемая площадь, близкая к той, которая достигается сжатием строкового словаря через gzip, bzip или ppmdi". - но, к сожалению, бумага является только оплатой). Я не уверен, насколько сложно реализовать эти идеи. Авторы этой статьи веб-сайт, где вы можете найти также реализации (в разделе "Коллекция индексов" ) различных сжатых алгоритмов индекса.
Если вы хотите продолжить свой подход, не забудьте проверить веб-сайты о деревья бит-бит и Дерево Radix.
Ответ 3
Нестандартная идея: вместо трюма хеш-таблицы. У вас в памяти будет только хэш и строковые данные, возможно сжатые.
Или вы можете позволить себе читать одну страницу? Только хеш и позиция файла в памяти, извлекают "страницу" с линиями, соответствующими этому хешу, предположительно небольшому числу упорядоченных строк, поэтому очень быстро можно искать в случае столкновений.
