Note: Descriptions are shown in the official language in which they were submitted.
70128-47D
Background of the Invention
This application is a divisional of Canadian Patent
Application, Serial Number 420,092.
lulled of the Invention
.
This invention relates to a structure and method for
searching computer data bases in order to locate and retrieve
lo textual information.
ascription of the Prior art
Prior art text comparators for searching a computer data
base are known Structures for carrying out such -techniques (such
structures are herein called "textual comparison systems") are
used, for example, by Lockheed Dialog Information Retrieval
Service, the United States Government "Flute" service, "Lewis",
and others.
Such prior art textual comparison systems are software
oriented in that a portion of the information stored in the
computer (called a "data base") must be loaded into the computer
working memory from a mass memory storage device (typically a
magnetic disk). The portion of the data base within the working
memory of the computer is scanned by the computer, as controlled
by software instructions, in order to determine if any portion of
the data base stored in the computer working memory matches -the
desired text. Typically the textual material comprising the data
base is stored by using a set of standard
1 transfer of sequential portions of the data base from a
2 large storage media, such as a disk, to the computer memory,
3 and the computer must then utilize an iterative process in
order to determine whether the desired text is contained
5 within that portion of the data base which has been
6 transferred to the computer memory. Because the computer
7 itself is performing the search, suckle prior art searching
8 techniques are rather slow and consequently expensive due
9 to the large amount of computer time required to perform a
I search-
11
12 Another prior art comparator system is described in
13 United States Patent No. 4,l52,762 issued May l, l979 to
14 Bird et at. Bird et at describe a method and structure for
text comparison which is rather complex and requires each
16 desired textual word or phrase to be stored in octal format
17 in one of a plurality of "key memories". In addition, the
18 Bird structure requires the use of additional memories,
19 including a "pointer memory" and a "hash memory", as well as
a wide variety of other sub circuits. Thus, the Bird
21 structure is rather complex.
I
23 SUMMARY
24
The present invention attacks the problem of text
26 comparison for the purpose of retrieving textual information
27 from a large data base system from a different point of
28 view. In accordance with one embodiment of this invention,
29 information stored in a mass memory unit, such as a magnetic
disk, as a plurality of bytes, each byte representing a
31 character, is input to a text comparison sub circuit which
32 includes a decoder means decoded data memory, and one or
33 more logical operator sections. Each byte of information
34 received from the disk is input to the decoder means and is
immediately decoded, and a signal corresponding to the
36 character corresponding Jo the byte input to the decoder
37 means byte is generated. The system is capable of handling
38 up to P different characters, where P is a selected positive
ii7~
1 integer.
3 The decoded data memory serves to store information received from the decoder means pertaining to characters
S represented by the bytes of information received from the
6 disk. The decoded data memory contains a plurality of P
7 serial in-parallel out shift registers, one shift register P
8 being uniquely associated with each one of the plurality of
9 P different characters forming the data base stored in the
lo storage device. 'Corresponding to the pith character (where p
lo is an integer given by 1~p~P) and contained within the
12 decoded data memory is a pith shift register uniquely
13 arranged to receive the signal from the decoder representing
14 the pith character. Upon receipt of a byte from the disk
corresponding to a specific character, a first signal (e.g.
16 a binary zero) is applied to the serial input lead of the
17 shift register uniquely associated with the character dew
18 coded by the decoder means, and a second signal (e.g. a
lo binary one) is applied to the serial input lead of all shift
registers associated with all other characters. A clock
21 signal is applied to each shift register of the decoded data
22 memory, thus shifting the data on the input lead of each
23 shift register into the least significant bit of the shift
24 register, and shifting each bit previously stored in a shift
register to the next most significant bit position within
26 the gift register. In this manner, the decoded data memory
27 will provide signals on the output leads of each shift rug
28 inter indicative of the most recently received character, as
29 well as each of the preceding (Clue) characters (i.e. a
character string" comprising K characters) received from
31 the mass memory unit and decoded, where K is the number of
3Z bits contained in each shift register of the decoded data
33 memory. Thus, each bit stored within a shift register will be a
34 binary one except for the binary zero bits stored within a shift
register corresponding to the location within the K bit
36 character string of a character corresponding to the shift
37 register. Of importance, only a single shift register within
38 the decoded data memory will store a binary zero bit
1 corresponding to each of the K positions within the K bit char-
2 cater string. By examining the bits stored within each shift
3 register of the decoded data memory, the characters comprise
1011
12
13
14
16
17
18
19
21
22
23
24
26
27
29
31
32
33
34
36
37
38
pa -
~2~7~
1 in the K bit character string, and their relative position
2 within the character string is determined.
4 The output leads of the shift registers which provide
signals defining the relative location of characters recently
6 received from the mass storage device and decoded by the de-
7 coder means are connected to the input leads of a number of one
8 or more logical operator sections which include logical gates,
such as AND gates and NOR gates, in order to provide an output
lo signal indicating that a desired textual phrase has been
11 located in the mass storage device.
12
13 The logical operator sections include word counters, pane-
14 graph counters, and other devices are employed as desired to
provide special text comparison functions. The text comparison
16 sub-circuit, the decoded data memory and the logical operator
17 sections of this invention are capable of operating at very high
18 speeds, equal to the data output speed of the mass memory unit 9
19 thus providing a very high speed textual comparison operation.
21 A second embodiment of a text comparator constructed in
22 accordance with this invention receives data stored in a mass
23 storage device. This embodiment includes word logic, delimiter
24 logic, set logic, set combination logic, proximity logic, and
programming logic. The delimiter logic serves to monitor the
26 characters transferred from the mass storage device and provides
27 a signal depicting whether the character being transferred is a
28 redefined delimiter character and, if so, the type of delimiter
29 character. The word logic serves to store data regarding pro-
defined words (i.e., strings of characters) which are to be lo
31 acted and provides output signals indicating when such prude-
32 fined words have been located. The set logic receives the de
33 limiter signals and word signals and provides output signals when
34 selected words are located in the same sentence, same paragraph,
etc., as desired. The set combination logic serves to combine
36 the signals from the set logic in order to generate output
37 signals in response to more complex search strategies then can be
38
'I!
or
-- 4
easily detected by the set logic. The proximity icky provides
output signals indicating when redefined words dejected by the
word logic, or pxedefined set of words, as detected by the set
logic, or a combination of this information, occurs within a
redefined proximity. or example, the proximity logic will de-
termite if a first selected word occurs within N (where N is a
selected integer) words of a second preselected word.
In accordance with a broad aspect of the invention
there is provided a textual comparison system for locating within
textual material the occurrence of a first desired character
string within a selected number of K (where K is a positive integer)
words (or sentences or paragraphs) of a second desired character
string comprising: first means for locating within textual mater-
tat the presence of said first desired character string, said
first means for locating providing a first signal indicating whelk-
or said first desired character string has been located; second
means for locating within textual material the presence of said
signal desired character string, said second means for locating
providing a second signal indicating whether said second desired
I character has been located; a first shift register which receives
as an input signal said first signal; a second shift register
which receives as an input signal said second signal; means for
clocking said first shift and second shift registers at the end of
each word (or sentence or paragraph) within said textual material;
a first logical gate having a plurality of K input leads connected
to the K least significant output leads of said first swept aegis-
ton, and wherein said first logical gate provides a firs-t output
signal indicating whether said first desired character string is
located within the previous K words (or sentences or paragraphs);
a second logical gate having a puerility of K input leads connect-
Ed to the K least significant output leads of said second shift
register, and wherein said second logical gate provides a second
output signal indicating whether said second desired character
string is located within the previous K words (or sentences or
paragraphs); and a third logical gate receiving as input signals
said first and said second output signals, thereby providing a
third output signal indicating whether said first desired kirk-
ton string is located within K words (or sentences or paragraphs)
of said second desired character string.
In accordance with another broad aspect of the invention
there is provided, in a textual comparison system, a structure for
detecting the presence of a plurality of delimiters within textual
material formed from a redefined sequence of characters, comprise
in: means for sequentially receiving a plurality of stored char-
caters; means for receiving a plurality of signals defining char-
caters associated with said plurality of delimiters to be detected;
means for providing, in response to the receipt of each of said
plurality of stored characters, a selected one of a plurality of
character output signals each uniquely associated with one of said
plurality of textual characters; and means for comparing the net-
alive positions of said plurality of character output signals,
thereby providing an output signal corresponding to the detected
delimiter when said relative positions owe said plurality of char-
cater output signals defines one of said delimiters.
.. ,~,. -pa-
In accordance with another broad aspect of the invention
there is provided, in a textual comparison system, set logic for
combining a plurality of word signals indicating redefined words
have been located between pairs of a redefined delimiter signal,
comprising: means for receiving said plurality of word signals;
means for storing said plurality of word signals; means for receive
in a plurality of delimiter signals; means for storing information
defining which of said plurality of delimiter signals is said pro-
defined delimiter signal; means for resetting said means for story
in said plurality of word signals in response to said predefineddelimiter signal; means for combining in a logical operation said
word signals stored within said means for storing said plurality
of word signals and providing a SET output signal; and means for
masking from said means for combining selected output signals from
said means for storing said plurality of word signals so as to
cause these signals to have no effect on said SET output signal.
In accordance with another broad aspect of the invention
there is provided, in a textual comparison system, set combination
logic for combining a plurality of SET signals indicating when
desired sets of characters have been detected, comprising: means
for receiving a plurality of SET signals; means for storing said
plurality of SET signals; means for combining said set signals in
a logical operation said SET signals stored within said means for
storing said plurality of SET signals and providing a SET combing
anion output signal;
means for muzzling from application to said means for
combining selected ones of said plurality of SET signals from have
in no effecting on said SET combination output signal.
-5b-
I
In accordance with another broad aspect of the invention
there is provided, in a textual comparison system, proximity
logic for detecting when a first selected word or set of words is
located within a selected proximity of N delimiter characters from
a second selected word or set of words, comprising: means for no-
ceiling a plurality of signals indicating when selected words or
sets of words have been detected from within textual material form-
Ed from a redefined sequence of characters; means for selecting
from said plurality of signals a first selected signal and a sea-
on selected signal; means for receiving a delimiter character means for storing the relative positions of the characters within
said textual material defined by said first and second selected
signals and providing relative position signals; means for storing
masking information, means for combining signals indicating the
relative position of said first and second selected signals; means
for masking selected ones of said relative position signals in
response to said masking information; and means for providing an
output signal when said first and second selected word is located
within said selected proximity.
BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 is a block diagram of a textual comparison
system constructed in accordance with this invention;
Figure 2 is a diagram of a decoder means utilized in
accordance with -this invention;
Figure 3 is a diagram showing the interrelation of Fig-
uses pa and 3b;
, . i
-5c-
Figures pa and 3b are diagrams of the decoded data mom-
or constructed in accordance with -this invention;
Figure 4 is a diagram of one shift register of the de-
coded elate memory of Figure 3;
Figures pa -through ye are diagrams of specific embodiments
of the logical operator section of this invention;
figure pa is a diagram of one embodiment of a word count-
or of this invention;
-So-
l Figure 6b is a diagram of one embo(lirnent Or a sentence
counter of this invention;
4 Figure 6c is a diagram of one embodiment of a paragraph
5 counter of this invention;
7 Figures pa and 7b are diagrams of another embodiment of
8 the logical operator section of this invention;
lo Fig. 8 is a block diagram of a textual comparator
if construction in accordance with a second embodiment of this
12 invention
13 Fig 9 is a diagram depicting the relationship between
14 Figs. pa, 9b and 9c which form a schematic diagram of the
delimiter logic 113 shown in Fig. 8;
16 Fig. 10 is a diagram depicting the relationship between
17 Figs aloud which in turn form a schematic diagram of the set
18 logic 114 depicted in Fig. 8;
lug Fig. 11 is a diagram which depicts the relationship
between Figs. aye and fib which in turn form a schematic
21 diagram of the set combination logic 115 depicted in Fig. 8;
22 Fig. 12 is a diagram depicting the relationship between
23 Figs. aye 12d which in turn form a schematic diagram of the
24 word logic 112 shown in Fig. 8; and
Fig. 13 is a diagram depicting the relationship between
26 Figs. awoke which in turn -form a schematic diagram of the
27 proximity logic 117 shown in Fig. 8.
28
29 DETAILED DESCRIPTION
-
I
31 The following specification recites certain standard,
32 well-known, and generally available TTL components. These TTL
33 components are available from a number of suppliers, including
34 but not limited to those listed in the specification, and as
will be appreciated by those of ordinary skill in the art,
36 these specified components can be used in accordance with the
37 teachings of this invention, regardless of the supplier. For
I further reference the Applicant cites the notional
Jo - 6
I
1 Semiconductor TTL Data Book", National Semiconductor
2 Corporation, 1976, the "Signetics TTL Logic Data Manual, l982",
3 Signetics, l982, and the "Signetics Low Power Skeptic Pocket
4 Guide", Signetics, l978.
6 FIRST EMBODIMENT
8 System Overview
9 Figure l shows a block diagram of a text comparator
constructed in accordance with the first embodiment of this
11 invention. Mass storage device if comprises a device suitable
12 for the storage of a large quantity of data.
13
14
16
17
1~3
19
21
22
23
24
26
27
28
29
31
32
33
34
36
37
38
,;,
pa
I
1 Such data lo typically called a "date base". The data
2 base might be, for example, textual material such as
3 Ignited States patents, judicial causations from various
4 courts, or other information. Mass storage device if
typically comprises a magnetic disk, as is well known in
6 the computer arts, and the data base stored within mass
7 storage device if is typically stored in ASCII format,
8 although this invention can be utilized in conjunction
9 with data bases stored in other than ASCII format (for
lo example, EBCDIC).
11
12 Data stored in mass storage device if is transferred
13 via bus ha to decoder 12. Typically, bus ha comprises a
I plurality of electrical leads, in order that a plurality
of bits forming a single byte of information may be trays-
16 furred simultaneously from mass storage device if to
17 decoder 12. The simultaneous transfer of a plurality of
18 bits forming a single byte is often referred to as "parallel
19 data output
21 Decoder 12 receives each byte transferred from mass
22 storage device if, and decodes that byte into one of a
23 plurality of unique decoded data signals. Each such
24 decoded data signal represents a unique one of the kirk-
lens which form the data base stored in mass storage
26 device if. For example, such characters typically comprise
27 the numbers zero through nine, twenty-six capital letters,
28 twenty six lower case letters, and a variety of punctu-
29 anion and special symbols such as asterisk, period, comma,
question mark, space, and the like. Inasmuch as ASCII is
31 one widely used method of coding such characters into a
32 plurality of bytes, this specification will refer to ASCII
33 coding in order to explain -the operation of one embodiment
34 of this invention. however, it is to be understood -that
this invention is equally useful in systems wherein coding
36 schemes other than ASCII is utilized. A cross reference
37 table listing each character and its ASCII equivalent is
38 given in Table l.
I
1 The output from decoder 12 is connected via bus aye
2 to decoded data memory 13. Because ASCII comprises a
3 plurality of 96 characters, bus aye in the preferred
4 embodiment comprises a plurality of 96 leads, one such
lead being associated with a unique one of the ASCII
6 characters. However, it should be understood that as many
7 leads as required can be used depending on the number of
8 characters to be decoded and in general bus aye comprises
9 a plurality of M leads, where M is a selected positive
integer representing the number of characters to be decoded.
11
12 Decoded data memory 13 stores the decoded data provided
13 by decoder 12 for a sequence of K characters stored in
I mass storage device 11 where K is a positive integer which
is fixed by the particular design of the decoded data
16 memory 13. Typically K will be either eight or sixteen,
17 although K may be any positive integer. Decoded memory 13
18 comprises a plurality of 96 shift registers, one shift
19 register for each ASCII character. K is equal to the
number of bits which are stored within each shift register.
21 The data it a logical one or a logical zero) contained
22 in each of the K bits of the 96 shift registers of decoded
23 data memory 13 indicates which ASCII characters form each
24 character of the K byte character string ending in the
most recently decoded character.
26
27 An output bus aye, containing a number of leads equal
28 to K96 (K96 equals K multiplied by 96), connects each of
29 the K96 output leads of the 96 shift registers of decoded
I data memory 13 to logical operator section 14. Logical
31 operator section 14 comprises one or more logical gates
32 which perform a logical operation on the data stored Lo
33 the shift registers of decoded data mammal 13. This
34 logical operation provides an output signal indicating
when a desired textual phrase, string of characters, or
36 sets of strings of characters, has been located within the
37 data base stored in Mass storage device 11. This output
38
1 signal from logical operator section 14 is applied via bus
2 aye to central processing unit (CPU) 15. Russ, central
3 processing unit 15 is made aware that a desired textual
4 phrase has been located in mass storage device 11. CPU 15
then follows its set of programmed instructions, and
6 utilizes -the desired textual phrase Welch has been located
7 in -the data base. Typically, CPU 15 stores the address
location of the beginning of the desired textual phrase
9 which has been located in -the data base, stores the record
number of the record (i.e., patent number, etc.) in which
11 the desired textual phrase has been found, or performs
12 other desired tasks in response -to the location and identi-
13 ligation of the desired textual phrase within the data
14 base. It is to be understood that, once the desired
textual phrase has been located within the data base
16 stored in mass storage device 11, and the CPU signaled by
17 logical operator section 14, the operation of CPU 15 is
18 generally the same as the operation of central processing
19 units in systems utilizing prior art text comparison
techniques.
2]
22 Decoder 12
23 Referring to Figure 2, the detailed operation of
24 decoder 12 will now be explained. The embodiment of
decoder 12 shown in Figure 2 is designed for use with
26 systems utilizing ASCII coding. For systems utilizing
27 other than ASCII coding, the specific design of decoder 12
28 differs from that shown in Figure 2, but is easily provided
29 by one of ordinary skill in the art, in light of the
teachings of this specification. In ASCII format, as
31 shown in Table 1, each character comprises eight binary
32 digits (bits) or two hexadecimal digits. Input bus ha
33 comprises eight leads, thus providing to decoder 12 in a
34 parallel output format the 8 bitts forming a single ASCII
character stored in mass storage device 11 (Figure 1).
36 Input bus ha also comprises an additional lead 99, which
37 provides a valid data signal (VIA) which, when high (logical
38
I
1 "1") indicates that valid data LO allowably on bus ha
2 from mass storage device 1].. The four Least significant
3 bits (LOB) of the ASCII byte received from bus ha are
4 applied to four bit buffer B-l, thus providing on leads Do
through Do buffered signals representing the four least
6 significant bits of the ASCII byte. Similarly, the four
7 most significant bits (MOB) of -the Asia byte received on
8 bus ha are applied to four bit buffer B-2, -thus providing
3 on leads D-7 through D-4 buffered signals representing the
four most significant bits of the ASIA I byte. Buffers B-l
11 and B-2 may comprise, for example, a 74125 device, such as
12 manufactured and sold by Texas Instruments.
13
14 The buffered four least significant bits (on leads Do
I through Do) are applied as input signals to demultiplexers
16 105-2 through 105-7 and the buffered four most significant
17 bits (on leads D-7 through Do are applied as input
18 signals to demultiplexer 103. Demultiplexers 103 and
19 105-2 through 105-7 are four bit to sixteen bit demulti.-
plexers such as the 74LS154 manufactured and sold by Texas
21 Instruments. Thus, each demultiplexer 103 and 105-2
22 through 105-7 provides a one of six-teen bit demul-tiplexing
23 function, although only six of -the sixteen output signals
24 from demultiplexer 103 (on leads R2 through R7) are used
because, as previously mentioned, ASCII comprises 96
26 characters, and these 96 characters are uniquely defined
I by the output leads of six separate four-to-sixteen bit
23 demultiplexers 105-2 through 105-7, as will be more fully
I described below. Accordingly, as shown in Table 1, the
four most significant bits of an ASCII byte range from a
31 binary 0001 pa decimal 1) to a binary 0111 (a decimal 7).
32
33 The output signal on each output lead of demulti-
34 plexers 103 and 105-2 -through 105-7 is normally high
(logical one). Each demultiplexer has as many output
36 leads (16) as there are different binary input signals
37 (16) which can be applied to its four input leads. Each
38
ii7~
1 output lead corresponds uniquely to one possible input
2 signal to -the demultiplexer. However, when four bit
3 input signal (the four most significant bitts on leads D-4
4 through D-7 connected to demultiplexer 103, or the four
least significant bits on leads Do through Do applied to
6 demultiplexers 105-2 through 105-7) is input to a demulti-
7 plexer, and that demultiplexer is enabled (to be more
8 fully described below), a logical zero is placed on the
9 output lead corresponding to the input signal applied to
the demultiplexer. For example, if a four bit binary
11 input signal 0101 is applied to a demultiplexer, and that
12 demultiplexer is enabled, the Outpllt lead 5 (corresponding
13 to a binary 0101~ of the demultiplexer will be low, and
14 all other output leads of the demultiplexer will be high.
All output leads of a disabled demultiplexer are high.
16
17 Demultiplexers 103 and 105-2 through 105-7 are enabled
18 by the application of a low signal to their respective
19 enable terminals. This occurs only when valid data is
preset on bus ha from the mass storage device. As
21 previously described, a logical one on valid data lead 99
22 indicates that valid data is present on bus ha. This
23 logical one signal is inverted by inventor aye, and a
24 logical Nero VIA signal is applied to NOR gate 102 and NOR
gates 104-2 through 104-7. Although NOR gates 102 and
26 104-2 through 104-7 are shown external to demultiplexers
27 103 and 105-2 through 105-7, these NOR gates are an integral
28 part of the 74LS154 devices. The output lead of NOR gate
29 102 is connected to the enable input lead of demultiplexer
103, and the output leads of NOR gates 104-2 through 104-7
31 are connected to the enable input leads of demultiplexers
32 105-2 through 105-7, respectively. Thus, with a low VIA
33 signal on lead 99, indicating that valid data is not
34 present on input bus ha, the VIA signal from the output
lead of inventor aye will be high, thus causing the
36 output signal from NOR gates 102 (having its other input
37 lead connected to ground) to be low, thus disabling
38
I
-12-
demultiplexer 103. With demultiplexer 103 disabled, leads
R2 through R7 will Allah be high; thus disabling demulti-
3 plexers 105-2 through 105-7.
On the other hand, with a logical. high on VIA lead
6 99, indicating that valid data is present on input bus 9,
7 the VIA signal will be low. Because one input lead of NOR
8 gate 102 is connected to ground (logical zero) and the
9 other input lead of NOR gate 102 is connected to ED a
low VIA signal causes the output signal from NOR gate 102
11 to go high, thus enabling demultiplexer 1.03. Demulti-
I plexer 103 then demultiplexes the fuller most significant
13 bits, thus providing a logical low on the unique output
14 lead R2 through R7 corresponding to the value of the four
most significant-bits (Do -through Do). Output leads R2
16 through R7 of demul-tiplexer 103 are connected to one input
17 lead of NOR gates 104-2 through 104-7, respectively, with
18 the other input lead of NOR gates 104-2 through 104-7
19 being connected to VIA. With a logical low VIA signal
applied to one lead of NOR gates 104-2 through 104-7 and a
21 logical low signal corresponding to the demultiplexed most
I significant bits of a unique one of leads R2 through R7
23 applied to the other lead of one of the NOR gates 104-2
24 through 104-7, a high signal will be generated on the
output lead of the NOR gate 104-2 through 104-7 correspond-
26 in to the value of the most significant bits Do through Do.
27 Thus, upon receipt of valid data thigh VIA signal) a
28 selected one of demultiplexers 105-2 through 105-7 will be
29 enabled, and all other demultiplexers 105-2 through 105-7
will be disabled by the logical high signal on the no-
31 mining leads R2 through R6 For example, with a high VIA
32 signal, indicating receipt of valid data, and the four
33 most significant bits equal to 0010, demultiple~er 103 is
34 enabled and a low signal generated on lead R2, with leads
R3 through R7 remaining high. Demultiplexer 105-~ is
36 enabled by the low VIA sunnily and the low signal own lead
37 R2. Demultiplexers 105-3 through 105-7 remain disabled by
38 the high level signals on leads R3 through R7, respectively.
1 The output signals on each OUtpllt lead of the disabled
2 demultiplexers 105-2 through Lucy will be high, as privily-
3 ouzel described. The signals on the output leads of the
4 enabled ogle of demultiplexers 105~2 through 105 7 will be
high, except for the single output fled which corresponds
6 to the decoded least significant bits on leads Do through
7 Do connected -to the input leads of demultiplexers 105-2
8 through 105-7. In -this manner, upon -the receipt of valid
g data on bus ha, a single low signal is generated on a
single output lead of demultiplexers 105-2 through 105-7.
11 The lead which contains that low signal corresponds to the
12 character represented by the Betty ASCII byte received on
13 bus ha. For example, with a high VIA signal and an eight
14 bit byte equal to 01101101 received on bus ha, demulti-
plexer 103 will be enabled, as previously described, and
16 the four most significant bits (0110) demultiplexed by
17 demultiplexer 103, thereby generating a logical low signal
18 on output lead R6. This will enable demultiplexer 105-6,
19 which in turn demul-tiplexes the four least significant
bits (1101), thereby generating the signals on a logical
21 low on output lead ED of demultiplexer 105-6, with all
22 other output leads of demultiplexer 105-6 remaining high.
23 Output lead ED corresponds to the ASCII character m,
24 represented by 01101101. A high signal is present on
leads R2, R3, I R5 and R.7, thus disabling demul-tiplexers
26 104-2, 104-3, 104-4, 104-5, and 104-7, thereby providing
27 high signals on output leads 20 through OF and I through
28 OF. For convenience, the output leads from de~ultiplexers
29 105-2 through 105-7 are numbered with two digits. The
first digit indicates which of the six demultiplexers
31 105-2 through 105-7 is connected to the lead, and the
32 second digit indicates the lead number represented in
33 hexadecimal as 0 through F). Utilizing -this notation, -the
34 first digit also represents -the four most significant bits
of the data word received on bus ha, and the second digit
I also represents the four least significant bits of the
37 data word received on bus ha.
38
2 Inventors Lola through loll provide a time delayed
VIA' signal. By applying the valid data signal (VIVA) on
3 lead 9g to the input lead of inventor Lola a time delayed
4 valid data signal (VIA') is gellerated by inverted loll on
S node 101. The VIA' signal is delayed from the VIA signal
6 my approximately 100 nanoseconds. The VIA' signal is used
7 to enable the decoded data memory :13 (Figure 1) to receive
8 data from output leads 20 through OF of decoder 12, but
9 provides a time delay sufficient to allow the proper
operation of decoder I prior to the receipt of decoded
11 data by decoded data memory 13. Each lnverter Lola -through
12 loll may comprise, for example, one of the six inventors
13 comprising a 7404 Hex inverted such as is manufactured
14 and sold by Texas Instruments.
16 Decoded Data Memory 13
17 Referring to Figures pa and 3b, the operation of
18 decoded data memory 13 will now be explained. Upon the
19 receipt of a high VIA' signal (corresponding to valid data
on input bus ha of decoder 12) on node 101 of decoded
21 data memory 13, buffer 201 provides high clock signals
22 CLUCK through CLUCK. Buffer 201 may comprise, for example,
23 a 74365 device manufactured and sold by Signetics.
24
Decoded data memory 13 comprises a plurality of shift
26 registers such as shift register SR20. For purposes of
27 clarity, the plurality of 96 shift registers are not India
28 visually labeled; only shift register SR2~ is so labeled.
29 However, the array of shift registers of decoded data
memory 13 of Figures pa and 3b are arranged in a matrix
AL comprising six rows (row 2 through row 7) and sixteen
32 columns (column 0 through column F). Thus, shift register
33 SR20 is the shift register located at the intersection of
34 row 2 and column I. In a similar manner, the shift register
located at the intersection of row n and column m will be
36 referred to as shift register SRnm in this specification.
37
38
I
-15-
1 Mach shift register SRnm (where n and m are positive
2 integers given by Lynn and lam is connected to a
3 unique one no of leads 20 through OF which corresponds to
4 that shift register. Thus, shift register SR20 is con
netted -to lead 20 and shift register SRnm is connected to
6 lead no. Leads 20, no and NM in turn are connected to the
7 decoder 12 of Figure 2. In this fashion, each shift
8 register of the decoded data memory 13 is connected to a
9 unique output lead of decoder 12 (Figure 2), thereby
lo causing each shift register of decoded data memory 13 to
11 correspond to a unique one of the 96 ASCII characters.
12 For convenience, the ASCII character associated with each
13 shift register is indicated above the shift register.
14 Thus, shift register SR20, connected to lead I cores-
ponds to a blank (b) which is coded in ASCII as a hex-
16 decimal "20", as shown in Table 1. In a similar manner,
17 each of the I shift registers of decoded data memory 13
18 corresponds to a unique ASCII character. As previously
19 mentioned, each shift register SRnm is capable of storing
K bits, thus allowing decoded data memory 13 to store K
21 decoded characters and their relative position within the
22 string of K characters.
23
24 Clock signals CLUCK through CLUCK are connected to
each shift register within row 2 through row 7, respectively.
26 Upon the receipt of a high VIA' signal, CLUCK through
27 CLUCK go high. The low to high transition of clock signals
28 CLUCK through CLUCK enables all shift registers of rows 2
29 through 7, respectively, of decoded data memory 13.
Enabling each shift register causes the signal on the
31 signal lead connected to that shift register to be stored
32 in the least significant bit of the shift register, and
33 all other data previously stored shifted to the next most
34 significant bit. Thus, for example, if a logical zero is
present on signal lead 20, and a high VIA' signal is
36 received, CLUCK will go high, thus causing the logical
37 zero on lead 20 to be stored in the least significant bit
38
I
16--
1 of shift register So All other data previously stored
2 in shift register SR2~ will be shifted to the next most
significant bit, with -the previously stored most sign-
4 ficant bit being lost.
S
6 The plurality of shift registers comprising decoded
7 data memory 13 may comprise, for example, eight bit serial.
8 in, parallel out shift registers, such as 74164 devices
9 manufactured and sold by Signetics. Alternatively, each
lo shift register SR2~ through SR7F may comprise a plurality
11 of 74164 devices serially connected in order to increase
12 the number of bits which are stored within each of the 96
13 shift registers forming decoded memory 13.
14
lo Of importance, only a single logical zero will be
16 present on signal leads 2~-7F at any time. thus, the
17 unique one of the 96 shift registers which corresponds to
18 the most recently decoded byte from mass storage device if
19 will stove a least significant bit equal to a logical
zero, wile all other shift registers will store a least
21 significant bit equal to a logical one. Thus, for example,
22 if a blank was the most recently decoded ASCII character,
23 decoded data memory 13 will indicate this fact by the
I presence of a logical zero as the least significant bit of
shift register 20, with the least significant bits of all
26 other shift registers SRnrn being equal -to a logical one.
I In a similar lesion, the previously decoded character will
28 be indicated by the presence of a logical zero as the next
29 to least significant bit stored in the shift register
corresponding to the previously decoded character. Thus,
31 Jo an "!" was the previously decoded character, the next
I to least significant bit stored within shift register SR21
33 (corresponding to the exclamation point) will be a logical -I
I zero, and the next to least significant bit stored within
all other shift registers will be a logical one. In this
36 manner, each of the most recently decoded K characters are
37 indicated by -the location of logical zeros within the shift
38
to
by
-17-
register of decoded data memory 13, where K is the number
' of bits stored in each shift register.
4 An example of the ability of decoded data memory 13
to store a character string which is decoded by decoder 12
6 (Figure I will now be given. Initially all bits contained
7 within each of the 96 shift registers of decoded data
memory 13, comprise logical ones, This may be accomplished,
9 for example, by providing a low VIA signal, thus disabling
I demultiplexers 105~2 through 105-7 Figure 2), and thereby
11 providing logical one signals on leads I through OF, and
12 providing a series of K low to high transitions on terminal
I 101, thus shifting a series of K logical one signals in-to
14 each K bit shift register (SR2~ through SR7F) of decoded
data memory 13. These low to high transitions on terminal
16 101 are easily provided with well Nina circuitry (not
17 shown)
18
19 If the word "Work" is to be decoded by decoder 12,
the 8 bits corresponding to the hexadecimal ASCII code 57
21 for a "W" will be output from mass storage device 11 to
22 input bus ha of decoder 12 (Fig. 2). A valid data signal
23 thigh VIA! will also be made available on bus ha. Demulti-
24 plexer 103 will be enabled, and a logical low signal
generated on lead R5 corresponding to the most significant
I bits of the ASCII code for W. The logical low on lead R5,
27 and the low signal will enable demultiplexer 105-5.
28 Demultiplexer 105-5 then demultiplexes the least signify-
29 cant bits, and provides a logical low on output lead 57.
All remaining output leads of demultiplexers 105-2 through
31 105-7 remain high at this time. The output signals on
32 demu'tiplexers 105-2 through 105-7 are then wafter the
33 time delay provided by inventors Lola through loll) shifted -I
34 into the least significant bit positions of -their eon-
responding shift registers of decoded data memory 13
36
37
38
57~
- 18
(Figure 3). Thus, the least significant bit of shift register
SR57 will store a logical zero, and -the least significant bits of
all remaining shift registers will store a logical one. The shift
register SR57 will store the bits 1110, and all other shift
registers will store the bits 1111, if shift registers SR20
through SR7F comprise four bit shift registers.
The letter "o" (hexadecimal OF) is then output from mass
storage device 11 to decoder 12 (Figure 2). Demultiplexer 103
decodes the four most significant bits Do through Do and provides
a logical low signal on output lead R6. The low signal on lead
R6, together with the low VIA signal, enables demul-tiplexer 105-6.
Demultiplexer 105-6 then decodes the four least significant bits
Do through Do, and provides a logical low signal on output lead
; OF. ~11 signals on all remaining output leads of demul-tiplexers
105-2 through 105-7 are logical ones at this time. The signals
on the output leads of demultiplexers 105-2 through 105-7 are then
shifted into the least significant bit of their associated shift
registers of decoded data memory 13 (Figure 3). At this time,
shift register SR6F corresponding to thy character "o" will store
the bits 1110, indicating that a "o" has been the most recently
decoded character. Similarly, shift register SR57 will store the
bits 1101, indicating that the character "W" was the previously
decoded character. All other shift registers of decoded data
memory 13 will store the bitts 1111 indicating that their associated
characters are not one of the last four characters decoded.
Roy character "r" (hexadecimal 72) is no output from
mass storage device 11 to decoder 12 (Figure 2). Demultiplexer
103 decodes the most significant bits of the character "r", and
I it
- aye -
provides a logical zero signal on output lead R7. Demultiplexer
105--7 is thus enabled, and provides a logical zero signal on
output lead 72, with -the signals on all other output leads 2
through OF being
-$~
I
9- .
logical ones. The signals on the output leads of demulti-
plexers 105-2 through 105-7 are then shifted in-to decoder
3 data memory 13 (Figure 3). Shift register SR72 will store
4 the bits lllC, shift register SR6F will store the bits
1101, shift register SR57 will store the bits 1011, and
6 all remaining shift registers will store the bit 1111,
7 indicating that the character string "Won" has been decoded.
The SHEA character "k" (hexadecimal 6B) is then
output from mass storage device 11 to decoder 12 (Figure 2).
11 Demultiplexer 103 decodes the most significant bits of the
12 ASCII character, thus providing a logical zero signal on
13 lead R6. The logical zero signal on lead R6 enables de-
14 multiplexer 105~6. Demultiplexer 105 6 demultiplexes the
least significant bits of the ASCII character, thereby
16 providing a logical Nero signal on output lead 6B, with
17 logical ones being present on all other output leads I
18 through OF. The data on the output leads of demultiplexer
19 105-2 through 105-7 is then shifted into decoded data
memory 13 (Figure pa). At this time, shift register SR6B
21 will store the bits 1110, shift register SR72 will store
22 the wits 1101, shift register OF will store the bits 1011,
23 and shift register SR57 will store the bits 0111, India
24 acting that the character string "Work" has been decoded.
////
26 ////
27 I///
I ////
29 ////
////
31 ////
32 ////
33 ////
34 ////
////
36 ////
37 ////
38 ////
"
:~2~5~
-20-
2 TABLE 1
ASCII ASCII
4 ASCII Code ASCII Code
Code (Hex- Code (Hex-
6 Character(Binarv) deciMal)C_aracter (Binary) decimal)
7 blank 00100000 20 P 01010000 50
' 00100001 Al Q 01010001 51
8 00100010 22 I 01010010 52
9 # 00100011 23 S 01010011 53
$ 00100100 24 T 01010100 54
% 00100101 25 01010101 55
11 & 00100110 26 V 01010110 56
' 00100111 27 W 01010111 57
12 ( 00101000 28 X 01011000 58
13 ) 00101001 29 Y 01011001 53
* 00101010 PA Z 01011010 PA
14 + 00101011 2B 01011011 5B
' 00101100 2C \ 01011100 5C
- 00101101 ED l 01011101 ED
16 00101110 YE -1 or A 01011110 YE
17 / 00101111 OF - 01011111 OF
0 00110000 30 ` 01100000 60
18 1 00110001 31 a 01100001 61
g 2 00110010 32 b 01100010 62
3 00110011 33 c 01100011 63
4 00110100 34 d Oily 64
21 5 00110101 35 e 01100101 65
6 00110110 36 f 01100110 66
22 7 001101l1 37 g 01100111 67
23 8 00111000 38 h 01101000 68
9 00111001 39 i 01101001 69
24 : 00111010 PA j 01101010 PA
; 00111011 3B k 01101011 6B
< 00111100 3C 1 01101100 6C
26 = 00111101 ED m 01101101 ED
> 00111110 YE n 01101110 YE
? 00111111 OF o 01101111 OF
28 @ 01000000 I p 01110000 7
29 A 01000001 41 q 01110001 71
B 01000010 42 r 01110010 72
C 01000011 43 s 01110011 73
31 D 01000100 44 t 01110100 74
E 01000101 45 u 01110101 75
32 F 01000110 46 v 01110110 76
33 G 01000111 47 w 01110111 77
H 01001000 48 x 01111000 78
34 I 01001001 49 y 01111001 79
J 0l001010 PA 01111010 PA
K 01001011 4B 01111011 7B
36 L 01001100 4C ' 01111100 7C
37 M 01001101 ED 01111101 ED
No 01001110 YE 01111110 YE
38 0 01001111 OF DEL 01111111 OF
I
-21-
A detailed view of the output leads of the shift
2 registers of decoded data memory 13 is shown in Figure 4.
3 Shift register SRmn, corresponding to the shift register
4 at the intersection of row n and column m, has a plurality
of K output leads for examining the bitts stored within
6 shift register SRnm. Thus, the least significant but
7 stored within shift register SRnm is available on lead
8 nil, the next to the least significant bit is available on
lead nm2, and the most significant bit is available Oil
lead nmK.
11
12 Logical Operator Section 14
13 Logical operator section l* comprises one or more
14 logical gates which may be hard wired -to decoded data
memory 13, or alternatively programmable connected under
16 computer control, as described latex. One embodiment of
17 logical operator section 14 (Figure 1) is shown in Figure
18 pa. Here, NOR gate aye is connected so as to provide a
13 logical one signal on output lead aye when the character
string "Work" has been located in mass storage device 11
21 (Figure 1). When the character string "Work" has been
22 received, the fourth least significant bit of shift register
23 SR57 (as provided on lead 574), the third least significant
24 bit of shift register SR6F (as provided on lead 6F3), the
second least significant bit of shift register SR72 (as
26 provided on lead 722), and the least significant bit of
27 shift register SR6B (as provided on lead 6B1), will all be
I equal to logical zeros. Thus, upon receipt of the character
29 string "Work", the output signal on lead aye of NO gate
761 (having its input leads connected to leads 574, 6F3,
31 722 and 6~1) will be a logical one, in contrast -to the
32 logical low signal present on lead aye at all other
33 times.
34
Because the character string "Work" will be detected
36 by NO gate aye upon decoding of the first four letters
37 of the word "Working" as well as for the word "Work", when
38
I
1 seeking to locate a character string equivalent to the
2 word "Work", and not any variations thereof, the logical
3 operator section 14 (Figure 1) is programmed to locate the
4 character string "Work" (where b is a blank character).
This is depicted in Figure 5b, where NOR gate 761b requires
6 the fifth least significant bit of shift register SR57 (on
7 lead 575), the fourth least significant bit of shift
8 register SR6F (on lead 6F4), the third least significant
9 bit of shift register SR72 (Gun lead 723), the second least
significant bit of shift register SR6B (on lead 6B2), and
11 the least significant bit of shift register SR20 (on lead
12 2~1) to all be logical zeros in order for the signal on
13 lead aye to be a logical one, indicating receipt of the
14 character string "Work".
16 By the appropriate connection of additional gates,
17 logical operator section 14 may perform other search
18 functions. For example, if it is desired -to locate within
19 mass storage device 11 all occurrences of either the word
"Work" or "work", the circuit of Figure 5c will serve as
21 logical operator section 14. Here, the input leads of AND
22 gate 760 are connected to leads 575 (from shift register
23 57 corresponding to the capital letter "Wow and 775 (from
24 shift register 77 corresponding to the lower case letter
"w"). Thus, a logical low on either lead 575 or lead 775
26 will provide a logical low signal on lead 760-1, which in
27 -turn is connected to an input lead of NOR gate 761C. The
28 remaining input leads of NOR gate 761C are connected to
29 leads 6F4, 723, 6B2, and 1~1, as in the embodiment of
Figure 5b. In this manner, a logical high output signal
31 is provided on lead 762C when either of the desired words
32 "Work" or "work" are located.
33
34 In many data base systems, additional symbols are
used to indicated the end of a word (HOW), the end of a
I sentence (EON), the end of a paragraph (HOP), and the end
37 of a document (HOD). These additional symbols may comprise
38
I
eight bit bytes which do not form one of the 96 ASCII
characters (i.e. comprise through OF or I through OF).
3 Alternatively, these additional s~bols may comprise one
4 or more ASCII characters. or example, -the end of sentence
S signal (EON) may comprise a period followed ho two blanks.
6 additional shift registers are utilized to serve as word
7 counters, sentence counters, and paragraph counters
9 An example of a word counter, which indicates which
I word within a sentence is being decoded, is shown in
11 Figure pa. Shift register SR-EOW may comprise a 74164
12 8-bit serial-in, parallel-out shift register, as has been
13 previously described for the shift registers of decoded
14 data memory I Alternatively, a plurality of 8-bit shift
registers may be connected serially, thus providing shift
16 register SR-EOW which is capable of storing greater than 8
17 bits. As shown in Figure pa, shift register SR-EOW is
8 provided a clock signal by the end of word (HOW) signal.
19 Thus, shift register SR-EOW is clocked upon receipt of an
HOW signal, thereby shifting data on input lead aye into
21 shift register SR-EOW and shifting data stored in the
22 shift register to the next most significant bit. Input
I lead aye is connected to the output lead of SO flip flop
24 999 (which may comprise a 74LS279 device manufactured by
Signetics). On receipt of a high EON signal, indicating
26 the end of a sentence, a logical low EON signal is generated
27 by inventor 998 (e.g. a 7404 device) and applied to the
28 clear input lead of shift register SR-EOW, thus clearing
29 shift register SR-EOW (i.e. shift register SR-EOW stores
all zeros when clear). This low EON signal also causes
31 flip flop 999 to provide a high output signal on lead
3Z aye. Upon the receipt a high HOW signal, indicating the
33 end of a word, the high output signal on lead aye is --
34 clocked into the least significant bit of shift register
SR-EOW. Also, upon receipt of a high HOW signal, inventor
36 997 provides a low R signal to reset flip flop 999, thus
37 causing flip flop 999 to provide a low output signal.
38
-24-
This low output signal is input to shift register SR-EOW
by the operation of subsequeIlt HOW signals applied to the
clock input lead of shift register SR-EOW, thereby shifting
4 the low Q signal on -the Output lead of flip flop 999 into
the least significant bit of shift register SR-EOW, and
6 shifting the data stored in each bit of shift register
7 SR-EOW to the next significant bit. Thus, the signal
g initially stored within the least significant bit of shift
9 register SR-EOW in response to a hush ERGS signal is shifted
to the left (i.e. the next most significant bit) upon
11 receipt of each HOW signal. In this manner, the signal
12 on leads Jowl -through Edgy, where j is the number of
13 bits stored within shift register SR-EOW, indicate which
14 word within the sentence is being decoded. Thus, for
example, if a logical one is present on lead Jowl the
16 first word in the sentence is being decoded. Similarly,
17 where a logical one is present on lead EYE, the second
18 word of the sentence is being decoded. Of importance,
9 only a single logical one will be present on leads oily
through Edgy. this is accomplished by applying a high
21 signal to the "clear" input lead of shift register SR-EOW
22 upon receipt of a high EON signal, thus resetting all bits
23 stored in shift register SR-EOW to logical zeros ir~nediately
24 prior to the storage of a logical one in the least signify-
cant bit of shift register SR-EOW when a high EON (End of
26 Sentence) signal is applied to input lead 876.
27
28 A sentence counter is shown in Figure 6b. The sentence
29 counter, comprising shift register SR-EOS having output leads
Easily through EoS-j, operates in a similar manner as the word
31 counter of Figure pa. However, US flip flop 989 has its input
32 lead connected to the HOP (End of Paragraph) signal, thereby
33 clearing shift register SR-EOS and setting flip flop 989 --
34 high upon receipt of each HOP signal. Upon the receipt of
a high EON signal, shift register SR-EOS is clocked in a
36 similar manner as SR-EOW (Figure pa), thereby storing a
37 logical one in the least significant bit of shift register
38
57~
-25-
SR-EOS upon receipt of the first serltence of each paragraph,
and clocking this logical one to -the next significant bit
3 upon receipt of each sunniness. Thus, the presence of a
4 logical one on a unique one of leads of Easily through
EOS-j indicates which sentence in a paragraph is being
decoded.
A paragraph counter is Shirley in figure 6c. The
9 paragraph counter, comprising shift register SR-EOP having
lo output leads EOP-l through Eop-i~ operates in a similar
11 manner as the word counter of Figure pa and the sentence
2 counter of Figure 6b. however, the HOP signal provides a
clock signal to the paragraph counter SR-EOP. The input
14 lead ~76c of the paragraph counter is connected to the
output lead of US flip flop 979, which is set by the HOD
16 wend of Document signal. The clear input lead is activated
17 upon receipt of a high HOD signal. In this manner, the
18 logical one appearing on a unique one of output leads
I EOP-l through HOP-; indicates which paragraph within the
I document is being decoded.
21
22 Utilizing the word counter, sentence counter, pane-
23 graph counter, and decoded data memory 13, complex full text
24 searching may be accomplished. For example, if it is
desired to locate a document stored within mass storage
26 device if in which the word "Work" appears in the third
27 Ford of the fourth sentence of the second paragraph, the
28 circuit of Figure Ed is used. The circuit of Figure Ed
29 comprises AND gate 901 having one input read connected -to
output lead 762b of the circuit of Figure 5b. Thus, a
31 logical high signal will be input to AND gate 901 on lead
32 762b when the character string Worn is decoded. Semi-
33 laxly, a logical high signal will be input to AND gate 901
34 when the third least significant bit of the word counter
is a logical one, indicating that the third word is being
36 decoded. This high signal will be available on lead
37 HOW 3. In a similar manner, when the fourth sentence of
38
-26-
1 the paragraph is being decoded, a logical high 'isle be
2 applied at an input signal to END gate 901 on lead OOZE,
3 and when the second paragraph of a document is being
4 decoded, a high input signal will be applied to AND gate
901 on lead ESPY. Thus, a logical high signal will be
6 present on output lead 901-1 only when the word "Work" is
7 decoded as the third word of -the fourth sentence of the
8 second paragraph of a document.
In accordance with this invention, full text searching
11 is accomplished to locate documents in which a plurality of
12 desired words occur within the same sentence. For example,
13 one embodiment of a logical operator section I which may
14 be utilized to locate text which includes the word "bat"
and "ball" in the same sentence is shown in Figure ye.
I NOR gate 976 has its input leads connected to leads 624,
17 613, 741 and 2~1 of decoded data memory 13, thus providing
I a logical high output signal on lead 976 1 when the word
19 "bat" has been decoded. Similarly, NOR gate 977 has its
input leads connected to leads 62S, 61~, 6C3, 6C2 and 2~1
21 of decoded data memory 13, thus providing a logical high
I on output lead 977-1 when the word "ball" is decoded.
23 Lead 976-1 is connected to the S input of SO flip-flop 978,
24 thus providing a logical high on the Q1 output lead 978-1
when the word "barb" has been decoded. Similarly, lead
26 977-1 is connected to the S input lead of SO flip-flop 979,
27 thus providing a high signal on the Q2 output lead 979-1
28 when the word "ball" has been decoded. Flip-flops 978
29 and 979 are reset by a low EON signal, which is applied
to the R input leads of the flip-flops. Thus, at the end
31 of each sentence, flip-flops 978 and 979 are reset I
32 and Q2 reset to logical zero), thus indicating that the
33 words "bat" and "ball" have not been decoded within the I-
34 next sentence. The output leads 978-1 and 979-1 from the
flip-flops are connected to the input of ED gate 980,
36 thus providing a logical high on output lead 980-1 when
37 the words "bat" and "ball" have been decoded within the
38
-
79L
-27-
1 same sentence (ire Al output lead of flip flop 978 and I
2 output lead of flip flop 979 both high). By utilizing the
3 end of paragraph (HOP) or the end of document (HOD) signal
4 in place of the end of sentence (EON) signal in the logical
operator section depicted in Figure ye, documents may be
6 located in which the words "bat" and "ball" are located
7 within the same paragraph, or document, respectively.
9 It is often desired to find the location within the
data base where a first desired word appears within a
11 selected number of words of a second desired word. For
I example, it may be desirable to locate instances where the
13 word "ball" appears within four words of the word "bat",
14 in order to locate portions of the data base referring to
baseball, while not locating portions of the data base
16 referring to any other type of ball ego. golf ball, etc.)
17 and any other type of bat (e.g. flying mammals). One
18 embodiment of logical operator section 14 which may act
19 complish this task of locating portions of the data base
wherein -the word "bat" appears within four words of the
21 word "ball" is shown in the schematic diagrams of Figures
22 pa and 7b.
23
24 Logical operator section 14 of Figure pa includes NOR
gate 976 and NOR gate 977, which are connected in the same
26 manner as NOR gates 976 and 977, respectively, of Figure
27 ye. Accordingly, a high output signal from NOR gate 976
28 indicates that the word "bat" has just been located.
29 Similarly, a low output signal from NOR gate 977 indicates
that the word ''ball" has just been located. Inventors
31 831 and 832 invert the output signal from NOR gates 976
32 and 977, respectively. Thus, upon detection of the word
33 "bat", the output signal from inventor 831 is low, thus
34 setting SO flip flop 833 to have a high Q output signal.
Similarly, upon detection of the word "ball", the output
36 signal from inventor 832 is low, thus setting SO flip flop
37 834 such that its Q output signal is high. The Q output
38
I
I
1 signals from SO flip flops 833 and 834 are docked into
the least significant bit of shift registers 834 and 83~,
3 respectively, upon receipt of a low HOW signal which is
4 applied to the clock input leads of shift registers 835
and 83~ SO flip flops 833 and ~34 are required in order
6 to preserve -the signal indicating -that -the desired words
7 have been decoded, until the receipt of the HOW signal
8 which clocks that data into shift registers 835 and 835,
9 respectively. If SO flip flops 833 and 834 were not used,
the signal indicating that the desired words had been
11 detected would be lost prior to being clocked into shift
12 registers 835 and 836, respectively. of importance, when
13 the HOW signal comprises a blank character (which appears
14 at the end of every word), and the desired word being
detected includes the blank character and the end of the
16 word (e.g. "bat" and "ball") shift registers 833 and 834
17 (and thus inventors 831 and 832) are not required, because
18 the HOW signal appears simultaneously with the high output
19 signal from either NOR gate 976 or NOR gate 977 indicating
-that the desired word has been decoded.
21
I Upon detection of the word "bat" and receipt of the
23 HOW signal, a logical one is clocked into the least sign-
24 ficant bit of shift register 835. After the data from
flip flops 833 and 834 have been clocked into shift rouge-
26 suers 835 and 836, respectively, upon the receipt of an
27 HOW signal, a low signal is applied to terminal 841 which
28 is connected to the reset (I input leads of flip flops
29 833 and 834, thus resetting the Q output signals of flip
flops 833 and 834 low. This reset signal applied to
31 terminal 841 may comprise, for example, a signal HOW',
32 which is derived from but delayed by approximately 75
33 microseconds from the HOW signal, thus resetting flip
34 flops 833 and 834 after the data appearing on their Q
output leads have been clocked into shift registers 835
36 and 836, respectively, upon receipt of a low HOW signal.
37 At the beginning of a search, a logical low signal is
38
~29-
l applied in a well known manner to node aye which lo
2 connected to the reset (R) input leads of shift registers
3 835 and 836, thus resetting each bit within shift registers
4 835 and 836 to logical zeros. Upon each subsequent Go
signal, the data in shift registers 835 and 836 is shifted
6 to the next most significant bit, with output data from SO
7 flip flops 833 and 834 being input to the least significant
g bits of shift registers 835 and 836, respectively. Act
9 cordingly, the signals appearing on output leads To through
To of shift register 835 indicate which one or ones of the
11 previous j words decoded was equal to bat and the
12 signals on the Output leads Pi through Pi of shift register
13 836 indicates which one of the previous j words decoded
14 was equal to "ball". In -this example, it is desired to
locate occurrences of the word bat within four words of
16 -the word "ball". Accordingly, the four least significant
17 output leads of shift registers 835 and 836 are connected
I -to the input leads of NOR gate 837 and 838, respectively.
lo Thus, NOR gate 837 generates a low output signal when the
I word "bat" is one of the four most recently decoded
21 words, and similarly, NO gate 838 provides a low output
22 signal when the word 'iballb" has been one of the four most
2.3 recently decoded words. The output leads of NOR gates 837
24 and 838 are connected to the input leads of NOR gate 839,
thus providing a high output signal from NOR gate 839
26 which is available on node 840 when both the words "bat"
27 and "Bali" have been decoded within four words of each
28 other.
29
The shift registers 835 and 836 are reset in a number
31 of desired ways. First, as previously described, on
32 beginning a search, shift registers 835 and 836 are cleared.
33 Shift registers 835 and 836 are also cleared upon receipt
34 of a high output signal from NOR gate 839, -thus indicating
I that the desired words have been decoded within four words
36 of each other. This reset procedure is designed to prevent
37 erroneous multiple high signals on the output lead of NOR
I
.57~
-30-
1 gate 339 under certain circumstances when the desired
2 words have been decoded. For example, if the desired
3 words are adjacent to essayer other, and shift registers 834
4 and 836 are not reset upon their firs-t detection, NOR gate
839 will provide a high output signal when the desired
6 words are the two most recently decoded words, the second
7 and third most recently decoded words, and the third and
8 fourth most recently decoded words, -thus providing three
9 signals for the same occurrence of the two desired words.
Thus, by resetting shift registers 835 and 836 upon receipt
11 of a high output signal from NOR gate 839, such erroneous
12 multiple signals will be prevented. Finally, shift rouge-
13 suers 835 and 836 may, if desired, be reset upon receipt
I of an EON signal, -thus requiring the desired words to appear
in -the same sentence. Alternatively, shift registers 835
16 and 836 may be reset by the HOP signal or the HOD signal,
17 thus requiring -the desired words to be located within the
18 same paragraph, or the same document, respectively.
19
Figure 7b shows NOR gate 870 having its input leads
21 connected to -the EON signal, the output signal from NOR
22 gate 839 appearing on terminal 840, and a signal labeled
23 as "begin search", which is high when a search is to
24 begin. Accordingly, NOR gate 870 will provide a low
output signal which is connected to terminate aye of
26 Figure pa to reset shift registers 835 and 836 at the
27 beginning of each search, at the end of each sentence, and
28 upon detection of the desired words and their desired
29 relationship by receipt of a high signal on terminal 840.
31 Those of ordinary skill in the art, in light of -the
32 teachings of this invention, are also able -to construct a
33 logical operation section 14 may also be constructed which
34 will detect the occurrence of a first desired word within
a fixed number of sentences of a second desired word.
36 Logical operator section 14 of Figure pa may be used for
37 this purpose with but a few modifications. For example,
38
1 shift registers 835 and 836 will, in this instance, Russell
2 their clock signals from the EON signal, and flip flops
3 833 and 834 will be reset ho a delayed EON' signal applied
4 to terminal 841. Furthermore, the NED gate 870 of Figure
7b will receive as its input signals -the HOP signal in
6 place of the EON signal, if it is desired that the two
7 words appear within the same paragraph. Alternatively,
3 the EON signal applied to NOR gate 870 of Figure 7b is
9 replaced by the GOD signal, when it is desired that the
two desired words appear in the same document.
11
12 Furthermore, it is to be understood that the decoder
13 12 and decoded data memory 13 (Figure 1) can be used with
14 logical operator section 14 other than those specific
embodiments provided in this specification. Similarly,
16 -the logical operator section 14 need not be used with the
17 specific embodiments of decoder 12 and decoded data memory
18 13 provided in this specification.
19
The logical operator section 14 (Figure 1) can comprise
21 hard wired logical gates which serve to search for desired
22 character strings. Alternatively, logical operator
23 section 14 may comprise a large number of logical gates,
24 including AND gates, OR gates, NOR gates, flip-flops, and
the like, which may be programmable connected in order to
26 provide the desired character search, in order to be
27 highly flexible in performing searches. The use of cross-
28 point switch arrays, and particularly such arrays imply-
29 minted as integrated circuits, will be useful in the
construction of logical operator section 14. One such 256
31 by 256 cross-point switching array is described in an
32 article entitled "Cross-Point Array IT Handles 256 Voice
33 and Data Channels", written by Lloyd Resume and appearing
34 in Electronics Magazine, October 6, 1981, pages 133-135.
Such a cross-point switch array is useful for connecting
36 the plurality of output leads from the shift registers of
37 decoded data memory 13 contained within bus aye, the HOW,
38
it
1 EON, HOP, and HOD signals, as well as providing inter-
2 connections between the logical gates of logical operators
3 section 14. Utilizing a suitable computer program, the
4 operation of such cross point switch arrays within logical
operators section 14 may be accomplished as a result of
6 simple commarlds describing the desired search. The computer
7 is programmed to receive the commands and operate the
8 cross point switch array in such a manner as to provide
9 proper connection between the leads within bus aye, the
HOW, EON, TOP and HOD leads, and the logical gates within
11 logical operator section 14.
I
13 As previously described, upon the decoding of the
14 desired character string, logical operator section 14
generates a signal on bus aye, which is connected to
16 central processing unit (CPU) 15 (Figure 1). CPU 15 -then
17 operates as programmed, for example, to store the document
18 number containing the desired character string, print the
19 sentence containing the desired character string, and the
like.
21
22 SECOND EMBODIMENT
23
24 yell Overview
A second embodiment of a text comparator constructed
26 in accordance with this invention is depicted in the block
27 diagram of Fig. 8. Text comparator 80 includes mass
28 storage device 111 which, as previously described in
29 conjunction with the first embodiment of this invention,
stores a large amount of textual data, often referred to
31 as the "data base." Data stowed in mass storage device
32 111 is transferred via bus Lola and made available -to word
33 logic 112, delimiter logic 113, set logic 114, set comb-
34 nation logic 115, proximity logic 117, and programming
logic 116, as is fully described below. Delimiter logic
36 113 serves to monitor the characters transferred from mass
37 storage device 111 on bus Lola and provides discrete
38
I
-33-
l signals depicting whether -the corrector ~elng transferred
2 is a redefined delimiter character. Sun delimiter
3 characters include, for example, special characters or
4 groups of characters denoting the end of a word (HOW), end
of a paragraph (HOP), end of a sentence (EON), end of a
document (HOD), end of a chapter (EON), and tile end of a
7 title (HOT). The delimiter signals provided by delimiter
logic 113 are required in order to allow the text comparator
9 80 to determine, for example, when two specified words
occur within the same sentence or within the same paragraph,
11 as is fully described below.
12
13 Word logic 112 serves -to store data regarding pro-
14 defined words (i.e., strings of characters) which are to
be located within the text stored in mass storage device
16 111. Word logic 112 then provides output word signals on
17 bus aye indicating when such redefined words have been
18 located in the character string being transferred from
19 mass storage device 111 via bus Lola. These word signals
20 are transferred via bus aye -to set logic 114 and proximity
21 logic 117.
22
23 Set logic 114 receives the delimiter signals from
24 delimiter logic 113 via bus aye and word signals from
word logic 112 via bus aye and determines when selected
I words are located in the same sentence, same paragraph,
27 etc., as desired, and provides output signals on bus aye
28 indicating when redefined words or strings of characters
29 have been so located.
31 The output signals from set logic 114 are applied to
32 set combination logic 115, which serves to combine the
33 signals from set logic 114 in order to generate output
34 signals on output bus aye indicating when the textual
information transferred from mass storage device 111 on
36 bus Lola meets the desired search strategy selected by the
37 user.
38
57~
-34-
1 Proximity logic 117 receives input signals from buses
2 Lola, aye, aye, and aye and combines this information
3 in order to provide output signals indicating when pro-
4 defined words detected by word logic 112, or redefined
set of words as detected by set logic 114, or a combine-
6 lion of this information, occurs within a redefined
7 proximity. For example, proximity logic 117 will determine
8 if a first selected word occurs within N (where N is a
9 selected integer) words of a second preselected word.
11 Programming logic 116 serves to receive search strategy
12 instructions from the user and in response thereto provide
13 the proper timing, addressing, and data signals via bus
14 Lola to word logic 112, delimiter logic 113, set logic
114, set combination logic 115, and proximity logic 117 to
16 cause to be stored within these elements the information
17 required to perform the desired search strategy.
18
19 While for ease and understanding word logic 112,
I delimiter logic 113, set logic 114, set combination logic
21 115, and proximity logic 117 will now be described in
22 separate subsections of this specification, it is to be
23 understood that each of these elements is, if required,
24 programmed by programming logic 116 prior to the execution
of a user defined textual search strategy.
26
27 Delimiter Logic 113
28 Fig. 9 depicts the relationship between Figs. pa
29 through 9c which in turn form a schematic diagram of one
embodiment of delimiter logic 113. Delimiter logic 113
31 provides on its output leads aye, aye, aye, Lowe,
32 aye, and aye, delimiter signals indicating, for example,
33 the end of a word, end of a paragraph, end of a document,
34 etc. These output leads 9 pa, aye, aye, Lowe, aye
35 and aye form bus aye of Fig. I
36
37
38
. , .
I
35-
1 II1 many textual data bases, the end of a word (HOW) is
indicated by a non-blank character followed by a blank.
3 This is preferred over the technique used by some textual
4 data bases where the end of a word is indicated simply by
a blank character, because at the end of a sentence and at
6 the end of a paragraph numerous planks may occur in sequence,
7 providing a corresponding plurality of undesired end of
8 word signals. Similarly, an end of a sentence is often
9 indicated by a period followed by two blanks, and an end
of paragraph is indicated by a period followed by three
11 blanks.
12
13 The portion of the delimiter logic 113 shown in Fig.
14 pa serves to detect the occurrence of a blank, a non-blank
character, and a period, and also combines these three
I characters in order to provide HOW, EON and HOP signals on
17 OlltpUt leads aye through aye, respectively. The eight
18 bit data word comprising bits DO through Do is latched
19 into latch 9~1 upon receipt of a clock signal (ILK) which
is provided by mass storage device 111 on bus Lola to
21 indicate that a valid data word is present on bus Lola
I Latch 9-1 comprises, for example, a 74373 device manufac-
23 lured by National Semiconductor Corporation (hereinafter
24 referred to as "National"). Latch 9-1 serves to store
data received on bus Lola and provide this data to the
26 remainder of delimiter logic 113 until the next data word
27 has been set onto bus Lola. Thus latch 9-1 provides bits
28 Do through Do on leads Lowe through Lowe Each bit DO
29 through Do is uniquely applied to one input lead of exile-
size OR gates Allah through aye, and are also uniquely
31 applied to one input lead of exclusive OR gates blue
32 through 9~2b8. The remaining input leads of exclusive OR
33 gates Allah through aye are connected either to a logical --
34 zero signal (typically zero volts) or a logical one signal
(typically 5 volts in order to program exclusive OR gates
36 Allah through aye so as to detect when a blank character
37 is transmitted on bus Lola. Similarly, the remaining
38
q~7~
-36-
input leads of exclusive OR gazes blue through 9-2b8 are
connected either to a logical Nero signal or a logical one
3 signal in order to program exclusive OR gates blue through
4 9-2b8 so as to detect when a period is -transmitted on bus
Lola.
7 Referring to table 1, it is seen that in ASCII, a
blank is a hexadecimal 20 binary 00100000). Accordingly,
9 the program leads of exclusive OR gazes Allah through
aye (i.e., those leads not connected to data bits Do
I through Do provided by leads 9 lo through 9-lh, respectively)
12 are programmed to the binary signal corresponding to the
13 inverse of the binary signal representing a blank. Thus,
14 the program leads of exclusive OR gates Allah through
aye are programmed to binary 11011111, respectively. In
16 this manner, when a blank signal is transmitted on bus
17 Lola and stored in latch 9-1, the Do through Do signals
18 applied to each exclusive OR gate Allah through aye are
19 opposite the program signal applied to these exclusive OR
gates, and each exclusive OR gate Allah through aye
21 provides a logical one output signal Oil its output lead.
22
I The output signals from exclusive OR gates Allah
24 through aye are applied to the input leads of RAND gate
aye. Thus, when a blank character is transmitted on bus
26 Lola, each input signal to RAND gate aye is a logical
I one, and the blank output signal from RAND gate guy is a
28 logical zero, indicating that a blank character has been
29 transmitted-
31 Conversely, when a non blank character is transmitted
32 on bus Lola and stored in latch 9-1, at least one exclusive
33 OR gate Allah through aye receives a data signal Do Jo
34 through Do which is identical to the programming signal
applied to that exclusive OR gate, and the output signal
36 from that exclusive Ox gate is a logical Nero. Thus, the
Jo blank output signal from RAND gate aye is a logical one,
38 indicating that a non blank character has been transmitted.
-
1 Jo
The output signal from Nt~ND gate aye is applied to
the input lead of D type flip-flop aye. The Q output
3 lead of flip flop aye is connected -to -the D input lead of
D-type flip flop sub whose Q output lead is in turn
connected to the D input lead of type flip-flop 9-~c.
6 Flip-flops aye through 9-5d thereby providing signals
7 indicating whether each of the last three characters
8 transmitted was a blank or a non blank character. D-type
9 flip-flops aye through 9-4c comprise, for example, one
flip lop of a 74175 lad D-type flip-flop manufactured by
11 National. Flip flops aye through 9-4c each receive their
12 clock signals from the Valid Data signal provided by mass
13 storage device 111 (Fig. 8) indicating that valid data is
14 available on bus Lola.
16 Again referring to table 1, it is seen that in ASCII,
17 a period is a hexadecimal YE (binary 00101110). Accordingly,
18 the program leads of exclusive OR gates blue through
19 9-2b8 (i.e., those leads not connected to data bits DO
through Do provided by leads Lowe through 9-lh, respectively)
21 are programmed to the binary signal corresponding to the
22 inverse of the binary signal representing a period. Thus,
23 the program leads of exclusive OR gates blue through
24 9-2b8 are programmed to binary 11010001, respectively. In
this manner, when a period signal is transmitted on bus
I Lola and stored in latch 9-1, -the DO through Do signals
I applied to each exclusive OR gate blue through 9-2b8 are
28 opposite the program signal applied to these exclusive OR
29 gates, and each exclusive OR gate blue through 9-2b8
provides a logical one output signal on its output lead.
31
32 The output signals from exclusive OR gates blue
33 through 9-2b8 are applied to the input leads of RAND gate
34 9-3b. Thus, when a period character is transmitted on bus
Lola, each input signal to RAND gate 9~3b is a logical one,
36 and the . output signal from NOD gate 9-3b is a logical
37 zero, indicating that the period has been transmitted.
38
1 Conversely, when a non period character is transmitted
2 on bus Lola and stored in latch I at least one exclusive
3 OR gate 9 blue through 9-2b8 receives a data signal DO
4 through Do which is identical to the programming signal
applied to that exclusive OR gate, and the output signal
6 from that exclusive OR gate is a logical zero. Thus, the
7 . output signal from NOD gate 9-3b is a logical one,
8 indicating that a non-period character has been transmitted.
I The output signal from NOD gate 9-3b is applied to
11 the D input lead of D type flip-flop aye. The Q output
12 lead of flip-flop aye is connected to the D input lead of
13 D-type flip-flop 9-5b, whose Q output lead is in -turn
I connected to the D input lead of D-type flip-flop 9-5c,
whose Q output lead is in turn connected to the D input
I lead of D-type flip-flop 9-5d. Flip-flops aye through
17 9-5d, Dupe flip-flops aye through 9-5d comprise, for
18 example, one flip-flop of a 74175 quad D-type flip-flop
19 manufactured by National. Flip-flops aye through 9-5d,
each receive their clock signals from the Valid Data
21 signal provided by mass storage device 111 (Fig. 8) indicate
22 in that valid data is available on bus Lola.
I
24 Because the end of a word is indicated by a non blank
US character followed by a blank character, one input lead of
I RAND gate 9-6 is connected to the Q output lead of flip-flop
27 9-4b and one input lead of RAND gate 9-6 is connected to
28 the Q CllpUt lead of flip-flop aye. Thus, when the kirk-
29 ton most recently transmitted on bus Lola is a blank, the
3Q Q output signal from flip flop aye is a logical one.
31 Similarly, when the preceding character transmitted on bus
32 Lola is a non blank character, the Q output signal from
33 flip-flop 9-~b is a logical one. With both input leads of
34 RAND gate 9-6 receiving logical one signals, the DOW
output signal generated by RAND gate 9-6 and available
36 output lead aye is a logical zero, indicating that the
37 end of a word has been detected. At all other times,
I
-39-
either the Q output lead of flip flop aye will provide a
2 logical zero signal (indicating that the character most
3 recently transmitted on bus Lola is a non blank character)
4 or -the Q output lead from flip flop 9--4b will provide a
logical zero signal, indicating that the previously received
6 character was not a non blank character, or both, -thereby
7 causing NAN vale 9-6 to generate a logical one HOW signal.
9 Similarly, because the end of a sentence is indicated
by a period followed by two blanks, RAND gate 9-7, which
11 generates a EON signal on its output lead aye, has one of
12 its three input leads connected to each of the Q output
13 leads of flip-flops aye, 9-4b, and 9-5c. In this manner,
14 when the two most recently received characters are blanks,
flip-flops aye and 9-4b provide logical one Q output
16 signals, and when the character preceding these two blank
17 characters is a period, flip-flop 9-5c provides a logical
18 one Q output signal, thereby causing RAND gate 9-7 to
19 generate a logical zero EON signal on output lead aye.
21 In a similar marker, the end of a paragraph is India
22 acted by a period followed by three blanks. Thus, RAND
23 gate 9-8 has one of its input leads connected to each of
24 the Q output leads of flip-flops aye, 9-4b, 9-4c, and
9-5d. In this manner, when the three most recently received
26 characters are all blanks, flip flops aye -through 9-4c
27 will provide logical one Q output signals to -three input
28 leads of RAND gate 9-8. When the character preceding
I these three blanks is a period, flip flop 9-5d will provide
a logical one Q output signal to the remaining input lead
31 of RAND gate 9-8, thereby causing RAND gate 9-8 -to generate
32 a logical zero HOP signal on output lead aye. Conversely,
33 when the four characters most recently transmitted on bus
34 Lola are not a period followed by three blanks, at least
one Q output signal from flip-flops aye, 9-4b, 9-4c, and
36 9 5b will be a logical zero, thereby causing RAND gate 9-8
37 to generate a logical one HOP signal on output lead aye
38
-40-
1 indicating that the end of a paragraph has no-t bee detected.
3 Because the HOW, EON and HOP signals are rather
4 universally indicated by a non-blank character followed by
a blank, a period followed by two blanks, and by a period
6 followed by three blanks, respectively, it is preferable
7 to utilize arrays of exclusive OR gates aye and 9-2b,
8 each exclusive OR gate having a programming lead hard
9 wired to a logical zero or logical one potential, in order
to detect the end of a word, end of a sentence, and end of
11 a paragraph. However, the HOD, EON, and HOT signals
12 oftentimes stored within mass memory device ill utilizing
13 a variety of special characters, depending on the database
14 used. for example, one system might store an HOD signal
in mass memory device 111 as a hexadecimal I while
16 another system might store an HOD signal in mass storage
17 device 111 as a hexadecimal FAX Accordingly, it is desire
18 able to provide delimiter logic 113 with the ability to be
19 programmed in a manner that will allow delimiter logic 113
to detect the presence of the HOD, EON and HOT signals,
21 regardless of how those signals are stored in the mass
22 storage device ill of the particular system being used.
23
24 The remainder of the delimiter logic 113 shown in
fig. 9 is capable of being programmed to detect any three
26 desired characters stored within mass storage device lull
27- In this embodiment, these three characters detected by the
28 circuit of Fig. 9 are the characters which are used to
29 indicate the end of a document (HOD), the end of a chapter
(EON) and the end of a title (HOT). The programming of
31 delimiter logic 113 occurs prior to the transfer of data
32 from mass storage device 111 to bus Lola for comparison.
33 Prior to such transfer, programming logic 116 (Fig. 8)
34 provides signals on bus Lola which serves -to preprogram
delimiter logic 113 as to the characters stored in mass
36 storage device 111 which serve as the HOD, EON and HOT
37 delimiters. For example, programming logic 116 will first
38
AL I
-41~
1 cause latch 9-9 (which comprises, for example a 74374
2 device manufactured by National) to store the inverse of
3 the binary signal corresponding to -the HOD delimiter
4 character stored in mass storage device 111. Thus, for
example, if the HOD delimiter characters stored in mass
6 storage device 111 is a hexadecimal bonnier 11111111)
7 its inverse (binary 00000000) is stored in latch 9-9.
8 This storage is performed by programming logic 116 providing
9 on bus Lola data bits Do through Do equal to 00000000 and
a suitable clock signal ILK to cause this data to be
I stored in latch 9-1. Programming logic 116 also provides
12 an address signal of 000 on address leads A through A,
13 respectively, of bus Lola. The address signal 000 is
14 applied to the address input leads of decoder 9-18 (which
comprises, for example, a 7~138 manufactured by National).
I Programming logic 116 also provides appropriate chip
17 enable signals El through En to decoder 9-18, thereby
18 enabling decoder 9-18. In response to these input signals,
19 decoder 9-18 provides a positive going clock signal CLUCKS 9-0
which is applied to latch 9-9. This positive going clock
21 signal ILK 9-0 causes the data present on leads Lowe
22 through 9-lh (i.e., the data stored in latch 9-1 by pro-
23 tramming logic 116) to be stored within latch 9-9. This
24 data is stored in latch 9-9 until programming logic 116
stores another eight bit word in latch 9-9. Generally,
26 because a given data base will not change the delimiter
27 character such as HOD, this data need be loaded into
28 latch 9-9 only once upon installation of the equipment.
29 however, in order to insure reliable operation of the
delimiter logic 113, it may be desirable to periodically
31 reload latch 9-9 with a binary 00000000 in order to insure
32 -that the proper data is stored in latch 9-9 despite any
33 incipient failures which would cause the data stored
34 within latch 9-9 to deviate from its intended value.
36 During the operation of -the text comparator, character
37 data is transferred from mass storage device 111 (Fig. 8)
38
~42-
1 to bus Lola and, in addition -to being compared by exclusive
2 OR gate arrays aye and 9-2b, is simultaneously compared
3 with the data stored in latch 9-9 by exclusive OR gate
4 array 9-2c two determine whether an HOD character has been
transmitted on bus Lola. Thus, when an EON character (hex
6 OF) is transmitted on bus Lola, a logical one signal will
7 be applied to one input lead of each exclusive OR gate
clue through 9-2c8 of exclusive OR (await array 9-2c. The
9 data stored within latch 9-9 is continuously applied to
the other input leads of exclusive OR gates clue through
11 9-2c8. Thus, when an FOX character is -transmitted on bus
12 Lola, the data signals Do through Do applied to one input
13 lead of exclusive OR gates clue through 9-2c8 will be the
14 inverse of the data which is applied by latch 9-9 to the
I other input lead of exclusive OR gates clue through
16 9-2c8, thereby causing each exclusive OR gate clue through
17 9-2c8 to provide a logical one signal on its output lead.
18 These output signals are in turn applied to the input
19 leads ox RAND gate 9-10, thus causing RAND gate 9-10 to
provide a logical zero HOD signal on output lead Lowe,
21 indicating that an HOD character is present on bus Lola.
I Conversely, if a character other than an HOD character is
23 transferred on bus Lola, at least one exclusive OR gate
24 clue through 9-2c8 receives a data signal Do through Do
which is identical to the data which that exclusive OR
26 gate receives from latch 9-9, and the output signal from
27 that exclusive OR gate is a logical zero, thus causing the
28 HOD signal from RAND gate 9-10 to be a logical one, India
29 acting that an HOD character has not been transferred on
bus Lola.
31
32 In a similar manner, latch 9-11, exclusive OR array
33 9-2d, and RAND gate 9-12 provide an EON signal on terminal
34 aye which indicates whether an end of chapter (EON)
character has been transferred on bus villa. Thus, for
36 example, if an EON character is hexadecimal FE (binary
37 11111110), prior to the textual comparison process, pro-
38
I
1 granting logic 116 provides a data signal Do thrush Do
2 equal to 00000001, and causes this signal -to be stored in
3 latch 9-11 by providing an A through A address signal of
4 001 which, together with appropriate enabling signals En
through En, in turn is applied to decoder 9-18, which in
6 turn provides a positive going CLUCKS 9-] signal which is
7 applied to latch 9-11. In this manner, when textual data
8 is transferred from mass storage device 111 (Fig. 8) to
9 bus Lola, each textual character is compared by exclusive
OR gate array 9-2d with the data stored in latch ill and
11 an EON signal is made available on OUtpilt terminal aye
12 indicating whether an EON character has been transmitted
13 on bus Lola.
14
In a similar mangler, latch 9-13, exclusive OR array
16 eye, and RAND gate 9-14 provide an HOT signal on terminal
17 aye which indicates whether an end of chapter (HOT) chat
18 factor has been transferred on bus Lola. Thus, for example,
19 if an HOT character is hexadecimal FED (binary 11111101),
prior to the textual comparison process, programming logic
21 116 provides a data signal Do through DO equal to 00000010,
22 and causes this signal to be stored in latch 9-13 by provide
23 in an A through A address signal of 010 which, together
24 with appropriate enabling signals En through En, in turn is
applied to decoder 9-18, which in turn provides a positive
26 going ILK 9-2 signal which is applied to latch 9-13. In
I this manner, when textual data is transferred from mass
28 storage device 111 (Fig. 8) to bus Lola, each textual chat
29 factor is compared by exclusive OR gate array eye with the
data stored in latch 9-13 and an HOT signal is made avail- -
31 able on output terminal aye indicating whether an HOT
I character has been transmitted on bus Lola.
33
34 Naturally, for data base systems which utilize special
characters to indicate HOW, EON, and HOP, circuitry anal
36 ogous to latch 9-9, exclusive OR gate array 9-2c, and RAND
37 gate 9-13 may be used in a similar manner as these circuit
38
I
1 elements are used to detect an END character Furthermore,
2 the programming leads of exclusive OR gate arrays aye and
3 9 2b need no-t be hard wired to logical zero or logical ore
4 signals, but rather could be wired to output signals
available from a memory device, if desired. Still further,
6 one or more of latches 9-9, I no 9-13 can he replaced
7 by hard wiring the programming input leads of exclusive OR
8 gate arrays 9-2c, 9 Ed, and eye, respectively, to appear-
9 private logical Nero and logical one signals, although, as
previously described, by utilizing latches 9-9, ill and
11 9-13, the delimiter logic 113 of Fig. 9 can be utilized
12 with any data base, regardless of the specific character
13 which that data base uses as an EON, EON, and HOT character.
14
Word Logic 112
16 Referring to Fig. 12, the operation of word logic 112
17 will now be described. Fig. 12 depicts a portion of word
18 logic 112 which is capable of detecting a redefined
lug string of up to eight characters. Although not shown in
Fig. 12, word logic 112 includes a latch (such as a 74373
21 device manufactured by National) provided between mass
22 storage device 111 (Fig. 8) and bus Lola, in order to
23 store data output from mass storage device 111 and provide
24 this data to the remainder of word logic 112 until the
next data word has been made available by mass storage
26 device 111. Naturally, other embodiments of this invention
27 will become readily apparent to those of ordinary skill in
28 the art in light of the teachings of this specification
29 which will allow character strings of more than (or, if
desired, less than eight characters -to be detected. It is
31 also to be understood that word logic 112 typically come
32 proses a plurality of the type of circuits shown in Fig.
33 12, in order that a plurality of character strings may be
34 detected simultaneously. Thus, for example, in this
embodiment word logic 112 contains a plurality of six-teen
36 circuits of the -type shown in Fig. 12, and thus a plurality
37 of sixteen separate character strings, each character
38
-45-
1 stripy comprising as many as eight characters, may be
2 detected simultaneously as character data LO transferred
3 from mass storage device 111 on bus Lola. Since each such
4 circuit contained within word logic 112 is identical, the
description of one such circuit as shown in Fig. 12 will
6 fully describe the operation of word logic 112.
By way of example, assume that it is desired Jo
9 locate each occurrence of the word "knife' within the
lo character data stored in mass storage device ill (Figure
11 8). Because this embodiment of word logic 112 is capable
12 of detecting up to sixteen character strings simultaneously,
13 "knife" will be referred to as word or We to distinguish
I from other words being detected. First, -the circuit of
Fig. 12 is programmed in order to be able to detect each
16 occurrence of the word "knife." To do this, programming
17 logic 116 (Fig. 8) sequentially stores within each character
18 latch 17-0 through 17-7 a binary signal corresponding to
19 the inverse of the binary signal representing each letter
of the word "knife." Thus, programming logic 116 provides
21 on bus Lola address signals A through A of 0000, together
22 with suitable enabling signals (no-t shown -to enable
23 decoder 16. These address signals are applied to decoder
24 16 which comprises, for example, a 74154 manufactured by
National. In response to this 0000 address signal, decoder
26 16 provides a positive going chip enable 0 (SUE) signal,
27 which is applied to character latch 17-0, thus causing the
28 data bits Do through Do provided on bus Lola by programming
logic 116 to be stored in latch 17-0. because the letter
30"k" is depicted in ASCII as a binary 01101011, programming
31 logic 116 provides a Do through Do signal on bus Lola of
32 Lyle, which is stored in character latch 17-0.
33
nooks, programming logic 116 provides an address
35signal A through A of 0001, which, together with suitable
36 enabling signals, cause decoder l:L6 to provide a positive
37 going SUE signal which is applied -to character latch 17-1,
38
~2.~5 it
-46-
1 thus causing character Latch 17-l to stove the I through
2 Do signal provided by programming logic 11.6. At this
3 time, programming logic 116 provides a Do through Do
4 signet. of 10010001, the inverse of the binary signal
01101i.10 which denotes -the letter "n" in SHEA. In a
6 similar manner, programming logic 116 sequentially goner-
7 ales address signals which, together with suitable enabling
8 signals, cause decoder 16 to provide positive going SUE
9 through SUE signals, thereby causing data words provided
by programming logic 116 to be stored in character latches
11 17-2 through 17-7, respectively. Since the selected word
12 is "knife", the data which is stored in character latch
13 17-2 is a binary 10010110, corresponding to the inverse of
14 the binary representation of the ASCII letter "i". The
lo data stored within character latch 17-3 is a binary 10011001,
16 (the inverse of the letter "f"), and the data stored
I within character latch 17-4 is a binary 10G11010 (the
18 inverse of the letter "e"). Because the word "knife"
19 contains only five letters, it is unimportant what is
stored in character latches 17-5 through 17-7, as the
21 presence or absence of the characters detected by character
22 latches 17-5 through 17-7 and their associated components
23 will be masked by RAND gates 22-5 through 22-7, respectively,
24 in order to have no effect on the WORD output signal
provided on output lead aye. Output lead aye
26 comprises one of the sixteen leads (leads aye through
27 aye not shown) forming bus aye. Leads aye through
28 aye provide word signals WORD I through WOODY
29 (Wow), respectively.
3G
31 The masking of unneeded characters is provided as
32 follows. After loading the required data into latches
33 17-0 through 17-7, programming logic 116 sets onto bus
I Lola an eight bit data word which defines which characters
are to be masked by RAND gates 22-0 through 22-7. This
36 eight bit mask word is stored in latch 20 (which may
37 comprise, for example, a 7437~ manufactured by National)
38
in response to -the Of 8 signal from decoder 16, which is
generated in response to appropriate signals from program-
3 mint logic 11~. Because "knife" contains only five kirk-
4 lens, the eight bit mask provided by programming logic 116
and stored in latch 20 is a binary 00011111, indicating
6 that the three characters detected by character latches
7 17~5 through 17-7 and their associated components are to
8 be masked
After the programming of the character latches 17-0
11 through 17-7 and the masking latch 20 of the WOODY circuit
12 of Fig. 12, the character latches and masking latches of
13 the World through WARD circuits are programmed in a
14 similar manner in order to allow these World through
I WARD circuits to detect additional words simultaneously
16 with the WARD circuit detecting occurrences of the word
17 "knife".
18
19 Mass storage device 111 then transfers its contents
on a character-by-character basis to bus Lola. Each data
21 bit Do through Do of each character transferred onto bus
22 Lola is applied to one input lead of a plurality of eight
23 exclusive OR gates, each such exclusive OR gate being
24 associated with one character latch 17~0 through 17-7.
Thus, the Do bit is applied to one input lead of exclusive
26 OR gate owe associated with character latch 17-0, one
27 input lead of exclusive OR gate Lowe associated with
28 character latch 17-1,... and one input lead of exclusive
29 OR gate aye associated with character latch 17-7. The
remaining input lead of each exclusive OR gate receives
31 the appropriate bit from its associated character latch
32 17-0 through 17-7. Thus, exclusive OR gate owe receives
33 the Do signal from bus Lola and the least significant bit Jo
34 stored in character latch 17-0. Similarly, exclusive OPT
gate oboe receives the Do signal from bus Lola, and the
I
37
38
I
1 second least significant bit styled in character latch
2 17-0, etc. Because character latch 17-0 stores the binary
3 inverse of the first character "k" to be detected, when
4 the cricketer "k" is set onto bus Lola, each exclusive OR
gate owe through 18-Oh receives complementary input
signals (i.e., one input signal is high, and the other
7 input signals is low), and thus the output signal from
8 each exclusive OR gate owe through 18-Oh is a logical
9 one which are in turn applied to the input leads of RAND
gate l9-0, thus providing a logical zero k output signal
11 from RAND gate 19-0. Conversely, if a character other
12 than a "k" is set onto bus Lola, at least one exclusive OR
13 gate owe through owe receives identical signals on its
14 input leads i.e. either both logical zero or both logical
one, and thus that exclusive OR gate generates a logical
16 zero output signal which causes RAND gate 19-0 -to provide
17 a logical one k output signal, indicating that the character
18 "k" has not been detected.
19
In a similar manner, the remaining character latches
21 17-1 through 17-4, and their associated exclusive OR gates
22 and RAND gates, provide logical zero n, i, f and e signals
23 on the output lead of RAND gates l9-1 through 19-4 when
24 the characters "n", "i", "f", and "e", respectively, are
detected. At all other times, the signals on -the output
26 lead of RAND gates 19-1 through 19-4 are logical one.
27
28 Roy output signals from RAND gates l9-0 -through 19-7
29 are applied to one input lead of masking RAND gates 22-0
through 22-7, respectively. Masking RAND gates 22~0
31 through 22-7 mask the detected character signals provided
32 my RAND gates 19-0 -through 19-7 in accordance with -the
33 masking word stored within masking latch 20. The least
34 significant bit stored in masking latch 20 is applied to
the other input lead of RAND gate 22-0, the second least
36 significant bit stored within that masking latch 20 is
37 applied to the other input lead of RAND gate 22-l, etc.,
38
- I -
1 and the most significant bit stored in masking latch 20 s
2 applied to the other input lead of RAND gate 22~7. Because
3 the three most significant lots stored in masking latch 20
4 are zeros, and these logical zeros are applied to one
input lead of RAND gates 22-5 -through 22-7, NOD gates
6 22-5 through 22-7 always provide logical one signals on
7 their output leads Thus, even though the output signals
8 from RAND gates 19-5 through 19-7 are applied to one input
g lead of RAND gates 22-5 through 22-7, respectively, these
signals from RAND gates 19-5 through 19-7 have no effect
11 on the output signals provided by RAND gates 19-5 through
12 19-7. Conversely, because the five least significant bits
13 stored in masking latch 20 are logical ones, the output
I signals provided by RAND gates 22-0 through 22-4 will be
the inverse of the signals provided by RAND gates 19-0
16 through 19 4, respectively. Thus, when the character "k"
17 is set onto bus Lola, RAND gate 19-0 provides a logical
I zero k signal to one input lead of NOD gate 22-0, which
19 in t-urn provides a logical one k output signal. In a
similar manner, when the letter "n" is set onto bus Lola,
21 RAND gate 22 1 provides a logical one n output signal;
22 when -the character "i" is set onto bus Lola, RAND gate
23 22-2 generates a logical one i output signal; when the
24 character "f" is set onto bus Lola, RAND gate 22-4 generates
a logical one f output signal; and when the character "e"
26 is set onto bus Lola, RAND gate 22-5 generates a logical
27 one e output signal. As previously described, RAND gates
28 22-5 through 22-7, corresponding to the detection of
29 characters which are no-t of interest when searching for
the character string "knife", always provide logical one
31 output signals.
32
33 The output signals from RAND gates 22-0 through 22-7
34 are applied to the input leads of shift registers 23-0
through 23-7, respectively. Shift register 23-0 is an
36 eight bit shift register, shift resister 23-1 is a seven
37 bit shift register, shift register 23-2 is a six bit shift
38
-50-
l register, etc., and shift register 23-7 is a one bit shift
2 register. Shift registers 23--0 through 23-7 wire formed,
3 for example, ho the appropriate connectlorl of a plurality
4 of 74174 hex Taipei flip flops manufactured by National.
Shift resisters 23-0 through 23-7 each I-ecelve clock
6 sigrlal on input lead aye which is provided by mass
7 storage device 111 (Fig. 8) on bus Lola, indicating that a
8 valid data character is present on bus Lola. The signals
9 provided by RAND gates 22-0 through 22-7 are received by
shift registers 23-0 through 23-7, and the content of each
if shift register 23~0 through 23-7 is shifted to the next
12 most significant bit within -that shift register upon
13 receipt of each clock signal on lead aye. In this
14 manner, the output signals as provided by shift registers
23-0 through 23-7 depict -the positional relationship of
16 the detected characters.
17
18 In order to provide a logical zero WICKED signal
lo indicating when the word "knife" is detected, and provide
a logical one W signal when the word "knife" is not
21 detected, shift registers 23-0 through 23-7 are used. In
22 this example, -the character string "nephew" is to be
23 detected, where each vindicates a "don't care" character.
24 To detect the character string "nephew", the most recently
detected character must be a i'don't care" character, the
26 second most recently detected character must also be a
I "don't care" character, the third most recently detected
I character must be a "don't care" character, the fourth
29 most recently detected character must be the letter "e",
the fifth most recently detected character must be a "f",
31 the sixth most recently detected character must be an "i",
32 the seventh most recently detected character must be an
33 "n", and the eighth most recently detected character must
34 be a "k". Accordingly, since the character "k" must be
I the eighth most recently detected character, the output
36 signal from RAND gate 22-0, indicating when the character
37 "k" has been detected, is applied to 8 bit shift register
38
it
1 23-0. Similarly, since the letter "n" must be the seventh
2 most recently detected character, -the output signal from
3 RAND gate Al which indicates when the letter "n" has
4 been detected, is applied to the input lead of seven bit
shift register 23-1, etc. When the proper sequence of
6 characters have been detected which spell "knlfeoOr'" the
7 output signal from each shift register 23-0 through 23-7
8 is a logical one, which in turn is applied to the input
9 leads of RAND gate 23-8, thus causing RAND gate 23-8 to
provide a logical zero WORD signal on output lead aye,
11 -thus indicating that "knife" has been detected. At all
12 other times, at least one output signal from shift registers
13 23-0 through 23-7 is a logical zero, thus causing RAND
14 gate 23-8 to provide a logical one signal on output
lead aye, thus indicating that "knife" has not been
16 detected.
17
18 It is apparent to those of ordinary skill in the art
lug in light of -the teachings of this specification that, if
desired, word logic 112 can be programmed such that pro-
21 tramming latches 17 0 through 17-7 and their associated
22 components detect the character string "oooknife", rather
23 -than "nephew" as described above. In this event, the
24 masking word stored in masking latch 20 will be 11111000,
indicating that the three characters detected by character
26 latches 17-0 through 17-3 and their associated components
27 are to be masked by RAND gates ~2-0 through 22-3, respect
28 lively. In this embodiment, where the "don't care" kirk-
29 lens precede the characters to be detected, the WORD signal
goes low upon receipt of the last character in the character
31 string being detected, rather than j characters later, where
32 j is the number of "don't care" characters in the character
33 string being detected (i.e., Jo for "oOOknifes").
34
It is also apparent to -those of ordinary skill in -the
36 art in light of the teachings of this specification that,
37 if desired, word logic 112 can be programmed such that the
38
-52~
1 programming latches 17-0 through 17-7 and their associated
2 components detect the character string "eflnku~n". In
3 this event, the masking words stored in masking latch 20
4 will be 00000111, indicating -that -the three characters
detected by character latches 17-5 through 17-7 and their
6 associated components are to be masked by RAND vales 22-5
7 through 22-7, respectively. In this event, however, shift
8 register 23-0 is a one bit shift register, shift register
9 23-1 is a two bit shift register, shift register 23 2 is a
-three bit shift register, etc., and shift register 23-7 is
11 an eight bit shift register.
12
13 It is also apparent to one of ordinary skill in the art
14 in light of the teachings of this specification that, if
desired, word logic 11~ can be programmed such that programming
16 latches 17-0 through 17-7 and their associated components
17 detect the characters string "~o~efink". In this event, the
18 masking word stored in masking latch 20 will be 11100000,
19 indicating that the characters detected by character latches
17-0 through 17-2 and their associated components are to be
21 masked by RAND gates 22-0 through 22-2, respectively. In
22 this event, shift register 23-0 is a one bit shift register,
23 etc., and shift register 23~7 is an eight bit shift register.
24
If it is desired to detect the occurrence of either
26 upper case or lower case letters, the sixth least signify-
27 cant bit received from mass storage device 111 is held high
28 and the word latches 17-0 through 17-6 are loaded with data
29 to cause -the detection of upper case letters forming the
desired word. Alternatively, the sixth least significant
31 bit received from mass storage device ]11 is held low, and
32 the word latches 17-0 through 17-6 are loaded with data to
33 cause the detection of lower case letters forming the
34 desired word. In either event, both upper and lower case
letters will be detected by latches 17-0 through 17 6 and
36 their associated components, as the sixth least significant
37 bit, which distinguishes between upper and lower case, is
38
-53-
1 effectively masked. In another embodiment of this invent
2 lion, the output signal from the sixth least significant
3 exclusive nor gates oboe, 18-lb, . . . 16 6b, are held
4 high, thereby effectively masking the sixth least signify-
cant bit and thus providing output signals when either
6 upper or lower case letters are detected.
Set Logic 114
9 Figs. lea through lo form a schematic diagram of set
logic 114. Although not shown in Figure 10, set logic 114
11 includes a latch (such as a 74373 device manufactured by
12 National) provided between mass storage device 111 (figure
13 8) and bus lea, in order to store data output from mass
14 storage device 111 and provide this data to the remainder
of set logic 114 until the next data word has been made
16 available by mass storage device 111. Set logic 114
17 serves to determine when a set of selected words are
18 detected within the same sentence, paragraph, document,
19 etc., as defined by the user's search strategy. For
example, that portion of set logic 114 shown in Fig. lo
21 detects when a redefined set of words O through 3 (i.e.,
22 a user defined set of` I through We signals generated by
23 word logic 112 (shown in Figs. 8 and 12) are detected
24 within the same sentence or paragraph, etc. As previously
described, the WOW through We signals are provided by word
26 decode logic 112 (Fig. 12). Set logic 114 as shown in
27 Fig. 12 is capable of receiving sixteen word signals
28 (i.e., WOW through Wow, although it is apparent to one of
29 ordinary skill in the art in light of the teachings of
this specification that set logic 114 can be constructed
31 to operate on any desired number of words which are each
32 detected, for example, by a unique one of an equal number
33 of circuits as shown in Fig. 12 which form word logic 112.
34 Furthermore, as will now be fully described, set logic 114
is capable of forming a plurality of sets, each set being
36 generated by a plurality of four words. It is readily
37 apparent to one of ordinary skill in the art in light of
33
I
1 the teachings of this specification that set logic 114 can
2 be constructed in order to form any desired number of
3 sets, each set being generated in response to any desired
4 number of words. Because the embodiment of set logic 114
depicted in Fig. 10 is formed of four substantially identi~
eel sub circuits (one such sub circuit being substantially
7 shown in each of Figs. aye through 10d), the following
8 description of the operation of the sub circuit of Fig. aye
9 is sufficient to describe the operation of the entire set
logic 114 depicted in Fig. aye through 10d.
11
12 Referring to Fig. aye, leads Lowe through 9-lh are
13 connected to Gus Lola to receive the data signals Do
14 through Do, respectively. The delimiter signals (HOT,
OKAY, EON, HOP, EON, and HOW) are received from delimiter
16 logic 113 figs. 8 and 9) on bus aye. The We through We
17 signals are received from appropriate portions of word
18 logic 112 (Figs. 8 and 12) and applied to the SET 3 input
19 leads of SO latches aye through 10-7d, respectively.
Latches aye through 10-7d serve to store data indicating
21 when words 0 through 3, respectively, have been detected
22 by word logic 112. SO latches aye through 10-7d each
I comprise, for example, one of the four latches contained
24 within a DM74279 device manufactured by National.
26 Multiplexer 10-3 selects the appropriate delimiter
27 signal or ground, as will be fully described later) and,
28 in response thereto, provides a RESET signal which is
I applied to the RESET (R) input leads of latches aye
through 10~7d, causing latches aye through 10-7d to be
31 reset to store logical zeros when the RESET signal is a
32 logical zero. Multiplexer 10-3 comprises, for example, a
33 74151 device manufactured by National. Latch 10-1 stores --
34 information provided by pro~rarnming logic 116 (Fig. a ) on
bus Lola during the programmirlg of the text comparator
36 prior to executing a textual search strategy. Latch 10-1
37 comprises for example, a 74374 device manufactured by
I National.
I
-55-
1 Latch 10-3 (for example a 7437~ device) serves to
2 store masking information which is provided by programming
3 logic 116 (Fig. 8) to latch 10-8 via bus Lola during the
programming of the text comparator of this invention prior
to the execution of a user-defined textual comparison
6 search strategy. Logical AND circuitry 10-36 combines the
7 through We signals in a logical A and a logical RAND
8 fashion and provides the Shetland (STAND) and -the SWEETENED
9 (Slid) signals on leads aye and aye, respectively.
Similarly, the logical OR circuitry 10-37 combines the I
11 through We signals in a logical OR and a logical NOR
12 fashion and provides the Seattle ( Slur ) and the Settler
13 slur) signals on leads aye and aye, respectively.
14 Logical AND circuitry 10-36 and logical OR circuitry
10-37, when masked by the masking data stored in masking
16 latch 10-8, provide output signals which indicate whether
17 the word 0 through 3 have been detected between two occur-
I fences of -the signal selected by decoder 10-3, thereby
19 providing output signals indicating whether words 0 through
3 have been detected in the same sentence, for example.
21
22 In order to program set logic 114, programming logic
23 116 (Fig. 8) first sets onto the Do through Do data lines
24 of bus Lola the information which is to be stored in latch
10-1. Programming logic 116 then provides the appropriate
26 A through A and En through En signals, thereby causing
27 multiplexer 9-18 (Fig pa) to generate a positive going
28 CLUCK signal, which is applied to latch 10-1, thereby
29 causing the Do through Do data on bus Lola to be stored
within latch 10-1. The three least significant bits
31 stored in latch 10-1 are applied to the address input
32 leads of multiplexer 10-3, and similarly the next three
33 least significant bits stored in latch 10-1 are applied to
34 the address input leads of multiplexer 10-~. The three
address signals applied to multiplexer 10-3 define which
36 delimiter signal (or ground, if the input lead of multi-
37 plexer 10-3 which is connected to ground, as shown, is
I
it
-56-
1 selected by multiplexer 10-4 in response tug the address
2 signals provided thereto by latch 10-1) are to geniality
3 the RESET signal on the output lead of multiplexer 10-3.
4 Ground is selected by multiplexer 10-3 in odor- to generate
a RESET signal when ~eslred to reset the contents of
6 flip-flops aye through 10-7d, for example on power-up of
7 the set logic 114. Next, programming logic 116 (Fig. 8)
8 sets onto the Do through Do data leads of bus Lola the
masking data which is -to be store in masking latch 10-8.
Programming logic 116 then sets onto bus aye the A
11 through A and the El through En signals which cause
12 demultiplexer 9-18 (Fig. pa) to generate a positive going
13 CLUCK signal, which in turn is applied to latch 10-8,
14 thereby causing -the data on leads Do through Do of bus
Lola to be stored in latch 10-8. If required by -the user
16 defined search strategy, programming logic 116 then repeats
17 these steps in order -to program the remaining latches
18 10-2, 10-9, 10-10, and 10-11 of set logic 114.
19
Assume, for example, that it is desired to locate
21 within the textual information stored in mass storage
22 device 111 all instances where the word "knife" (WORD)
23 occurs within the same sentence as the word "blood"
24 (Widely. Programming logic 116 programs word logic 112 as
previously described, to cause WORD to be the ~^70rd "knife"
I and World to be the word "blood", thus causing a low We
27 signal and a low We signal to be generated upon detection
28 of the words "knife" and "blood", respectively. Because
29 it is desired to locate these two words only within the
same sentence, the latches aye through 10-7d must be
31 reset upon receipt of the EON delimiter signal. Accordingly,
32 programming logic 116 stores within latch 10~1 three least
33 significant bits which, when applied -to -the address input
34 leads of multiplexer 10-3, cause multiplexer 10-3 to
select the EON signal applied via bus aye to generate the
36 RESET signal. Furthermore, because only WORD and WORD
37 are of interest in -this particular search, programming
38
to
-57-
logic 116 causes to be stored in masking latch 10-8 an
eight bit mask which will cause the We and We signals -to
3 have no effect on the output signals generated by the
4 logical AND logic circuitry 10-36.
6 Because in this example the words "knife" and "blood"
7 are to be combined a logical AND operation, the output
8 signals from logical OR circuitry 10-37 are not used, and
9 thus the value of the four most significant bits stored in
masking latch 10-8 is unimportant. However, in order to
11 cause logical AND circuitry 10-36 to provide Stand and
12 Stand output signals generated by the logical operation
13 Stand = (We AND We) the four least significant bits (Do
14 through Do) provided by programming logic 116 and stored
in latch 10-8 must be equal to 1100, respectively. In
I this manner, the least significant bit stored in masking
17 latch 10 8 is a logical zero, which is applied to one
18 input lead of NOR gate 10-12h. With a logical zero signal
19 applied to one input lead of NOR gate 10-12h, the other
input lead of NOR gate 10-12h, which is connected to the Q
21 output lead of flip flop aye, controls the output signal
22 from NOR gate 10-12h. Similarly, with the second least
23 significant bit being a logical zero, which is applied to
24 one input lead of NOR gate 10-12g, the other input lead of
NOR gate 10-12g, which is connected to the Q output lead
26 of flip flop 10-7b, causes NOR gate 10-12g to generate its
27 output signal in response to the We signal stored in flip
28 flop 10-7b. Because the third and fourth least significant
29 bits stored in masking latch 10-8 are logical ones and are
each applied to one input lead of NOR gates 10-12f and
31 eye, respectively, NOR gates eye and 10-12f always
32 provide logical zero output signals, indicating that the
33 We and We signals stores in latches 10-7c and 10 Ed,
I respectively (and thus WORD and WORD) are unimportant
and form no part of the logical operation performed by
36 logical AN circuitry 10-36.
37
38
-58-
1 The output signals from NOR gates eye through
2 10-12h are applied to the input leads of NOR gate 10~
3 Because the output signals from NOR gates eye and
10-12f are always a logical zero, they will have no effect
on the output signal generated by NOR gate 10-14. However,
6 only when the output signals generated by NOR gates 10 12g
7 and 10-12h are logical zeros, inducting that logical ones
8 are stored in both shift registers aye and 1.0-7b (i.e.,
9 logical zero We and We signals have been received and thus
logical one We and We signals stored in flip flops aye
11 and 10-7b, respectively, since the last RUSS signal)
12 will the Stand output signal from NOR gate 10-14 be a
13 logical one, indicating that the words "knife" and "blood"
14 have both been located in a single sentence.
16 As previously described, -the RESET signal is, in
17 this example, genera-ted by multiplexer 10-3 in response
18 to the EON signal. Accordingly, the data stored in latches
I aye and 10-7d is reset to logical zeros in response to a
logical zero RESET signal. If after a logical zero
21 RESET signal the word "knife" is detected, a logical zero
22 We signal is applied to the 3 input lead of flip-flop
23 aye, thus causing a logical one to be stored in flip
24 flop aye. This generates a logical one Q output signal
from flip-flop aye which is applied to one input lead of
I NOR gate 10-12h, thus causing NOR gate aye to generate
27 a logical zero output signal. However, because the won
28 "blood" (World) has not been detected, a logical zero is
29 still stored in shift register 10-7b, and shift register
10-7b provides a logical zero Q output signal which is
31 applied to one input lead of NOR gate 10-12g. This,
32 together with the logical zero input signal applied to its
33 other input lead from latch 10-8, causes NOR gate 10-12g
34 to provide a logical one output signal, thus causing NOR
gate 10-14 to generate a logical zero Shetland output
36 signal, indicating that the words "knife" and "blood" have
37 not both detected in the same sentence. If an OOZE signal
38
ALLAH
-59-
1 is now genera-ted prior to the detection of eye word "blood",
2 multiplexer 10-3 generates a logical zero ESSAY signal
3 and the shift registers 10 pa through 10-7d are reset to
4 store logical zeros, thereby preventing an erroneous
output signal from logical AND circuitry 10-36 should the
6 word "blood' be detected in a subsequent sentence which
does not also contain the word knife
9 In a similar manner, if the search strategy requires
the location of all occurrences of either the word "knife"
11 or "blood" in the same sentence, the logical OR circuitry
12 10-37 is utilized. In this event, the four most significant
13 masking bits stored in masking latch 10-8 by programming
14 logic 116 are 0011. With -the most significant bit from
masking latch 10-8 being applied -to one input lead of RAND
16 gate aye, NED gate aye always generates a logical
17 one output signal, and thus -the We signal stored in shift
18 register 10-7d has no effect on the output signals generated
19 by OR logic circuitry 10-37. Similarly, because the
second most significant masking bit stored in masking latch
21 10-8 is applied to one input lead of RAND gate 10-12b,
22 RAND gate 10-12b always generates a logical one output
I signal, and thus the We signal stored in shift register
24 10-7c has no effect on the output signal generated by
logical OR circuitry 10-37. The third and fourth most
26 significant masking bits stored in masking latch 10-8 are
27 logical ones, and are applied to one input lead of RAND
28 gates 10-12c and 10-12d, respectively. These logical one
29 signals cause the output signals from RAND gates 10-12c
and 10-12d to be generated in response to the We and We
31 signals stored in flip-flops aye and 10~7b, respectively,
32 and applied to the other input lead of RAND gates 10 12d
33 and 10~12c, respectively. If the word "knife" is detected,
34 a logical zero We signal is generated by word logic 112,
and thus a logical one WOW signal is stored in flip-flop
36 aye. This logical one WOW signal causes RAND gate 10-12d
37 to generate a logical zero output signal which causes RAND
38
-60-
1 gate 10~13 to generate a logical one Slur signal on output
2 lead aye (and causes inverted 10-5 to generate a logical
3 zero Slur signal on output lead aye), thus indicating
4 that -the word "knife" has been detected. Similarly, if
the word "blood" is detected a logical zero Wit signal is
6 generated by word logic 112 and thus a logical one W],
7 signal is stored in flip flop 10-7b. This logical one We
8 signal causes RAND gate 10-12c to generate a logical zero
9 output signal, which in turn causes RAND gate lG-13 to
generate a logical one Slur signal on output lead aye
11 (and causes inverted 10-15 to generate a logical zero Slur
12 signal on output lead aye), thus indicating that the
13 word "blood" has been detected. If neither the word
14 "knife" or the word "blood" is detected, flip flops aye
-through 10-7d will each s-tore a logical zero signal, NAY
16 gates aye through ]0-]2d each generate logical one
17 output signals, RAND gate 10-13 generates a logical zero
18 Slow signal, and inventor 10~15 generates a logical one
19 Slur signal), thus indicating that neither "knife" or
"blood" has been detected.
21
22 Set Combination Logic 115
23
24 Set combination logic 115 serves to combine the set
signals provided by set logic 114 (Figure 10) in accordance
26 with a user defined search strategy. Although not shown
27 in Figure if, set combination logic 115 includes a latch
28 (such as a 74373 device manufactured by National) provided
29 between mass storage device 111 (Fig. 8) and bus Lola, in
order to store data output from mass storage device ill
31 and provide this data to the remainder of set combination
32 logic 115 until the next data word has been made available
33 by mass storage device 1]1. Set combination logic 115
34 includes latches 11-2 and 11-3 (which comprise, for example
I 74374 devices manufactured by National) which store set
36 combination words provided by programming logic 116 in
37 response to the user defined search strategy. Latches 11-2
38
~2~7~
-61-
and 11~3 store this information in response to -the CLUCK
and CLUCK signals, respectively, generated by decoder
3 9-17 (Fig. 9), as previously described). Set combination
4 logic 115 also includes US flip-flops Lola through 11-lh
which comprise, for example, 74279 devices manufactured by
6 National. Shift registers Lola through ll~lh store the
7 SPOOR, STAND through S30R, D signals provided by set
8 logic 114 (Figure 10). Flip-flops Lowe through 11-lh are
9 reset by reset signal ha provided by programming logic
116 (Fig. 8) when a search strategy is begun.
11
12 Latch ll-2 stores the masking word provided by pro-
13 tramming logic 116, in order to cause RAND gates aye
14 through 11-2h and their associated components to combine
the set signals stored in flip flops Lola through 11-lh
16 in a logical OR function. For example, if it is desired
17 to combine -the S00R and STAND signals, programming logic
I 116 (Figure 8) causes latch 11-2 to store Do through Do
19 signals of 00000011, where the logical ones indicate which
set signals are two be combined in the logical OR function.
21 Thus, latch 11-2 provides logical zero signals to one
22 input lea of RAND gates aye through 11-2f, thereby
23 causing the output signals from these RAND gates aye
24 through 11-2f to be logical ones. Latch 11-2 also provides
US logical one signals to one input lead of RAND gates 11-2g
I and 11-2h. The other input leads of RAND gates 11-2g and
27 if oh are connected to the Q output leads of flip flops
28 Lola and 11 lb, respectively. Prior to the SPOOR and
29 I signals going low, the Q output signals from flip-flops
Lola and if lb are logical zero, thus causing the output
31 signals from 11-2g and 11-2h to be logical ones. This
32 causes the Output signal from RAND gate 11-3 to be logical
33 zero, and the output signal from inventor 11-4 -to be
34 logical one. Thus, only when a logical zero SPOOR signal
or D signal has been generated by set logic 114 (Fig.
36 10), will the Q output signal from flip-flops Lola or
37 11-lb be a logical one, thereby causing the output signal
38 from RAND gates 11-2g and 1]-2h to be a logical zero.
-62-
1 With one input signal to RAND gate 11-3 a logical zero,
2 the output signal from RAND gate 11-3 is a logical one,
3 indicating that -the logical OR connation of the set
4 signals defined by the masking word stored in latch 11-2
has been met. This logical one signal from NOD gate
6 11-3 causes -the output signal from irlverter 11-4 be a
7 logical zero, thereby causing -the cutpllt signal from NAN
8 gate 11-9 to be a logical one.
In a similar manner, latch 11-3 stores a masking word
11 provided by programming logic 116 in order to combine the
12 set signals applied to flip flops Lowe through ll-lh to
13 be combined in a logical AND fashion. Thus, if it is
14 desired to combine the SPOOR signal with the S0~NV signal
in a logical AN function, latch 11-3 is programmed by
16 programming logic 116 (Fig. 8) -to store Do -through Do
17 signals 11111100. With logical ones applied to one input
18 lead of NOR gates aye through 11-5f, the output signals
19 from these NOR gates are logical zeros. With logical
zero signals applied by latch 11-3 to one input lead of
21 NOR vales 11-5g and 11-5h, the output signals from NOR
22 gates 11~5g and 11-5h will be logical zero only when both
23 the SPOOR and SUAVE signals have been logical zero, thus
24 causing logical one Q signals to be provided by both
flip-flops Lola and ll-lb, respectively. With the output
26 signal from both NOR gates 11-5g or 11-5h logical zeros,
27 the output signal from NOR gates 11-7 is logical one, and
I the output signal from NAN gate 11-~ is a logical zero,
29 indicating that both SCOW and STAND has been low. This
causes the output signal from RAND gate 11-9 to be a
31 logical one.
32
33 Thus, a logical one on thy output lead of NAN gate --
34 11-9 indicates that either the logical OR function provided
35 by latch 11-2 and its associated components or the logical
36 AN function provided by latch 11-3 and its associated
37 components, has been met. This logical one output signal
38 from RAND gate 11-9 is available Oil lead aye to provide
73~
1 an interrupt signal to a central processing unit (CPU, not
2 shown) if desired. This interrupt signal can be inverted by an
3 inventor (not shown) if desired. This logical one output
4 signal trot RAND gate 11-9 also provides a clock signal to
5 latch 11 10 and which comprises, for example a 74373 device
6 manufactured by National), thus causing the Q output signals
7 from flip flops Lola through 11-lh to be stored in latch
8 11-10. Terminal aye receives an output enable signal from
9 the central processing unit, thereby causing the bits stored in
latch 11-10 which indicate the status of the set signals
11 received and stored within flip-flops Lola through 11-lh, to
12 be set onto bus 1 l l a for use by the central processing unit, if
13 desired.
14
Proximity Lo
16
17 Referring to Figure 13, the operation of proximity logic
18 117 will now be described. Proximity logic 117 includes a
19 latch (such as a 71l373 device manufactured by National)
provided between mass storage device -I 11 (Figure 8) and bus
21 Lucy in order to store data output from mass storage device
22 111 and provide this data to the remainder of proximity logic
23 117 until the next data word has been made available by mass
24 storage device aye Proximity logic 117 serves to detect
when a first selected word (detected by word logic 112 of`
26 Fig. 12) or set (detected by set logic 114 of Fig. 10) is
27 located within a specific distance or proximity of a second
28 selected word or set. For example, proximity logic 117 can
29 be programmed to detect when a first word "knife" (detected
by word logic 112 as, for example, word zero) is located
31 within n words of a second selected word "blood" (detected by
32 word logic 112 as, for example, word four), wherein n is a
33 selected integer ranging from -7 to 7. Naturally, it is
I apparent to those of ordinary skill in the art in light of
the teachings of this specification that alternative
36 embodiments of proximity logic 117 can be constructed which
37 will allow selection from a greater number of words or sets,
38
- 63
-64
1 and where the range of proximities can be any desired number,
2 including numbers greater than 7. Furthermore, proximity
3 logic 117 allows detection of words or- sets within a plural-
4 fly of n delimiter characters. Thus, proximity logic 117 is
capable, for example, of detecting when a first selected
6 word or set is located within n sentences, paragraphs,
7 documents, etc., of a second selected word or set.
9 The operation of the embodiment of proximity logic
117 shown in Figure 13 is as follows. Proximity logic 117
11 includes latches 13-2 and 13~5 which are programmed by pro-
12 tramming logic 116 to store address bits which in turn are
13 applied to decoders 13-3 and 13-4, respectively, which
I cause decoders 13-3 and 13~4 to select which delimiter
15 signal will provide clock signals CLUE 13-1 and ILK 13-2,
16 respectively. Itches 13-2 and 13-5 comprise, for example,
17 74374 devices manufactured by National. Latch 13 2 is pro-
18 trammed by programming logic 116 setting onto bus Lola the
19 desired word to be stored, and appropriate address signals
which cause decoder 16 (Figure 12) -to generate a SUE signal.
21 Latch 13-5 is then programmed by programming logic 116
22 setting onto bus aye the desired bits to be stored within
23 latch 13-5, and appropriate address signals A through A to
24 cause decoder 16 to generate a Cell signal. Latch SUE
(also a 74374 device) is then programmed in a similar manner
26 to provide address signals -to decoders 13-8 and 13-9, which
27 in turn each select one of a plurality of word and set
28 signals for use by proximity logic 117, as will be more
29 fully understood with reference to the following discussion.
31 The data stored within latch 13-2 also provides three
32 address bits to decoder 13 6, which causes decoder 13-6 to
33 select the appropriate word or set signal to be applied to
34 the input lead of shift register 13-11. In a similar
fashion, latch 13-10, which is programmed by programming
36 logic 116 when accessed by a SUE signal generated by
37 decoder 16 (Figure 12), provides address signals to decoders
38 13-8 and 13-9 which selects -the appropriate set and word
-65-
1 signals for input to shift registers 13-15 and 13-17. o
Lutz from latch 13-2 and one bit from latch Lowe serve as
3 address input signals to decoder 13-7, thereby select g
4 the appropriate word and set signals for input to shift
register 13-13. Latches 13-2, 13-5, and 13-10 comprise,
for example, 7437~ devices manufactured by National.
7 Decoders 13-3, 13-4, 13-6, 13-7, 13-8, and 13-9 comprise,
8 for example 74151 devices manufactured by National.
lo The operation of shift register 13-11, latch 13-12,
11 and their related components is identical to -the operation
12 of shift register 13-13 and latch 13-14, shift register
13 13-15 and latch 13-16, and shift register 13-17 and latch
14 13-l~, and their related components, and thus only the
operation of shift register 13-11 and latch 13-12 and
16 their associated components will be described here. Shiv'
17 registers 13-11, 13~13, 13-15 and 13-17 comprise, for
18 example 74164 serial in-parallel out shift registers
19 manufactured by National. Latches 13-12, 13-14, 13-16,
and 13-18 comprise, for example, 74374 devices manufactured
21 by National. Latch 13-12 is programmed by programming
22 logic 116 in response to a SUE signal generated by decoder
23 16 figure 12) in response to the appropriate A through
24 A signals provided by programming logic 116. Latch 13-12
stores an eight bit proximity word which defines the
26 desired proximity of the words or sets being searched.
27 Shift register 13-11 stores signals representing the
28 relative position of the set or word selected by decoder
29 151. The wits stored in latch 13-12 indicate which post-
lions within shift register 13-11 are of interest in the
31 search strategy. For example, if it is desired to find
32 word zero within two words of word seven (i.e., "undirected"
33 proximity), programming logic 116 programs latch 13-2 to
34 cause decoder 13 6 to select the We signal, and decoder
I 13-7 to select the We signal. Furthermore, programming
36 logic 116 programs latch 13-12 to store 00000111, and
37 latch 13-14 to store Oily. Programming logic 116
38 programs latch 13 2 to cause decoder :L3-3 to select the
-66-
signal as the CLUE 1 signal, thus causing the We and
2 I signals selected by decoders 13-6 and 13-7, respectively,
3 to be shifted into shift registers 13-1]. and 13-13, respect
4 lively, on each DOW signal.
6 With -the four most significant bits of latch 13-12
7 logical zeros, RAND gates aye through eye are
8 disabled, thereby providing logical one output signals
9 regardless of the contents of the foe most significant
bits of shift register 13-11. However, because the three
11 least significant bits stored in latch 13-12 are logical
12 ones, the output signals from RAND gates 13-19f through
13 13-19h are the logical inverse of the three least signify-
14 cant bits of shift register 13-11. Thus, if a logical one
is stored in any of the three least significant bitts of
16 shift register 13-11, -the output signal from the associated
17 RAND gate 13-19f -through 13-19h is a logical zero, thus
18 causing RAND gate 13-23 to generate a logical one output
19 signal. Thus, when both word zero and word seven appear
within the last three words decoded (i.e., word zero is
21 within two words of word 7), the output signal from RAND
22 gates 13-23 and 13-24 are both logical ones, and thus the
23 output signal from RAND gate aye is a logical zero,
24 indicating that word zero and word seven have been located
within two words of each other.
26
27 In a similar manner, RAND gates 13-27b through 13-27h
28 provide output signal based on the appropriate logical
29 combinations of the output signals from NAY gates i3-23
through 13-26. Latch 13-5 also provides three address
31 signals to decoder 13-28 (which comprises, for example, a
32 74151 device as manufactured by National) which in turn
33 selects the output signals from one of RAND gates aye
34 through 13-27h to provide an interrupt signal on terminal
13-50. This interrupt signal is used to indicate to a
36 central processing unit (not shown) that the text comparator
37 of this invention has detected the occurrence of the
38 desired words or sets of words defined by the search
.;, I,
--67-
strategy, as defined by the output signal from the NAY
gate aye through 13-27h which has been selected by
3 decoder 13-28.
In one embodiment of this invention, proximity logic
6 117 also includes latch 13-29, which comprises, for example
7 a 7437~ device as manufactured by National. Latch 13-29
8 stores the output signals provided by RAND gates aye
9 through 13-27h, and thereby allows the central processing
lo unit (not shown) to determine the value of the signals
I provided by RAND gates aye through 13-27h at any desired
12 time. In one embodiment of this invention, one eight bit
13 word representing the output signals from RAND gates
14 aye through 13-27h is stored in latch 13~29, and is
made available to a central processing unit (not shown on
I Gus Lola.
17
18 Proximity logic 117 is also capable of detecting a
19 so-called "directed" proximity of words or sets of words.
In this event, the eight bit proximity word stored in
21 latches 13-12, 13-14, 13-16, and 13-18 will contain only a
22 single logical one bit, thereby causing proximity logic
23 117 to provide an output signal indicating when a first
24 word or set is located within a precise proximity of a
second selected word or set. Thus, for example, proximity
26 logic 117 can be programmed to detect the occurrence of
27 word zero in a location which is exactly n words after the
I occurrence of word seven, for example, where n is an
29 integer ranging from -7 to +7. Thus, if it is desired to
locate the occurrence of word 0 which is precisely four
31 words after word 7, decoder 13-6 selects word 0, decoder
32 13-7 selects word 7, latch 13-12 stores 00000001, latch
33 13-13 stores 00010000, and decoder 13-28 selects the
34 output signal from RAND gate aye, -thus providing an
interrupt signal on output lead 13-50 when word 0 is
I located exactly four words after word 7.
37
38
~2~5~
-68-
1 Alternatively, if it is desired to locate the occur-
2 fence of word 0 which is precisely four words before word
3 7, decoder 13-6 selected word 0, decoder 13-7 selects word
4 7, latch 13-12 stores 00010000, latch 13-13 stores 00000001,
and decoder 13-2~ selects the output signal from RAND gate
6 aye, thus providing an interrupt signal on output lead
7 13-50 when word 0 is located exactly four words before
8 word 7.
Furthermore, if it is desired to locate -the occurrence
11 Of word 0 which is within four words before word 7 (i.e.,
12 word 0 is the first, second, -third or fourth word before
13 word 7), decoder 13-6 selects word 0, decoder 13-7 selects
14 word 7, latch i3-12 stores 0011110, latch 13-13 stores
00000001, and decoder 13-28 selects the output signal from
16 RAND gate aye, thus providing an interrupt signal on
I output lead 13~5~ when word 0 is located within four words
18 before word 7.
19
It is also understood to one of ordinary swill in the
21 art in light of the teachings of this specification, that
22 proximity logic 117 can be constructed to detect the
23 occurrence of greater combinations of words and sets,
24 merely by expanding the number of latches, decoders, and
shift registers, and logic gates aye through 13-27h, in
26 order to detect more complex search strategies.
27
28 While this specification has explained the operation
29 of this invention in conjunction with several specific
embodiments, it is to be understood that this specific
31 cation is not to operate as a limitation on the scope of
32 the invention. Many other embodiments of this invention
33 will become apparent to those skilled in the art in light
34 of the teachings of this invention.
36
37
38
,.,
