Word/number and number/word mapping

• US 5,754,847 A
• Filed: 10/16/1991
• Issued: 05/19/1998
• Est. Priority Date: 05/26/1987
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kaplan, Ronald M., Kay, Martin
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US07/776,909
• Time in Patent Office: 2,407 Days
• Field of Search: 364/200, 364/900, 395/611, 395/612, 395/759, 395/760
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A compactly stored word list that includes a directed graph data structure is used for word to number (W/N) and number to word (N/W) mapping. Each word accepted by the data structure is mapped to a unique corresponding number within a dense set of numbers ranging from zero to one less than the total number of acceptable words. Some common suffixes are collapsed into shared branches, which is possible because the numbers are not stored within the word list. In addition, some branches of the data structure can be skipped during mapping because of information associated with branch points. That information permits the mapping scan to continue with a next branch or with an alternative branch. That information also indicates the number of suffix endings in the next branch; this number is used to keep a count of the word endings during word to number mapping; it is also used both to determine whether to continue with the next branch and also to reduce the number being mapped during number to word mapping. The branching information includes a full length pointer to the next branch or a shorter length pointer index to a table in which the pointer is stored. In either case, the number of suffix endings in the next branch is annexed to the pointer. The pointers and pointer indexes are assigned iteratively, the shortest pointer indexes first, then longer pointer indexes, and finally the full length pointers. In each case, a pointer or pointer index is assigned only if beneficial, and the assignment of pointers and pointer indexes is cleared and redone if a better assignment can be made.

Claims

1. A method of operating a data processing system to map from a string of elements to a respective number;

the data processing system including;

circuitry for obtaining string data indicating a string of elements;

mapping data for mapping from each of a plurality of strings to a respective number; and

a processor connected for receiving the string data and for accessing the mapping data;

the mapping data including a plurality of data units;

the data units including first, second, and third sequences of data units;

the string indicated by the string data having a prefix substring of elements and a suffix substring of elements, the elements of the suffix substring following the elements of the prefix substring, the suffix substring having a suffix ending;

the first sequence of data units including;

prefix element information indicating the elements of the prefix substring;

first suffix ending information indicating a first number of suffix endings; and

branching information;

the second sequence of data units including;

a second sequence start data unit; and

second suffix ending information indicating a second number of suffix endings;

the third sequence of data units including;

a third sequence start data unit;

suffix element information indicating the elements of the suffix substring;

a substring ending data unit indicating the suffix substring'"'"'s suffix ending; and

third suffix ending information indicating a third number of suffix endings between the third sequence start data unit and the substring ending data unit;

the branching information being information that the processor can use to obtain branch indicating data, second sequence branch data, third sequence branch data, and second number data;

the branch indicating data indicating whether to branch to the second sequence of data units or to the third sequence of data units;

the second sequence branch data indicating a location of the second sequence start data unit so that if the branch indicating data indicates a branch to the second sequence of data units, the processor can use the second sequence branch data to access the second sequence of data units;

the third sequence branch data indicating a location of the third sequence start data unit so that if the branch indicating data indicates a branch to the third sequence of data units, the processor can use the third sequence branch data to access the third sequence of data units;

the second number data indicating the second number of suffix endings;

the method comprising;

operating the processor to receive the string data; and

operating the processor to use the string data and the mapping data to obtain the string'"'"'s respective number;

the act of operating the processor to use the string data and the mapping data comprising;

accessing the first sequence of data units;

using the prefix element information and the string data to determine that the elements of the prefix substring are indicated by the prefix element information;

using the first suffix ending information to obtain first number data indicating the first number of suffix endings;

using the branching information to obtain the branch indicating data, the third sequence branch data, and the second number data;

if the branch indicating data indicates a branch to the third sequence of data units, accessing the third sequence of data units using the third sequence branch data;

using the third suffix ending information to obtain third number data indicating the third numbers of suffix endings;

using the third element information and the string data to determine that the elements of the suffix substring are indicated by the third element information; and

using the first number data, the second number data, and the third number data to obtain the string'"'"'s respective number.

2. The method of claim 1, further comprising:

using the string'"'"'s respective number to retrieve information related to the string.

3. The method of claim 1 in which the circuitry for obtaining the string data obtains string data indicating a text that includes the string;

the method further comprising;

using the string'"'"'s respective number to compress the text indicated by the string data.

4. The method of claim 1 in which the third sequence of data units includes a subsequence of data units between the third sequence start data unit and the substring ending data unit, the subsequence of data units including a plurality of suffix ending data units, the third suffix ending information including string ending information in each of the suffix ending data units;

the act of using the first number data, the second number data, and the third number data comprising;

after the act of using the branching information, using the first number data and the second number data to obtain count data indicating a sum of the first number and the second number;

