EP0083393A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method of compressing information and an apparatus for compressing English text
Assignee: Unisys Corp
•
Filing: 1982-09-25
•
Granted: —
•
Expires: 2002-09-25
Abstract
Abstract There is described a method of storing alphanumeric text in a random access memory or disk file where the text is received as a string of ASCII coded characters that are then separated into tokens which may be either groups of alpha characters, numeric characters or punctuation characters. Each alpha token is encoded by comparing the token with a table of words stored in a global dictionary. If present in the dictionary, the token is stored in the memory as two or three four-bit nibbles which identify its location in the dictionary. if not in the dictionary, the characters in the front of the token are compared with a list of word beginnings or prefixes. If a match is found, two nibbles are stored in the random access memory identifying the prefix, the prefix characters are stripped from the token, and the process is repeated. If no more prefixes are found, the end of the word is matched against a stored group of word endings or suffixes. Two nibbles are stored in the random access memory identifying the suffix, and the suffix characters are stripped from the token. The suffix matching is repeated on the remaining ending characters of the token. If there are no more identifiable suffixes, the number of characters remaining in the stem of the token is determined. After all letters are removed by identifying all suffixes, the remaining stem is encoded as one or two nibbles for each letter plus a nibble identifying the length of the stem. If no suffix was identified, a nibble is stored indicating that the stem is either four or five characters in length, or the actual length of the stem is stored as an additional nibble. After the stem length has been encoded, the individual letters of the stem are encoded by one or two nibbles for each letter as determined from tables of individual characters.
Inventors
- 👤 Craig Adam Snow
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-27 19:24
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; G; G06; G06F; G06F40/00; G06F40/10; G06F40/12; G06F40/126; G06F40/20; G06F40/237; G06F40/242; G06F40/268; G06F40/279; G06F40/284
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
84 words
A method of compressing information by coding and storing alphabetic characters forming an individual word as a string of four-bit units, comprising: storing in a first table a plurality of commonly used words, locating the individual word in the table, storing a group of units in the memory in response to a match with a word in the first table, and coding the stored units to indicate the word is in the first table and the location of the word in the first table.
Claim 2
Independent Claim
84 words
A method of compressing information by coding and storing alphabetic characters forming an individual word as a string of four-bit units, comprising: storing in a first table a plurality of commonly used words, locating the individual word in the table, storing a group of units in the memory in response to a match with a word in the first table, and coding the stored units to indicate the word is in the first table and the location of the word in the first table.
Claim 3
Dependent Claim
142 words
The method of claim 1 further including the steps of: storing in a second table a plurality of common prefixes, comparing successive groups of characters at the beginning of said individual word being compressed with the prefixes in the second table when the full word is not present in the first table, storing a string of at least two four-bit units in the memory in response to a match between a group of characters in the word being compressed and a prefix in the second table, coding the stored units to indicate the prefix is in the second table and the location of the prefix in the second table, and storing additional units in the memory indicating the number of characters and the value of each character not part of a group of characters matched with a prefix in the second table.
Claim 4
Dependent Claim
105 words
The method of claim 2 further including the steps of: storing in a third table a plurality of suffixes, comparing successive groups of characters at the end of a word being compressed with suffixes in the third table when the full word is not present in the first table, storing a string of at least two units in the memory in response to a match between a group of characters in the word being compressed and a suffix in the third table, coding the stored units to indicate the suffix is in the third table and the location of the suffix in the third table.
Claim 5
Independent Claim
290 words
A method of storing alphanumeric text in a random access memory where the text is received as a string of characters, each coded as a standard eight-bit byte, comprising the steps of: separating the string of characters into groups, comparing a selected group of characters with a first table of stored groups of characters, storing a digit indicating the group of characters is in the first table and storing the address of the group of characters in the first table'in the random access memory if a comparison between the selected group and a group in the table is found, comparing a first portion of the selected group of characters with a second table of stored groups of characters if all the characters of the selected group do not compare with any group of characters in the first table, storing a digit indicating a portion of the selected groups is in the second table and the address of the group of characters in the second table in the random access memory if said group is the same as said first portion of the selected group, comparing a second portion of the selected gorup with a third table of stored groups if all the characters in said first portion do not compare with any group of characters in the second table, storing a digit indicating a portion of the selected group is in the third table and storing the address of the group in the third table in the random access memory if said group is the same as the second portion of the selected group, storing the number of the remaining characters not found in the tables, and storing the remaining individual characters in coded form in the random access memory.
Claim 6
Independent Claim
290 words
A method of storing alphanumeric text in a random access memory where the text is received as a string of characters, each coded as a standard eight-bit byte, comprising the steps of: separating the string of characters into groups, comparing a selected group of characters with a first table of stored groups of characters, storing a digit indicating the group of characters is in the first table and storing the address of the group of characters in the first table'in the random access memory if a comparison between the selected group and a group in the table is found, comparing a first portion of the selected group of characters with a second table of stored groups of characters if all the characters of the selected group do not compare with any group of characters in the first table, storing a digit indicating a portion of the selected groups is in the second table and the address of the group of characters in the second table in the random access memory if said group is the same as said first portion of the selected group, comparing a second portion of the selected gorup with a third table of stored groups if all the characters in said first portion do not compare with any group of characters in the second table, storing a digit indicating a portion of the selected group is in the third table and storing the address of the group in the third table in the random access memory if said group is the same as the second portion of the selected group, storing the number of the remaining characters not found in the tables, and storing the remaining individual characters in coded form in the random access memory.
Claim 7
Dependent Claim
36 words
The method of claim 4 further including the steps of: coding the individual characters as a single 4-bit unit or as two 4-bit units depending on the location of the character in a table of characters.
Claim 8
Dependent Claim
35 words
The method of claim 5 further including the step of: determining which character, if any, preceded the character being coded, and selecting a different table of characters depending on the value of the preceding character.
Claim 9
Independent Claim
120 words
The method of compressing and storing information in the form of successive characters received as ASCII coded 8-bit bytes, by converting the information to strings of 4-bit nibbles, comprising the steps of: decoding each byte in succession to determine if it is an alpha type character, a numeric type character, or a punctuation type character, storing successive characters of the same type as a group, encoding a group of numeric characters as a string of 4-bit nibbles in which the first nibble is coded to indicate the number of numeric characters in the group and each successive nibble is coded to indicate the value of each successive numeric character in the group, and storing the string of encoded 4-bit nibbles.
Claim 10
Independent Claim
120 words
The method of compressing and storing information in the form of successive characters received as ASCII coded 8-bit bytes, by converting the information to strings of 4-bit nibbles, comprising the steps of: decoding each byte in succession to determine if it is an alpha type character, a numeric type character, or a punctuation type character, storing successive characters of the same type as a group, encoding a group of numeric characters as a string of 4-bit nibbles in which the first nibble is coded to indicate the number of numeric characters in the group and each successive nibble is coded to indicate the value of each successive numeric character in the group, and storing the string of encoded 4-bit nibbles.
Claim 11
Dependent Claim
71 words
The method of claim 7 further including the steps of: comparing a stored group of punctuation or alpha characters with a plurality of different groups of characters stored as words in a dictionary table, encoding the group of punctuation or alpha characters as a string of 4-bit nibbles which identify the location of the same group of characters if present in the table, and storing the string of encoded 4-bit nibbles.
Claim 12
Dependent Claim
149 words
The methof of claim 7 further including the steps of: determining when a group of alpha characters is not found in the dictionary table, comparing the beginning characters of the group with a plurality of beginning character combinations stored in a prefix table, encoding the beginning characters as a plurality of 4-bit nibbles indicating the location of the corresponding prefix in the prefix table if present in the prefix table, comparing the ending characters of the group of alpha characters with a plurality of ending characters stored in a suffix table, encoding the ending characters as a plurality of 4-bit nibbles indicating the location of the ending characters as a plurality of 4-bit nibbles, comparing each of any remaining characters with a set of characters in a character table, and encoding the character as one or more 4-bit nibbles indicating the location of the character in the character table.
Claim 13
Dependent Claim
38 words
The method of claim 9 further including the steps of: providing a separate character table of characters for each alpha character, and selecting one of the character tables corresponding to the preceding character in the group being encoded.
Claim 14
Independent Claim
270 words
A method of encoding alpha character words in which the individual characters of the words are initially coded in ASCII coded 8-bit bytes, comprising the steps of: storing a set of word beginning character combinations in a prefix memory, comparing the beginning characters of the word being encoded with each of the beginning character combinations in the prefix memory to determine if the beginning characters of the word are present in the prefix table, generating and storing a binary coded value indicating that the beginning characters of the word are in the prefix memory and indicating the location in the prefix memory if the beginning characters are present in the prefix table, deleting the beginning characters from the alpha word if they are present in the prefix memory, storing a set of word ending character combinations in a suffix memory, comparing the ending characters of the word being encoded with each of the ending character combinations in the suffix memory, generating and storing a binary coded value indicating that the ending character combination of the word is in the suffix table and indicating the location of the word in the suffix memory, deleting the ending characters from the alpha character word if they are present in the suffix memory, storing at least one set of all the alpha characters in a predetermined sequence in a character memory, generating and storing a binary coded value indicating the number of characters remaining in the alpha word being encoded, and generating and storing a binary coded value for each of the remaining characters indicating the location of the character in the character memory.
Claim 15
Independent Claim
270 words
A method of encoding alpha character words in which the individual characters of the words are initially coded in ASCII coded 8-bit bytes, comprising the steps of: storing a set of word beginning character combinations in a prefix memory, comparing the beginning characters of the word being encoded with each of the beginning character combinations in the prefix memory to determine if the beginning characters of the word are present in the prefix table, generating and storing a binary coded value indicating that the beginning characters of the word are in the prefix memory and indicating the location in the prefix memory if the beginning characters are present in the prefix table, deleting the beginning characters from the alpha word if they are present in the prefix memory, storing a set of word ending character combinations in a suffix memory, comparing the ending characters of the word being encoded with each of the ending character combinations in the suffix memory, generating and storing a binary coded value indicating that the ending character combination of the word is in the suffix table and indicating the location of the word in the suffix memory, deleting the ending characters from the alpha character word if they are present in the suffix memory, storing at least one set of all the alpha characters in a predetermined sequence in a character memory, generating and storing a binary coded value indicating the number of characters remaining in the alpha word being encoded, and generating and storing a binary coded value for each of the remaining characters indicating the location of the character in the character memory.
Claim 16
Independent Claim
76 words
A method of decoding compressed information in the form of words stored as 4-bit nibble strings, comprising the steps of: decoding the first nibble of a string to determine if the word represented by the nibble string is in a dictionary table, addressing and reading out the word from the table using the first nibble and the next nibble in the string as an address if the first nibble indicates the word is in the table.
Claim 17
Independent Claim
76 words
A method of decoding compressed information in the form of words stored as 4-bit nibble strings, comprising the steps of: decoding the first nibble of a string to determine if the word represented by the nibble string is in a dictionary table, addressing and reading out the word from the table using the first nibble and the next nibble in the string as an address if the first nibble indicates the word is in the table.
Claim 18
Dependent Claim
72 words
The method of claim 12 further comprising the steps of: decoding the first nibble to determine if the decoded word represented by the nibble string was a numeric word, decoding the second nibble to determine the number of digits in the word being decoded if the first digit indicates a numeric string, and decoding as digits an additional number of nibbles corresponding to the number of digits indicated by the second nibble.
Claim 19
Independent Claim
210 words
A method of decoding a compressed word of information stored as a string of 4-bit nibbles into a set of ASCII coded 8-bit bytes wherein the value and relative sequential position of the respective nibbles in the string is used to select the bytes, comprising the steps of: determining the value of the first nibble in the string; if the first nibble is a first predetermined value, using the second nibble to address a first table of ASCII coded character combinations forming the beginning of words; storing the addressed combination of characters from the first table a the prefix of the word; if the first nibble is a second predetermined value, using the second nibble to address a second table of ASCII coded character combinations forming the ending of words; storing the addressed combination of characters from the second table as the suffix of the word; if the first nibble is either said first or said second predetermined value and the third nibble is a third predetermined value, using the fourth nibble to count out a corresponding number of succeeding nibbles; using each of said succeeding nibbles to address a table of individual ASCII coded characters; and storing the addressed characters from the table as the stem of the word.
Claim 20
Independent Claim
210 words
A method of decoding a compressed word of information stored as a string of 4-bit nibbles into a set of ASCII coded 8-bit bytes wherein the value and relative sequential position of the respective nibbles in the string is used to select the bytes, comprising the steps of: determining the value of the first nibble in the string; if the first nibble is a first predetermined value, using the second nibble to address a first table of ASCII coded character combinations forming the beginning of words; storing the addressed combination of characters from the first table a the prefix of the word; if the first nibble is a second predetermined value, using the second nibble to address a second table of ASCII coded character combinations forming the ending of words; storing the addressed combination of characters from the second table as the suffix of the word; if the first nibble is either said first or said second predetermined value and the third nibble is a third predetermined value, using the fourth nibble to count out a corresponding number of succeeding nibbles; using each of said succeeding nibbles to address a table of individual ASCII coded characters; and storing the addressed characters from the table as the stem of the word.
Claim 21
Dependent Claim
100 words
Apparatus for compressing English text coded as a sequence of ASCII coded 8-bit bytes as strings of 4-bit nibbles comprising: means storing a group of bytes corresponding to one word of text, means comparing the group of bytes with groups of bytes in a dictionary table representing a list of words, means responsive to the comparing means for signaling whether or not the group of bytes is in the dictionary table, means responsive to the signaling means for generating at least two nibbles identifying the location of the group bytes in the dictionary, and means storing the generated nibbles sequentially.
Claim 22
Dependent Claim
100 words
Apparatus for compressing English text coded as a sequence of ASCII coded 8-bit bytes as strings of 4-bit nibbles comprising: means storing a group of bytes corresponding to one word of text, means comparing the group of bytes with groups of bytes in a dictionary table representing a list of words, means responsive to the comparing means for signaling whether or not the group of bytes is in the dictionary table, means responsive to the signaling means for generating at least two nibbles identifying the location of the group bytes in the dictionary, and means storing the generated nibbles sequentially.
Claim 23
Dependent Claim
284 words
Apparatus of claim 15 further including: means responsive to the signaling means when the stored group of bytes is not present in the dictionary table for comparing the beginning bytes of the stored word with group? of bytes stored in a prefix cable, means responsive to the comparing means for signaling whether or not the group of bytes is in the prefix table, means responsive to the signaling means for generating at least two nibbles identifying the location of the beginning group of bytes in the prefix table, means removing the beginning group of bytes from the stored word of text, means responsive to the signaling means when the beginning bytes are not in the prefix table for comparing the ending bytes of the stored word with groups of bytes stored in a suffix table, means for signaling whether or not the ending group of bytes is in the prefix table, means responsive to the signaling means for generating at least two nibbles identifying the location of the ending group of bytes in the suffix table, means removing the ending group of bytes from the stored word, means responsive to the signaling means when the ending bytes are not in the suffix tables for counting the number of remaining bytes of the stored word, means generating a nibble indicating the counted number of remaining bytes, means responsive to each of said remaining bytes in sequence for comparing each byte with all characters stored in character table, means responsive to the comparing means for generating at least one nibble for each byte identifying the location of the same byte in a table of characters, and means storing each of said generated nibbles in predetermined sequence.
Claim 24
Dependent Claim
77 words
Apparatus of claim 16 further including means for storing a plurality of tables of characters coded as bytes, each table having a portion of the characters addressable by a single nibble and a portion of the character addressable by two nibbles, the characters stored respectively in the two portions being different for each table, means for selecting one of the tables to operate with said means for comparing each byte with characters stored in a character table.
Claim 25
Dependent Claim
68 words
Apparatus of claim 17 further including means responsive to the value of the byte in the stored group preceeding the byte being compared for selecting one of said plurality of character tables, each character having an associated table of characters arranged in the two portions of the table according to the frequency in which each character in the table follows the associated preceeding character in standard English words.
Claim 26
Dependent Claim
83 words
Apparatus of claim 15 further comprising: means sensing when the stored group of bytes are numeric characters, means responsive to said sensing means for counting the number of bytes in the stored group of bytes, means generating a first nibble coded to indicate the word is numbers means generating a second nibble coded to indicate the number of bytes counted, and means generating an additional nibble for each numeric byte coded to indicate the corresponding digit value, the generated nibbles being stored sequentially.
Claim 27
Dependent Claim
107 words
Apparatus of claim 15 further including means sensing when the stored group of bytes are punctuation characters, means responsive to the signaling means and the sensing when the stored group of bytes is not in the dictionary table and the stored group of bytes are punctuation characters for counting the number of bytes in the stored group of bytes, means generating at least two nibbles coded to indicate that the bytes are punctuation and not in the dictionary table, means generating a nibble indicating the number of bytes counted, and means storing said generated nibbles followed by all the bytes in their ASCII coded form in sequence.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.