Data processing device and method for selecting data words contained in a dictionary

• US 5,267,165 A
• Filed: 03/14/1991
• Issued: 11/30/1993
• Est. Priority Date: 03/20/1990
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Sirat, Jacques A.
• Primary Examiner(s): Weinhardt, Robert A.
• Application Number:
  US07/669,155
• Time in Patent Office: 992 Days
• Field of Search: 364/419
• US Class Current: 704/10
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing

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.

Claims

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

2. The device of claim 1 wherein the means for identifying is a neural network.

3. A device as claimed in claim 2, characterized in that the neural network is a layered neural network.

4. A device as claimed in claim 2, characterized in that the neural network is a tree-like neural network.

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

6. The device of claim 5 wherein the neural net is trained using the fixed length data words DR and known outputs.

7. The device of claim 5 wherein the means for supplying is a memory addressed by the output signals of the neural network.

8. The device of claim 1 wherein the means for supplying is a memory addressed by output signals from the means for identifying.

9. The device of claim 8 wherein the memory stores a set of sub-dictionaries which encompasses the entire multidimensional space.

10. The device of claim 1 wherein the means for identifying is a programmable logic array.

11. The device of claim 1 wherein the means for identifying is a combinatory logic circuit.

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

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

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

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

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

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

18. The method of claim 17 wherein the steps are all performed by a single preprogrammed apparatus.

19. The method of claim 17 wherein the apparatus is a neural network.

20. The method of claim 19 wherein the neural network is a layered neural network.

21. The method of claim 19 wherein the neural network is a tree-like neural network.

22. The method of claim 17 wherein the test word is in the form of signals representing an unpreprocessed input vector.

23. The method of claim 17 wherein the test word is represented according to a principal component analysis of unpreprocessed data words DR.

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