the act of using the third suffix ending information to obtain third number data comprising;

for each suffix ending data unit in the subsequence of data units, modifying the count data to indicate a number that is incremented by one so that when the processor accesses the substring ending data unit, the count data indicates a sum of the first number, the second number, and the third number.

5. The method of claim 4 in which the string'"'"'s respective number is the sum of the first number, the second number, and the third number.

6. The method of claim 1 in which the branching information includes a number of branching data units at a location at an end of the first sequence of data units;

the third sequence start data unit being positioned immediately after the branching data units;

the branching data units including length information indicating a length of the branching data units;

the act of using the branching information comprising;

using the length information and the location of the branching data units to obtain the third sequence branch data indicating the location of the third sequence start data unit.

7. The method of claim 1 in which the mapping data further includes a table with an entry that includes skip number information indicating the second number of suffix endings;

the branching information further being information that the processor can use to obtain table pointer data indicating a location of the entry in the table;

the act of using the branching information comprising;

using the branching information to obtain table pointer data indicating a location of the entry in the table;

using the table pointer data to access the entry in the table; and

using the skip number information to obtain the second number data.

8. The method of claim 1 in which the string'"'"'s suffix substring has a first element;

the branching information further being information that the processor can use to obtain following element data indicating an element that could follow the prefix substring;

the act of using the branching information comprising;

using the branching information to obtain following element data indicating an element that could follow the prefix substring;

using the following element data and the string data to determine whether the following element data indicates the suffix substring'"'"'s first element; and

if the following element data indicates the suffix substring'"'"'s first element, setting the branch indicating data to indicate a branch to the second sequence of data units; and

if the following element data does not indicate the suffix substring'"'"'s first element, setting the branch indicating data to indicate a branch to the third sequence of data units.

9. A method of operating a data processing system to map from a number to a respective string of elements;

the data processing system including;

circuitry for obtaining map number data indicating a number;

mapping data for mapping from each of a plurality of numbers to a respective string of elements; and

a processor connected for receiving the map number data and for accessing the mapping data;

the mapping data including a plurality of data units;

the data units including first, second, and third sequences of data units;

the number'"'"'s respective string of elements having a prefix substring of elements and a suffix substring of elements, the elements of the suffix substring following the elements of the prefix substring, the suffix substring having a suffix ending;

the first sequence of data units including;

prefix element information indicating the elements of the prefix substring;

first suffix ending information indicating a first number of suffix endings; and

branching information;

the second sequence of data units including;

a second sequence start data unit; and

second suffix ending information indicating a second number of suffix endings;

the third sequence of data units including;

a third sequence start data unit;

suffix element information indicating the elements of the suffix substring;

a substring ending data unit indicating the suffix substring'"'"'s suffix ending; and

third suffix ending information indicating a third number of suffix endings between the third sequence start data unit and the substring ending data unit;

the branching information being information that the processor can use to obtain branch indicating data, second sequence branch data, third sequence branch data, and second number data;

the branch indicating data indicating whether to branch to the second sequence of data units or to the third sequence of data units;

the second sequence branch data indicating a location of the second sequence start data unit so that if the branch indicating data indicates a branch to the second sequence of data units, the processor can use the second sequence branch data to access the second sequence of data units;

the third sequence branch data indicating a location of the third sequence start data unit so that if the branch indicating data indicates a branch to the third sequence of data units, the processor can use the third sequence branch data to access the third sequence of data units;

the second number data indicating the second number of suffix endings;

the method comprising;

operating the processor to receive the map number data; and

operating the processor to use the map number data and the mapping data to obtain the respective string of the number indicated by the map number data;

the act of operating the processor to use the map number data and the mapping data comprising;

accessing the first sequence of data units;

using the prefix element information to obtain prefix data indicating the elements of the prefix substring;

using the first suffix ending information to obtain first number data indicating the first number of suffix endings;

using the branching information to obtain the branch indicating data, the third sequence branch data, and the second number data;

if the branch indicating data indicates a branch to the third sequence of data units, accessing the third sequence of data units using the third sequence branch data;

using the third suffix ending information to obtain third number data indicating the third number of suffix endings;

using the map number data, the first number data, the second number data, and the third number data to find the substring ending data unit;

using the suffix element information to obtain suffix data indicating the elements of the suffix substring; and

using the prefix data and the suffix data to obtain the respective string of elements of the number indicated by the map number data.

10. The method of claim 9 in which the third sequence of data units includes a respective subsequence of data units between the third sequence start data unit and the substring ending data unit, the subsequence of data units including a plurality of suffix ending data units, the third suffix ending information including string ending information in each of the suffix ending data units;

the act of using the map number data, the first number data, the second number data, and the third number data to find the substring ending data unit comprising;

