Abstract Automated information retrieval relies heavily on statistical regularities that emerge as terms are deposited to produce text. This paper examines statistical patterns expected of a pair of terms that are semantically related to each other. Guided by a conceptualization of the text generation process, we derive measures of how tightly two terms are semantically associated. Our main objective is to probe whether such measures yield reasonable results. Specifically, we examine how the tendency of a content bearing term to clump, as quantified by previously developed measures of term clumping, is influenced by the presence of other terms. This approach allows us to present a toolkit from which a range of measures can be constructed. As an illustration, one of several suggested measures is evaluated on a large text corpus built from an on‐line encyclopedia.

This article examines some consequences for information control of the tendency of occurrences of content-bearing terms to appear together, or clump. Properties of previously defined clumping measures are reviewed and extended, and the significance of these measures for devising retrieval strategies discussed. A new type of clumping measure, which extends the earlier measures by permitting gaps within a clump, is defined, and several variants examined. Experiments are carried out that indicate the relation between the new measure and one of the earlier measures, as well as the ability of the two types of measure to predict compression efficiency.

The aim of this paper is to give a comprehensive comparison of well-known longest common subsequence algorithms (for two input strings) and study their behaviour in various application environments. The performance of the methods depends heavily on the properties of the problem instance as well as the supporting data structures used in the implementation. We want to make also a clear distinction between methods that determine the actual lcs and those calculating only its length, since the execution time and more importantly, the space demand depends crucially on the type of the task. To our knowledge, this is the first time this kind of survey has been done. Due to the page limits, the paper gives only a coarse overview of the performance of the algorithms; more detailed studies are reported elsewhere.

Several ingenious and theoretically elegant principles for shifting a pattern (relative to text) during a pattern matching process have been devised during the last decade. Somewhat surprisingly, however, the fastest practical implementations do not try to maximize the length of the shift – on the contrary, they strip the components assisting in moving the pattern to a bare minimum. To compensate, at least partly, for the loss thus incurred, the concept of a guard has been introduced, the purpose of which is to detect a possible mismatch at a small computational cost before entering the actual match loop. In this paper, a comprehensive study of the factors having an effect on the selectivity of various guard strategies is given. Our aim is to complement the report of Smith [1] (Softw. Pract. Exper., 24(4), 435–436 (1994)) and show that a fine-grained setting for this experiment is needed in order to detect detailed behaviour of the search process. Copyright © 1999 John Wiley & Sons, Ltd.

This paper focuses on finding approximations for the longest common subsequence (lcs) of two strings. Most methods which calculate an approximation for the more general problem accepting N (N/spl ges/3) input strings, give typically trivial results for the restricted case under study. Because of the small number of reliable existing heuristics, we introduce several new ones in this survey. The majority of the presented algorithms give a lower bound for the lcs. Thus they can be used, for example, as a filter to decide quickly, if a more detailed, space- and time-consuming study is needed. A lower bound can also be used to limit the search space of an exact lcs method effectively. The upper bounds complement the information about the true lcs; they form a basis to make a judgement about the reliability of a lower bound. Extensive tests have been carried out to show the strengths of the heuristics and a discussion about their role in various environments is given.

Information Retrieval Systems identify content bearing words, and possibly also assign weights, as part of the process of formulating requests. For optimal retrieval efficiency, it is desirable that this be done automatically. This article defines the notion of serial clustering of words in text, and explores the value of such clustering as an indicator of a word's bearing content. This approach is flexible in the sense that it is sensitive to context: a term may be assessed as content-bearing within one collection, but not another. Our approach, being numerical, may also be of value in assigning weights to terms in requests. Experimental support is obtained from natural text databases in three different languages. © 1998 John Wiley & Sons, Inc.

Many of the most effective compression methods involve complicated models. Unfortunately, as model complexity increases, so does the cost of storing the model itself. This paper examines a method to reduce the amount of storage needed to represent a Markov model with an extended alphabet, by applying a clustering scheme that brings together similar states. Experiments run on a variety of large natural language texts show that much of the overhead of storing the model can be saved at the cost of a very small loss of compression efficiency.

