Eu tenho um subconjunto dos caminhos simples em um gráfico. O comprimento dos caminhos é delimitado por .
Qual é a maneira mais compacta (em termos de memória) de representar os caminhos de forma que nenhum outro caminho além dos selecionados seja representado?
Observe que eu quero usar essa representação em um algoritmo que irá percorrer esse subconjunto de caminhos repetidamente e que eu quero ser bastante rápido; portanto, por exemplo, não posso usar nenhum algoritmo de compactação padrão.
Uma representação que me veio à cabeça foi representá-las como um conjunto de árvores. No entanto, acho que reduzi-lo a um número ideal de árvores é difícil para o NP? Que outras representações seriam boas?
graphs
data-structures
Optar
fonte
fonte
Respostas:
Um Trie pode fazer o truque: http://en.wikipedia.org/wiki/Trie
Rotule cada extremidade do seu gráfico com uma letra. Em seguida, adicione as strings que representam os caminhos através do seu gráfico para o teste. Para cumprir o requisito de que "nenhum outro caminho além dos selecionados seja representado", você pode deixar todos os vértices da árvore em branco e rotular as arestas, exceto quando as arestas que vão da raiz ao vértice representam um dos seus caminhos. rotule o vértice com algo. Um bool, o número do caminho sob alguma ordem, etc.
Depois de criar seu teste, existem algoritmos para compactá-lo para uma representação ótima (ou quase ótima). (veja o artigo vinculado da Wikipedia.)
fonte
Talvez você deva dar uma olhada em estruturas de dados sucintas . São estruturas de dados que tentam armazenar informações no espaço próximo ao limite inferior da teoria da informação, preservando a capacidade de executar operações nelas.
Existem estruturas para árvores, dicionários etc. Não me lembro de nenhuma que faria exatamente o que você deseja, mas talvez alguma combinação ou modificação delas o ajudasse.
fonte
Dependendo da complexidade e do processamento pré / pós necessário para o seu algoritmo, talvez a opção mais simples seja essa. Você pode representá-los trivialmente como matrizes e salvá-los compactados em um HDF5. Esta biblioteca está equipada com alguns algoritmos de compactação rápidos, de modo que a leitura e gravação de dados compactados podem ser ainda mais rápidas que as não compactadas.
Aqui estão algumas parcelas:
Tempo de acesso sequencial por elemento para um EArray de 15 GB e tamanhos diferentes:
Velocidade de descompressão usando Blosc no PyTables:
E, se eles forem delimitados em comprimento, você poderá armazená-los em uma tabela e, portanto, provavelmente ganhar um pouco mais de espaço. E ao recuperá-los da memória, você já os possui de uma forma muito conveniente para aplicar seu algoritmo.
fonte