Let $\varphi=(1+\sqrt{5})/2$ denote the golden section. We investigate relationships between unbounded iterations of the floor function applied to various combinations of $\varphi$ and $\varphi^2$. We use them to formulate an algebraic polynomial-time winning strategy for a new four-pile take-away game Flora, which is motivated by partitioning the set of games into subsets CompGames and PrimGames. We further formulate recursive, arithmetic, and word-mapping winning strategies for it. The arithmetic one is based on the Fibonacci numeration system. We further show how to generate the floor words induced by the iterations using word-mappings and characterize them using the Fibonacci numeration system. We also exhibit an infinite array of such sequences.

Methods for the correct and efficient handling of annotations in a full-text retrieval system were investigated. The problem with annotations is that they cannot be treated as regular text, since this would disrupt proximity searches, but on the other hand, they cannot be ignored, as they may carry important information. Moreover, in some cases, a user may wish to restrict a search to prespecified subsets of annotations. We suggest a new way of processing the database to overcome the above dilemma.

For an ordered sequence of n weights, Huffman's algorithm constructs in time and space O(n) a search tree with minimum average path length, or, which is equivalent, a minimum redundancy code. However, if an upper bound B is imposed on the length of the codewords, the best known algorithms for the construction of an optimal code have time and space complexities O(Bn2). A new algorithm is presented, which yields sub-optimal codes, but in time O(n log n) and space O(n). Under certain conditions, these codes are shown to be close to optimal, and extensive experiments suggest that in many practical applications, the deviation from the optimum is negligible.

Under what conditions can Huffman codes be efficiently decoded in both directions? The usual decoding procedure works also for backward decoding only if the code has the affix property, i.e., both prefix and suffix properties. Some affix Huffman codes are exhibited, and necessary conditions for the existence of such codes are given. An algorithm is presented which, for a given set of codeword lengths, constructs an affix code, if there exists one. Since for many distributions there is no affix code giving the same compression as the Huffman code, a new algorithm for backward decoding of non-affix Huffman codes is presented, and its worst case complexity is proved to be linear in the length of the encoded text.

The concordance of a full-text information retrieval system contains for every different word W of the data base, a list L(W) of “coordinates”, each of which describes the exact location of an occurrence of W in the text. The concordance should be compressed, not only for the savings in storage space, but also in order to reduce the number of I/O operations, since the file is usually kept in secondary memory. Several methods are presented, which efficiently compress concordances of large fulltext retrieval systems. The methods were tested on the concordance of the Responsa Retrieval Project and yield savings of up to 49% relative to the non-compressed file; this is a relative improvement of about 27% over the currently used prefix-omission compression technique.

In static full-text retrieval systems, which accommodate metrical as well as Boolean operators, the traditional approach to query processing uses a “concordance”, from which large sets of coordinates are retrieved and then merged and/or collated. Alternatively, in a system with l documents, the concordance can be replaced by a set of bit-maps of fixed length l, which are constructed for every different word of the database and serve as occurrence maps. We propose to combine the concordance and bit-map approaches, and show how this can speed up the processing of queries: fast ANDing and ORing of the maps in a preprocessing stage, lead to large I/O savings in collating coordinates of keywords needed to satisfy the metrical and Boolean constraints. Moreover, the bit-maps give partial information on the distribution of the coordinates of the keywords, which can be used when queries must be processed by stages, due to their complexity and the sizes of the involved sets of coordinates. The new techniques are partially implemented at the Responsa Retrieval Project.

Families of Fibonacci codes and Fibonacci representations are defined. Their main attributes are robustness, manifesting itself by the local containment of errors; and simple encoding and decoding. The main application explored is the transmission of binary strings in which the length is in an unknown range, using robust Fibonacci representations instead of the conventional error-sensitive logarithmic ramp representation. Though the former is asymptotically longer than the latter, the former is actually shorter for very large initial segments of integers.

The “concordance” of an information retrieval system can often be stored in form of bit-maps, which are usually very sparse and should be compressed. Hierarchical bit-vector compression consists of partitioning a vector vi into equi-sized blocks, constructing a new bit-vector vi+1 which points to the non-zero blocks in vi, dropping the zero-blocks of vi, and repeating the process for vi+1. We refine the method by pruning some of the tree branches if they ultimately point to very few documents; these document numbers are then added to an appended list which is compressed by the prefix-omission technique. The new method was thoroughly tested on the bit-maps of the Responsa Retrieval Project, and gave a relative improvement of about 40% over the conventional hierarchical compression method.

