Summary Lossless compression methods based on the Burrows‐Wheeler transform (BWT) are regarded as an excellent compromise between speed and compression efficiency: they provide compression rates close to the PPM algorithms, with the speed of dictionary‐based methods. Instead of the laborious statistics‐gathering process used in PPM, the BWT reversibly sorts the input symbols, using as the sort key as many following characters as necessary to make the sort unique. Characters occurring in similar contexts are sorted close together, resulting in a clustered symbol sequence. Run‐length encoding and Move‐to‐Front (MTF) recoding, combined with a statistical Huffman or arithmetic coder, is then typically used to exploit the clustering. A drawback of the MTF recoding is that knowledge of the character that produced the MTF number is lost. In this paper, we present a new, competitive Burrows‐Wheeler posttransform stage that takes advantage of interpolative coding—a fast binary encoding method for integer sequences, being able to exploit clusters without requiring explicit statistics. We introduce a fast and simple way to retain knowledge of the run characters during the MTF recoding and use this to improve the clustering of MTF numbers and run‐lengths by applying reversible, stable sorting, with the run characters as sort keys, achieving significant improvement in the compression rate, as shown here by experiments on common text corpora.

A simple and efficient nonblock coding scheme for binary sources is suggested. It uses a probability model to map any source string to a unique integer, and thereby defines an enumeration of all possible strings. Contrary to normal enumerative coding, the new method is noncombinatorial and operates sequentially, incrementing the code value symbol by symbol, by simple arithmetic. It is akin to arithmetic coding but does not use intervals. For memoryless sources, the redundancy per symbol is shown to be asymptotically less thanp3bits, wherepis the smaller of symbol probabilities. Especially, for integer-valued 1/p, the code is asymptotically optimal. These results are confirmed by both analysis and experiments with arbitrary-precision arithmetic. In a practical implementation, the source is partitioned into substrings enabling restricted-precision arithmetic. Thanks to subtle implicit coding, the additional redundancy is marginal. The source model can be also context-based, and even adaptivity can be incorporated. A peculiarity of the method is that decoding is done backwards (LIFO). Hence, for higher-order models, the string suffix, not prefix, is used as the context domain. The speed of the practical version is close to that of binary arithmetic coders.

A new, simple non-statistical source coding technique for sequences of integers is suggested. The method is based on a tournament scheme, with the sequence arranged into pairs, where maxima (‘winners’) are encoded recursively, and minima are encoded by semi-fixed-length codes using the related maxima to bound the code lengths. In the experiments, tournament coding has outperformed the other non-statistical methods (gamma, delta, Fibonacci and interpolative coding) for uniform distribution of numbers. Also for non-uniform distributions the method is quite competitive.

In this paper, we approach the definition of design methodologies for on-chip distributed platforms. The focus is on one segmented bus approach, the SegBus platform. The approach suggests the creation of a Unified Modeling Language (UML) profile that will allow a unified representation of both platform and application

A major challenge in the design of any real time system is the proper selection of implementation and platform alternatives. In this paper, a suitable FPGA-based design of the H.264 decoder is presented. Since H.264 standard only specifies the syntax and semantics of the video stream and not the video codec itself, the selection process may be directed based upon the temporal complexity of different parts of the decoder. Here, we present the process flow of these parts using basic algebraic operators. The analysis of the required logic elements to implement the decoder, on various platforms, is presented

The article suggests a partitioning algorithm for quantitative attributes to support the discovery of frequent fuzzy patterns among transactions containing such attributes. More precisely, we present a heuristic, multivariate, top-down partitioning algorithm that divides attribute ranges into such intervals that the discovered frequent sets are also dense, and thus probably more interesting to the user. Our approach is fuzzy, so that the derived intervals have fuzzy bounds, and thereby also the derived frequent sets are fuzzy. The crisp (nonfuzzy) case is obtained as a special case. We evaluate the goodness of the partitioning method by measuring the average and absolute information amounts of the obtained fuzzy frequent sets. For the mining task, any fuzzy frequent item set mining method can be used. Experiments show that the algorithm is able to do multidimensional partitioning in a balanced way, and the “interestingness” of the obtained frequent sets is quite high, especially for correlated attributes. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 1111–1126, 2004.

Composite objects often involve recursive relationships, so-called bills-of-materials, which are cumbersome to handle in relational database systems. The relationships constitute a directed graph, where the successors of a node represent its components, recursively. Instead of the whole transitive closure (all ancestor-descendant pairs), the task is to retrieve the descendants of any given node. A simple relational solution is suggested, which packs information of the ancestor path of each node into a fixed-length code, called the signature. The code is nonunique, and its purpose is to define a relatively small superset of the descendants, as well as to establish a basis for clustering. It supports effective retrieval of the descendants, in terms of both disk accesses and DBMS calls. The method performs best for tree-structured graphs, where the processing time typically decreases by a factor of more than 10, compared to a simple loop of joins. Also, general directed graphs, both acyclic and cyclic, can be processed more effectively. The method is implemented on top of a relational system, but advantages can be gained on other platforms, too.

