[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Hey, Rob!
How did you implement Auto Spell mode for Hemlock?
Did you use something like what is described below?
Also, how do you feel about patents on Software?
How do you feel about LPF and RMS?
(and TLAs (three letter acronyms, lots of them at DEC))
-pk.
Article 41 of gnu.emacs.announce:
From: rms@gnu.ai.mit.edu (Richard Stallman)
Newsgroups: gnu.announce,gnu.emacs.announce,gnu.gcc.announce,gnu.g++.announce,gnu.misc.discuss
Subject: another outrageous patent
Message-ID: <9203240339.AA09461@mole.gnu.ai.mit.edu>
Date: 24 Mar 92 03:39:16 GMT
Reply-To: lpf-patent-4783761@gnu.ai.mit.edu
Followup-To: poster
Lines: 244
Approved: info-gnu@prep.ai.mit.edu
To: info-gnu@prep.ai.mit.edu, info-gnu-emacs@prep.ai.mit.edu,
info-gcc@prep.ai.mit.edu
[Please repost this message as widely as possible.]
Here is a patent that, if valid, could make it impossible to extend
GNU Emacs in a useful way at some time in the future.
It is also outrageous in that it covers things that any programmer
would consider obvious.
The basic idea is that you have a dictionary stored as a branching
tree of words with common prefixes. As you read characters, you look
them up in the tree and advance through it. If you get something that
isn't the beginning of a word, you know right away. Simple, no?
We are looking for anything that might serve as prior art to
defeat the patent.
Valid prior art consists of disclosure to the public of a technique
that is covered by the patent. If you wrote a program using the
technique, that may not count at all if you didn't tell the public
about the technique. (But it might count, especially if an
intelligent user running the program could tell what it was doing.)
On the other hand, if the ideas themselves were published, then
there's no need to have written a program as well: just the
publication is sufficient.
In order to be "prior", the disclosure has to be before the date of
the patent application. In this case, 26 Dec 1985.
Since the point of prior art is to use it in a court case, it is
important to find something that we can *prove* was disclosed. We
wouldn't want to go into court asking the jury to take one person's
word for it. We'd like something that many people saw, or something
that was published in on paper at a date we can substantiate, etc.
(If the example you have in mind was a widely-used program or product,
then we can probably find a description on paper somewhere if we look
hard enough.)
If you have prior art, don't tell the net--just tell us. If the
patent holder finds out about the prior art, they could have the
patent reexamined in an effort to nullify the prior art.
Please send your replies to lpf-patent-4783761@prep.ai.mit.edu, not to
me personally.
UNITED STATES PATENT #4,783,761
TITLE: Spelling Check Dictionary with Early Error Signal
GRANTED: 8 Nov 1988
FILED: 26 Dec 1985 (application #813,351)
ABSTRACT:
A method and apparatus for adding a low-cost spelling check
dictionary feature to document preparation systems such as portable
electronic typewriters, the spelling check being performed on a
character-by-character basis and an error signal emitted upon the
earliest determination that an input character does not conform to
that of any word listed in the dictionary. Semiconductor ROM is used
for storage of the dictionary listing and for program control of the
spelling check. Text compression methods are utilized to permit
storage of large vocabularies (about 35,000 words) while minimizing
the ROM capacity required (about 3 IC's of 256K bits each).
CLAIMS:
1. A dictionary storage apparatus containing a word list used to
verify the spelling order of character inputs comprising:
(a) input means for receiving character inputs;
(b) a first storage means for storing character information structured
to sequentially check the spelling order of a first predetermined
series of received character inputs;
(c) a second storage means extending from said first storage means
and containing further character information structured to check the
spelling order of a variable string of character inputs strung from
said predetermined series to validate spelling of words; and
(d) signal output means connected to said first and second storage
means for generating a signal immediately in response to a received
character input being out of spelling order as structured in said
first and second storage means.
2. A dictionary storage apparatus for use with a source of
characters, the apparatus containing a list of correctly-spelled
words for verifying the spelling order of character inputs,
comprising:
(a) word terminators in said list, one said terminator
distinguishing each complete word therein,
(b) input means for receiving character inputs in a first code
format,
(c) a first storage means for storing character information
structured to sequentially check the spelling order of a first
predetermined series of received character inputs, said character
information in said first storage means being in said first code
format and held in a plurality of bytes, one character per byte, and
comprising a succession of character sequences having at least two
characters therein, a first character selected from all characters of
the alphabet and groups identified by a particular one of said first
characters in combination with at least one other alphabetic
character, at least some of said groups being less in number than the
entire alphabet;
(d) a second storage means extending from said first storage means
and containing further character information structured to check the
spelling order of a variable string of character inputs strung from
said predetermined series to validate spelling of words, said further
character information in said second storage means comprises a tree
structure with a plurality of branches, each of said branches
stemming from a discrete one of said sequences in said first storage
means and at least one word remnant being associated with said
discrete one sequence, said word remnant containing at least one
character held in a second code format and being followed by said
word terminator;
(e) normally disabled means decoding said second code format into
said first code format, said means for decoding being enabled at the
end of each said discrete one sequence;
(f) comparison means operable upon receipt of each said character
input and effective to check agreement between the received one of
said character inputs and ordinally corresponding ones of said
character information as to words stored in said first storage means
and in said second storage means, and
(g) signal output means connected to said first and second storage
means for generating a signal immediately in response to a received
character input being out of spelling order as structured in said
first and second storage means and determined by said comparison
means.
3. The dictionary storage apparatus of claim 2, wherein said
character inputs include an end-of-word input, a plurality of word
remnants is associated with said discrete one sequence and held in
said second code format; a last one of said plurality being followed
by a said word terminator; and said output means are operable to
generate said signal upon receipt of a character input other than
said end-of-word input in ordinal correspondence with the word
terminator following said last word remnant.
4. The dictionary storage apparatus of claim 2, wherein at least
one said sequence includes a said word terminator, said second format
is a compressed code format having variable numbers of bits for the
different characters, some characters having a bit-length in excess
of a byte, and said word terminator has a discrete code in said first
format and said second format.
5. The dictionary storage apparatus of claim 2, wherein said first
code format requires less than all bits of said byte to distinguish
said characters, at least one bit being in excess, and said decoding
means for said second code format is enabled in response to a
predetermined state of said excess one bit.
6. The dictionary storage apparatus of claim 5, wherein said first
code format stores said character code in the less significant five
bits of said byte and the set state of the most significant bit of
said byte indicates the ordinal position for enabling said second
code format decoding means.
7. The dictionary storage apparatus of claim 6, wherein said
second code format decoding means includes means counting bytes and
bits occupied by the variable numbers of bits in given codes.
8. A dictionary storage apparatus for use with a source of
characters, the apparatus containing a list of correctly-spelled
words for verifying the spelling order of character inputs,
comprising:
(a) input means for receiving character inputs,
(b) an end-of-word input among said characer inputs,
(c) a starting address for said word list,
(d) a first storage means for storing character information
structured to sequentially check the spelling order of a first
predetermined series of received character inputs, said character
information in said first storage means being held in groups by
alphabetic order of association in particular sets of character
combinations having a predetermined number of characters,
(e) a second storage means extending from said first storage means
and containing further character information structured to check the
spelling order of a variable string of character inputs strung from
said predetermined series to validate spelling of words, said further
character information in said second storage means comprising a tree
structure with a plurality of branches, each of said branches
stemming from a discrete one of said sets and holding a plurality of
character-containing word remnants associated with said discrete one
set;
(f) means for sequentially scanning said character information,
beginning with said starting address;
(g) signal output means connected to said first and second storage
means for generating a signal immediately in response to received
character input being out of spelling order as structured in said
first and second storage means and determined by said comparison
means,
(h) a word terminator code marking the end of each word in said
character information stored in said first storage means and in said
second storage means, and
(i) further means operable to return said scanning means to said
starting address in response to receipt of said end-of-word input
while scanning said word terminator code marking the end of a word in
said list.
9. The dictionary storage apparatus of claim 8, further including
an end-of-table character, and wherein said first and second storage
means include blocks of a register, each branch having said character
information therein stored in a respective block, at least some
characters of said word remnants being found in separate,
random-length word portions hierarchically interspersed in said block
in accordance with the order of the alphabet, and said word
terminator following a last word remnant in each branch being
followed in turn by said end-of-table character.
10. A method of checking the spelling of words entered into a
record by a keyboard operator, comprising the steps of:
(a) compactly storing a list of words in a first multi-character
memory device,
(b) entering a string of characters into a second memory device,
each character of said string representing an element at a next
higher ordinal position in a word said operator desires to enter in
said record,
(c) scanning discrete portions of said first memory device
concomitantly with each entry of a further character of said string,
(d) responsive to each said entry, comparing said further
character with a succession of scanned characters at a corresponding
ordinal position in each word of said list stored in said first
memory device, previous characters in said each word matching
previously entered characters of said string, and
(e) issuing a distinctive signal immediately upon determining
existence of a mismatch between said further character and said
succession of scanned characters at said corresponding ordinal
position.
11. The method of claim 10, wherein said storing step is effected
in two stages:
(i) a first stage storing preselected permutations of a
predetermined number m of alphabetic characters appearing as an
initial sequence only in words of said list, said permutations being
arranged in alphabetically-ordered sets and subsets, each m-th
character of a sequence being an argument of a look-up table having a
corresponding address value indicative of the starting location of an
alphabetically-ordered subset of (m + 1)th characters forming an
individual group, with each (m + 1)th character of the augmented
sequence being an argument of a further look-up table having a
corresponding address value indicating start of a further
alphabetically ordered set of n characters having a particular one of
said m + 1 character permutations in common; m being less than or
equal to n, but greater than or equal to 1;
(ii) a second stage storing a plurality of word remnants, each
remnant containing at least one further character completing a word
of said word list, and being comprised in said set of n characters
combined with said particular one of the permutations.
----------------------------------------------------------------------