using the map number data, the first number data, and the second number data to obtain count data indicating a difference between the number indicated by the tag number data and a sum of the first number and the second number;

the act of using the third suffix ending information to obtain third number data comprising;

for each suffix ending data unit in the subsequence of data units, modifying the count data to indicate a number that is decremented by one so that when the processor accesses the substring ending data unit, the count data indicate zero.

11. The method of claim 10 in which the first sequence of data units includes a respective subsequence of data units, the subsequence of data units including a plurality of suffix ending data units, the first suffix ending information including string ending information in each of the suffix ending data units;

the act of using the first suffix ending information to obtain first number data comprising;

for each suffix ending data in the subsequence of data units in the first sequence, modifying the map number data to indicate a number that is decremented by one so that when all data units in the subsequence have been accessed, the map number data has been modified to indicate a difference between the number indicated by the map number data and the first number;

the act of using the map number data, the first number data, and the second number data to obtain count data further comprising;

subtracting the second number from the number indicated by the map number data as modified to obtain the count data.

12. The method of claim 10 in which the number indicated by the tag number data is a sum of the first number, the second number, and the third number.

13. The method of claim 9 in which the act of using the prefix element information to obtain prefix data comprises:

loading and unloading entries indicating string elements in a stack so that when the branching information is accessed, the stack entries indicate string elements forming the prefix substring.

14. The method of claim 13 in which the act of using the suffix element information to obtain suffix data comprises:

loading and unloading entries indicating string elements in the stack so that when the substring ending data unit is accessed, the stack entries indicate string elements forming the prefix substring and the suffix substring.

15. The method of claim 9 in which the circuitry for obtaining the map number data obtains series data indicating a series of numbers that includes the number indicated by the map number data;

the method further comprising;

using the respective string of elements of the number indicated by the map number data to decompress the series of numbers indicated by the series data.

16. The method of claim 9 in which the branching information includes a number of branching data units at a location at an end of the first sequence of data units;

the third sequence start data unit being positioned immediately after the branching data units;

the branching data units including length information indicating a length of the branching data units;

the act of using the branching information comprising;

using the length information and the location of the branching data units to obtain the third sequence branch data indicating the location of the third sequence start data unit.

17. The method of claim 9 in which the mapping data further include a table with an entry that includes skip number information indicating the second number of suffix endings;

the branching information further being information that the processor can use to obtain table pointer data indicating a location of the entry in the table;

the act of using the branching information comprising;

using the branching information to obtain table pointer data indicating a location of the entry in the table;

using the table pointer data to access the entry in the table; and

using the skip number information to obtain the second number data.

18. The method of claim 9 in which the act of using the first suffix ending information to obtain first number data comprises:

obtaining count data indicating a difference between the number indicated by the map number data and the first number;

the act of using the branching information comprising;

using the branching information to obtain the second number data;

using the second number data and the count data to compare the difference indicated by the count data with the second number; and

if the difference indicated by the count data is less than the second number, setting the branch indicating data to indicate a branch to the second sequence of data units; and

if the difference indicated by the count data is greater than the second number, setting the branch indicating data to indicate a branch to the third sequence of data units.

19. An article of manufacture for use in a system that includes:

a processor;

the processor obtaining string data indicating a string of elements;

the string having a prefix substring of elements and a suffix substring of elements, the elements of the suffix substring following the elements of the prefix substring, the suffix substring having a suffix ending;

the article comprising;

memory for storing data; and

mapping data stored in the memory so that the processor can access the mapping data for mapping from each of a plurality of strings to a respective number;

the mapping data comprising;

a first sequence of data units;

the first sequence of data units comprising;

prefix element information indicating the elements of the prefix substring;

first suffix ending information indicating a first number of suffix endings; and

branching information;

the prefix element information, the first suffix ending information, and the branching information being positioned within the first sequence of data units so that the processor can access the first sequence of data units, use the prefix element information and the string data to determine that the elements of the prefix substring are indicated by the prefix element information, use the first suffix ending information to obtain first number data indicating the first number of endings, and use the branching information to branch either to the second sequence of data units or to the third sequence of data units;

a second sequence of data units;

the second sequence of data units comprising;

a second sequence start data unit; and

second suffix ending information indicating a second number of suffix endings; and

a third sequence of data units;

the third sequence of data units comprising;

a third sequence start data unit;

suffix element information indicating the elements of the suffix substring;

a substring ending data unit indicating the suffix substring'"'"'s suffix ending; and

third suffix ending information indicating a third number of suffix endings between the third sequence start data unit and the substring ending data unit;

the branching information being information that the processor can use to obtain branch indicating data, second sequence branch data, third sequence branch data, and second number data;

the branch indicating data indicating whether to branch to the second sequence of data units or to the third sequence of data units;

