In recent years researchers have become increasingly convinced that the performance of information retrieval systems can be greatly enhanced by the use of key phrases for automatic conceptual document indexing and retrieval. In this article we describe two programs, INDEX and INDEXD, which locate repeated phrases in a document, gather statistical information about them, and rank them according to their value as index phrases. The programs show promise as the basis for a sophisticated conceptual indexing system. The simpler program, INDEX, ranks phrases in such a way that frequently occurring phrases which contain several frequently occurring words are given a high ranking. INDEXD is an extension of INDEX which incorporates a dictionary for stemming, weighting of words and validation of syntax of output phrases. Sample output of both programs is included, and we discuss plans to combine INDEXD with linguistic and artificial intelligence techniques to provide a general conceptual phrase-indexing system that can incorporate expert knowledge about a given application area. © 1990 John Wiley & Sons, Inc.

Abstract In recent years, several authors have presented algorithms that locate instances of a given string, or set of strings, within a text. Recently, authors have given less consideration to the complementary problem of processing a text to find out what strings appear in the text, without any preconceived notion of what strings might be present. A system called PATRICIA, which was developed two decades ago, is an implementation of a solution to this problem. The design of PATRICIA is very tightly bound to the assumptions that individual string elements are bits and that the user of the system can provide complete lists of starting and stopping places for strings. This paper presents an approach that drops these assumptions. Our method allows different definitions of indivisible string elements for different applications, and the only information the user provides for the determination of the beginning and ends of strings is a specification of a maximum length for output strings. This paper also describes a portable C implementation of the method, called PORTREP. The primary data structure of PORTREP is a trie represented as a ternary tree. PORTREP has a method for eliminating redundancy from the output, and it can function with a bounded number of nodes by employing a heuristic process that reuses seldom‐visited nodes. Theoretical analysis and empirical studies, reported here, give confidence in the efficiency of the algorithms. PORTREP has the ability to form the basis for a variety of text‐analysis applications, and this paper considers one such application, automatic document indexing.

In this paper we report progress on the development of ALLOY, a system that simplifies automatic document indexing and retrieval by combining techniques from several different approaches: expert, linguistic and statistical. The system is being designed to allow a panel of experts to create an ALLOY system for a given field by providing the necessary input that ALLOY needs to automatically index documents and to set up a convenient user interface. The input provided by the experts includes a hierarchy of concepts and an expert dictionary. The amount of information that the panel must provide for given field is considerably less than the amount required to build a complete thesaurus or knowledge base about that field.

The quadtree has recently become a major data structure in image processing. This correspondence investigates ways in which quadtrees may be efficiently stored as a forest of quadtrees and as a new structure we call a compact quadtree. These new structures are called virtual quadtrees because the basic operations we expect to perform in moving about within a quadtree can also be performed on the new representations. Space and time efficiency are investigated and it is shown these new structures often given an improvement in both.