Compression of grouped data

• US 5,895,463 A
• Filed: 05/20/1997
• Issued: 04/20/1999
• Est. Priority Date: 05/20/1997
• Status: Expired due to Term

• Current Assignee: FEP Holding Company, Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Franklin Electronic Publishers Incorporated (Saunders Acquisition Corp.)
• Inventors: Dowling, William F., Kotlarsky, Anatoly
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US08/859,022
• Time in Patent Office: 700 Days
• Field of Search: 707/1, 707/3, 707/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An electronic reference device provides the ability to access all members of any one of a plurality of groups of data items in response to a user input of any one member of the group being accessed. The reference device includes a memory having a data item list, a token uniquely identifying each member of the data item list, and a plurality of groups of the data item list. Certain members of said data item list being a member of one or more of the groups and certain members of the data item list being a member of none of the groups. An ordered search list consists of each member of the data item list which is a member of at least one of the groups. A delta value is associated with each member of the ordered search list. The sum of the delta values up through any one of the members of the ordered search list provides the value of the token for the corresponding member of the data item list. Each member of the search list has a next-entry pointer identifying another member of the search list. All members of the search list that are linked by a set of inter-connecting next-entry pointers correspond to members of the data item list from the same one of the groups.

Claims

1. An electronic reference device providing the ability to access all members of any one of a plurality of groups of data items in response to a user input of any one member of the group being accessed, comprising:

a memory having a data item list,

a token uniquely identifying each member of said data item list,

a plurality of groups of said data item list,

certain members of said data item list being a member of one or more of said groups and certain members of said date item list being a member of none of said groups,

an ordered search list consisting of each member of said data item list which is a member of at least one of said groups,

a delta value associated with each member of said ordered search list,

the sum of said delta values up through any one of said members of said ordered search list providing the value of said token for the corresponding member of said data item list,

each member of said search list having a next-entry pointer identifying another member of said search list,

all members of said search list that are linked by a set of inter-connecting next-entry pointers corresponding to members of said data item list from the same one of said groups.

2. The electronic reference device of claim 1 wherein:

certain members of said data item list are a member of multiple ones of said groups, and

each member of said data item list that is a member of multiple groups is listed only once in said data item list and has a single token.

3. The electronic reference device of claim 2 wherein:

each item that is a member of multiple groups is represented by a number of consecutive entries in said search list equal to the number of groups of which said item is a member,

the ones of said consecutive entries in said search list which correspond to a single item on said item list constituting a common set on said search list,

the first member of any one of said common sets having a delta value appropriate to the corresponding member of said data item list, the rest of the members of that common set having a delta value of zero.

4. The electronic reference device of claim 1 wherein:

each member of said data item list that is not a member of any of said groups is unrepresented in said search list.

5. The electronic reference device of claim 1 wherein:

each member of said search list is identified by one and only one next-entry pointer.

6. An electronic reference device providing the ability to access all members of any one of a plurality of groups of data items in response to a user input of any one member of the group being accessed, comprising:

a memory having a data item list,

a token uniquely identifying each member of said data item list,

a plurality of groups of said data item list,

certain members of said data item list are a member of multiple ones of said groups, each member of said data item list that is a member of multiple groups being listed only once in said data item list and has a single token.

an ordered search list consisting of each member of said data item list which is a member of at least one of said groups,

a delta value associated with each member of said ordered search list,

the sum of said delta values up through any one of said members of said ordered search list providing the value of said token for the corresponding member of said data item list,

each member of said search list having a next-entry pointer identifying another member of said search list,

all members of said search list that are linked by a set of inter-connecting next-entry pointers corresponding to members of said data item list from the same one of said groups.

7. The electronic reference device of claim 6 wherein:

certain members of said data item list are a member of none of said groups, each member of said data item list that is not a member of any of said groups being unrepresented in said search list.

8. The electronic reference device of claim 6 wherein each member of said data item list that is a member of multiple groups is listed only once in said data item list and has a single token.

9. The electronic reference device of claim 8 wherein:

each item that is a member of multiple groups is represented by a number of consecutive entries in said search list equal to the number of groups of which said item is a member,

the ones of said consecutive entries in said search list which correspond to a single item on said item list constituting a common set on said search list,