An earlier paper developed a procedure for compressing concordances, assuming that all alements occurred independently. The models introduced in that paper are extended here to take the possiblity of clustering into account. The concordance is conceptualized as a set of bitmaps, in which the bit locations reporesent documents, and the one-bits represent the occurrence of given terms. Hidden Markov Models (HMM's) are used to describe the clustering of the one-bits. However, for computational reasons, the HMM is approximated by traditional Markov models. A set of criteria is developed to constrain the allowable set of n -state models, and a full inventory is given for n ≤ 4. Graph-theoretic reduction and complementation operations are defined among the various models and are used to provide a structure relating the models studied. Finally, the new methods were tested on the concordances of the English Bible and of two of the world's largest full-text retrieval systems: the Tre´sor de la Langue Franc¸aise and the Responsa Project.

InformationRetrieval Systems typically distinguish between content bearing words and terms on a stop list.But "content-bearing " is relative to a collection.For optimal retrieval efficiency, it is desirable to have automated methods for custom building a stop list.This paper defines the notion of serial clustering of words in text, and explores the value of such clustering as an indicator of a word bearing cent ent.The numerical measures we propose may also be of value in assigning weights to terms in requests.Experimental support is obtained from natural text databases in three different languages.

An earlier paper developed a procedure for compressing concordances, assuming that all elements occurred independently. In this paper, the earlier models are extended to take the possibility of clustering into account. The authors suggest several models adapted to concordances of large full-text information retrieval systems, which are generally subject to clustering.>

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.>

Much of compression theory assumes knowledge of exact statistics of the alphabet being encoded. In practice, codes are often based on approximations of true statistics. This paper examines the consequences of random fluctuations on coding efficiency. It shows that exact statistics permit more efficient encoding, but when the error is due to random fluctuation, the savings are small and of magnitude of the extra table needed for decoding.>

Article Is Huffman coding dead? (extended abstract) Share on Authors: Abraham Bookstein View Profile , Shmuel T. Klein View Profile , Timo Raita View Profile Authors Info & Claims SIGIR '93: Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrievalJuly 1993 Pages 80–87https://doi.org/10.1145/160688.160697Online:01 July 1993Publication History 5citation1,017DownloadsMetricsTotal Citations5Total Downloads1,017Last 12 Months11Last 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 SiteGet Access

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.

The authors discuss concordance compression using the framework now customary in compression theory. They begin by creating a mathematical model of concordance generation, and then use optimal compression engines, such as Huffman or arithmetic coding, to do the actual compression. It should be noted that in the context of a static information retrieval system, compression and decompression are not symmetrical tasks. Compression is done only once, while building the system, whereas decompression is needed during the processing of every query and directly affects the response time. One may thus use extensive and costly preprocessing for compression, provided reasonably fast decompression methods are possible. Moreover, compression is applied to the full files (text, concordance, etc.), but decompression is needed only for (possibly many) short pieces, which may be accessed at random by means of pointers to their exact locations. Therefore the use of adaptive methods based on tables that systematically change from the beginning to the end of the file is ruled out. However, their concern is less the speed of encoding or decoding than relating concordance compression conceptually to the modern approach of data compression, and testing the effectiveness of their models.>

Two hybrid methods of distributive sort and quicksort are given. The first method sorts an array of records and the second one sorts a linearly linked list in a stable way. The expected running time of the methods is O(n) for n records and for a wide class of distributions of the keys (including all bounded densities with a compact support). For most other distributions the running time is O(n log n), and the worst case time is O(n2). The array version needs extra storage space for n records and approximately n/5 integers. In the linked list version only an array of n/5 pointers is needed. The observed running times of the algorithms compare favourably with those of other efficient bucket sort algorithms.

Text compression is often done using a fixed, previously formed dictionary (code book) that expresses which substrings of the text can be replaced by code words. There always exists an optimal solution for text-encoding problem. Due to the long processing times of the various optimal algorithms, several heuristics have been proposed in the literature. In this paper, the worst-case compression gains obtained by the longest match and the greedy heuristics for various types of dictionaries is studied. For general dictionaries, the performance of the heuristics can be almost the weakest possible. In practice, however, the dictionaries have usually properties that lead to a space-optimal or near-space-optimal coding result with the heuristics.

Abstract Substring search is a common activity in computing. The fastest known search method is that of Boyer and Moore with the improvements introduced by Horspool. This paper presents a new implementation which takes advantage of the dependencies between the characters. The resulting code runs 25 per cent faster than the best currently‐known routine.

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.>

In many situations text compression is carried out with a previously formed fixed dictionary (code book) expressing those often-occurring substrings of a text which are to be replaced by code words. The problem of encoding a text in a space-optimal manner is equivalent to the problem of finding a shortest path between a given pair of vertices in an acyclic and bandwidth-limited network. By combining an algorithm for finding shortest paths with the string matching algorithm of Aho and Corasick,1 a time-efficient approximation algorithm for the space-optimal encoding is obtained. The performance of the approximation algorithm depends on the amount of storage space available in the fast memory of a computer. With an unrestricted, though at most linear working storage on the length of the input text, a space-optimal encoding is obtained. However, even a fixed internal memory of moderate size guarantees almost optimal compression, and in spite of this the running time of the algorithm is comparable to that of the longest match heuristic.

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.

This paper presents a compression system for disc files. The system is automatic in the sense that once started, it selects those files from the user directory which have not been recently used, compresses them, builds a directory for them and places the data as a whole under one filename. This has resulted in savings of approximately 50% in a DEC2060 computer system and in university use, which is due to the coding and to the space saved in avoiding the allocation of unnecessary directory pages of the file system. Alternative ways to design a compression system are also discussed.

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.