公开(公告)号：CA944082A

公开(公告)日：1974-03-19

申请号：CA83261

申请日：1970-05-21

Applicant: IBM

Inventor： LOIZIDES EDWARD ,  STEIGERWALT GEORGE F

IPC: G06F12/00 ,  G06F17/30

Abstract: 1280486 Information retrieval INTERNATIONAL BUSINESS MACHINES CORP 3 June 1970 [26 June 1969] 26724/70 Heading G4C Means for generating a multi-level compressed index comprises means for assembling a plurality of boundary pairs of uncompressed keys, means for assigning a respective pointer to each of the uncompressed key pairs, the pointer representing the location of a compressed index block represented by the uncompressed key pair, and means for compressing uncompressed keys. A sorted index of uncompressed keys, each accompanied by a pointer to associated data, is read from an I/O unit a block of keys at a time (with their pointers) into a low store, the last key of each block and the first key of the next (without their pointers) being also placed in a high store where a pointer (selected sequentially from a pointer table) is appended to each such pair of keys. Each block of keys in the low store is compressed as in Specification 1,280,484 (referred to) and passed to an I/O unit to make room for the next block of uncompressed keys, the compressed block forming part of a first level of a compressed index. When a block of uncompressed keys has accumulated in the high store, it is passed to an I/O unit as a block of an uncompressed second level of the index. When the original sorted index has been completely processed in this way, the uncompressed second level of the index is read into the low store a block at a time, with the last two uncompressed keys of each block being also placed in the high store. Appending of pointers, compression, &c. take place as with the previous level, to give a compressed second level and an uncompressed third level. The latter is then used like the uncompressed second level, and so on, until the last generated compressed level has a predetermined number of blocks (normally one) or alternatively until a predetermined number of levels has been generated if this point is reached first. Each pointer in any level above the first, points to a corresponding block in the next lower level. A pointer to the single block of the highest level may be appended to a stored name of the index. Searching in the generated index requires only one block per level to be searched, and usually only a part of that since the search in a given compressed block ends whenever the search argument is lower than a compressed key with which it is compared. Magnetic tape, disc or drum are mentioned for the I/O units.

公开(公告)号：CA848590A

公开(公告)日：1970-08-04

申请号：CA848590D

Applicant: IBM

Inventor： O'CONNOR LEO T JR ,  CARTHEW JOHN R ,  LOIZIDES EDWARD ,  RICHARD WILLIAM H ,  MACKIE DAVID ,  MITTA LOUIS A

公开(公告)号：DE1277921B

公开(公告)日：1968-09-19

申请号：DEJ0028395

申请日：1965-06-22

Applicant: IBM

Inventor： CARTHEW JOHN ROBERT ,  LOIZIDES EDWARD ,  MITTA LOUIS ALBERT

IPC: G06F3/00 ,  H04Q11/04

Abstract: 1,043,330. Code converters. INTERNATIONAL BUSINESS MACHINES CORPORATION. May 27, 1965 [June 23, 1964], No. 22546/65. Heading G4H. A code converter includes a store storing a plurality of data characters each represented in a plurality of codes, comparing means for identifying the set of representations associated with a character to be converted, and means for reading out from the identified set the representation of the character in the desired code. In a first embodiment (Figs. 1-4, not shown), a number of time slots in a delay line store each store a character in each of four codes, each such coded representation being preceded by two bits identifying the code. Each such representation and its code identifier are compared in turn, serially by bit, with the representation and identifier of the character to be converted until equality is found. The code identifier of the desired code is then compared, serially by bit, with the identifiers in the rest of the slot until equality is found when the representation following the current identifier in the store is passed to the system output. Here " the rest of the slot " means the preceding or succeeding part of the slot depending on which part the desired code representation is in, as determined by comparing the two identifiers. Two taps, one slot length apart, are provided on the delay line to enable the appropriate slot portion to be obtained. The system is time-division-multiplexed between a number of other units, characters being transmitted parallel by bit. In a second embodiment (Figs. 5-6, not shown), each time slot stores one character in two codes A and B, first in code A, then in code B, and then in code A again. The input character is compared with the store contents until equality is found when the following character in store is passed out. In this way conversion either way between codes A and B is performed. Dummy bits can be inserted in the case of codes of different bit lengths, or each slot can be broken up into 2(2 ) + 1 character sections, where m and n are the numbers of bits in the longer and shorter codes respectively.