Modifying an input string partitioned in accordance with directionality and length constraints

• US 6,023,760 A
• Filed: 05/16/1997
• Issued: 02/08/2000
• Est. Priority Date: 06/22/1996
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Karttunen, Lauri J.
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US08/857,942
• Time in Patent Office: 998 Days
• Field of Search: 395/898, 704/2, 704/9, 704/10, 707/6, 341/55, 712/300
• US Class Current: 712/300
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

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.

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.

2. The method of claim 1 wherein the second substring includes a copy of the first substring and also includes one or more marking elements.

3. The method of claim 2 wherein the second substring includes a first marking element at an end of the cony of the first substring.

4. The method of claim 3 wherein the first substring includes a multiword token and the first marking element includes an end-of-token symbol.

5. The method of claim 2 wherein the second substring includes a second marking element at a start of the copy of the first substring.

6. The method of claim 5 wherein the second substring further includes a third marking element at an end of the copy of the first substring and wherein the first substring is one of a set of regular expressions, the second marking element including a prefix symbol, and the third marking element including a suffix symbol.

7. The method of claim 1 wherein the first substring is one of a proper name, a date, an address, a formatted number, a sequence of white space characters, a letter sequence, a multiword expression, or a phrase.

8. The method of claim 1 in which the finite state data structure is a finite state transducer.

9. The method of claim 1 wherein the the second substring includes a string from a second regular language.

10. The method of claim 9 wherein the first substring includes a first indicator at a start of the first substring and a second indicator at an end of the first substring, and wherein the second substring includes an empty string.

11. The method of claim 9 wherein the first substring includes a first indicator, and wherein the second substring includes the first indicator.

12. The method of claim 9 wherein the first substring includes a second indicator at a start of the first substring, and wherein said second substring includes the second indicator.

13. The method of claim 12 wherein at least one of the first indicator and the second indicator is a regular pattern.

14. The method of claim 12 wherein the first indicator includes a SGML start tag and the second indicator includes a SGML end tag.

15. The method of claim 8 in which the finite state transducer is deterministic and in which the output string is a unique output string produced by applying the input string to the finite state transducer.

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; and

a 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.

17. The article of claim 16 in which the finite state data structure is a finite state transducer.

18. The article of claim 17 in which the finite state transducer is deterministic and in which the output string is a unique output string produced by applying the input string to the finite state transducer.

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.

20. The machine of claim 19 in which the finite state data structure is a deterministic finite state transducer and in which the output string is a unique output string produced by applying the input string to the finite state transducer.