Browse Prior Art Database

Computation of Masks for Use in Determining Keyword Conflict

IP.com Disclosure Number: IPCOM000079507D
Original Publication Date: 1973-Jul-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 1 page(s) / 11K

Publishing Venue

IBM

Related People

Kellerman, E: AUTHOR

Abstract

An algorithm is described for computing masks (binary strings) to be associated with a given series of keywords. These masks have the property that the result of ANDing two of them results in all 0's if, and only if, the associated two keywords do not conflict with each other.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 1

Computation of Masks for Use in Determining Keyword Conflict

An algorithm is described for computing masks (binary strings) to be associated with a given series of keywords. These masks have the property that the result of ANDing two of them results in all 0's if, and only if, the associated two keywords do not conflict with each other.

Prior methods for determining conflict include checking a conflict matrix. This conflict matrix contains a 1 in position (`I', `J') if, and only if, the `I'-th keyword and the `J'-th keyword conflict. All other positions contain 0's.

The input to the algorithm is an `N' by `N' conflict matrix: `M'. This matrix must be symmetrical, and its main diagonal must contain all 1's.

The output from the algorithm is another matrix: `MSK'. The `I'-th row of `MSK' is the mask to be associated with the `I'-th keyword.

The description which follows will have after every step, a concise description of that step, in APL. These statements are given for the purpose of exact definition only. It is recognized that in a practical application, the definition would be coded in a more efficient programming language.

(Image Omitted)

1