the second sequence branch data indicating a location of the second sequence start data unit so that if the branch indicating data indicate a branch to the second sequence of data units, the processor can use the second sequence branch data to access the second sequence of data units;

the third sequence branch data indicating a location of the third sequence start data unit from which a location of the third sequence start data unit can be obtained so that if the branch indicating data indicate a branch to the third sequence of data units, the processor can use the third sequence branch data to access the third sequence of data units;

the second number data indicating the second number of suffix endings;

the third sequence start data unit, the suffix element information, and the third suffix ending information being positioned within the third sequence of data units so that the processor can access the third sequence of data units using the third sequence branch data;

use the third suffix ending information to obtain third number data indicating the third number of suffix endings;

use the third element information and the string data to determine that the elements of the suffix substring are indicated by the third element information; and

use the first number data, the second number data, and the third number data to obtain the string'"'"'s respective number.

20. The article of claim 19 in which the branching information comprises a following element data unit that the processor can access to obtain following element data indicating an element that could follow the prefix substring.

21. The article of claim 19 in which the branching information comprises a number of branching data units at an end of the first sequence of data units;

the third sequence start data unit being positioned immediately after the branching data units;

the branching data units including;

length information from which the processor can obtain length data indicating the length of the branching data units;

second sequence location information from which the processor can obtain the second sequence branch data; and

second number information from which the processor can obtain the second number data.

22. The article of claim 19 in which the mapping data further comprise a table including an entry;

the branching information comprising a number of branching data units at an end of the first sequence of data units;

the third sequence start data unit being positioned immediately after the branching data units;

the branching data units including;

length information from which the processor can obtain length data indicating the length of the branching data units;

entry location information from which the processor can obtain entry pointer data indicating a location of the entry in the table;

the entry in the table including;

second sequence pointer data indicating the location of the second sequence start data unit; and

second branch number data indicating the second number of suffix endings.

23. The article of claim 19 in which the branching information is positioned at an end of the first sequence of data units;

the first sequence of data units further comprising second branching information that the processor can use to obtain the second sequence branch data and the second number data so that the second sequence of data units includes shared suffix endings;

the second branching information being positioned at a location other than the end of the first sequence of data units.

24. The article of claim 19 in which the third sequence of data units comprises a subsequence of data units between the third sequence start data unit and the substring ending data unit, the subsequence of data units including a plurality of suffix ending data units, the third suffix ending information including string ending information in each of the suffix ending data units.

25. The article of claim 24 in which each of the suffix ending data units also includes element label information, the string ending information and the element label information of each suffix ending data unit being encoded.

26. The article of claim 25 in which each suffix ending data unit is a byte.

27. The article of claim 19 in which the respective numbers of the plurality of strings form a dense set of unique numbers.

28. The article of claim 19 in which each of the plurality of strings is an acceptable word, each of the elements being a character.

29. The article of claim 19 in which the string'"'"'s respective number is equal to the sum of the first, second, and third numbers of suffix endings.

30. A system comprising:

circuitry for obtaining string data indicating a string of elements;

the string having a prefix substring of elements and a suffix substring of elements, the elements of the suffix substring following the elements of the prefix substring, the suffix substring having a suffix ending;

mapping data for use in mapping between each of a plurality of strings and a respective number;

a processor connected for receiving the string data and for accessing the mapping data;

the mapping data comprising;

a first sequence of data units;

the first sequence of data units comprising;

prefix element information indicating the elements of the prefix substring;

first suffix ending information indicating a first number of suffix endings; and

branching information;

the prefix element information, the first suffix ending information, and the branching information being positioned within the first sequence of data units so that the processor can access the first sequence of data units, use the prefix element information and the string data to determine that the elements of the prefix substring are indicated by the prefix element information, use the first suffix ending information to obtain first number data indicating the first number of endings, and use the branching information to branch either to the second sequence of data units or to the third sequence of data units;

a second sequence of data units;

the second sequence of data units comprising;

a second sequence start data unit; and

second suffix ending information indicating a second number of suffix endings; and

a third sequence of data units;

the third sequence of data units comprising;

a third sequence start data unit;

suffix element information indicating the elements of the suffix substring;

a substring ending data unit indicating the suffix substring'"'"'s suffix ending; and

third suffix ending information indicating a third number of suffix endings between the third sequence start data unit and the substring ending data unit;

the branching information being information that the processor can use to obtain branch indicating data, second sequence branch data, third sequence branch data, and second number data;

the branch indicating data indicating whether to branch to the second sequence of data units or to the third sequence of data units;

the second sequence branch data indicating a location of the second sequence start data unit so that if the branch indicating data indicate a branch to the second sequence of data units, the processor can use the second sequence branch data to access the second sequence of data units;

