Method to compress linguistic structures

• US 6,535,886 B1
• Filed: 10/18/1999
• Issued: 03/18/2003
• Est. Priority Date: 10/18/1999
• Status: Expired due to Term

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Koontz, Eugene
• Primary Examiner(s): Amsbury, Wayne
• Application Number:
  US09/420,515
• Time in Patent Office: 1,247 Days
• Field of Search: 707/102, 707/6, 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 40/123 Storage facilities
• CPC Class Codes: H03M 7/3097 Grammar codes
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and system for compressing a data structure. A segment is identified within the data structure. Each segment identified is counted for the number of occurrences of the segment within the data structure. If the number of occurrences is greater than one, the segment is saved in a recurring data structure. Also, the recurring segment within the data structure is replaced with an index to the segment stored in the recurring data structure.

Claims

1. A computerized method for compressing a data structure, comprising:

identifying at least one segment within the data structure, wherein the at least one segment is a discrete sub-structure of the data structure and comprises at least one feature-value pair; and

if the number of occurrences of the at least one segment within the data structure is greater than one,

saving the at least one segment in a recurring data structure, and

replacing the at least one segment within the data structure with an index corresponding to the at least one segment in the recurring data structure.

2. The method of claim 1, wherein the data structure is a linguistic data structure.

3. The method of claim 1, wherein the at least one segment within the data structure is a textual representation.

4. The method of claim 1, wherein counting a number of occurrences includes storing the at least one segment and a count value corresponding to the number of occurrences of the at least one segment within the data structure in a table.

5. The method of claim 1, wherein identifying at least one segment includes finding a recurring textual representation within the data structure.

6. The method of claim 5, wherein replacing the at least one segment replaces the recurring textual representation with a numerical index.

7. The method of claim 6, wherein the index points to a location within the recurring data structure, the location being associated with the replaced textual representation.

8. The method of claim 7, wherein the index is stored in the recurring data structure.

9. A computerized system for compressing a data structure, comprising:

a segmentator configured to determine at least one segment within the data structure, wherein the at least one segment is a discrete sub-structure of the data structure and comprises at least one feature-value pair;

a segment counter configured to count a number of occurrences of the at least one segment within the data structure; and

a recurring data structure for storing the at least one segment if the number of occurrences of the at least one segment is greater than one, wherein the at least one segment in the data structure is replaced by an index corresponding to the at least one segment in the recurring data structure.

10. The system of claim 9, wherein the data structure is a linguistic data structure.

11. The system of claim 9, wherein the at least one segment within the data structure is a textual representation.

12. The system of claim 9, wherein the segment counter is also configured to store the at least one segment and a count value representing the number of occurrences of the at least one segment within the data structure in a table.

13. The system of claim 12, further comprising:

an indexing engine configured to store the at least one segment if the count value of the at least one segment is greater than one in the recurring data structure and replacing the at least one segment in the data structure with the index corresponding to the at least one segment in the recurring data structure.

14. The system of claim 9, wherein the segmentator is also configured to find a recurring textual representation within the data structure.

15. The system of claim 14, wherein the recurring textual representation within the data structure is replaced by the numerical index.

16. The system of claim 9, wherein the index is stored in the recurring data structure.

17. An article of manufacture including one or more computer-readable media with executable instructions therein, which, when executed by a processing device causes the processing device to:

identify at least one segment within the data structure, wherein the at least one segment is a discrete sub-structure of the data structure and comprises at least one feature-value pair;

count a number of occurrences of the at least one segment within the data structure;

save the at least one segment in a recurring data structure if the number of occurrences is greater than one; and

replace the at least one segment within the data structure with an index corresponding to the at least one segment in the recurring data structure.

18. The article of manufacture of claim 17, wherein identify at least one segment includes to find a recurring textual representation within the data structure.

19. The article of manufacture of claim 17, wherein replace the at least one segment within the data structure includes to replace the recurring textual representation within the data structure by a numerical index.

20. The article of manufacture of claim 17, wherein the index is stored in the recurring data structure.

21. An apparatus for compressing a data structure comprising:

means for identifying at least one segment within the data structure, wherein the at least one segment is a discrete sub-structure of the data structure and comprises at least one feature-value pair;

means for counting a number of occurrences of the at least one segment within the data structure; and

a recurring data structure for storing the at least one segment if the number of occurrences of the at least one segment is greater than one, wherein the at least one segment in the data structure is replaced by an index corresponding to the at least one segment in the recurring data structure.

22. The apparatus of claim 21, wherein the data structure is a linguistic data structure.

23. The apparatus of claim 21, wherein the at least one segment within the data structure is a textual representation.

24. The apparatus of claim 21, wherein the means for counting further stores a count value representing the number of occurrences of the at least one segment in a table.

25. The apparatus of claim 24, further comprising:

a means for indexing to store the at least one segment in the recurring data structure if the count value of the at least one segment is greater than one, and further for replacing the at least one segment in the data structure with the index corresponding to the at least one segment in the recurring data structure.

26. The apparatus of claim 21, wherein the means for identifying is further operable to find a recurring textual representation within the data structure.

27. The apparatus of claim 26, wherein the recurring textual representation within the data structure is replaced by the numerical index.

28. The apparatus of claim 21, wherein the index is stored in the recurring data structure.