Modifying an input string partitioned in accordance with directionality and length constraints
First Claim
1. A processor implemented method of modifying an input string of a regular language, the input string including at least two symbols, the method comprising:
- a) receiving the input string;
b) applying the input string to a finite state data structure to obtain an output string that is a modified version of the input string in which a first substring in the input string is replaced by a second substring in the output string;
the finite state data structure indicating a set of replaceable substrings that includes the first substring and indicating, for each replaceable substring, a replacement substring, the second substring being the replacement substring of the first substring;
the input string being partitionable into any of two or more different substring series in accordance with the set of replaceable substrings;
the finite state data structure partitioning the input string into a substring series that includes the first substring in accordance with a directionality constraint and a length constraint;
the finite state data structure being derived to partition input strings only in accordance with the directionality constraint and the length constraint;
the directionality constraint requiring partition of the input string as if the set of replaceable substrings were compared with the input string by one of from-left-to-right and from-right-to-left; and
the length constraint requiring partition of the input string as if, where two or more of the set of replaceable substrings could be matched, one of the matching replaceable substrings was selected for replacement, the selected substring being the longest or the shortest; and
c) providing the output string as output.
4 Assignments
0 Petitions
Accused Products
Abstract
A processor implemented method of modifying a string of a regular language, which includes at least two symbols and at least two predetermined substrings. Upon receipt of the string, the processor determines an initial position within the string of a substring matching one of the preselected substrings. To make this determination, the processor either matches symbols of the string starting from the left and proceeding to the right or by starting from the right and proceeding to the left. After identifying the initial position, the processor then selects either the longest or the shortest of the preselected substrings. The processor then replaces the matching substring with the string of the lower language associated with the selected preselected substring and outputs the modified string.
-
Citations
20 Claims
-
1. A processor implemented method of modifying an input string of a regular language, the input string including at least two symbols, the method comprising:
-
a) receiving the input string; b) applying the input string to a finite state data structure to obtain an output string that is a modified version of the input string in which a first substring in the input string is replaced by a second substring in the output string;
the finite state data structure indicating a set of replaceable substrings that includes the first substring and indicating, for each replaceable substring, a replacement substring, the second substring being the replacement substring of the first substring;
the input string being partitionable into any of two or more different substring series in accordance with the set of replaceable substrings;
the finite state data structure partitioning the input string into a substring series that includes the first substring in accordance with a directionality constraint and a length constraint;
the finite state data structure being derived to partition input strings only in accordance with the directionality constraint and the length constraint;the directionality constraint requiring partition of the input string as if the set of replaceable substrings were compared with the input string by one of from-left-to-right and from-right-to-left; and the length constraint requiring partition of the input string as if, where two or more of the set of replaceable substrings could be matched, one of the matching replaceable substrings was selected for replacement, the selected substring being the longest or the shortest; and c) providing the output string as output. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. An article of manufacture for use in a system that includes a processor and a storage medium access device, the article comprising:
-
a storage medium for storing data;
data stored on the storage medium being accessible by the processor through the storage medium access device; anda finite state data structure stored on the storage medium to which the processor can apply an input string to obtain an output string that is a modified version of the input string, a first substring in the input string being replaced by a second substring in the output string;
the finite state data structure indicating a set of replaceable substrings that includes the first substring and indicating, for each replaceable substring, a replacement substring, the second substring being the replacement substring of the first substring;
the input string being partitionable into any of two or more different substring series in accordance with the set of replaceable substrings;
the finite state data structure partitioning the input string into a substring series that includes the first substring in accordance with a directionality constraint and a length constraint;
the finite state data structure being derived to partition input strings only in accordance with the directionality constraint and the length constraint;the directionality constraint requiring partition of the input string as if the set of replaceable substrings were compared with the input string by one of from-left-to-right and from-right-to-left; and the length constraint requiring partition of the input string as if, where two or more of the set of replaceable substrings could be matched, one of the matching replaceable substrings was selected for replacement, the selected substring being the longest or the shortest. - View Dependent Claims (17, 18)
-
-
19. A machine comprising:
-
a processor; and a finite state data structure to which the processor can apply an input string to obtain an output string that is a modified version of the input string, a first substring in the input string being replaced by a second substring in the output string;
the finite state data structure indicating a set of replaceable substrings that includes the first substring and indicating, for each replaceable substring, a replacement substring, the second substring being the replacement substring of the first substring;
the input string being partitionable into any of two or more different substring series in accordance with the set of replaceable substrings;
the finite state data structure partitioning the input string into a substring series that includes the first substring in accordance with a directionality constraint and a length constraint;
the finite state data structure being derived to partition input strings only in accordance with the directionality constraint and the length constraint;the directionality constraint requiring partition of the input string as if the set of replaceable substrings were compared with the input string by one of from-left-to-right and from-right-to-left; and the length constraint requiring partition of the input string as if, where two or more of the set of replaceable substrings could be matched, one of the matching replaceable substrings was selected for replacement, the selected substring being the longest or the shortest. - View Dependent Claims (20)
-
Specification