У меня есть подмножество простых путей в графе. Длина путей ограничена .
Каким самым компактным способом (с точки зрения памяти) я могу представить пути так, чтобы не были представлены никакие другие пути, кроме выбранных?
Обратите внимание, что я хочу использовать это представление в алгоритме, который будет перебирать этот набор путей снова и снова, и я хочу быть достаточно быстрым, поэтому, например, я не могу использовать какие-либо стандартные алгоритмы сжатия.
Одно из представлений, которое мне пришло в голову, представляло их как набор деревьев. Я предполагаю, однако, что подвести его к оптимальному количеству деревьев сложно в NP? Какие еще представления будут хорошими?
graphs
data-structures
выбирать
источник
источник
Ответы:
Три может сделать свое дело: http://en.wikipedia.org/wiki/Trie
Пометьте каждый край вашего графика буквой. Затем добавьте строки, которые представляют пути через ваш график в Trie. Чтобы выполнить требование, что «никакие другие пути, кроме выбранных, не представлены», вы можете оставить все вершины дерева пустыми и пометить ребра, кроме случаев, когда ребра, ведущие от корня к вершине, представляют один из ваших путей, а затем пометить вершину чем-то. A bool, номер пути при некотором порядке и т. Д.
После того, как вы построили свой файл, есть алгоритмы его сжатия до оптимального (или почти оптимального) представления. (см. связанную статью Wikipedia.)
источник
Возможно, вам стоит взглянуть на сжатые структуры данных . Это структуры данных, которые пытаются хранить информацию в пространстве, близком к теоретико-информационной нижней границе, сохраняя при этом способность выполнять над ними операции.
Существуют такие структуры для деревьев, словарей и т. Д. Я не помню ни одной, которая бы делала именно то, что вы хотите, но, возможно, некоторая их комбинация или модификация помогут вам.
источник
В зависимости от сложности и предварительной / последующей обработки, требуемой для вашего алгоритма, возможно, самый простой вариант - это способ. Вы можете тривиально представить их как массивы и сохранить их в сжатом виде в формате HDF5. Эта библиотека оснащена некоторыми быстрыми алгоритмами сжатия, так что чтение и запись сжатых данных может быть даже быстрее, чем без сжатия.
Вот несколько сюжетов:
Время последовательного доступа на элемент для массива EAR на 15 ГБ и различных размеров фрагментов:
Скорость распаковки с использованием Blosc на PyTables:
И, если они ограничены в длине, вы можете хранить их в таблице, и, таким образом, возможно, получить немного больше места. И когда вы извлекаете их из памяти, они уже есть в очень удобной форме для применения вашего алгоритма.
источник