Generating and searching compressed data

• US 7,026,964 B2
• Filed: 03/17/2005
• Issued: 04/11/2006
• Est. Priority Date: 01/31/2002
• Status: Expired due to Term

• Current Assignee: Rovi Technologies Corporation (Adeia Inc.)
• Original Assignee: Microsoft Corporation
• Inventors: Baldwin, James Armand, Barrett, Peter T.
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US11/082,391
• Publication Number:
  US 20050219085A1
• Time in Patent Office: 390 Days
• Field of Search: 341/55, 341/87, 725/39, 725/40, 725/53, 725/54, 707/3, 707/7, 707/101, 707/104.1
• US Class Current: 341/87
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence
• CPC Class Codes: H04N 21/2353 specifically adapted to content descriptors, e.g. coding, compressing or processing of metadata
• CPC Class Codes: H04N 21/25833 involving client hardware characteristics, e.g. manufacturer, processing or storage capabilities allocation of resources considering hardware capabilities in multiprogramming arrangements G06F9/5044; allocation of resources considering software capabilities in multiprogramming arrangements G06F9/5055
• CPC Class Codes: H04N 21/26208 the scheduling operation being performed under constraints
• CPC Class Codes: H04N 21/26233 involving content or additional data duration or size, e.g. length of a movie, size of an executable file
• CPC Class Codes: H04N 21/26283 for associating distribution time parameters to content, e.g. to generate electronic program guide data
• CPC Class Codes: H04N 21/4335 Housekeeping operations, e.g. prioritizing content for deletion because of storage space restrictions storage management, e.g. defragmentation G06F3/0604; unloading stored programs G06F9/445; storage management in file systems G06F16/10; buffering arrangements in a network node or in an end terminal in packet networks H04L49/90
• CPC Class Codes: H04N 21/443 OS processes, e.g. booting an STB, implementing a Java virtual machine in an STB or power management in an STB
• CPC Class Codes: H04N 7/163 by receiver means only
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Data destined for a client is compressed at a server in a manner that produces a compressed data string that can be searched in its compressed state. The server constructs a code table that assigns codes from a standard code set (e.g., ASCII code set) that are normally unused to selected character pairs in the data string (e.g., the most frequently occurring character pairs). During compression, the selected character pairs are replaced with the corresponding codes. Identifiers are inserted into the compressed data string to separate substrings. To search the compressed data string at the client, a search query is compressed and compared to the compressed substrings. The substring identifiers are used to quickly locate each successive compressed substring. When a match is found, the matching substring is decompressed by replacing the code in the compressed substring with the corresponding character pair in the code table.

Claims

1. A method comprising:

compressing an alphanumeric data string to form a compressed data swing;

inserting identifiers throughout the compressed data string to form distinct substrings;

fragmenting the data string into equal-size fragments prior to delivery of the data string to a remote client; and

searching the compressed data string using the identifiers to index from substring to substring.

2. A method as recited in claim 1, wherein the compressing comprises substituting available character codes in a character code set that are not used to represent individual characters in the data string for selected character pairs in the data string.

3. A method as recited in claim 1, further comprising:

identifying frequently occurring character pairs in the alphanumeric data string;

constructing a code table with first codes that represent individual characters in the data string and second codes that can be assigned to represent the frequently occurring character pairs in the data string; and

compressing the data string by substituting the second codes for the frequently occurring character pairs.

4. A method as recited in claim 3, wherein the identifying comprises:

using a counts table with counts associated with every possible combination of two characters; and

for each character pair in the data string, incrementing a count associated with the character pair in the counts table.

5. A method as recited in claim 3, wherein the constructing comprises:

marking in the code table individual characters found in the data string and associating the first codes with the individual characters; and

assigning any remaining codes as the second codes to represent the frequently occurring character pairs.

6. A computer-readable medium comprising computer-executable instructions that, when executed, direct a computing device to perform the method as recited in claim 1.

7. A method for preparing program data for delivery to a client that executes an electronic program guide, comprising:

initially allocating different-size portions of memory representative of a client memory for different time units represented in the electronic program guide;

evaluating whether program data for the different time units fits in the respective different-size portions of the memory; and

adjusting quantities of the program data for the different time units to identify an entire set of program data for storage at the client, wherein different quantities of the program data are stored for the different time units.

8. A method as recited in claim 7, further comprising fragmenting the program data into equal-size fragments prior to delivery to the client.

9. A method as recited in claim 7, wherein the time units comprise 24-hour days.

10. A method as recited in claim 7, wherein the allocating comprises allocating more of the memory for time units that are closer in time and less of the memory for time units that are further out in time.

11. A computer-readable medium comprising computer-executable instructions that, when executed, direct a computing device to perform the method as recited in claim 7.

12. A method comprising:

forming a data string of program data for an electronic program guide;

compressing the data string by identifying frequently occurring character pairs in the data string and substituting character codes from a character code set, which are not used to represent individual characters, in place of the frequently occurring character pairs; and

fragmenting the data string into equal-size fragments prior to delivery of the data string to a remote client.

13. A method as recited in claim 12, further comprising:

storing the program data in multiple tables, each table comprising one or more records with one or more fields; and

sorting the records in the tables according to a selected field type prior to delivery of the program data to the remote client, wherein the records form the data string.

14. A method as recited in claim 13, wherein the tables comprises a particular structure and the sorting rearranges the records without changing the particular structure.

15. A method as recited in claim 13, wherein the selected field type is selected from a group of fields including actor names, program genre, title, and ratings.

16. A method as recited in claim 13, wherein the records comprise program records containing programming information, individual program records having a title field to identify a program name, and the sorting comprises arranging the program records in the tables according to a stopped name version of the program name in the title field.

17. A method as recited in claim 12, further comprising:

compressing the data string to form a compressed data string;

inserting identifiers throughout the compressed data string to form distinct substrings; and

searching the compressed data string using the identifiers to index from substring to substring.

18. A computer-readable medium comprising computer-executable instructions that, when executed, direct a computing device to perform the method as recited in claim 12.