the third sequence branch data indicating a location of the third sequence start data unit from which a location of the third sequence start data unit can be obtained so that if the branch indicating data indicate a branch to the third sequence of data units, the processor can use the third sequence branch data to access the third sequence of data units;

the second number data indicating the second number of suffix endings;

the third sequence start data unit, the suffix element information, and the third suffix ending information being positioned within the third sequence of data units so that the processor can access the third sequence of data units using the third sequence branch data;

use the third suffix ending information to obtain third number data indicating the third number of suffix endings;

use the third element information and the string data to determine that the elements of the suffix substring are indicated by the third element information; and

use the first number data, the second number data, and the third number data to obtain the string'"'"'s respective number.

31. The system of claim 30, further comprising stored information related to the string, the processor further being connected for retrieving the information related to the string using the string'"'"'s respective number.

32. The system of claim 30, further comprising circuitry for obtaining a text including strings in the plurality of strings, the processor being connected for receiving the text.

33. An article of manufacture for use in a system that includes circuitry for obtaining number data indicating a number and a processor connected for receiving the number data;

the article comprising a memory for storing data and mapping data stored in the memory so that the processor can access the mapping data for mapping from each of a plurality of numbers to a respective string of elements;

the respective string of the number indicated by the number data having a prefix substring of elements and a suffix substring of elements, the elements of the suffix substring following the elements of the prefix substring, the suffix substring having a suffix ending;

the mapping data comprising;

a first sequence of data units;

the first sequence of data units comprising;

prefix element information indicating the elements of the prefix substring;

first suffix ending information indicating a first number of suffix endings; and

branching information;

the prefix element information, the first suffix ending information, and the branching information being positioned within the first sequence of data units so that the processor can access the first sequence of data units, use the prefix element information to obtain prefix data indicating the elements of the prefix substring, use the first suffix ending information to obtain first number data indicating the first number of suffix endings, and use the branching information to branch either to the second sequence of data units or to the third sequence of data units;

a second sequence of data units;

the second sequence of data units comprising;

a second sequence start data unit; and

second suffix ending information indicating a second number of suffix endings; and

a third sequence of data units;

the third sequence of data units comprising;

a third sequence start data unit;

suffix element information indicating the elements of the suffix substring;

a substring ending data unit indicating the suffix substring'"'"'s suffix ending; and

third suffix ending information indicating a third number of suffix endings between the third sequence start data unit and the substring ending data unit;

the branching information being information that the processor can use to obtain branch indicating data, second sequence branch data, third sequence branch data, and second number data;

the branch indicating data indicating whether to branch to the second sequence of data units or to the third sequence of data units;

the second sequence branch data indicating a location of the second sequence start data unit so that if the branch indicating data indicate a branch to the second sequence of data units, the processor can use the second sequence branch data to access the second sequence of data units;

the third sequence branch data indicating a location of the third sequence start data unit from which a location of the third sequence start data unit can be obtained so that if the branch indicating data indicate a branch to the third sequence of data units, the processor can use the third sequence branch data to access the third sequence of data units;

the second number data indicating the second number of suffix endings;

the third sequence start data unit, the suffix element information, the third suffix ending information, and the substring ending data unit being positioned within the third sequence of data units so that the processor can access the third sequence of data units using the third sequence branch data;

use the third suffix ending information to obtain third number data indicating the third number of suffix endings;

use the map number data, the first number data, the second number data, and the third number data to find the substring ending data unit;

use the suffix element information to obtain suffix data indicating the elements of the suffix substring; and

use the prefix data and the suffix data to obtain the respective string of elements of the number indicated by the map number data.

34. The article of claim 33 in which the branching information comprises a number of branching data units at an end of the first sequence of data units;

the third sequence start data unit being positioned immediately after the branching data units;

the branching data units including;

length information from which the processor can obtain length data indicating the length of the branching data units;

second sequence location information from which the processor can obtain the second sequence branch data; and

second number information from which the processor can obtain the second number data.

35. The article of claim 33 in which the mapping data further comprise a table including an entry;

the branching information comprising a number of branching data units at an end of the first sequence of data units;

the third sequence start data unit being positioned immediately after the branching data units;

the branching data units including;

length information from which the processor can obtain length data indicating the length of the branching data units; and

entry location information from which the processor can obtain entry pointer data indicating a location of the entry in the table;

the entry in the table including;

second sequence pointer data indicating the location of the second sequence start data unit; and

second branch number data indicating the second number of suffix endings.

36. The article of claim 33 in which the branching information is positioned at an end of the first sequence of data units;

the first sequence of data units further comprising second branching information that the processor can use to obtain the second sequence branch data and the second number data so that the second sequence of data units includes shared suffix endings;

