Browse Prior Art Database

Offset Value Coding

IP.com Disclosure Number: IPCOM000089804D
Original Publication Date: 1977-Dec-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 5 page(s) / 76K

IBM

Related People

Conner, WM: AUTHOR

Abstract

Offset value coding is a method to record the outcome of string comparison operations in a code, so that subsequent string comparisons can be replaced with code comparisons.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 33% of the total text.

Page 1 of 5

Offset Value Coding

Offset value coding is a method to record the outcome of string comparison operations in a code, so that subsequent string comparisons can be replaced with code comparisons.

Offset value coding may be applied to a variety of sorting networks, e.g., linear lists, heaps and loser trees.

Performance improvements over traditional sorting networks are achieved by: Replacement of most string compare operations by code word comparison. Elimination of redundant comparison of leading equal characters. Localized reference pattern due to fewer record references. Elimination of inner loop tests for special conditions (next string, dummy, etc.). Definitions and Theorems.

Consider two key values A and B, each composed of characters A[1,P] and B[1,P]. (A[i] denoting the i:th character of A, A[i,]] denoting characters A[i] through A[j]. 1. The difference offset between A and B is defined as the offset to the first different character between A and B: O(A,B) = i when A[1,i-1] = B[1,i-1] and A[i] = B[i]. 2. The difference value between A and B is defined as the complement of the first different character from the higher key: V(A > JB) = COMPL(A[i]) when A[1.i-1] = B[1,i-1] and A[i] > B[i]. 3. The offset value code between A and B is defined as the difference offset concatenated with the difference value: OVC(A > B) = O(A,B),V(A > B) or OVC(A > B) = i,COMPL(A[i]) when A[1,i-1] = B[1,i-1] and A[i] > B[i], thus A > B. 4. Unequal Code Theorem: When B > A, C > A and OVC(B > A) > OVC(C > A), then B < C and OVC(C > B) = OVC(C > A). 5. Equal Code Theorem: When B > A, C > A and OVC(B > A)- OVC(C > A), then 0(B,C) > 0(B,A). 6. Reverse Unequal Code Theorem: When B < A, C < A and OVC(A > B) ) OVC(A > C). then B > C and OVC(B > C) = OVC(A > C). 7. Reverse Equal Code Theorem: When B < A, C < A and OVC(A > B) = OVC(A > C), then 0(B,C) > 0(B,A). 8. Delete Theorem: When A < B < C then OVC(C > A) = MIN(OVC(B > A),OVC(C > B)).

Offset value coded linear lists: An offset value coded linear list is an ordered set of records R(i), O < i </= N. With each record R(i) is associated a code OC(i). Then for each 1 < i </= N: R(i) > R(i-1) and OC(i)= OVC(R(i) > R(i-1)).

Special codes with offset zero may be used to flag beginning of list and trailing dummy, effectively injecting an imaginary prefix flag character. In the algorithms 01 is used for new string: OVC(R(i)) R(i-1)) = 01 if R(i) begins a string, and 00 is used to flag a high dummy: OVC(High dummy > R(i)) = 00. Thus OC(1) = 01 and OC(N + 1) = 00.

Offset value coded linear lists may be used for two-way merging as well as in A merging network. (The lists may be composed of multiple strings.)

Offset value coded heaps: An offset value coded heap is a binary tree structure. There is a set of nodes 1 to N, each node i associated with record R (i) and an offset value code OC(i). An example is shown in Fig. 1.

1

Page 2 of 5

Between nodes i and i/2 there is a son/parent relationship: node i/2 is said to be t...