the present invention is intended to operate in a computer or telecommunications system comprising a data processing means , a memory means , and a data storage device containing data records . the data processing means may be , for example , a conventional computer or a microprocessor in a modem or other communications device . the data storage device may be , for example , a conventional disk drive or a buffer embedded in a modem . the invention describes a method of operating the data processing means for compactly storing data while maintaining its natural collating sequence , and for efficiently restoring retrieved data to an uncompacted form using a general compression technique . in the following description , numerous specific details and examples are set forth in order to provide a thorough understanding of the present invention . it will be obvious , however , to one skilled in the art that variants are possible and that the invention may be practiced without adhering to these details in every particular . in some instances where well - known methods are employed , their details are omitted in order not to unnecessarily obscure the present invention . referring to fig1 a , there is shown generally the structure of an uncompressed data string containing repetitions of a target pattern and therefore suitable for compression in accordance with the present invention . in order to fully understand the present method , it should be understood that each symbol cv1 , cv2 , and cv3 represents the binary value of a character in a sequential data stream , s . the binary values chosen generally conform to one of a number of commonly used character sets , such as the ascii character set shown in fig3 . although ascii has been used as an exemplary character set , the present invention is not limited to ascii representation , and may be used with any character set . cv2 is serially repeated in the data stream a total of r1 times at its first occurrence , and r2 times at its second occurrence . fig2 is a flow chart of a compression procedure in accordance with a preferred embodiment of the current invention . in step 200 the procedure is started , and in step 202 the sequence which will be the target for compression is selected . the target may be either a single - octet character , such as the ascii representation of the space character , a multi - octet character , such as may be found in representations of japanese or chinese characters , or even a run of repeating characters . in step 204 , a sequence length equal to the length of the target pattern is selected . thus , if the target pattern is one single - octet character , the sequence length will be one , but if the target pattern is a character or sequence which fills four octets , the sequence length will be four octets also . in the present invention , the sequence length also determines the compression ceiling , the maximum run of target patterns which can be compressed at once . the compression ceiling for the preferred embodiment of the present invention is half of the maximum binary value which can be stored in the sequence length , plus one . thus , for a one octet target pattern , the maximum binary value of the sequence length will be 255 , and the compression ceiling will be 1 / 2 ( 255 + 1 )= 128 . runs in excess of the ceiling may be broken apart for compression in accordance with the invention . in step 206 , a threshold for repetitions of the target pattern is selected . in many instances , selecting a threshold of one will provide maximum compression benefits , but in a few instances , applying the method with a threshold of one will expand the data rather than compacting it and in these instances a threshold of two or greater may advantageously be selected . in step 208 , a counter is reserved to track sequential repetitions of the target pattern in the data stream , and this run count is initialized at zero . data characters from the data stream are read sequentially by the procedure , one sequence length at a time . in steps 210 and 212 , the data processing means determines whether data is present at the next spot in the data stream and if data is not present , the data processor proceeds to step 232 , which will be discussed later . if data is present , the processor gets these next characters at step 214 , and at step 216 , compares the next characters to the target pattern . if the next characters match the target pattern , the run count is incremented by one at step 218 , and the processor then advances one sequence length in the data stream and repeats steps 210 and 212 with new data . if however , the next characters do not match the target pattern , then after step 216 , the processor tests at step 220 whether the current run count is lower than the predetermined threshold . if it is , the next characters are simply written into the data storage device at step 222 and the processor returns to step 208 . if , however , the threshold has been equaled or exceeded , then the compression sequence is begun . at step 224 , the value of the next character is compared to the value of the target pattern . all of the comparisons shown in fig2 and later in fig4 are done in accordance with whatever collating sequence it is desired that the values will be ordered by . thus , the present invention may be used even if a specially programmed collating sequence is being used instead of the natural collating sequence , merely by doing all comparisons in accordance with the specially programmed sequence . if the target pattern is the lesser of the two values , then , as shown at step 228 , a compression count is calculated as a predetermined number less the difference between the current run count and the threshold . the predetermined number is preferably the bit value of the sequence length . thus , for a one octet sequence length , the predetermined number would be 255 . if the target pattern is the greater of the two values , then a compression count is calculated as the difference between the current run count and the threshold , as shown at step 230 . in either case , the target pattern , the compression count computed at step 228 or 230 , and the next characters , which will be seen to be the pattern following the final repetition of the target pattern in the run of repetitions , are written into the data storage device and the processor returns to step 208 . if the repetitions of the target pattern continue to the end of the data stream , then when the processor tests for next characters at step 212 , it will find none and proceed to step 232 . at step 232 , the current run count is compared to the threshold . if the run count is below the threshold , the procedure ends at step 238 . if the run count equals or exceeds the threshold , at step 234 a compression count is calculated as the difference between the current run count and the threshold , and at step 236 , the target pattern and the compression count are written into the data storage device , and only then does the procedure end at step 238 . fig3 shows the compacted structure of the data string of fig1 when compressed in accordance with the invention . it will be recalled that a run of r1 repetitions of cv2 occurred between cv1 and cv3 , and a run of r2 repetitions of cv2 occurred after cv3 . for the purposes of this example , cv2 is taken to be one octet in length . if cv2 was selected as the target pattern and t as the threshold for repetitions , then regardless of the lengths of the two runs of cv2 , the compacted data stream becomes only 6 characters long , with the encoded characters cc1 and cc2 representing , respectively , the first and second runs of cv2 . cc1 will equal r2 - t if cv3 & lt ; cv2 ( in the selected collating sequence ) or 255 -( r2 - t ) if cv3 & gt ; cv2 . cc2 will equal r2 - t . applying the present invention to the example data discussed above demonstrates the improvement over prior art compression methods in maintaining the collating sequence of the data provided by the present invention . it will be recalled that the example data ( in which space characters were represented as x &# 39 ; s for ease of visualization ), was : if this data were to be compressed in accordance with the invention , using the ascii character set shown in fig5 the space character as the target pattern , the natural collating sequence , and a threshold of 1 , the compacted result would be : because the natural collating order of the data is preserved by the compression operation , sorting and multiple search operations can be performed on the data without decompression , providing a significant increase in efficiency . however , once data is sorted or selected , it will normally be required by the user in non - compressed form . fig4 shows a procedure for restoring compacted data in accordance with a preferred embodiment of the invention . turning now to fig4 the procedure is started in step 300 , and in step 302 the sequence which was used as the target for compression when the data was compacted is input or recalled . as earlier noted , the target pattern may be either a single character , such as a spacer character , a multi - octet character , such as may be found in representations of japanese or chinese characters , or even a run of repeating multi - octet characters . in step 304 , a sequence length equal to the length of the target pattern is selected , and in step 306 , the compression threshold which was used in compacting the data is input or recalled . in step 308 , a counter is reserved to track sequential repetitions of the target pattern in the data stream , and this run count is initialized at zero . data characters from the data stream are read sequentially by the procedure , one sequence length at a time . in steps 310 and 312 , the data processing means advances by one sequence length and determines whether data is present at the next spot in the data stream . if data is not present , the data processor ends the procedure . if data is present , the processor gets these next characters at step 314 , and at step 316 , compares the next characters to the target pattern . if the next characters match the target pattern , the run count is incremented by one at step 320 , and the processor tests at step 322 whether the current run count is lower than the predetermined threshold . if either the next characters do not match the target pattern at step 216 , or the run count is lower than the threshold at step 322 , the next characters are simply written into the data storage device at step 318 and the processor then advances one sequence length in the data stream and repeats steps 310 and 312 with new data . if , however , the target pattern is matched and the threshold is reached , the decompression sequence is begun at step 324 . at step 324 , the processor advances one sequence length to read the pattern of characters first following the characters just tested . because of the requirement that the threshold be reached before proceeding to this step , this pattern will be the first pattern after an identified occurrence of the target pattern which does not match the target pattern , and will always be the code for the compression count computed in the compression procedure . the purpose of the decompression procedure is to remove this first pattern from the data stream and replace it in the data stream with a fixed number of additional repetitions of the target pattern , the fixed number being chosen to be the sum of the first pattern and the threshold count if the pattern following the first pattern is less than the target pattern or if there is no following pattern , and to be a preselected number plus the threshold count less the first pattern if the following pattern is greater than the target pattern . if the preselected number is chosen , as is preferred , to be the maximum binary value of sequence length , then the first pattern will be less than the compression ceiling if the pattern following the first pattern is less than the target pattern or if there is no following pattern , and will be greater than the compression ceiling if the following pattern is greater than the target pattern . testing the size of the first pattern is more efficient than testing the relationship between the target pattern and following pattern directly , so the invention is preferably implemented by testing the first pattern size , as shown in step 326 . if the target pattern is the lesser of the two values , then , as shown at step 328 , a run count , r , is calculated as the predetermined number , most preferably the bit value of the sequence length , plus the difference between the threshold and the first following pattern . if the target pattern is the greater of the two values , then a run count , r , is calculated as the sum of the first following pattern and the threshold , as shown at step 330 . in either case , at step 332 , the target pattern is then written to the data storage device r times is written into the data storage device . it will be seen that the first following pattern is never written into the data storage device in this procedure . the processor next advances a sequence length in the data stream at step 334 , and then returns to step 308 . if the repetitions of the target pattern continued to the end of the data stream , then when the processor returns to test for the next data at step 312 , it will find none and end the procedure . thus , there has been described herein a method of operating the data processing means for compactly storing data while maintaining its natural collating sequence , and for efficiently restoring retrieved data to an uncompacted form using a general compression technique . it will be understood that various changes in the details , arrangements , and steps which have been described and illustrated above in order to explain the nature of the present invention may be made by those skilled in the art without departing from the principle and scope of the present invention as expressed in the appended claims .