Stored mapping data with information for skipping branches while keeping count of suffix endings

Claim 1

An article of manufacture for use in a machine that includes a processor, the article comprising: memory for storing data, the data stored in the memory being accessible by the processor when the article is used in the machine; and mapping data stored in the memory; the mapping data indicating a set of strings of elements; the mapping data comprising; data units arranged in a sequence and indicating information about strings in the set such that the mapping data can be used by the processor to perform mapping between each string in the set and a respective number by keeping count os suffix endings; the data units including: a branching subsequence of data units from which the processor can continue to any of N branch subsequences of data units during mapping, where N is greater than one; the N branch subsequences having an order; branch skipping information that the processor can obtain from the branching subsequence; the branch skipping information indicating, for each of the N branch subsequences, a number of suffix endings; the number of suffix endings for each branch subsequence being equal to a number of suffix endings that would be skipped if the processor skips the branch subsequences preceding the branch subsequence in the order; and branch taking information that the processor can obtain from the branching subsequence; the branch taking information indicating, for each of the N branch subsequences, a location at which the processor can access the branch subsequence; the branch skipping information and the branch taking information together providing sufficient information that the processor can access any of the N branch subsequences, skip any branch subsequences that precede the accessed branch subsequence in the order, and keep a count of suffix endings that accurately reflects any suffix endings skipped.

Claim 6

A method of operating a machine; the machine including: memory for storing data; a processor connected for accessing data stored in the memory; and mapping data stored in the memory; the mapping data indicating a set of strings of elements; the mapping data including; data units arranged in a sequence and indicating information about strings in the set such that the mapping data can be used by the processor to perform mapping between each string in the set and a respective number by keeping count of suffix endings; the data units including: a branching subsequence of data units from which the processor can continue to any of N branch subsequences of data units during mapping, where N is greater than one; the N branch subsequences having an order; branch skipping information that the processor can obtain from the branching subsequence; the branch skipping information indicating, for each of the N branch subsequences, a number of suffix endings; the number of suffix endings for each branch subsequence being equal to a number of suffix endings that would be skipped if the processor skips the branch subsequences preceding the branch subsequence in the order; and branch taking information that the processor can obtain from the branching subsequence; the branch taking information indicating, for each of the N branch subsequences, a location at which the processor can access the branch subsequence; the branch skipping information and the branch taking information together providing sufficient information that the processor can access any of the N branch subsequences, skip any branch subsequences that precede the accessed branch subsequence in the order, and keep a count of suffix endings that accurately reflects any suffix endings skipped; the method comprising: operating the processor to obtain a string of elements; operating the processor to map the string of elements to a respective number; the string of elements including a prefix substring of elements and a suffix substring of elements; the act of operating the processor to map the string of elements comprising: using the prefix substring of elements to access the branching subsequence and obtain a prefix count of suffix endings; using the suffix substring of elements to obtain branch indicating data indicating a first one of the N branch subsequences in which to continue mapping; using the branch indicating data to obtain the branch skipping information and the branch taking information for the first branch subsequence; using the branch skipping information for the first branch subsequence and the prefix count of suffix endings to obtain an updated count of suffix endings; the updated count indicating the sum of the prefix count and the number of suffix endings that would be skipped if the processor skips the branch subsequences preceding the first branch subsequence in the order; and using the branch taking information for the first branch subsequence to access the first branch subsequence to continue mapping.

Claim 7

A method of operating a machine; the machine including: memory for storing data; a processor connected for accessing data stored in the memory; and mapping data stored in the memory; the mapping data indicating a set of strings of elements; the mapping data including; data units arranged in a sequence and indicating information about strings in the set such that the mapping data can be used by the processor to perform mapping between each string in the set and a respective number by keeping count of suffix endings; the data units including: a branching subsequence of data units from which the processor can continue to any of N branch subsequences of data units during mapping, where N is greater than one; the N branch subsequences having an order; branch skipping information that the processor can obtain from the branching subsequence; the branch skipping information indicating, for each of the N branch subsequences, a number of suffix endings; the number of suffix endings for each branch subsequence being equal to a number of suffix endings that would be skipped if the processor skips the branch subsequences preceding the branch subsequence in the order; and branch taking information that the processor can obtain from the branching subsequence; the branch taking information indicating, for each of the N branch subsequences, a location at which the processor can access the branch subsequence; the branch skipping information and the branch taking information together providing sufficient information that the processor can access any of the N branch subsequences, skip any branch subsequences that precede the accessed branch subsequence in the order, and keep a count of suffix endings that accurately reflects any suffix endings skipped; the method comprising: operating the processor to obtain a string of elements; operating the processor to map the string of elements to a respective number; the string of elements including a prefix substring of elements and a suffix substring of elements; the act of operating the processor to map the string of elements comprising: using the prefix substring of elements to access the branching subsequence and obtain a prefix count of suffix endings; using the suffix substring of elements to obtain branch indicating data indicating a first one of the N branch subsequences in which to continue mapping; using the branch indicating data to obtain the branch skipping information and the branch taking information for the first branch subsequence; using the branch skipping information for the first branch subsequence and the prefix count of suffix endings to obtain an updated count of suffix endings; the updated count indicating the sum of the prefix count and the number of suffix endings that would be skipped if the processor skips the branch subsequences preceding the first branch subsequence in the order; and using the branch taking information for the first branch subsequence to access the first branch subsequence to continue mapping.