the second branching information being positioned at a location other than the end of the first sequence of data units.

37. The article of claim 33 in which the third sequence of data units comprises a subsequence of data units between the third sequence start data unit and the substring ending data unit, the subsequence of data units including a plurality of suffix ending data units, the third suffix ending information including string ending information in each of the suffix ending data units.

38. The article of claim 37 in which each of the suffix ending data units also includes element label information, the string ending information and the element label information of each suffix ending data unit being encoded.

39. The article of claim 38 in which each suffix ending data unit is a byte.

40. The article of claim 33 in which the respective numbers of the plurality of strings form a dense set of unique numbers.

41. The article of claim 33 in which each of the plurality of strings is an acceptable word, each of the elements being a character.

42. The article of claim 33 in which the number indicated by the map number data is equal to a sum of the first, second, and third numbers of suffix endings, so that the third number of suffix endings is equal to a difference between the number indicated by the map number data and a sum of the first and second numbers of suffix endings.

43. A system comprising:

circuitry for obtaining map number data indicating a number;

mapping data for use in mapping each of a plurality of numbers to a respective string of elements;

the respective string of the number indicated by the map number data having a prefix substring of elements and a suffix substring of elements, the elements of the suffix substring following the elements of the prefix substring, the suffix substring having a suffix ending;

a processor connected for receiving the map number data and connected for accessing the mapping data;

the mapping data comprising;

a first sequence of data units;

the first sequence of data units comprising;

prefix element information indicating the elements of the prefix substring;

first suffix ending information indicating a first number of suffix endings; and

branching information;

the prefix element information, the first suffix ending information, and the branching information being positioned within the first sequence of data units so that the processor can access the first sequence of data units, use the prefix element information to obtain prefix data indicating the elements of the prefix substring, use the first suffix ending information to obtain first number data indicating the first number of suffix endings, and use the branching information to branch either to the second sequence of data units or to the third sequence of data units;

a second sequence of data units;

the second sequence of data units comprising;

a second sequence start data unit; and

second suffix ending information indicating a second number of suffix endings; and

a third sequence of data units;

the third sequence of data units comprising;

a third sequence start data unit;

suffix element information indicating the elements of the suffix substring;

a substring ending data unit indicating the suffix substring'"'"'s suffix ending; and

third suffix ending information indicating a third number of suffix endings between the third sequence start data unit and the substring ending data unit;

the branching information being information that the processor can use to obtain branch indicating data, second sequence branch data, third sequence branch data, and second number data;

the branch indicating data indicating whether to branch to the second sequence of data units or to the third sequence of data units;

the second sequence branch data indicating a location of the second sequence start data unit so that if the branch indicating data indicate a branch to the second sequence of data units, the processor can use the second sequence branch data to access the second sequence of data units;

the third sequence branch data indicating a location of the third sequence start data unit from which a location of the third sequence start data unit can be obtained so that if the branch indicating data indicate a branch to the third sequence of data units, the processor can use the third sequence branch data to access the third sequence of data units;

the second number data indicating the second number of suffix endings;

the third sequence start data unit, the suffix element information, the third suffix ending information, and the substring ending data unit being positioned within the third sequence of data units so that the processor can access the third sequence of data units using the third sequence branch data;

use the third suffix ending information to obtain third number data indicating the third number of suffix endings;

use the map number data, the first number data, the second number data, and the third number data to find the substring ending data unit;

use the suffix element information to obtain suffix data indicating the elements of the suffix substring; and

use the prefix data and the suffix data to obtain the respective string of elements of the number indicated by the map number data.

44. The system of claim 43, further comprising circuitry for obtaining a series of numbers including the numbers in the plurality of numbers, the processor being connected for receiving the series of numbers.

45. An article of manufacture for use in a system that includes circuitry for obtaining string data indicating a string of elements and a processor connected for receiving the string data;

the string having a prefix substring of elements and a suffix substring of elements, the elements of the suffix substring following the elements of the prefix substring, the suffix substring having a suffix ending;

the article comprising;

memory for storing data; and

mapping data stored in the memory so that the processor can access the mapping data for mapping from each of a plurality of strings to a respective number;

the mapping data comprising;

a first sequence of data units;

the first sequence of data units comprising;

prefix element information indicating the elements of the prefix substring;

first suffix ending information indicating a first number of suffix endings; and

branching information;

the prefix element information, the first suffix ending information, and the branching information being positioned within the first sequence of data units so that the processor can access the first sequence of data units, use the prefix element information and the string data to determine that the elements of the prefix substring are indicated by the prefix element information, use the first suffix ending information to obtain first number data indicating the first number of endings, and use the branching information to branch either to the second sequence of data units or to the third sequence of data units;

a second sequence of data units;

the second sequence of data units comprising;

