12 papers · ranked by Valyu relevance
Benjamin Paaßen, Irena Koprinska, Kalina Yacef
Tree data occurs in many forms, such as computer programs, chemical molecules, or natural language. Unfortunately, the non-vectorial and discrete nature of trees makes it challenging to construct functions with tree-formed output, complicating tasks such as optimization or time series prediction. Autoencoders address…
Mahdi Amani, Abbas Nowzari-Dalini
We study the problem of generating, ranking and unranking of unlabeled ordered trees whose nodes have maximum degree of ∆. This class of trees represents a generalization of chemical trees. A chemical tree is an unlabeled tree in which no node has degree greater than 4. By allowing up to ∆ children for each node of…
Harry Richman, Cheng Zhang, Frederick A. Matsen
As part of work to connect phylogenetics with machine learning, there has been considerable recent interest in vector encodings of phylogenetic trees. We present a simple new "ordered leaf attachment" (OLA) method for uniquely encoding a binary, rooted phylogenetic tree topology as an integer vector. OLA encoding and…
Amirmohammad Farzaneh, Mihai-Alin Badiu, Justin P. Coon
—Measuring the complexity of tree structures can be beneficial in areas that use tree data structures for storage, communication, and processing purposes. This complexity can then be used to compress tree data structures to their informationtheoretic limit. Additionally, the lack of models for random generation of…
Amichai Painsky, Saharon Rosset
Ensemble methods are among the state-of-the-art predictive modeling approaches. Applied to modern big data, these methods often require a large number of sub-learners, where the complexity of each learner typically grows with the size of the dataset. This phenomenon results in an increasing demand for storage space…
Jie Zhang, En‐hui Yang, John C. Kieffer
We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a…
Amirmohammad Farzaneh, Mihai-Alin Badiu, Justin P. Coon
—Routing tables in ad hoc and wireless routing protocols can be represented using rooted trees. The constant need for communication and storage of these trees in routing protocols demands an efficient rooted tree coding algorithm. This efficiency is defined in terms of the average code length, and the optimality of the…
Christian Steinruecken
—This article describes lossless compression algorithms for multisets of sequences, taking advantage of the multiset's unordered structure. Multisets are a generalisation of sets where members are allowed to occur multiple times. A multiset can be encoded na¨ıvely by simply storing its elements in some sequential…
Ioannis S. Xezonakis, Svoronos Leivadaros
- In this paper we implement an n-ary Huffman Encoding and Decoding application using different degrees of tree structures. Our goal is to compare the performance of the algorithm in terms of compression ratio, decompression speed and weighted path length when using higher degree trees, compared to the 2-ary Huffman…
Travis Gagie, Gonzalo Navarro, Yakov Nekrich, Alberto Ordóñez
Most of the attention in statistical compression is given to the space used by the compressed sequence, a problem completely solved with optimal prefix codes. However, in many applications, the storage space used to represent the prefix code itself can be an issue. In this paper we introduce and compare several…
Domenico Cantone, Simone Faro
We present a new variable-length computation-friendly encoding scheme, named SFDC (Succinct Format with Direct aCcesibility), that supports direct and fast accessibility to any element of the compressed sequence and achieves compression ratios often higher than those offered by other solutions in the literature. The…
Subhash Kak
Mathematically, ternary coding is more efficient than binary coding. It is little used in computation because technology for binary processing is already established and the implementation of ternary coding is more complicated, but remains relevant in algorithms that use decision trees and in communications. In this…