Patent ID: 6069999
Filing Date: 2000-05-30
Classification: G06K,G06T

Abstract:
A computer-implemented method for compressing font data for a printer wherein the font data is stored in a computer memory and includes a plurality of character strings each including information for bit map reproduction of a line of a character, the bit map comprising a map of the character into a plurality of bit positions arranged in lines and columns wherein each bit position represents a binary bit and wherein association of a bit position with a zero indicates no printing in that bit position of the map and association of a bit position with a one indicates printing in that bit position of the map such that printing in each bit position of the map will reproduce the character, the first line of the bit map including information for reproducing the top of the character, the last line including information for reproducing the bottom of the character, the first column including information for reproducing the left side of the character and the last column including information for reproducing the right side of the character, each of the character strings including a character specification number that identifies the configuration and font type of the character, a character header that identifies the height and width of the character and electrically generated binary character data that contains information for bit map reproduction of a line of the character, said method comprising the steps of:(a) restructuring the stored electrically generated binary character data for all characters with eight columns according to a data restructuring technique, the data restructuring technique including the substeps of:(1) restructuring each group of two original lines having eight columns to equal one restructured line having sixteen columns wherein the eight columns from the first original line comprise the first eight columns of the restructured line and wherein the eight columns of the second original line comprise the second eight columns of the restructured line, such that the restructured character string describing the restructured line includes the character specification number and character header of the original first line and includes sixteen bits of electrically generated binary character data; and(2) providing computer logic state zeros in the second eight columns of the last restructured line if the original electrically generated binary character data has an odd number of lines;(b) encoding each character according to a redirection encoding technique, the redirection encoding technique including the substeps of:(1) beginning from the last line and examining each line of each of the exclusive or encoded characters for commonalty thereby to identify a plurality of groups of common characters wherein each group of common characters has a plurality of characters with a plurality of lines that are identical;(2) identifying one character of each group of common characters as the literal character and maintaining its exclusive or encoded electrically generated binary character data in its original exclusive or encoded form;(3) redirection encoding each remaining character of each group of common characters by replacing the common exclusive or encoded electrically generated binary character data with an address indicating the identity of the literal character of the group and the line within the exclusive or encoded literal character to begin reproducing the remainder of the redirection encoded character; and(4) encoding the character header of all characters of a common group except the literal character to indicate redirection encoding;(c) performing a line frequency analysis to determine which lines of all electrically generated binary character data occur with most frequency and providing an index table to record the lines occurring with most frequency;(d) selecting the character to be encoded and identifying the selected character as the subject character;(e) selecting the line of the subject character to be encoded and identifying the line as the subject line;(f) determining whether the subject line is an indexed line and, if so, selecting indexing as the preliminary encoding technique and performing step j;(g) determining the length of one run encoded data for the subject line wherein the length of one run encoded electrically generated binary character data may be determined by adding six to two times the ceiling of (log.sub.2 x) and adding the number of bits which need to be added as a prefix to indicate one run encoded data, and dividing the sum by eight, wherein x equals the number of bytes in the subject line;(h) determining the length of Group encoded data for the subject line wherein the length of Group encoded data may be determined by adding one, x, 8(r) and the number of bits which need to be added as a prefix to indicate Group encoded data, subtracting the floor of (r/4) from this sum, and dividing the resultant number by eight, wherein x equals the number of bytes in the subject line;(i) determining the length of literal encoded data for the subject line wherein the length of literal encoded data for the subject line equals the length of the subject line;(j) determining the length of quote encoded data for the subject line wherein the length of the quote encoded data equals the length of the subject line plus a prefix necessary to identify quote encoded data;(k) selecting as the preliminary encoding technique for each character string the encoding technique of steps (g)-(j) which yield the shortest encoded data length;(l) determining whether the subject line is a duplicate of the previous line of the subject character, and if so, determining the number of subsequent duplicate lines of the subject character and the length of encoding all duplicates according to duplicate encoding, and if not, selecting the preliminary encoding technique as the encoding technique for the line and performing step (m);(m) determining whether the length of encoded data according to duplicate encoding is less than encoding according to the preliminary encoding technique, and if so, selecting duplicate encoding as the encoding technique for the subject line and all subsequent duplicate lines of the subject character, and if not, encoding the subject line according to a duplication technique, the duplication encoding technique including the substeps of:(1) encoding the data of the subject line to indicate duplication encoding and the number of times the data is duplicated; and(2) performing step (n);(n) encoding the data according to the preliminary encoding technique as follows;(1) encoding according to the literal encoding technique by not altering the data of the subject line;(2) encoding according to the quote encoding technique by providing a prefix to indicate quote encoding and not altering the data of the subject line;(3) encoding according to the one run encoding technique by providing a first byte of data to indicate at which column a group of contiguous computer logic state ones begins, providing a second byte of the data to indicate at which column the group of contiguous computer logic state ones ends and providing a prefix to indicate one run encoding; and(4) encoding according to the Group encoding technique by providing a prefix to indicate whether the first bit position of the electrically generated binary character data is a one or computer logic state zero, and, sequentially with respect to each group of contiguous computer logic state ones and computer logic state zeros:(i) providing a one for each set of eight contiguous computer logic state ones or computer logic state zeros and deleting one bit from the set of contiguous computer logic state ones or computer logic state zeros;(ii) providing a computer logic state zero if the number of contiguous computer logic state ones or computer logic state zeros remaining after step (n)(4)(i) is less than eight;(iii) providing a modulo eight binary representation of the number of contiguous computer logic state ones or computer logic state zeros, less than eight, minus one remaining after step (n)(4)(i);(iv) providing computer logic state ones for each group of eight or less contiguous computer logic state ones or computer logic state zeros that comprise the last set of contiguous computer logic state ones or computer logic state zeros; and(v) providing a electrically generated binary character data prefix to indicate Group encoded electrically generated binary character data;(o) determining whether all lines of the subject character have been encoded and if not performing step e, and if so performing step (p); and(p) determining whether all characters have been encoded and if not performing step d.