home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2574 < prev    next >
Encoding:
Internet Message Format  |  1992-09-07  |  2.5 KB
  1. Path: sparky!uunet!ogicse!uwm.edu!linac!pacific.mps.ohio-state.edu!cis.ohio-state.edu!daisy.learning.cs.cmu.edu!Marc.Ringuette
  2. From: Marc.Ringuette@daisy.learning.cs.cmu.edu
  3. Newsgroups: comp.programming
  4. Subject: Re: How to find vectors with minimum Hamming-distance?
  5. Message-ID: <9209042121.AA00144@news.cis.ohio-state.edu>
  6. Date: 4 Sep 92 20:56:00 GMT
  7. Article-I.D.: news.9209042121.AA00144
  8. Sender: daemon@cis.ohio-state.edu
  9. Organization: The Ohio State University Department of Computer and Information Science
  10. Lines: 43
  11.  
  12. rainer@ruble.fml.tuwien.ac.at (Rainer Staringer) writes,
  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. Good problem!  Some friends and I tried to come up with something
  24. better, but couldn't.  We were thinking along the lines of geometric
  25. algorithms (but couldn't manage to extend a 2-d closest-pair-of-points
  26. algorithm) or something based on sorting or divide-and-conquer.  I like
  27. the other poster's n*log(n)*m! answer -- deliciously crazy and good for
  28. minuscule m.
  29.  
  30. ----
  31.  
  32. If you expect the distribution to be skewed, with a small number of
  33. very well matched pairs of vectors, then you might adopt a method with
  34. better average-case behavior at the expense of worst-case running time.
  35.  
  36. You could use a hashing technique to see if you might luck out and find
  37. two duplicate vectors.
  38.  
  39. With an extra log n factor, you can compare the n^2 candidate
  40. vector-pairs in a best-first fashion, comparing elements in each pair
  41. only until you have seen more mismatches than the best so far.  This
  42. means that if b is the number of total mismatches for the best pair,
  43. p_ij is the number of elements in the largest prefix of vectors i and j
  44. which has fewer than b mismatches, and P is the sum of all p_ij, then
  45. the algorithm runs in time O(P log n), where n*b+m <= P <= n^2*m.
  46.  
  47. ----
  48.  
  49. Other ideas, anyone?  If not, how about a lower bound on the worst case 
  50. running time?
  51.  
  52.  
  53. [ Marc Ringuette | Cranberry Melon University, Cucumber Science Department  ]
  54. [ mnr@cs.cmu.edu | 412-268-3728 |      ".surivorter erutangis a ma I"       ]
  55.