A TRANSPOSITION ALGORITHM FOR DIGITAL DATA COMPRESSION KEYS

摘要

A key transposition algorithm, a procedure by which computer words are transformed into entities that are used to store and retrieve table information with great efficiency, is useful in many areas of computer information retrieval. A specific key transposition algorithm is presented which applies to a set of digital data compression key integers over the range of 1 < or = k < or = n. This set is non-continuous and non-uniform, but has definable subsets (ranging over k sub i < or = k < or = k sub j) which are sequentially uniform. The algorithm operates from densely stored tables and performs most entries to obtain table information with a divide and add operation. A minimum controlled scan is used to retrieve the information only when a transition occurs between one subrange and another. The number of scanned key integers is usually very small. Some timing comparisons with a logarithmic search are presented showing from 30 to 40 percent improvements depending on the digital data compression key structure defined.