Patent US5950184A successfully refreshed from Google Patents.
US5950184A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Indexing a database by finite-state transducer
Assignee: Xerox Corp
•
Filing: 1996-11-14
•
Granted: 1999-09-07
•
Expires: 2016-11-14
Abstract
Abstract A technique of using the path numbers of an acyclic finite-state transducer as a method of indexing a database. Each entry in the database has associated therewith one or more keys. A finite state transducer is provided defining the keys for the database. For each key, a path number is determined associated with that key, the path number defining a mapping between that key and the (or each) corresponding entry in the database.
Inventors
- 👤 Lauri J. Karttunen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:48
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; Y; Y10; Y10S; Y10S707/00; Y10S707/99931
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
92 words
A method of indexing a database, each entry in the database having associated therewith one or more keys, said method comprising the steps of: (a) providing a finite-state transducer defining the keys for the database, each state in said finite-state transducer having an associated state number; (b) generating a path number for each key using said finite-state transducer, said path number based solely on said associated state number for states in said finite-state transducer, said path number defining a mapping between that key and the or each corresponding entry in the database.
Claim 2
Independent Claim
92 words
A method of indexing a database, each entry in the database having associated therewith one or more keys, said method comprising the steps of: (a) providing a finite-state transducer defining the keys for the database, each state in said finite-state transducer having an associated state number; (b) generating a path number for each key using said finite-state transducer, said path number based solely on said associated state number for states in said finite-state transducer, said path number defining a mapping between that key and the or each corresponding entry in the database.
Claim 3
Dependent Claim
44 words
The method of claim 1, further comprising the step (c) of generating a file position map defining the address, in the database, of each of said entries, and wherein each entry in said file position map is associated with one of said path numbers.
Claim 4
Dependent Claim
46 words
The method of claim 1, wherein step (a) further comprises: for each state in the finite-state transducer, associating said state number with that state, said state number preferably equating to the number of paths of any length (Including zero) from that state to a final state.
Claim 5
Dependent Claim
40 words
The method of claim 3, wherein step (b) further comprises: (b1) for each path in the finite state transducer, determining a path number, associated with that path, as a function of the state numbers of the states along that path.
Claim 6
Dependent Claim
30 words
The method of claim 1, wherein step (b) further comprises: (b1) generating a mapping of each path number to the address of the or each corresponding entry in the database.
Claim 7
Dependent Claim
12 words
The method of claim 1, wherein said database comprises an electronic dictionary.
Claim 8
Dependent Claim
17 words
The method of claim 6, wherein the or each said key comprises a headword in the dictionary.
Claim 9
Dependent Claim
25 words
The method of claim 7 in which the headword of the or each said key is a headword associated with an additional marker or markers.
Claim 10
Dependent Claim
29 words
The method of claim 8 wherein at least one additional marker is selected from the group consisting of a part-of-speech tag, a sense number, and a target language indicator.
Claim 11
Independent Claim
176 words
A method of retrieving an entry in a database comprising the steps of: indexing said database by performing the steps of: (a) providing a finite-state transducer defining the keys for the database, each state in said finite-state transducer having an associated state number; (b) for each key, determining a path number associated with that key using said finite state transducer, said path number based solely on said associated state number for states in said finite-state transducer, and said path number defining a mapping between that key and the or each corresponding entry in the database; (c) generating a file position map defining the address, in the database, of each of said entries, each of said addresses in said file position map associated with one of said path numbers; retrieving said entry by performing the steps of: (d) receiving a key input by a user; (e) determining the or each path number associated with the key using said finite state transducer; and (f) retrieving the entry corresponding to the or each path number determined in step (e).
Claim 12
Independent Claim
176 words
A method of retrieving an entry in a database comprising the steps of: indexing said database by performing the steps of: (a) providing a finite-state transducer defining the keys for the database, each state in said finite-state transducer having an associated state number; (b) for each key, determining a path number associated with that key using said finite state transducer, said path number based solely on said associated state number for states in said finite-state transducer, and said path number defining a mapping between that key and the or each corresponding entry in the database; (c) generating a file position map defining the address, in the database, of each of said entries, each of said addresses in said file position map associated with one of said path numbers; retrieving said entry by performing the steps of: (d) receiving a key input by a user; (e) determining the or each path number associated with the key using said finite state transducer; and (f) retrieving the entry corresponding to the or each path number determined in step (e).
Claim 13
Dependent Claim
32 words
The method of claim 10, wherein step (f) further comprises the substep of obtaining, for the or each path number determined in step (e), a corresponding address in said file position map.
Claim 14
Dependent Claim
28 words
The method of claim 11, wherein step (f) further comprises the substep of retrieving the database entry at the or each address obtained from said file position map.
Claim 15
Dependent Claim
12 words
The method of claim 10, wherein said database comprises an electronic dictionary.
Claim 16
Dependent Claim
106 words
An article of manufacture comprising: a program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for creating an index for a database, said method steps comprising: (a) providing a finite-state transducer defining the keys for the database, each state in said finite-state transducer having an associated state number; (b) generating a path number for each key using said finite-state transducer, said path number based solely on said associated state number for states in said finite-state transducer, said path number defining a mapping between that key and the or each corresponding entry in the database.
Claim 17
Dependent Claim
106 words
An article of manufacture comprising: a program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for creating an index for a database, said method steps comprising: (a) providing a finite-state transducer defining the keys for the database, each state in said finite-state transducer having an associated state number; (b) generating a path number for each key using said finite-state transducer, said path number based solely on said associated state number for states in said finite-state transducer, said path number defining a mapping between that key and the or each corresponding entry in the database.
Claim 18
Dependent Claim
66 words
The article of manufacture as recited in claim 14, wherein said method steps are further for retrieving an entry in said database, said method steps further comprising: (d) receiving a key input by a user; (e) determine the or each path number associated the key using said finite state transducer; and (f) retrieving the entry corresponding to the or each path number determined in step (e).
Claim 19
Independent Claim
100 words
An apparatus comprising a processor, a memory device operatively coupled to the processor, and means for indexing a database, each entry in the database having associated therewith one or more keys, by: (a) providing a finite-state transducer defining the keys for the database, each state in said finite-state transducer having an associated state number; (b) generating a path number for each key using said finite-state transducer, said path number based solely on said associated state number for states in said finite-state transducer, said path number defining a mapping between that key and the or each corresponding entry in the database.
Claim 20
Independent Claim
100 words
An apparatus comprising a processor, a memory device operatively coupled to the processor, and means for indexing a database, each entry in the database having associated therewith one or more keys, by: (a) providing a finite-state transducer defining the keys for the database, each state in said finite-state transducer having an associated state number; (b) generating a path number for each key using said finite-state transducer, said path number based solely on said associated state number for states in said finite-state transducer, said path number defining a mapping between that key and the or each corresponding entry in the database.
Claim 21
Dependent Claim
28 words
The apparatus of claim 16 wherein the indexing means comprises a software program executable by the processor, the program being stored at least partially in the memory device.
Claim 22
Dependent Claim
50 words
The apparatus of claim 16 further comprising: means for retrieving an entry from a database by: (d) receiving a key input from the input device; (e) determining the or each path number associated with the key; and (f) retrieving the entry corresponding to the or each path number thus determined.
Claim 23
Dependent Claim
28 words
The apparatus of claim 18 wherein the entry-retrieving means comprises a software program executable by the processor, the program being stored at least partially in the memory device.
References Cited (Backward Citations)
US4285049A
Cited
US5754847A
Cited
US5553283A
Cited
US5551026A
Cited
US5278981A
Cited
US5519857A
Cited
US5452451A
Cited
US5369577A
Cited
US5388234A
Cited
US5594641A
Cited
US5625554A
Cited
EP0583083A2
Cited
US5642522A
Cited
EP0649105A1
Cited
US5680511A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-06 | 2003-03-08 | 2003-09-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-06 | 2007-03-08 | 2007-09-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-06 | 2011-03-08 | 2011-09-07 | $7700.00 | Window Closed / Lapsed |