Patent US5267165A successfully refreshed from Google Patents.
US5267165A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data processing device and method for selecting data words contained in a dictionary
Assignee: US Philips Corp
•
Filing: 1991-03-14
•
Granted: 1993-11-30
•
Expires: 2011-03-14
Abstract
Abstract A data processing device for selecting data words which are contained in a dictionary and which are nearest to a data word to be processed according to a correspondence criterion. The device includes: first apparatus for segmenting the space enclosing the assembly of data words of the dictionary; second apparatus for generating, for each segment, sub-dictionaries by making an arbitrary segment correspond, in accordance with the correspondence criterion, to words of a sub-dictionary; third apparatus for utilising the sub-dictionaries by determining, for an arbitrary data word to be processed, the segment with which it is associated, followed by determination, in accordance with the correspondence criterion, of that word or words among the words of the sub-dictionary associated with the segment which corresponds (correspond) best to the arbitrary data word to be processed. Segmentation can be realised by means of a layered or tree-like neural network. The device may be used for data compression or data classification.
Inventors
- 👤 Jacques A. Sirat
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 21:18
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/31; G06F16/313
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
193 words
A data processing device for storing and selecting a plurality of fixed length data words DR, the device comprising a) means for identifying a mesh within a multidimensional space representation of a dictionary of the data words DR, the identified mesh corresponding to a test word DO, the multidimensional space containing a plurality of meshes, each mesh being assigned at least one of the data words DR, each data word being either: i) within the mesh to which that data word is assigned; or ii) on a boundary between the mesh, to which the data word is assigned, and another mesh; b) means for supplying a respective sub-dictionary in response to the identified mesh, the respective sub-dictionary containing all of the data words DR which correspond, according to a correspondence criterion, to those data words DR which are assigned to the identified mesh; and c) means for applying said correspondence criterion between the test word DO and the respective sub-dictionary in order to select one or more corresponding words MS, the corresponding words MS being those which are closest to said test word DO in said multidimensional space according to said correspondence criterion.
Claim 2
Dependent Claim
193 words
A data processing device for storing and selecting a plurality of fixed length data words DR, the device comprising a) means for identifying a mesh within a multidimensional space representation of a dictionary of the data words DR, the identified mesh corresponding to a test word DO, the multidimensional space containing a plurality of meshes, each mesh being assigned at least one of the data words DR, each data word being either: i) within the mesh to which that data word is assigned; or ii) on a boundary between the mesh, to which the data word is assigned, and another mesh; b) means for supplying a respective sub-dictionary in response to the identified mesh, the respective sub-dictionary containing all of the data words DR which correspond, according to a correspondence criterion, to those data words DR which are assigned to the identified mesh; and c) means for applying said correspondence criterion between the test word DO and the respective sub-dictionary in order to select one or more corresponding words MS, the corresponding words MS being those which are closest to said test word DO in said multidimensional space according to said correspondence criterion.
Claim 3
Dependent Claim
14 words
The device of claim 1 wherein the means for identifying is a neural network.
Claim 4
Dependent Claim
18 words
A device as claimed in claim 2, characterized in that the neural network is a layered neural network.
Claim 5
Dependent Claim
18 words
A device as claimed in claim 2, characterized in that the neural network is a tree-like neural network.
Claim 6
Dependent Claim
31 words
The device of claim 2 wherein the neural network has input means for receiving data words and output neurons for supplying output signals having output state configurations specific to each mesh.
Claim 7
Dependent Claim
21 words
The device of claim 5 wherein the neural net is trained using the fixed length data words DR and known outputs.
Claim 8
Dependent Claim
22 words
The device of claim 5 wherein the means for supplying is a memory addressed by the output signals of the neural network.
Claim 9
Dependent Claim
22 words
The device of claim 1 wherein the means for supplying is a memory addressed by output signals from the means for identifying.
Claim 10
Dependent Claim
19 words
The device of claim 8 wherein the memory stores a set of sub-dictionaries which encompasses the entire multidimensional space.
Claim 11
Dependent Claim
15 words
The device of claim 1 wherein the means for identifying is a programmable logic array.
Claim 12
Dependent Claim
15 words
The device of claim 1 wherein the means for identifying is a combinatory logic circuit.
Claim 13
Dependent Claim
25 words
The device of claim 1 or 6 wherein the means for identifying responds to data words in the form of signals representing unpreprocessed input vectors.
Claim 14
Dependent Claim
37 words
The device of claim 1 or 6 wherein the means for identifying responds to principal components of data or test words which are pre-processed according to a principal component analysis of a distribution of unpreprocessed data words.
Claim 15
Dependent Claim
39 words
The device of claim 1 wherein inputs to the means for identifying are signals representing vectors, the multidimensional space is a vector space, and the correspondence criterion is a distance according to a metric defined on the vector space.
Claim 16
Independent Claim
34 words
A device as claimed in any one of the claims 1, characterized in that any correspondence criterion between two words is determined by either a distance or a similarity between the latter two words.
Claim 17
Dependent Claim
31 words
A device as claimed in claim 15, characterized in that said correspondence is obtained by determining nearest-neighbours distances between the test word DO and sub-dictionary words SDR of its assigned sub-dictionary.
Claim 18
Dependent Claim
187 words
Method for storing and selecting a plurality of fixed length data words DR, the method comprising the following steps a) identifying a mesh within a multidimensional space representation of a dictionary of the data words DR, the identified mesh corresponding to a test word DO, the multidimensional space containing a plurality of meshes, each mesh being assigned at least one of the data words DR, each data word being either: i) within the mesh to which that data word is assigned; or ii) on a boundary between the mesh, to which the data word is assigned, and another mesh; b) supplying a respective sub-dictionary in response to the identified mesh, the respective sub-dictionary containing all of the data words DR which correspond, according to a correspondence criterion, to those data words DR which are assigned to the identified mesh; and c) applying said correspondence criterion between the test word DO and the respective sub-dictionary in order to select one or more corresponding words MS, the corresponding words MS being those which are closest to said test word DO in said multidimensional space according to said correspondence criterion.
Claim 19
Dependent Claim
187 words
Method for storing and selecting a plurality of fixed length data words DR, the method comprising the following steps a) identifying a mesh within a multidimensional space representation of a dictionary of the data words DR, the identified mesh corresponding to a test word DO, the multidimensional space containing a plurality of meshes, each mesh being assigned at least one of the data words DR, each data word being either: i) within the mesh to which that data word is assigned; or ii) on a boundary between the mesh, to which the data word is assigned, and another mesh; b) supplying a respective sub-dictionary in response to the identified mesh, the respective sub-dictionary containing all of the data words DR which correspond, according to a correspondence criterion, to those data words DR which are assigned to the identified mesh; and c) applying said correspondence criterion between the test word DO and the respective sub-dictionary in order to select one or more corresponding words MS, the corresponding words MS being those which are closest to said test word DO in said multidimensional space according to said correspondence criterion.
Claim 20
Dependent Claim
16 words
The method of claim 17 wherein the steps are all performed by a single preprogrammed apparatus.
Claim 21
Dependent Claim
12 words
The method of claim 17 wherein the apparatus is a neural network.
Claim 22
Dependent Claim
14 words
The method of claim 19 wherein the neural network is a layered neural network.
Claim 23
Dependent Claim
14 words
The method of claim 19 wherein the neural network is a tree-like neural network.
Claim 24
Dependent Claim
20 words
The method of claim 17 wherein the test word is in the form of signals representing an unpreprocessed input vector.
Claim 25
Dependent Claim
22 words
The method of claim 17 wherein the test word is represented according to a principal component analysis of unpreprocessed data words DR.
Claim 26
Dependent Claim
41 words
The method of claim 17 wherein the test word is presented in the form of signals representing vectors, the multidimensional space is a vector space, and the correspondence criterion is a distance according to a metric defined on the vector space.
References Cited (Backward Citations)
US5109509A
Cited
US4771385A
Cited
US4799188A
Cited
US4903206A
Cited
US4862408A
Cited
US5113340A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-29 | 1997-05-31 | 1997-11-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-29 | 2001-05-31 | 2001-11-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-29 | 2005-05-31 | 2005-11-30 | $7700.00 | Window Closed / Lapsed |