US5721939A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for tokenizing text
Assignee: Xerox Corp
•
Filing: 1995-08-03
•
Granted: 1998-02-24
•
Expires: 2015-08-03
Abstract
Abstract An efficient method and apparatus for tokenizing natural language text minimizes required data storage and produces guaranteed incremental output. Id (text) is composed with a tokenizer to create a finite state machine representing tokenization paths. The tokenizer itself is in the form of a finite state transducer. The process is carried out in a breadth-first manner so that all possibilities are explored at each character position before progressing. Output is produced incrementally and occurs only when all paths collapse into one. Output may be delayed until a token boundary is reached. In this manner, the output is guaranteed and will not be retracted unless the text is globally ill-formed. Each time output is produced, storage space is freed for subsequent text processing.
Inventors
- 👤 Ronald M. Kaplan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 07:59
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/279; G06F40/284
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
128 words
A method for tokenizing text with a tokenizing transducer comprising the steps of: (a) storing all current configurations including at least one current configuration in a configuration storage unit, the at least one current configuration including an extension state and an output node; (b) selecting one said at least one current configuration that has not been processed; (c) processing said selected current configuration wherein processing includes creating any next configurations; (d) repeating steps b and c until all of said current configurations have been processed; (e) freeing all of said current configurations; (f) redefining all of the any next configurations as current configurations and the next text position as the current text position; (g) counting said current configurations; and (h) providing output when exactly one next configuration exists.
Claim 2
Independent Claim
128 words
A method for tokenizing text with a tokenizing transducer comprising the steps of: (a) storing all current configurations including at least one current configuration in a configuration storage unit, the at least one current configuration including an extension state and an output node; (b) selecting one said at least one current configuration that has not been processed; (c) processing said selected current configuration wherein processing includes creating any next configurations; (d) repeating steps b and c until all of said current configurations have been processed; (e) freeing all of said current configurations; (f) redefining all of the any next configurations as current configurations and the next text position as the current text position; (g) counting said current configurations; and (h) providing output when exactly one next configuration exists.
Claim 3
Dependent Claim
20 words
The method of claim 1, further comprising the step of providing output in the form of a finite state machine.
Claim 4
Dependent Claim
47 words
The method of claim 1, wherein the processing step comprises: selecting any unprocessed transitions from the extension state of the selected configuration; determining a range symbol; and setting an extension state configuration based on the range symbol to one of a current configuration and a next configuration.
Claim 5
Dependent Claim
22 words
The method of claim 3, wherein the extension state configuration has an extension state that is the destination of the selected transition.
Claim 6
Dependent Claim
40 words
The method of claim 4, wherein the extension state configuration is set to the next configuration when the range symbol matches the current text character and is set to the current configuration when the range symbol is equal to epsilon.
Claim 7
Dependent Claim
49 words
The method of claim 5, wherein said processing step further comprises adding an output edge to an output node of the extension state configuration and labelling said output edge with a domain symbol of the selected transition, said output edge pointing to the output node of the selected configuration.
Claim 8
Dependent Claim
21 words
The method of claim 6, wherein said processing step is repeated until all of said any unprocessed transitions have been processed.
Claim 9
Dependent Claim
21 words
The method of claim 1, wherein said step of providing output occurs when the one next configuration is marked for output.
Claim 10
Dependent Claim
29 words
The method of claim 8, wherein said one next configuration is marked for output only if all output edges at its output node are labelled with a token boundary.
Claim 11
Dependent Claim
39 words
The method of claim 1, further comprising: defining all possible paths including at least one path in steps a-f; ending a path prior to reaching an end of text; and deleting said path in order to free storage space.
Claim 12
Dependent Claim
23 words
The method of claim 1, further comprising providing output in the form of a finite state machine having edges pointing to output nodes.
Claim 13
Dependent Claim
16 words
The method of claim 1, wherein said step of providing output comprises outputting a best path.
Claim 14
Dependent Claim
18 words
The method of claim 1, wherein after said step of providing output, the output is deleted from storage.
Claim 15
Dependent Claim
28 words
The method of claim 1, wherein the tokenizing transducer is defined by the following rules: a. .→epsilon/ -- |. b. |→epsilon/ -- punctuation c. space→white-space+; and d. |→white-space+.
Claim 16
Dependent Claim
24 words
The method of claim 1, wherein said tokenizing transducer is created by the steps of: defining punctuation conventions; and defining higher level lexical information.
Claim 17
Dependent Claim
22 words
The method of claim 15, wherein the higher level lexical information includes a list of compound words and a list of abbreviations.
Claim 18
Dependent Claim
25 words
The method of claim 15, further comprising the step of composing the higher level lexical information with the tokenizer to form a finite state transducer.
Claim 19
Dependent Claim
79 words
The method of claim 15, further comprising: representing said higher level lexical information as a transducer H; pairing said tokenizing transducer with H to create acceptable states; selecting any unprocessed transitions from the extension state of the selected configuration; determining a range symbol; determining if said range symbol matches a current text character; and determining whether said transition results in an output edge that has one of the acceptable states if the range symbol matches the current text character.
Claim 20
Independent Claim
122 words
A system for tokenizing text, comprising: an I/O device for inputting recognized text and outputting tokenized text; control means for selecting recognized text and for selecting tokenized text to be output; a tokenizing means for defining configurations each of said configurations comprising, an output node; an extension state; a designation of one of current and next; and a designation of one of processed and unprocessed; determining means for determining all possible transitions at the extension state of each of said configurations; comparing means for comparing a range character with a current text character wherein said determining means defines a path based on the comparison; a configuration storage unit for storing the configurations; and an output storage unit for storing the tokenized text.
Claim 21
Independent Claim
122 words
A system for tokenizing text, comprising: an I/O device for inputting recognized text and outputting tokenized text; control means for selecting recognized text and for selecting tokenized text to be output; a tokenizing means for defining configurations each of said configurations comprising, an output node; an extension state; a designation of one of current and next; and a designation of one of processed and unprocessed; determining means for determining all possible transitions at the extension state of each of said configurations; comparing means for comparing a range character with a current text character wherein said determining means defines a path based on the comparison; a configuration storage unit for storing the configurations; and an output storage unit for storing the tokenized text.
Claim 22
Dependent Claim
40 words
The system of claim 19, further comprising counting means for counting a number of configurations remaining in the configuration storage unit, wherein when the number of remaining configurations is exactly equal to one, the I/O device outputs the tokenized text.
Claim 23
Dependent Claim
31 words
The system to claim 19, wherein the tokenizing means comprises a tokenizing transducer defined by the following rules: a. .→epsilon/ -- |. b. |→epsilon/ -- punctuation c. space→white-space+; and d. |→white-space+.
Claim 24
Dependent Claim
18 words
The system according to claim 19, wherein the tokenizing transducer includes punctuation conventions and higher level lexical information.
Claim 25
Dependent Claim
22 words
The system according to claim 22, wherein the higher level information includes a list of compound words and a list of abbreviations.
Claim 26
Dependent Claim
22 words
The system according to claim 22, wherein the rules are composed with the higher level lexical information to form the tokenizing transducer.
References Cited (Backward Citations)
US5438511A
Cited
US5323316A
Cited
US5477451A
Cited
US5594641A
Cited
JPH06332718A
Cited
US5510981A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-02-23 | 2001-08-25 | 2002-02-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-02-23 | 2005-08-25 | 2006-02-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-02-23 | 2009-08-25 | 2010-02-24 | $7700.00 | Window Closed / Lapsed |