V
DETAILED ACTION
Claims 20 and 39-40 interpreted under 35 USC §112(f).
Claims 1-16, 20, and 39-41 rejected under 35 USC §101, as directed to an abstract idea.
Claim 41 rejected under 35 USC §101, as directed to non-statutory subject matter.
Claims 1-16, 20, and 39-41 rejected under 35 USC §103.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder (i.e., unit) that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are:
Claim 20: “a list constructing unit” and a “first compression unit” configured to perform functions. Claims 39-40 are dependent on claim 20 and subject to the same claim interpretation.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-16, 20, and 39-41 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claims 1, 20, and 39-41
[Step 1] Claims 1, 20, 39-41 recite a method, system, chip, device, and/or medium for performing a process comprising steps of (1) constructing a word list based on word length and frequency, and (2) compressing text using the word list.
[Step 2A – Prong One] The process recited in claims ## are directed to an abstract idea. The recited limitations (1) and (2) are a process that, under its broadest reasonable interpretation, covers mental processes including "observations, evaluations, judgments, and opinions" that "can be performed in the human mind, or by a human using a pen and paper" MPEP 2106.04(a)(III). The step of (1) is accomplished by a human reading a small excerpt of text and using reading comprehension to write a list of each word, the length of each word, and the frequency read of each word. The step of (2) is accomplished by a human arbitrarily assigning codes to given words based on frequency and length. The claim does not recite any particular means of compression, so the claim encompasses any mental means of arbitrarily encoding text to make it shorter.
[Step 2A – Prong Two] Claims 1, 20, and 39-41 do not recite additional elements that integrate the judicial exception into a practical application. The additional elements recited include computer hardware (e.g. processor and memory); these additional elements are merely instructions to implement an abstract idea on a computer. MPEP 2106.04(d). Further, the claim limitations attempt to cover any solution for shortening text based on word length and frequency, without providing a particular solution or way to achieve a desired outcome. See MPEP 2106.05(f)(1).
[Step 2B] Claims 1, 20, and 39-41 do not recite a combination of elements that amount to significantly more than the judicial exception itself. The broadest reasonable interpretation of the process comprising limitations (1) and (2) is a mental process. The additional elements recited are merely instructions to implement the mental process on a computer. Accordingly, these limitations are not enough to qualify as "significantly more" when recited with a judicial exception (i.e. the mental process). MPEP 2106.05(A). Further, these claim limitations fail to improve the functioning of the computer itself, because "a claim whose entire scope can be performed mentally, cannot be said to improve computer technology." See MPEP 2106.05(a)(I). The additional elements of constructing a list are recognized as well-understood, routine, and conventional activity of storing and retrieving information in memory. See MPEP 2106.05(d)(II)(iv).
Claim 2
The additional step of dividing text using delimiters does not render the judicial exception as a practical limitation or make a combination that is significantly more than the judicial exception because the step is drawn to an abstract idea as a mental process. The step of dividing text using delimiters is accomplished by a human using reading comprehension to determine when words start and end.
Claims 3-4, 8, 11, and 15
The additional elements of describing the specific data structure formats do not integrate the judicial exception into a practical application, because it only amounts to insignificant extra-solution activity of data output (i.e. store the data into a document). See MPEP 2106.05(g). This additional element does not recite significantly more than a judicial exception, because it is recognized as well-understood, routine, and conventional activity of storing and retrieving information in memory. See MPEP 2106.05(d)(II)(iv).
Claims 5-7, 9-10, 12-14, and 16
The additional steps of traversing words in a document and performing comparisons procedures on each word does not render the judicial exception as a practical limitation or make a combination that is significantly more than the judicial exception because the step is drawn to a mental process. The step of traversing the texts, combining words, and replacing words with a coded value is directed to “collecting information, analyzing it, and displaying certain results of the collection and analysis,” and the steps themselves “are recited at a high level of generality such that they could practically be performed in the human mind.” See MPEP 2106.04(a)(2)(III)(A).
Claim 41
Claim 41 is rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter. The claim(s) does/do not fall within at least one of the four categories of patent eligible subject matter because the claim is drawn to signals per se. A transitory signal, while physical and real, "does not possess concrete structure" and "is not composed of matter." MPEP 2106.03. The present specification is silent as reciting the bounds of “storage medium.” Accordingly, claim 41 is directed to non-statutory subject matter because the claimed “storage medium” is interpreted to include transitory signal embodiments.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-16, 20, and 39-41 are rejected under 35 U.S.C. 103 as being unpatentable over Suzuki, U.S. PG-Publication No. 2018/0336217 A1, in view of Millett, U.S. Patent No. 5,913,209.
Claim 1
Suzuki discloses a text compression method. Suzuki discloses a method that “compresses symbolic information that is organized into a plurality of documents,” wherein documents are “a string of symbol of any length (e.g., a sentence, paragraph, or text file)” and symbols are “code that constitutes of carries information (e.g., a letter, number, non-alphanumeric character, syllable, or word).” Suzuki, ¶ 3.
Suzuki discloses the method, comprising: performing word segmentation processing on texts to be compressed. The method “identifies and counts all occurrences of unique original symbols and stores each unique original symbol” and each original symbol is “stored in a standardization memory.” In one embodiment, identifying original symbols is performed by interpreting “certain non-alphanumeric characters (e.g., a space) as denoting a break between two symbols,” wherein the method “interprets a space as a break between symbols” (i.e., segmenting words based on spaces). Id. at ¶¶ 21-22.
Suzuki discloses collecting statistics about … and word frequency of the words obtained after the word segmentation processing to construct a corresponding keyword list. Suzuki discloses that standardization memory 140 “associated an original symbol (in column 160) with its respective standard symbol (in column 150) and a count of hoe many times each original symbol appears in the uncompressed text (in column 170).” Id. at ¶ 21; FIG. 1. The standardization memory 140 “sorts the entries ... according to the counts stored in column 170,” so that the method “can assign shorter standard symbols to the symbols that appear most frequently.” Id. at ¶ 28. Figure 2 illustrates “compression dictionary 200” used “to store associations between a unique symbol pair and its replacement symbol” (compression dictionary 200 → keyword list). Id. at ¶ 32. Compression dictionary 200 stores “the count associated with each symbol,” and may “sort the entries … based on the counts of each symbol pair … before assigning replacement symbols or making any replacements to produce document 321.” Id. at ¶¶ 40-43.
Suzuki discloses compressing the texts to be compressed based on the constructed keyword list. The method “produces a compressed output document by replacing symbol pairs with their associated replacement symbols if the count for the symbol pair exceeds a threshold,” and then may “repeat the compression process by using the output document as an input document for an additional pass,” then “recursively perform additional passes until no further replacements can be made.” Id. at ¶¶ 4-6. Compression dictionary 200 comprises replacement symbols that are “an address … where the symbol pair associated with the replacement symbol is stored,” wherein “replacement symbols from the first pass are inserted into output documents and stored in the compression dictionary.” Id. at ¶¶ 44-45. In one embodiment, the method “only uses replacement symbols if their associated count exceeds a predetermined threshold.” Id. at ¶ 47.
Suzuki does not expressly disclose collecting statistics about word length of the words obtained after the word segmentation processing to construct a corresponding keyword list.
Millett discloses collecting statistics about word length of the words obtained after the word segmentation processing to construct a corresponding keyword list. Millett discloses a “method … for compressing a text index to recover disk space, “ in order “to provide a text index compression system which executes very quickly.” Millett, 2:46-51. The method “reads each word of the selected documents” and “for each unique word … the index records the ‘granules’ in which the word is found,” wherein a granule “may be any grouping of words within a document or set of documents.” Id. at 4:23-31. The method builds two primary data structures “the in-memory Word List and the [Non-Repeating Word Number Stream] NRWNS,” wherein the NRWNS stored ”sequentially a representation of the stream of words found in the set of documents, each word being represented by a unique word number.” Each word in the Word List “is stored as a node of a binary tree.” Each node of the binary tree comprises fields of: ‘(1) flags for memory control; (2) a pointer to the left tree node (or NULL); (3) a pointer to the right tree node (or NULL); (4) a counter for the number of granules (units) in which the word occurs: (5) the unique Word Number associated with the word (assigned sequentially); (6) the last granule (unit) in which the word was found; (7) the length of the word; and (8) the actual characters of the word.” Id. at 5:3-6:25. Accordingly, the disclosed “Word List” is a keyword list comprising statistical word frequency (i.e., a counter for the number of granules in which the word occurs) and word length (i.e., the length of the word).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention to modify the text compression method of Suzuki to incorporate the text compression index features taught by Millett. One of ordinary skill in the art would be motivated to integrate the text compression index features into Suzuki, with a reasonable expectation of success, in order to improver performance by providing “a text index compression system which executed very quickly” Millett, 2:50-51; See Also 5:47-48 (“logical structure of the Word List is a key factor for the speed with which the index is created”).
Claim 2
Suzuki discloses wherein performing word segmentation processing on texts to be compressed comprises: dividing the texts to be compressed by delimiters to obtain a plurality of corresponding words. The method “identifies and counts all occurrences of unique original symbols and stores each unique original symbol” and each original symbol is “stored in a standardization memory.” In one embodiment, identifying original symbols is performed by interpreting “certain non-alphanumeric characters (e.g., a space) as denoting a break between two symbols,” wherein the method “interprets a space as a break between symbols” (i.e., segmenting words based on spaces). Suzuki, ¶¶ 21-22.
Claim 3
Millett discloses wherein the collecting statistics about word length and word frequency of the words obtained after the word segmentation processing to construct a corresponding keyword list comprises: based on a preset keyword data structure and a keyword pointer array, collecting statistics about word length and word frequency of the words obtained after the word segmentation process to construct a corresponding keyword list. The method builds two primary data structures “the in-memory Word List and the [Non-Repeating Word Number Stream] NRWNS,” wherein the NRWNS stored ”sequentially a representation of the stream of words found in the set of documents, each word being represented by a unique word number.” Each word in the Word List “is stored as a node of a binary tree.” Each node of the binary tree comprises fields of: ‘(1) flags for memory control; (2) a pointer to the left tree node (or NULL); (3) a pointer to the right tree node (or NULL); (4) a counter for the number of granules (units) in which the word occurs: (5) the unique Word Number associated with the word (assigned sequentially); (6) the last granule (unit) in which the word was found; (7) the length of the word; and (8) the actual characters of the word.” Id. at 5:3-6:25.
Figure 3 illustrates the “logical structure of the Word List,” comprising a linked pointer list with a structure wherein each element (i.e., hash bucket) “is accessed by a unique hash number representing the first two characters of the word,” and each sub-element (i.e., sub-bucket) “represents a group of words beginning with the particular two characters,” each element “contains a pointer to a separate binary tree (303a) of words and a count of how many words are in the tree” each sub-bucket containing words of the same character length (e.g., “first sub-bucket container words of three characters or less,” “second sub-bucket contains words of four characters,” “third sub-bucket contains words of five characters and so on”). Id. at 5:58-6:11; FIG. 3. Accordingly, the logical structure of the Word List using hash pointers is analogous to the claimed preset keyword data structure and a keyword pointer array.
Claim 4
Millett discloses wherein the keyword data structure comprises: a next member configured to point to a hash singly linked list pointer of a next word with the same hash value. Figure 3 illustrates the “logical structure of the Word List,” comprising a linked pointer list with a structure wherein each element (i.e., hash bucket) “is accessed by a unique hash number representing the first two characters of the word,” and each sub-element (i.e., sub-bucket) “represents a group of words beginning with the particular two characters,” each element “contains a pointer to a separate binary tree (303a) of words and a count of how many words are in the tree” each sub-bucket containing words of the same character length (e.g., “first sub-bucket container words of three characters or less,” “second sub-bucket contains words of four characters,” “third sub-bucket contains words of five characters and so on”). Id. at 5:58-6:11; FIG. 3.
Millett discloses a word member configured to record a corresponding word. Millet discloses that each “word is stored as a node of a binary tree.” Id. at 5:48-65. Each node comprises a field storing “(8) the actual characters of the word.”
Millett discloses a total_cnt member configured to record [[the]] a number of occurrences of the corresponding word. Each node comprises a field storing “(4) a counter for the number of granules (units ) in which the word occurs.”
Millett discloses a word_len member configured to record a symbol length of the corresponding word. Each node comprises a field storing “(7) the length the word.”
Millett discloses an idx_type member configured to record a coded value of the corresponding word. Each node comprises a field storing “(5) the unique Word Number associated with the word (assigned sequentially).” Id. at 6:13-46.
Claim 5
Millett discloses wherein performing word segmentation processing on texts to be compressed, and collecting statistics about word length and word frequency of the words obtained after the word segmentation processing to construct a corresponding keyword list comprises: traversing the divided words in the texts to be compressed to obtain a current word traversed to; calculating the hash value corresponding to the current word; with the calculated hash value as an index, determining whether there is a keyword data structure instance of the current word in the keyword singly linked list pointed to by the corresponding pointer in the keyword pointer array. Millett discloses building the word list by scanning the selected documents and traversing each word; the method traverses each word by getting a word from the file (Step 1), processing each word (Step 3), and then moving on to the next word (Step 3.5.2 or 3.6.7). Millett, 6:46-7:28.
Millett discloses in response to a determination that the current word exists in the keyword singly linked list pointed to by the corresponding pointer in the keyword pointer array, increasing the total_cnt member in the corresponding keyword data structure instance by a preset first numerical value. At step 3.5, if a match to a word is found, then at 3.5.1.4 the method increments frequency count for this word. Id.
Millett discloses in response to a determination that the current word does not exist in the keyword singly linked list pointed to by the corresponding pointer in the keyword pointer array, constructing the corresponding keyword data structure instance for the current word, and inserting the constructed keyword data structure instance into the keyword singly linked list pointed to by the corresponding pointer in the keyword pointer array. At step 3.3, if no binary tree exists for the hash value corresponding to the word, then the method creates a bucket in the binary tree (i.e., constructs the corresponding keyword data structure instance).
Millett discloses obtaining the next word as the current word traversed to, and restarting from calculating the hash value of the current word until the traversal of the texts to be compressed is completed. Millett discloses building the word list by scanning the selected documents and traversing each word; the method traverses each word by getting a word from the file (Step 1), processing each word (Step 3), and then moving on to the next word (Step 3.5.2 or 3.6.7). When the method reaches the end of file granule marker at step 4, the processing is ended. Millett, 6:46-7:28.
Claim 6
Suzuki discloses wherein compressing the texts to be compressed based on the constructed keyword list comprises: traversing the texts to be compressed to obtain a current word traversed to; combining the current word traversed to with a delimiter at a corresponding position to form a key word of a corresponding type; based on the numerical value of the idx_type member in the keyword data structure instance corresponding to the current word, determining whether the key words of the corresponding type have been allocated an encoding slot. Suzuki discloses that embodiments “identify and replace symbol pairs… by processing the text of each document in sequential order” (i.e., traversal). Each pass through the document “involves comparing each sequential symbol pair to entries of the compress dictionary.” Suzuki, ¶¶ 35-36.
Suzuki discloses in response to a determination that the key words of the corresponding type have not been allocated an encoding slot and there is an idle encoding slot, allocating an encoding slot for the key words of the corresponding type, and recording the corresponding coded value in the idx_type member of the corresponding keyword data structure instance. A ‘symbol pair’ is a key word type comprising two words separated by a delimiter. See Id. at ¶¶ 3, 22. A replacement symbol is “an address in the compression dictionary where the symbol pair associated with the replacement symbol is stored,” wherein replacement symbols “are inserted into output documents and stored in the compression dictionary” (replacement symbol → coded value in the idx_type member). Id. at ¶¶ 44-45. Suzuki discloses that if “the comparison does not produce a match, the symbol pair is identified as unique and added to the compression dictionary” (i.e., recording the corresponding coded value). Id. at ¶ 36.
Suzuki discloses in response to a determination that the key words of the corresponding type have been allocated an encoding slot, obtaining the coded value recorded in the idx_type member of the corresponding keyword data structure instance. Suzuki discloses that if “the comparison results in a match, the compared symbol pair’s count is incremented, and if the replacement threshold is met, the symbol pair is replaced with a replacement symbol.” Id. at ¶ 36.
Suzuki discloses replacing the key words of the corresponding type in the texts to be compressed with the coded value recorded in the idx_type member of the corresponding keyword data structure instance. Figure 4 illustrates an embodiment of the method, wherein replacement phase 450 “searches the input documents for symbol pairs that match entries in the compression dictionary (451),” and if “replacements are possible” the method “replaces symbol pairs with an associated replacement symbol (452).” Id. at ¶¶ 66-67; FIG. 4.
Suzuki discloses obtaining the next word as the current word traversed to, and restarting from the step of combining the current word traversed to with the delimiter at a corresponding position to form the key words of the corresponding type until the traversal of the texts to be compressed is completed, and obtaining a corresponding first compressed text. After replacements are made (452), the method “operates recursively by returning to cataloging phase 400 to begin a subsequent pass on the output of the previous pass.” Upon completion, “the example embodiment stores the compressed output documents and terminated (499).” Id.
Claim 7
Suzuki discloses wherein after allocating an encoding slot for the key words of the corresponding type, further comprising based on a preset final word data structure, constructing a final word data structure instance of the key words of the corresponding type to record an encoding information of the key words of the corresponding type. The standardization memory 140 is used to construct a compression dictionary 200. Suzuki, ¶¶ 32-33; FIG. 2. Whereas the standardization memory 140 comprises a list of keywords, the compression dictionary 200 comprises a list of pairs of keywords (compression dictionary 200 → final word data structure instance of key words), the pairs of keywords being of a type of two words separated by a delimiter.
Claim 8
Suzuki discloses wherein the final word data structure comprises: a Str member configured to record the information of the key words of the corresponding type. Figure 2 illustrates a data structure representing compression dictionary 200. Column 210 “stores each unique symbol pair from the text processed” (unique symbol pair → key words of the corresponding type). Suzuki, ¶¶ 41-42
Suzuki discloses a cnt member configured to record the number of occurrences of the key words of the corresponding type. Column 211 “stores the count associated with each symbol.” Id.
Millet discloses a method of compressing text using two primary data structures: “the in-memory Word List and the [Non-Repeating Word Number Stream] NRWNS,” wherein the NRWNS stored ”sequentially a representation of the stream of words found in the set of documents, each word being represented by a unique word number.” Each word in the Word List “is stored as a node of a binary tree.” Each node of the binary tree comprises fields of: ‘(1) flags for memory control; (2) a pointer to the left tree node (or NULL); (3) a pointer to the right tree node (or NULL); (4) a counter for the number of granules (units) in which the word occurs: (5) the unique Word Number associated with the word (assigned sequentially); (6) the last granule (unit) in which the word was found; (7) the length of the word; and (8) the actual characters of the word.” Millett, 5:3-6:25.
Millett discloses a Len member configured to record a character length of the key words of the corresponding type. Each node comprises a field storing “(7) the length the word.” Id.
Millett discloses a node_cnt member configured to record a number of different corresponding types of key word adjacent to the key words of the corresponding type; and a tree member configured to record the information of an adjacency merged red-black tree of the key words of the corresponding type. Each node of the binary tree comprises fields of: ‘(1) flags for memory control; (2) a pointer to the left tree node (or NULL); (3) a pointer to the right tree node (or NULL). Id.
Claim 9
Suzuki discloses wherein taking the coded value of the key words of the corresponding type in the first compressed text as a large coded word, after obtaining the first compressed text, further comprising: performing merged encoding on the large coded word in the first compressed text to obtain a second compressed text. Figure 4 illustrates an embodiment of the method, wherein replacement phase 450 “searches the input documents for symbol pairs that match entries in the compression dictionary (451),” and if “replacements are possible” the method “replaces symbol pairs with an associated replacement symbol (452).” Id. at ¶¶ 66-67; FIG. 4. After replacements are made (452), the method “operates recursively by returning to cataloging phase 400 to begin a subsequent pass on the output of the previous pass” (subsequent pass output → second compressed text). Upon completion, “the example embodiment stores the compressed output documents and terminated (499).” Suzuki, ¶¶ 66-67; FIG. 4
Claim 10
Suzuki discloses wherein performing merged encoding on the large coded word in the first compressed text comprises: based on a preset merged word data structure, constructing an adjacency merged red-black tree for each of the large coded words in the first compressed text; and based on the constructed adjacency merged red-black tree, performing merged encoding
on the large coded word in the first compressed text. Suzuki discloses that in each pass, the method “generates a pass-related section in the compression dictionary.” Suzuki, ¶ 41. A column identifier “indicates the pass during which the symbol pair was identified.” Id. at ¶ 44. A symbol pair identified in a later pass is analogous to a “large coded words,” i.e. the symbol pairs are found to be adjacent to other symbol pairs. Suring the replacement stage of a pass, the method “creates a compressed output document by replacing symbol pairs in an input document with replacement symbols from compression dictionary 200.” Id. at ¶ 52. The method performs “recursive passes until no further replacements are possible,” wherein “[s]ymbol pairs identified in a second or subsequent pass can be two replacement symbols,” or :can be a combination of a replacement symbol and an uncompressed symbol.” i.e., merged encoding. Id. at ¶ 56.
Claim 11
Suzuki discloses wherein the merged word data structure comprises: an entry member configured to represent a root node of the adjacency merged red-black tree; a code member configured to record the coded value of the key word of the corresponding type adjacent to the root node; and a count member configured to record the number of occurrences of the key words of the corresponding type adjacent to the root node. Figure 2 illustrates a data structure representing compression dictionary 200. Column 210 “stores each unique symbol pair from the text processed” (unique symbol pair → key words of the corresponding type). Column 211 “stores the count associated with each symbol.” Further, symbol pairs identified in a later pass can be a replacement symbol comprising a sequence of an uncompressed symbol followed by another replacement symbol; for example after a second pass “the example embodiment has replaced the four-symbol ‘phrase’ S1-S79-S75-S5 with the single symbol R3P2” (i.e., recoding the coded value of the key word of the corresponding type adjacent to the root node). Suzuki, ¶¶ 41-42
Claim 12
Suzuki discloses wherein based on a preset merged word data structure, constructing an adjacency merged red-black tree for each of the large coded words in the first compressed text comprises: scanning the first compressed text to obtain current two adjacent large coded words
traversed to; the current two adjacent large coded words include a previous large coded word and
a next large coded word after the previous large coded word; determining the corresponding adjacency merged red-black tree by taking a tree member in the final word data structure corresponding to the previous large coded word as a root; querying a merged word data structure instance with a key value of the next large coded word in the determined adjacency merged red-black tree; in response to a determination that there is a corresponding merged word data structure instance, increasing the count member in the corresponding merged word data structure instance by a preset second value; in response to a determination that there isn't a corresponding merged word data structure instance, constructing a corresponding merged word data structure instance, and insert the merged word data structure constructed into the adjacency merged red-black tree of the previous large coded word; and obtaining next two adjacent large coded words in the first compressed text, and restarting from the step of determining the corresponding adjacency merged red-black tree by taking a tree member in the final word data structure corresponding to the previous large coded word as a root until the traversal of the first compressed text is completed. Suzuki discloses that in each pass, the method “generates a pass-related section in the compression dictionary.” Suzuki, ¶ 41. A column identifier “indicates the pass during which the symbol pair was identified.” Id. at ¶ 44. A symbol pair identified in a later pass is analogous to a “large coded words,” i.e. the symbol pairs are found to be adjacent to other symbol pairs. Suring the replacement stage of a pass, the method “creates a compressed output document by replacing symbol pairs in an input document with replacement symbols from compression dictionary 200.” Id. at ¶ 52. The method performs “recursive passes until no further replacements are possible,” wherein “[s]ymbol pairs identified in a second or subsequent pass can be two replacement symbols,” or :can be a combination of a replacement symbol and an uncompressed symbol.” i.e., merged encoding. Id. at ¶ 56.
Figure 4 illustrates an embodiment of the method, wherein replacement phase 450 “searches the input documents for symbol pairs that match entries in the compression dictionary (451),” and if “replacements are possible” the method “replaces symbol pairs with an associated replacement symbol (452).” Id. at ¶¶ 66-67; FIG. 4. After replacements are made (452), the method “operates recursively by returning to cataloging phase 400 to begin a subsequent pass on the output of the previous pass” (subsequent pass output → second compressed text). Upon completion, “the example embodiment stores the compressed output documents and terminated
(499).” Suzuki, ¶¶ 66-67; FIG. 4
Claim 13
Suzuki discloses wherein performing merged encoding on the large coded word in the first compressed text comprises: taking the first compressed text as a current text to be merged, and traversing the current text to be merged to obtain the current two adjacent large coded words traversed to; querying a merged word data structure instance with a key value of the next large coded word in the adjacency merged red-black tree of the previous large coded word of the current two adjacent large coded words; in response to a determination that the numerical value of the count member in the queried merged word data structure instance is greater than or equal to a preset merged threshold allocating a new merged encoding slot for the current two adjacent large coded words. The method “only uses replacement symbols if their associated count exceeds a predetermined threshold.” Suzuki, ¶ 47. The “replacement symbols can be associated with ta symbol pair when the symbol pair … meets the replacement threshold.” Id. at ¶ 50. The compression dictionary “only contains entries for symbol pairs that exceed the replacement threshold because entries with counts not exceeding the threshold were not retained.” Id. at ¶ 53. In one embodiment, the threshold is enforced “by populating the compression dictionary with only symbol pairs that exceed the threshold.” Id. at ¶ 67.
Suzuki discloses constructing a corresponding final word data structure instance; replacing the current two adjacent large coded words in the current text to be merged with the coded value of the corresponding merged encoding slot; obtaining the next two adjacent large coded words in the current text to be merged as the current two adjacent large coded words, and restarting from the step of querying a merged word data structure instance with a key value of the next large coded word in the adjacency merged red-black tree of the previous large coded word of the current two adjacent large coded words until the traversal of the current text to be merged is completed, and obtaining a next text to be merged. Suzuki discloses that in each pass, the method “generates a pass-related section in the compression dictionary.” Id. at ¶ 41. A column identifier “indicates the pass during which the symbol pair was identified.” Id. at ¶ 44. A symbol pair identified in a later pass is analogous to a “large coded words,” i.e. the symbol pairs are found to be adjacent to other symbol pairs. Suring the replacement stage of a pass, the method “creates a compressed output document by replacing symbol pairs in an input document with replacement symbols from compression dictionary 200.” Id. at ¶ 52. The method performs “recursive passes until no further replacements are possible,” wherein “[s]ymbol pairs identified in a second or subsequent pass can be two replacement symbols,” or :can be a combination of a replacement symbol and an uncompressed symbol.” i.e., merged encoding. Id. at ¶ 56.
Figure 4 illustrates an embodiment of the method, wherein replacement phase 450 “searches the input documents for symbol pairs that match entries in the compression dictionary (451),” and if “replacements are possible” the method “replaces symbol pairs with an associated replacement symbol (452).” Id. at ¶¶ 66-67; FIG. 4. After replacements are made (452), the method “operates recursively by returning to cataloging phase 400 to begin a subsequent pass on the output of the previous pass” (subsequent pass output → second compressed text). Upon completion, “the example embodiment stores the compressed output documents and terminated
(499).” Suzuki, ¶¶ 66-67; FIG. 4
Suzuki discloses determining whether a preset merging stop condition is met; and in response to a determination that the preset merging stop condition isn't met, taking the next text to be merged as the current text to be merged, and restarting from the step of traversing the current text to be merged to obtain the current two adjacent large coded words traversed to until the preset merging stop condition is met, and obtaining the second compressed text. Embodiments are “programmed to repeat recursively until compression is complete, e.g., until no more pairs of symbols meet the threshold for replacement.” Id. at ¶ 34. During the recursive processing of documents, if “no replacement are possible during a pass, the example embodiment stores the compressed output documents and terminated.” Id. at ¶ 67. Accordingly, whether any replacements meet the occurrence threshold is a preset merging stop condition.
Claim 14
Suzuki discloses wherein the preset merging stop condition is any one of the following:
a number of merging rounds is greater than a corresponding round threshold; all of the numerical values of the count member of the merged word data structure instance in the adjacency merged red-black tree of the key words of the corresponding type in the first compressed text are less than the merged threshold; and the encoding slots have been allocated. Embodiments are “programmed to repeat recursively until compression is complete, e.g., until no more pairs of symbols meet the threshold for replacement.” Suzuki, ¶ 34. During the recursive processing of documents, if “no replacement are possible during a pass, the example embodiment stores the compressed output documents and terminated.” Id. at ¶ 67. Accordingly, if all possible replacements are less than the replacement threshold, then a preset merging stop condition is met.
Claim 15
Suzuki discloses wherein the key words of the corresponding type comprise: a first type of key word, including the corresponding word and the delimiter after the word; a second type of key word, including the corresponding delimiter and the word after the delimiter; a third type of key word, including the corresponding word and the delimiters before and after the word; and
a fourth type of key word, including only the corresponding word. A ‘symbol pair’ is a key word type comprising two words separated by a delimiter. See Suzuki, ¶¶ 3, 22. A replacement symbol is “an address in the compression dictionary where the symbol pair associated with the replacement symbol is stored,” wherein replacement symbols “are inserted into output documents and stored in the compression dictionary” (replacement symbol → coded value in the idx_type member). Id. at ¶¶ 44-45. Accordingly a ‘symbol pair’ is analogous to a second type of key word including the corresponding delimiter and the words after the delimiter.
Claim 16
Suzuki discloses wherein before allocating an encoding slot for the key words in the keyword list, further comprising: deleting keywords that do not meet a preset encoding conditions from the keyword list. Suzuki discloses truncating (i.e., deleting portions of) “the compression dictionary having entries with counts less than the threshold.” Suzuki, ¶ 48.
Claim 20
Claim 20 is rejected utilizing the aforementioned rationale for Claim 1; the claim is directed to a system performing the method.
Claim 39
Claim 39 is rejected utilizing the aforementioned rationale for Claims 1 and 20; the claim is directed to a system performing the method. Claim 39 is interpreted as a dependent claim; depending on parent claim 20.
For purposes of statutory subject matter; the recited “chip” is interpreted as an integrated circuit described in paragraph 239 of the present specification.
Claim 40
Claim 39 is rejected utilizing the aforementioned rationale for Claims 1, 20, and 39; the claim is directed to a system performing the method. Claim 40 is interpreted as a dependent claim; depending on parent claims 39 and 20.
Claim 41
Claim 41 is rejected utilizing the aforementioned rationale for Claim 1; the claim is directed to a medium storing instructions corresponding to the method. Claim 41 is interpreted as a dependent claim; depending on parent claim 1.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. See Morishita, U.S. Patent No. 6,047,298 (describing a “text compression dictionary generation apparats”).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to FRANK D MILLS whose telephone number is (571)270-3172. The examiner can normally be reached M-F 10-6 ET.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, KEVIN YOUNG can be reached at (571)270-3180. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/FRANK D MILLS/Primary Examiner, Art Unit 2194 January 23, 2026