home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2565 < prev    next >
Encoding:
Text File  |  1992-09-03  |  1.1 KB  |  29 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!email!news
  3. From: rainer@ruble.fml.tuwien.ac.at (Rainer Staringer)
  4. Subject: How to find vectors with minimum Hamming-distance?
  5. Message-ID: <1992Sep3.132931.2083@email.tuwien.ac.at>
  6. Sender: news@email.tuwien.ac.at
  7. Nntp-Posting-Host: ruble.fml.tuwien.ac.at
  8. Reply-To: rainer@eimoni.tuwien.ac.at
  9. Organization: Technical University of Vienna
  10. Date: Thu, 3 Sep 1992 13:29:31 GMT
  11. Lines: 16
  12.  
  13. I stumbled over the following problem recently, and I wonder if there
  14. is a clever algorithm for it: I have a set of n m-dimensional vectors
  15. (vector elements are from a finite set, but not necessarily binary),
  16. and I want to find the 2 vectors with the minimum Hamming-distance
  17. (i.e. those which have the most elements in common). Is there any
  18. way you can find them using less than O(n^2) vector comparisons?
  19. I know there is a clever algorithm for the equivalent problem with
  20. Euclidean metric, but I could not find any for the Hamming-metric
  21. variant.
  22.  
  23. Thanks for any ideas, references, etc.
  24.  
  25.     Rainer
  26. --
  27. Rainer Staringer                   | rainer@fml.tuwien.ac.at
  28. Financial Markets Lab, TU Vienna   | +43 (1) 58801/8138
  29.