US5136289A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dictionary searching system
Assignee: Fujitsu Ltd
•
Filing: 1991-08-06
•
Granted: 1992-08-04
•
Expires: 2011-08-06
Abstract
Abstract A dictionary searching system retrieves a character string which is described by input reference number and characters from a plurality of mutually different character strings which are registered in a dictionary in correspondence with reference numbers assigned to the character strings. The dictionary searching system includes a dictionary which is made up of an index part for storing in correspondence with the reference numbers a reference number which is assigned to one of character strings which are obtained by adding a character to the character string which is assigned the input reference number and the character which is added to the one of the character strings and a list part for storing in correspondence with the reference numbers a reference number which is assigned to one of character strings having a last character which differs from that of the character string which is assigned the input reference number and the character which is added to the one of the character strings, a reading part for initially reading information from the index part by specifying the input reference number and thereafter reading information from the list part by specifying the reference number which is read from the dictionary, a detecting part for detecting each character which matches the input characters out of characters read from the dictionary and for outputting a result of this detection as a retrieval result, and a deciding part for deciding whether or not a reference number is included in an output of the dictionary and for outputting a result of this detection as a retrieval result, where the reading part, the detecting part and the deciding part operate independently of each other.
Inventors
- 👤 Shigeru Yoshida
- 👤 Yasuhiko Nakano
- 👤 Yoshiyuki Okada
- 👤 Hirotaka Chiba
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 05:43
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/237; G06F40/242; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3088
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
285 words
A dictionary searching system for retrieving a character string which is described by input reference number and characters from a plurality of mutually different character strings which are registered in a dictionary in correspondence with reference numbers assigned to the character strings, said dictionary searching system comprising: a dictionary including an index part and a list part, said index part storing in correspondence with the reference numbers a reference number which is assigned to one of character strings which are obtained by adding a character to the character string which is assigned the input reference number and the character which is added to the one cf the character strings, said list part storing in correspondence with the reference numbers a reference number which is assigned to one of character strings having a last character which differs from that of the character string which is assigned the input reference number and the character which is added to the one of the character strings; reading means, coupled to said dictionary, for initially reading information from the index part by specifying the input reference number and thereafter reading information from the list part by specifying the reference number which is read from said dictionary; detecting means, coupled to said dictionary, for detecting each character which matches the input characters out of characters read from said dictionary and for outputting a result of this detection as a retrieval result; and deciding means, coupled to said dictionary, for deciding whether or not a reference number is included in an output of said dictionary and for outputting a result of this detection as a retrieval result, said reading means, said detecting means and said deciding means operating independently of each other.
Claim 2
Dependent Claim
285 words
A dictionary searching system for retrieving a character string which is described by input reference number and characters from a plurality of mutually different character strings which are registered in a dictionary in correspondence with reference numbers assigned to the character strings, said dictionary searching system comprising: a dictionary including an index part and a list part, said index part storing in correspondence with the reference numbers a reference number which is assigned to one of character strings which are obtained by adding a character to the character string which is assigned the input reference number and the character which is added to the one cf the character strings, said list part storing in correspondence with the reference numbers a reference number which is assigned to one of character strings having a last character which differs from that of the character string which is assigned the input reference number and the character which is added to the one of the character strings; reading means, coupled to said dictionary, for initially reading information from the index part by specifying the input reference number and thereafter reading information from the list part by specifying the reference number which is read from said dictionary; detecting means, coupled to said dictionary, for detecting each character which matches the input characters out of characters read from said dictionary and for outputting a result of this detection as a retrieval result; and deciding means, coupled to said dictionary, for deciding whether or not a reference number is included in an output of said dictionary and for outputting a result of this detection as a retrieval result, said reading means, said detecting means and said deciding means operating independently of each other.
Claim 3
Dependent Claim
53 words
The dictionary searching system as claimed in claim 1, wherein said reading means carries out a reading process in which information from said dictionary at predetermined time intervals, and said detecting means and said deciding means respectively carry out detecting and deciding processes in parallel with the reading process of said reading means.
Claim 4
Dependent Claim
32 words
The dictionary searching system as claimed in claim 2, wherein the processes of said reading means, said detecting means and said deciding means are carried out in a form of pipeline processing.
Claim 5
Dependent Claim
45 words
The dictionary searching system as claimed in claim 1, wherein the retrieval result output from said detecting means indicates that a character string corresponding to the input character string is found in said dictionary when the characters read from said dictionary match the input characters.
Claim 6
Dependent Claim
56 words
The dictionary searching system as claimed in claim 1, wherein the retrieval result output from said deciding means indicates that no character string corresponding to the input character string is registered in said dictionary when at least one of the index part and the list part stores no reference number corresponding to the input reference number.
Claim 7
Dependent Claim
313 words
A dictionary searching system for retrieving a character string which is described by input reference number and characters from a plurality of mutually different character strings which are registered in a ditionary in correspondence with reference numbers assigned to the character strings, said dictionary searching system comprising: a dictionary including an index part and a list part, said index part storing in correspondence with the reference numbers identification information corresponding to one of candidate character strings which are obtained by adding a character to the character string which is assigned the input reference number and pointers which indicate storage locations of other candidate character strings, said list part storing in correspondence with the reference numbers identification information corresponding to one of candidate character strings having a last character which differs from that of the character string which is assigned the input reference number and pointers which indicate storage locations of other candidate character strings; reading means, coupled to said dictionary, for initially reading the pointer and identification information from the index part based on the input reference number and thereafter reading the pointer and identification information from the list part by specifying the list part by the pointer which is read from said dictionary; detecting means, coupled to said dictionary, including comparator means for comparing each identification information read from said dictionary with the input characters, for detecting each character which matches the input characters out of the candidate character string read from said dictionary and for outputting a result of this detection as a retrieval result; and deciding means, coupled to said dictionary, for deciding whether or not an unread candidate character string exists in said dictionary based on the pointer read from said dictionary and for outputting a result of this detection as a retrieval result, said reading means, said detecting means and said deciding means operating independently of each other.
Claim 8
Dependent Claim
313 words
A dictionary searching system for retrieving a character string which is described by input reference number and characters from a plurality of mutually different character strings which are registered in a ditionary in correspondence with reference numbers assigned to the character strings, said dictionary searching system comprising: a dictionary including an index part and a list part, said index part storing in correspondence with the reference numbers identification information corresponding to one of candidate character strings which are obtained by adding a character to the character string which is assigned the input reference number and pointers which indicate storage locations of other candidate character strings, said list part storing in correspondence with the reference numbers identification information corresponding to one of candidate character strings having a last character which differs from that of the character string which is assigned the input reference number and pointers which indicate storage locations of other candidate character strings; reading means, coupled to said dictionary, for initially reading the pointer and identification information from the index part based on the input reference number and thereafter reading the pointer and identification information from the list part by specifying the list part by the pointer which is read from said dictionary; detecting means, coupled to said dictionary, including comparator means for comparing each identification information read from said dictionary with the input characters, for detecting each character which matches the input characters out of the candidate character string read from said dictionary and for outputting a result of this detection as a retrieval result; and deciding means, coupled to said dictionary, for deciding whether or not an unread candidate character string exists in said dictionary based on the pointer read from said dictionary and for outputting a result of this detection as a retrieval result, said reading means, said detecting means and said deciding means operating independently of each other.
Claim 9
Dependent Claim
53 words
The dictionary searching system as claimed in claim 6, wherein said reading means carries out a reading process in which information from said dictionary at predetermined time intervals, and said detecting means and said deciding means respectively carry out detecting and deciding processes in parallel with the reading process of said reading means.
Claim 10
Dependent Claim
32 words
The dictionary searching system as claimed in claim 7, wherein the processes of said reading means, said detecting means and said deciding means are carried out in a form of pipeline processing.
Claim 11
Dependent Claim
31 words
The dictionary searching system as claimed in claim 6, wherein the identification information includes the reference number of the candidate character string and the last character of the candidate character string.
Claim 12
Dependent Claim
52 words
The dictionary searching system as claimed in claim 6, wherein said list part includes a plurality of lists respectively storing at least one candidate character string, and said comparator means includes a plurality of comparators for simultaneously making the match detection for each of the candidate character strings read from the lists.
Claim 13
Dependent Claim
29 words
The dictionary searching system as claimed in claim 10, wherein the lists of the list part within said dictionary respectively correspond to lists used by an open hashing method.
References Cited (Backward Citations)
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4701745A
Cited
US4876541A
Cited
US4881075A
Cited
US5058137A
Cited
US5049881A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-08-04 | 1996-02-03 | 1996-08-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-08-04 | 2000-02-03 | 2000-08-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-08-04 | 2004-02-03 | 2004-08-04 | $7700.00 | Window Closed / Lapsed |