У меня проблема: мне нужен поиск файловой системы с эффективным использованием пространства на основе префикса пути к файлу. Префикс поиска отсортированного текста, другими словами. Поговори, скажи мне, и я подумал о том же. Проблема в том, что попытки недостаточно эффективны, не без других уловок.
У меня достаточно данных:
- около 450M в простом текстовом листинге Unix-формата на диске
- около 8 миллионов строк
- GZIP по умолчанию сжимает до 31M
- bzip2 по умолчанию сжимает до 21M
Я не хочу есть где-то близко к 450M в памяти. На этом этапе я был бы рад использовать где-то около 100M, поскольку существует множество избыточностей в виде префиксов.
Я использую C # для этой работы, и для простой реализации дерева все равно потребуется один листовой узел для каждой строки в файле. Учитывая, что каждому листовому узлу потребуется какая-то ссылка на последний фрагмент текста (32 бита, скажем, индекс в массив строковых данных, чтобы минимизировать дублирование строки), а служебные данные объекта CLR составляют 8 байтов (проверено с помощью windbg / SOS) , Я буду тратить> 96 000 000 байтов на структурные издержки без сохранения текста вообще.
Давайте посмотрим на некоторые статистические атрибуты данных. При наполнении деревом:
- всего уникальных "кусков" текста около 1,1 млн.
- Всего уникальных фрагментов около 16M на диске в текстовом файле
- средняя длина фрагмента составляет 5,5 символов, макс. 136
- без учета дубликатов, всего около 52 миллионов символов в кусках
- Внутренние узлы Trie в среднем около 6,5 детей с макс. 44
- около 1,8 м внутренних узлов.
Превышение скорости создания листа составляет около 15%, избыточное создание внутреннего узла составляет 22% - под избыточным созданием я подразумеваю листья и внутренние узлы, созданные во время построения дерева, но не в конечном дереве как пропорцию от конечного числа узлов каждого типа.
Вот анализ кучи из 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, похоже, не удаляет его (пара явных коллекций была сделана до этого dump) - !gcroot в SOS не указывает никаких корней, но я ожидаю, что более поздний GC освободит его.
MiniList<T> является заменой List<T> с использованием точного размера (то есть линейного роста, O(n^2) производительности сложения) T[] во избежание потери пространства; это тип значения и используется InteriorNode для отслеживания детей. Это T[] добавляется в стопку System.Object[].
Итак, если я суммирую «интересные» элементы (помеченные *), я получу около 270M, что лучше, чем необработанный текст на диске, но все еще не достаточно близко к моей цели. Я подумал, что издержки объекта .NET были слишком большими, и создал новый «тонкий» три, используя только массивы типа значения для хранения данных:
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
// ...
}
Эта структура сократила объем данных до 139 МБ и до сих пор является эффективно проходимым механизмом для операций только для чтения. А поскольку это так просто, я могу легко сохранить его на диск и восстановить, чтобы избежать затрат на повторное создание дерева каждый раз.
Итак, есть ли предложения по более эффективным структурам для поиска префиксов, чем trie? Альтернативные подходы, которые я должен рассмотреть?