the first member of any one of said common sets having a delta value appropriate to the corresponding member of said data item list, the rest of the members of that common set having a delta value of zero.

10. The electronic reference device of claim 6 wherein:

each member of said search list is identified by one and only one next-entry pointer.

11. An electronic reference device providing the ability to access all members of any one of a plurality of groups of data items in response to a user input of any one member of the group being accessed, comprising:

a memory having a data item list,

a token uniquely identifying each member of said data item list,

a plurality of groups of said data item list,

certain members of said data item list being a member of one or more of said groups and certain members of said data item list being a member of none of said groups,

each member of said data item list that is a member of multiple groups being listed only once on said data item list and having a single token,

an ordered search list consisting of each member of said data item list which is a member of at least one of said groups,

each member of said data item list that is not a member of any of said groups being unrepresented in said search list,

a delta value associated with each member of said ordered search list,

the sum of said delta values up through any one of said members of said ordered search list providing the value of said token for the corresponding member of said data item list,

each member of said search list having a next-entry pointer identifying another member of said search list,

each member of said search list being identified by one and only one next-entry pointer,

all members of said search list that are linked by a set of inter-connecting next-entry pointers corresponding to members of said data item list from the same one of said groups,

each item that is a member of multiple groups being represented by a number of consecutive entries in said search list equal to the number of groups of which said item is a member,

the ones of said consecutive entries in said search list which correspond to a single item on said item list constituting a common set on said search list,

the first member of any one of said common sets having a delta value appropriate to the corresponding member of said data item list, the rest of the members of that common set having a delta value of zero.

12. An electronic reference product for accessing linked data, comprising:

a data item memory storing a plurality of data items, the data item memory associating each of the data items with a unique token value;

a search list memory including a plurality of ordered search list entries, each search list entry having a token value associated therewith, the order of the search list entries being the same as the order of the respective associated token values, each search list entry having a next-entry pointer identifying a linked search list entry, each of the token values associated with a search list entry being equal to a token value of a corresponding data item;

a plurality of the search list entries including a delta value, the delta value being the difference between the value of the associated token and the value of the token associated with the preceding data entry;

at least one base value, each base value storing a token value corresponding to a search list entry;

means for accessing the data item memory to determine a search token associated with a data item input by a user;

means for searching the search list to find a matching search list entry corresponding to the search token;

means for accessing the search list to find a linked search list entry identified by the next-entry pointer of the matching search list entry;

means for accessing the search list to calculate a linked token value associated with the linked search list entry;

means for accessing the data item memory to determine a linked data item associated with the linked token value; and

means for displaying the linked data item.

13. The electronic reference product of claim 12 wherein each search list entry is a member of a sublist, members of a common sublist being linked by the next-entry pointers of their respective members.

14. The electronic reference product of claim 13 wherein each data item which corresponds to a search list entry is a member of a group, each sublist being associated with a group, each member of a group having a corresponding search list entry in the associated sublist.

15. The electronic reference product of claim 14 wherein each data item is a lexical word.

16. The electronic reference product of claim 15 wherein each group is a group of rhyming lexical words.

17. The electronic reference product of claim 15 wherein each group is a group of synonyms.

18. The electronic reference product of claim 14 wherein all search list entries which correspond to data items in a common group are linked by the next-entry pointers of the search list entries in a circular fashion.

19. The electronic reference product of claim 14 wherein the number of groups of which each respective data item is a member is equal to the number of search list entries corresponding to the respective data item.

20. The electronic reference product of claim 19 wherein search list entries which correspond to a common data item are adjacent in the search list.

21. The electronic reference product of claim 14, wherein the search list memory further includes at least one group tag entry associated with a tagged sublist, the group tag entry being linked to the tagged sublist by the next-entry pointer of an entry in the tagged sublist.

22. The electronic reference product of claim 21, wherein the group tag entry and the sublist members in the associated tagged sublist are linked by the next-entry pointers thereof in a circular fashion.

23. The electronic reference product of claim 12, wherein the means for searching the search list includes means for performing a binary search on the search list.

24. The electronic reference product of claim 12 further comprising a word tag memory, the word tag memory including a plurality of word tag entries, each word tag entry including a word tag and associated word tag data, each word tag identifying an entry in the search list.