Claim 8

A method of operating a machine; the machine including: memory for storing data; a processor connected for accessing data stored in the memory; and mapping data stored in the memory; the mapping data indicating a set of strings of elements; the mapping data including; data units arranged in a sequence and indicating information about strings in the set such that the mapping data can be used by the processor to perform mapping between each string in the set and a respective number by keeping count of suffix endings; the data units including: a branching subsequence of data units from which the processor can continue to any of N branch subsequences of data units during mapping, where N is greater than one; the N branch subsequences having an order; branch skipping information that the processor can obtain from the branching subsequence; the branch skipping information indicating, for each of the N branch subsequences, a number of suffix endings; the number of suffix endings for each branch subsequence being equal to a number of suffix endings that would be skipped if the processor skips the branch subsequences preceding the branch subsequence in the order; and branch taking information that the processor can obtain from the branching subsequence; the branch taking information indicating, for each of the N branch subsequences, a location at which the processor can access the branch subsequence; the branch skipping information and the branch taking information together providing sufficient information that the processor can access any of the N branch subsequences, skip any branch subsequences that precede the accessed branch subsequence in the order, and keep a count of suffix endings that accurately reflects any suffix endings skipped; the method comprising: operating the processor to obtain a number; operating the processor to map the number to a respective string of elements; the respective string including a prefix substring of elements and a suffix substring of elements; the act of operating the processor to map the number comprising: using the number to access the branching subsequence, to obtain a count of remaining suffix endings, and to obtain the prefix substring of elements; using the count of remaining suffix endings and the branch skipping information of the N branch subsequences to obtain branch indicating data indicating a first one of the N branch subsequences in which to continue mapping; using the branch indicating data to obtain the branch skipping information and the branch taking information for the first branch subsequence; using the branch skipping information for the first branch subsequence and the count of remaining suffix endings to obtain an updated count of remaining suffix endings; the updated count indicating a result of subtracting, from the count of remaining suffix endings, the number of suffix endings that would be skipped if the processor skips the branch subsequences preceding the first branch subsequence in the order; and using the branch taking information for the first branch subsequence to access the first branch subsequence to continue mapping.

Claim 9

A method of operating a machine; the machine including: memory for storing data; a processor connected for accessing data stored in the memory; and mapping data stored in the memory; the mapping data indicating a set of strings of elements; the mapping data including; data units arranged in a sequence and indicating information about strings in the set such that the mapping data can be used by the processor to perform mapping between each string in the set and a respective number by keeping count of suffix endings; the data units including: a branching subsequence of data units from which the processor can continue to any of N branch subsequences of data units during mapping, where N is greater than one; the N branch subsequences having an order; branch skipping information that the processor can obtain from the branching subsequence; the branch skipping information indicating, for each of the N branch subsequences, a number of suffix endings; the number of suffix endings for each branch subsequence being equal to a number of suffix endings that would be skipped if the processor skips the branch subsequences preceding the branch subsequence in the order; and branch taking information that the processor can obtain from the branching subsequence; the branch taking information indicating, for each of the N branch subsequences, a location at which the processor can access the branch subsequence; the branch skipping information and the branch taking information together providing sufficient information that the processor can access any of the N branch subsequences, skip any branch subsequences that precede the accessed branch subsequence in the order, and keep a count of suffix endings that accurately reflects any suffix endings skipped; the method comprising: operating the processor to obtain a number; operating the processor to map the number to a respective string of elements; the respective string including a prefix substring of elements and a suffix substring of elements; the act of operating the processor to map the number comprising: using the number to access the branching subsequence, to obtain a count of remaining suffix endings, and to obtain the prefix substring of elements; using the count of remaining suffix endings and the branch skipping information of the N branch subsequences to obtain branch indicating data indicating a first one of the N branch subsequences in which to continue mapping; using the branch indicating data to obtain the branch skipping information and the branch taking information for the first branch subsequence; using the branch skipping information for the first branch subsequence and the count of remaining suffix endings to obtain an updated count of remaining suffix endings; the updated count indicating a result of subtracting, from the count of remaining suffix endings, the number of suffix endings that would be skipped if the processor skips the branch subsequences preceding the first branch subsequence in the order; and using the branch taking information for the first branch subsequence to access the first branch subsequence to continue mapping.