a second sequence start data unit; and

second suffix ending information indicating a second number of suffix endings; and

a third sequence of data units;

the third sequence of data units comprising;

a third sequence start data unit;

suffix element information indicating the elements of the suffix substring;

a substring ending data unit indicating the suffix substring'"'"'s suffix ending; and

third suffix ending information indicating a third number of suffix endings between the third sequence start data unit and the substring ending data unit;

the branching information being information that the processor can use to obtain branch indicating data, second sequence branch data, third sequence branch data, and second number data;

the branch indicating data indicating whether to branch to the second sequence of data units or to the third sequence of data units;

the second sequence branch data indicating a location of the second sequence start data unit so that if the branch indicating data indicate a branch to the second sequence of data units, the processor can use the second sequence branch data to access the second sequence of data units;

the third sequence branch data indicating a location of the third sequence start data unit from which a location of the third sequence start data unit can be obtained so that if the branch indicating data indicate a branch to the third sequence of data units, the processor can use the third sequence branch data to access the third sequence of data units;

the second number data indicating the second number of suffix endings;

the third sequence start data unit, the suffix element information, and the third suffix ending information being positioned within the third sequence of data units so that the processor can access the third sequence of data units using the third sequence branch data;

use the third suffix ending information to obtain third number data indicating the third number of suffix endings;

use the third element information and the string data to determine that the elements of the suffix substring are indicated by the third element information; and

use the first number data, the second number data, and the third number data to obtain the string'"'"'s respective number.

46. An article of manufacture for use in a system that includes circuitry for obtaining number data indicating a number and a processor connected for receiving the number data;

the article comprising;

memory for storing data; and

mapping data stored in the memory so that the processor can access the mapping data for mapping from each of a plurality of numbers to a respective string of elements;

the respective string of the number indicated by the number data having a prefix substring of elements and a suffix substring of elements, the elements of the suffix substring following the elements of the prefix substring, the suffix substring having a suffix ending;

the mapping data comprising;

a first sequence of data units;

the first sequence of data units comprising;

prefix element information indicating the elements of the prefix substring;

first suffix ending information indicating a first number of suffix endings; and

branching information;

the prefix element information, the first suffix ending information, and the branching information being positioned within the first sequence of data units so that the processor can access the first sequence of data units, use the prefix element information to obtain prefix data indicating the elements of the prefix substring, use the first suffix ending information to obtain first number data indicating the first number of suffix endings, and use the branching information to branch either to the second sequence of data units or to the third sequence of data units;

a second sequence of data units;

the second sequence of data units comprising;

a second sequence start data unit; and

second suffix ending information indicating a second number of suffix endings; and

a third sequence of data units;

the third sequence of data units comprising;

a third sequence start data unit;

suffix element information indicating the elements of the suffix substring;

a substring ending data unit indicating the suffix substring'"'"'s suffix ending; and

third suffix ending information indicating a third number of suffix endings between the third sequence start data unit and the substring ending data unit;

the branching information being information that the processor can use to obtain branch indicating data, second sequence branch data, third sequence branch data, and second number data;

the branch indicating data indicating whether to branch to the second sequence of data units or to the third sequence of data units;

the second sequence branch data indicating a location of the second sequence start data unit so that if the branch indicating data indicate a branch to the second sequence of data units, the processor can use the second sequence branch data to access the second sequence of data units;

the third sequence branch data indicating a location of the third sequence start data unit from which a location of the third sequence start data unit can be obtained so that if the branch indicating data indicate a branch to the third sequence of data units, the processor can use the third sequence branch data to access the third sequence of data units;

the second number data indicating the second number of suffix endings;

the third sequence start data unit, the suffix element information, the third suffix ending information, and the substring ending data unit being positioned within the third sequence of data units so that the processor can access the third sequence of data units using the third sequence branch data;

use the third suffix ending information to obtain third number data indicating the third number of suffix endings;

use the map number data, the first number data, the second number data, and the third number data to find the substring ending data unit;

use the suffix element information to obtain suffix data indicating the elements of the suffix substring; and

use the prefix data and the suffix data to obtain the respective string of elements of the number indicated by the map number data.

47. An article of manufacture for use in a system that includes circuitry for obtaining string data indicating a string of elements and a digital processor connected for receiving the string data;

the string having a prefix substring of elements and a suffix substring of elements, the elements of the suffix substring following the elements of the prefix substring, the suffix substring having a suffix ending;

the article comprising;

digital memory for storing data in a form accessible by the digital processor; and

mapping data stored in the digital memory so that the digital processor can access the mapping data for mapping from each of a plurality of strings to a respective number;

the mapping data comprising;

a first sequence of data units;

the first sequence of data units comprising;

prefix element information indicating the elements of the prefix substring;