25. The electronic reference product of claim 12, further comprising a base value memory for storing each base value.

26. An electronic memory for use with an electronic reference product providing the ability to access all members of any one of a plurality of groups of data items in response to a user input of any one member of the group being accessed, the memory comprising:

a data item memory storing a plurality of data items, the data item memory associating each of the data items with a unique token value;

a search list memory including a plurality of ordered search list entries, each search list entry having a token value associated therewith, the order of the search list entries being the same as the order of the respective associated token values, each search list entry having a next-entry pointer identifying a linked search list entry, each of the token values associated with a search list entry being equal to a token value of a corresponding data item;

a plurality of the search list entries including a delta value, the delta value being the difference between the value of the associated token and the value of the token associated with the preceding search list entry; and

at least one base value, each base value storing a token value corresponding to a search list entry;

the next-entry pointers being selected such that the data item corresponding to each search list entry is in a common group with the data item corresponding to the respective linked search list entry.

27. The electronic memory of claim 26 wherein each search list entry is pointed to by one and only one next-entry pointer.

28. The electronic memory of claim 26 wherein the data items are lexical words.

29. The electronic memory of claim 28 wherein the groups are groups of rhyming words.

30. The electronic memory of claim 28 wherein the groups are groups of synonyms.

31. An electronic memory for use with an electronic reference product providing the ability to access all members of any one of a plurality of groups of data items in response to a user input of any one member of the group being accessed, the memory comprising:

a data item memory storing a plurality of data items, the data item memory associating each of the data items with a unique token value;

a search list memory including a plurality of ordered search list entries, each search list entry having a token value associated therewith, the order of the search list entries being the same as the order of the respective associated token values, each search list entry having a next-entry pointer identifying a linked search list entry, each of the token values associated with a search list entry being equal to a token value of a corresponding data item;

a plurality of the search list entries including a delta value, the delta value being the difference between the value of the associated token and the value of the token associated with the preceding search list entry;

at least one base value, each base value storing a token value corresponding to a search list entry;

a first program memory for determining a search token associated with a data item input to an electronic reference product by a user;

a second program memory for searching the search list to find a matching search list entry corresponding to the search token;

a third program memory for accessing the search list to find a linked search list entry identified by the next-entry pointer of the matching search list entry;

a fourth program memory for accessing the search list to calculate a linked token value associated with the linked search list entry;

a fifth program memory for accessing the data item memory to determine a linked data item associated with the linked token value; and

a sixth program memory for directing the electronic reference product to display the linked data item.

32. The electronic reference product of claim 31 wherein each search list entry is a member of a sublist, members of a common sublist being linked by the next-entry pointers of their respective members.

33. The electronic reference product of claim 32 wherein each data item which corresponds to a search list entry is a member of a group, each sublist being associated with a group, each member of a group having a corresponding search list entry in the associated sublist.

34. The electronic reference product of claim 33 wherein each data item is a lexical word.

35. The electronic reference product of claim 34 wherein each group is a group of rhyming lexical words.

36. The electronic reference product of claim 34 wherein each group is a group of synonyms.

37. The electronic reference product of claim 33 wherein all search list entries which correspond to data items in a common group are linked by the next-entry pointers of the search list entries in a circular fashion.

38. The electronic reference product of claim 33 wherein the number of groups of which each respective data item is a member is equal to the number of search list entries corresponding to the respective data item.

39. The electronic reference product of claim 38 wherein search list entries which correspond to a common data item are adjacent in the search list.

40. The electronic reference product of claim 33, wherein the search list memory further includes at least one group tag entry associated with a tagged sublist, the group tag entry being linked to the tagged sublist by the next-entry pointer of an entry in the tagged sublist.

41. The electronic reference product of claim 40, wherein the group tag entry and the sublist members in the associated tagged sublist are linked by the next-entry pointers thereof in a circular fashion.

42. The electronic reference product of claim 31, wherein the second program memory for searching the search list includes means for performing a binary search on the search list.

43. The electronic reference product of claim 31 further comprising a word tag memory, the word tag memory including a plurality of word tag entries, each word tag entry including a word tag and associated word tag data, each word tag identifying an entry in the search list.

44. The electronic reference product of claim 31, further comprising a base value memory for storing each base value.