A numeration system is a set of integers (basis elements) such that every integer can be represented uniquely over the set using integer digits of bounded size. Such systems are scattered in many fields in mathematics and computer science. Many of the known ones and new ones are unified and derived from a basic result on recursively defined basis elements. Applications are indicated.

A method for compressing large dictionaries is proposed, based on transforming words into lexicographically ordered strings of distinct letters, together with permutation indexes. Algorithms to generate such strings are described. Results of applying the method to the dictionaries of two databases, in Hebrew and English, are presented in detail. The main message is a method of partitioning the dictionary such that the "information bearing fraction" is stored in fast memory, and the bulk in auxiliary memory.

A method for compressing large dictionaries is proposed, based on transforming words into lexicographically ordered strings of distinct letters, together with permutation indexes. Algorithms to generate such strings are described. Results of applying the method to the dictionaries of two large databases, in Hebrew and English, are presented. The main message is a method of partitioning the dictionary such that the ‘information bearing fraction’ is stored in fast memory, and the bulk in auxiliary memory.

An efficient algorithm for generating a sequence of all the permutations P(i) on N symbols using parallel processors, all of which perform identical operations, is presented (0 /(/) is given explicitly.

The main features of document indexing are abstracted. It is shown that the easy part of indexing, namely the question whether there is a bounded number of descriptors for indexing a document is NP-complete. Thus even the most efficient algorithm for exact indexing is not, at least at the present time, bounded by a polynomial-time function.

We consider the game of Checkers generalized to an N × N board. Although certain properties of positions are efficiently computable (e.g., can Black jump all of White's pieces in a single move?), the general question, given a position, of whether a specified player can force a win against best play by his opponent, is shown to be PSPACE-hard. Under certain reasonable assumptions about the "drawing rule" in force, the problem is itself in PSPACE and hence is PSPACE-complete.

In a full-text natural-language retrieval system, frequent need for automatic hngulst~c analysis arises, e.g for keyword expansion in a search process, content analysis, or automatic construction of concordances The avadablhty of sophisticated hngulstic tools, which is highly desirable for languages such as Enghsh, is quite imperative for, say, Semmc languages, whose complex morphological structure renders simple-minded and approximate soluuons such as suffix stripping totally useless.Sophisticated tools were designed and constructed via the fusion of grammatical analysis and grammatical synthesis, resulting in a set of global files which provide in some sense a complete grammatical and lexlcal description of the language These files induce a set of local files which adapt to the database at hand and permit flexible on-hne morphological analysis.

AaSTRACT.In a full-text natural-language retrieval system, local feedbacl~ is the process of formulating a new ~mproved search based on clustering terms from the documents returned m a previous search of any given query Experiments were run on a database of US patents It ~s concluded that m contrast toglobalclustermg, where the size of matrices hmmts apphcatmns to small databases and improvements are doubtful, local clustering is practical also for large databases and appears to improve overall performance, especially tf metrical constraints and weighting by proximity are embedded m the local feedback The local methods adapt themselves to each mdwtdual search and produce useful searchonymsterms which are "synonymous" m the context of one query Searchonyms lead to new ~mproved search formulahons both via manual and vm automahc feedback

A full text retrieval system was designed for the responsa literature, which is a large corpus of Hebrew legal cases. The unique problems of the data base --- mixture of Hebrew, Aramaic and vernaculars, lack of vowels and punctuation, extreme language inflection problems, homographs, existence of thousands of grammatical variants of any given keyword --- dictated development of new methods. Among them we list "grammatical synthesis", which synthesizes all grammatical variants of a given keyword; "Compact KWIC", which enables the user to have a glimpse of the nature of the search before having performed it; effective citation index imbedded in full text searches; and, in general, extensive use of both positive and negative feedback within a single search run. A number of searches performed on a relatively small data base gave in each case a recall of 100%. The average precision was 34%. A KWIC of strategic portions of retrieved documents usually enables a quick disposal of non-relevant material.

Atomic Energy Commission.Reproduction in whole or in part is permitted for any purpose of the U. S. Government.