Article Free Access Share on Effective clustering of objects stored by linear hashing Author: Jukka Teuhola Dept. of Computer Science, Univ. of Turku, Lemminkäisenkatu 14, FIN-20520 Turku, Finland Dept. of Computer Science, Univ. of Turku, Lemminkäisenkatu 14, FIN-20520 Turku, FinlandView Profile Authors Info & Claims CIKM '95: Proceedings of the fourth international conference on Information and knowledge managementDecember 1995 Pages 274–280https://doi.org/10.1145/221270.221590Published:02 December 1995Publication History 0citation299DownloadsMetricsTotal Citations0Total Downloads299Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The 'parts explosion' is a classical problem, which is hard for relational database systems, due to recursion. A simple solution is suggested, which packs information of an ancestor path of a tuple into a fixed-length code, called signature. The coding technique is carefully adjusted to enable an efficient retrieval of the transitive closure, in terms of both disk accesses and DBMS calls. The code is lossy, and its purpose is to define a reasonably small superset of the closure, as well as establish an effective order of clustering. The method performs best for tree-structured hierarchies, where the processing time typically decreases by a factor of more than ten, compared to the trivial method. Also general directed graphs, both acyclic and cyclic, can be handled more efficiently.>

Arithmetic coding is known to be optimal in compressing strings of independent symbols, the probabilities of which are given. However the method has some disadvantages that the present variant tries to overcome. The idea here is to apply arithmetic coding piecewise, by cutting the process regularly. The result consists of fixed-length sequences of bits, representing variable-length substrings of the source. For implementation reasons, the bit sequences are composed of machine words, allowing one to use basic arithmetic efficiently. The compression gain approaches the optimum when the sequence size is increased.>

The bit-oriented finite-state model applied in Dynamic Markov Compression (DMC) [5]) is here generalized to a larger alphabet. The finite-state machine is built adaptively during compression, by applying two types of modifications to the machine structure: state cloning and shortcut creation. The machine size is kept tolerable by an escape transition mechanism. Similar to DMC, the new method is combined with arithmetic coding, based on the maintained transition frequencies. The experiments show that the new approach produces notably better compression gains for different sorts of texts in natural and formal languages. In some cases the results are better than for any compression technique found in the literature.

A new coding technique, FIXARI, is easily programmed to produce fixed-length codewords quickly for partial decoding and indexing. Errors in transmission (bit switches) remain local to the keyboard.>

Heapsort is an internal sorting method which sorts an array of n records in place in O(n log n) time. Heapsort is generally considered unsuitable for external random-access sorting. By replacing key comparisons with merge operations on pages, it is shown how to obtain an in-place external sort which requires O(m log m) page references, where m is the number of pages which the file occupies. The new sort method (called Hillsort) has several useful properties for advanced database management systems. Not only does Hillsort operate in place, i.e., no additional external storage space is required assuming that the page table can be kept in core memory, but accesses to adjacent pages in the heap require one seek only if the pages are physically contiguous. The authors define the Hillsort model of computation for external random-access sorting, develop the complete algorithm and then prove it correct. The model is next refined and a buffer management concept is introduced so as to reduce the number of merge operations and page references, and make the method competitive to a basic balanced two-way external merge. Performance characteristics are noted such as the worst-case upper bound, which can be carried over from Heapsort, and the average-case behavior, deduced from experimental findings. It is shown that the refined version of the algorithm which is on a par with the external merge sort.>

The knowledge of a short substring constitutes a good basis for guessing the next character in a natural language text. This observation, i.e. repeated guessing and encoding of subsequent characters, is very fundamental for the predictive text compression. The paper describes a family of such compression methods, using a hash table for searching the prediction information. The experiments show that the methods produce good compression gains and, moreover, are very fast. The one-pass versions are especially apt for “on-the-fly” compression of transmitted data, and could be a basis for specialized hardware.

In the compression of the text files, the dependencies between the successive characters should be exploited to as great an extent as possible. There are two obvious possibilities: either to detect and encode often occurring character strings, or to encode successors of character blocks. This paper presents two methods based on the latter approach. In the first method we encode only the most probable successors of blocks, whereas in the second we encode them all, using the knowledge of their distribution. The second method uses recursion to store effectively the dependencies between the characters and this results in good compression gains in practical cases.

Abstract Parsing can be applied to compress source programs. A suitably encoded parse tree, together with the symbol table, constitutes a very compact representation of the program. The paper reports a Prolog implementation of the method, including automatic, syntax‐directed, encoder and decoder generators. The test results show compression gains of 50–60 per cent.

A variant of indexed lists is proposed for the management of priority queues: the queue is divided into a number of two-way linked sublists. The adequate sublist can be found by using an address mapping function and a sublist index. The dynamic reorganisation of the sublists and the index is based on the analysis of the statistics collected during the process. The method is tested in the environment of discrete event simulation. Comparison with the previous index and tree algorithms, shows that the new method is advantageous at least for priority queues of moderate size.