Компактная коллекция для строк с общими префиксами - реализация Java

Question

Мне нужно хранить миллионы строк с общими префиксами (они не соответствуют путям файловой системы) в структуре типа Set в памяти и запрашивать коллекцию, чтобы узнать, существует ли путь.

например

/path
/path/1
/path/2
/path/1/a
/path/1/b

Я хочу сохранить их максимально эффективно (они будут в памяти), учитывая, что будет много общих префиксов для всех задействованных строк, будет ли Trie разумным кандидатом?

Я ищу рекомендацию по реализации подходящей структуры данных в Java.

Answer 1

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

см. Также ...

http://code.google.com/p/trie/

http://code.google.com/p/radixtree/

Answer 2

Это похоже на хорошую реализацию кандидата: https://github.com/rkapsi/patricia-trie

Answer 3

Давайте рассмотрим компромиссы перед любыми предложениями.

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

Как долго эти пути?Вы показали пример с очень короткими путями, поэтому мы ищем около ста мегабайт для хранения этих миллионов путей.У меня нет ссылки на максимальную длину пути, но 256 символов запоминаются.Таким образом, ваши пути займут максимум 512 Мб памяти.У вас так много памяти?

Насколько равномерно распределены пути?Другими словами, соблюдаете ли вы правило 80:20, когда 80% путей находятся в 20% каталогов?Причина, по которой я спрашиваю, состоит в том, что структуре три требует некоторой формы индекса между уровнями.Если у вас много каталогов с несколькими путями под ними, у вас будет много накладных расходов для поддержки дерева.

Рекомендации: если бы у меня было достаточно памяти, я бы использовалHashSet<String> и покончим с этим.

Если у меня не было много памяти и структуры каталогов, которая следовала правилу 80:20 (или, скорее, 95: 5), я 'Я думаю о HashMap<String,Set<String>>.Ключом этой карты будет самая длинная строка начального пути с «разумным» количеством дубликатов, а значениями будут оставшиеся строки.Вы будете исследовать эту карту с постепенно сокращающимися ведущими компонентами, пока не найдете совпадение, а затем исследовать набор для остатка.

Это оставляет открытым вопрос о "разумном" дублировании.Это объем дублирования, при котором издержки двухэлементной структуры данных преодолеваются за счет сокращения дублирования.Например, /usr/bin/ может быть допустимым (потому что он содержит тысячи файлов и вы сохраняете 9 символов или 18 байтов от каждого), но /usr/local/bin/, вероятно, не будет (по крайней мере, в моей системе, он содержит только один файл).

Answer 4

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

Конечно, достаточно просто проверить это, сравнив структуры данных Tries, упомянутые выше.

Answer 5

Что бы я использовал:

1. многоуровневая карта, которая напоминает структуру каталогов.
2. Сбалансированное дерево с отдельными символами в качестве ключей и другими деревьями в качестве значений.

Answer 6

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

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

Я хотел бы убедиться, что вам действительно нужно это сделать, поскольку вы можете хранить миллион записей в JVM довольно удобно. ;)

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