first suffix ending information indicating a first number of suffix endings; and

branching information;

the prefix element information, the first suffix ending information, and the branching information being positioned within the first sequence of data units so that the digital processor can access the first sequence of data units, use the prefix element information and the string data to determine that the elements of the prefix substring are indicated by the prefix element information, use the first suffix ending information to obtain first number data indicating the first number of endings, and use the branching information to branch either to the second sequence of data units or to the third sequence of data units;

a second sequence of data units;

the second sequence of data units comprising;

a second sequence start data unit; and

second suffix ending information indicating a second number of suffix endings; and

a third sequence of data units;

the third sequence of data units comprising;

a third sequence start data unit;

suffix element information indicating the elements of the suffix substring;

a substring ending data unit indicating the suffix substring'"'"'s suffix ending; and

third suffix ending information indicating a third number of suffix endings between the third sequence start data unit and the substring ending data unit;

the branching information being information that the digital processor can use to obtain branch indicating data, second sequence branch data, third sequence branch data, and second number data;

the branch indicating data indicating whether to branch to the second sequence of data units or to the third sequence of data units;

the second sequence branch data indicating a location of the second sequence start data unit so that if the branch indicating data indicate a branch to the second sequence of data units, the digital processor can use the second sequence branch data to access the second sequence of data units;

the third sequence branch data indicating a location of the third sequence start data unit from which a location of the third sequence start data unit can be obtained so that if the branch indicating data indicate a branch to the third sequence of data units, the digital processor can use the third sequence branch data to access the third sequence of data units;

the second number data indicating the second number of suffix endings;

the third sequence start data unit, the suffix element information, and the third suffix ending information being positioned within the third sequence of data units so that the digital processor can access the third sequence of data units using the third sequence branch data;

use the third suffix ending information to obtain third number data indicating the third number of suffix endings;

use the third element information and the string data to determine that the elements of the suffix substring are indicated by the third element information; and

use the first number data, the second number data, and the third number data to obtain the string'"'"'s respective number.

48. An article of manufacture for use in a system that includes circuitry for obtaining number data indicating a number and a digital processor connected for receiving the number data;

the article comprising;

digital memory for storing data in a form accessible by the digital processor; and

mapping data stored in the digital memory so that the digital processor can access the mapping data for mapping from each of a plurality of numbers to a respective string of elements;

the respective string of the number indicated by the number data having a prefix substring of elements and a suffix substring of elements, the elements of the suffix substring following the elements of the prefix substring, the suffix substring having a suffix ending;

the mapping data comprising;

a first sequence of data units;

the first sequence of data units comprising;

prefix element information indicating the elements of the prefix substring;

first suffix ending information indicating a first number of suffix endings; and

branching information;

the prefix element information, the first suffix ending information, and the branching information being positioned within the first sequence of data units so that the digital processor can access the first sequence of data units, use the prefix element information to obtain prefix data indicating the elements of the prefix substring, use the first suffix ending information to obtain first number data indicating the first number of suffix endings, and use the branching information to branch either to the second sequence of data units or to the third sequence of data units;

a second sequence of data units;

the second sequence of data units comprising;

a second sequence start data unit; and

second suffix ending information indicating a second number of suffix endings; and

a third sequence of data units;

the third sequence of data units comprising;

a third sequence start data unit;

suffix element information indicating the elements of the suffix substring;

a substring ending data unit indicating the suffix substring'"'"'s suffix ending; and

third suffix ending information indicating a third number of suffix endings between the third sequence start data unit and the substring ending data unit;

the branching information being information that the digital processor can use to obtain branch indicating data, second sequence branch data, third sequence branch data, and second number data;

the branch indicating data indicating whether to branch to the second sequence of data units or to the third sequence of data units;

the second sequence branch data indicating a location of the second sequence start data unit so that if the branch indicating data indicate a branch to the second sequence of data units, the digital processor can use the second sequence branch data to access the second sequence of data units;

the third sequence branch data indicating a location of the third sequence start data unit from which a location of the third sequence start data unit can be obtained so that if the branch indicating data indicate a branch to the third sequence of data units, the digital processor can use the third sequence branch data to access the third sequence of data units;

the second number data indicating the second number of suffix endings;

the third sequence start data unit, the suffix element information, the third suffix ending information, and the substring ending data unit being positioned within the third sequence of data units so that the digital processor can access the third sequence of data units using the third sequence branch data;

use the third suffix ending information to obtain third number data indicating the third number of suffix endings;

use the map number data, the first number data, the second number data, and the third number data to find the substring ending data unit;

use the suffix element information to obtain suffix data indicating the elements of the suffix substring; and

use the prefix data and the suffix data to obtain the respective string of elements of the number indicated by the map number data.