NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/programm/2566

Text File | 1992-09-03 | 2.9 KB | 70 lines

Newsgroups: comp.programming
Path: sparky!uunet!ulowell!news.bbn.com!usc!sdd.hp.com!news.cs.indiana.edu!umn.edu!thompson
From: [e-mail] (T. Scott Thompson)
Subject: Re: How to find vectors with minimum Hamming-distance?
Message-ID: <[e-mail]>
Sender: [e-mail] (Usenet News Administration)
Nntp-Posting-Host: hermes.socsci.umn.edu
Reply-To: [e-mail]
Organization: Economics Department, University of Minnesota
References: <[e-mail]>
Date: Thu, 3 Sep 1992 16:29:12 GMT
Lines: 56

[e-mail] (Rainer Staringer) writes:

>I stumbled over the following problem recently, and I wonder if there
>is a clever algorithm for it: I have a set of n m-dimensional vectors
>(vector elements are from a finite set, but not necessarily binary),
>and I want to find the 2 vectors with the minimum Hamming-distance
>(i.e. those which have the most elements in common). Is there any
>way you can find them using less than O(n^2) vector comparisons?
>I know there is a clever algorithm for the equivalent problem with
>Euclidean metric, but I could not find any for the Hamming-metric
>variant.

How about this (off the top of my head): If the vectors are drawn from
a finite set then the problem can be transformed into a finite
collection of sorting problems, each of which can be solved faster
than O(n^2).  Here is what I have in mind.

min-dist := m+1;
<initialize vector-array>;
for <every permutation of the coordinate system> do
   begin
   <sort vector-array according to the lexicographic ordering induced by the
    current labelling of the coordinates>
   min-this-time := m+1
   for i := 1 to n-1 do
      begin
      current-dist := m - #zeros( vector-array(i) - vector-array(i+1) );
      if current-dist < min-this-time then
         begin
         v1 := vector-list(i);
         v2 := vector-list(i+1);
         min-this-time := current-dist;
         end;
      end;
   if min-this-time < min-dist then
      begin
      p1 := <inverse-of-current-permutation>(v1);
      p2 := <inverse-of-current-permutation>(v2);
      min-dist := min-this-time;
      end;
   end;

At the end the vectors p1 and p2 will hold two points achieving the
minimum distance.  The distance itself is in min-dist.

The time, considered as a function of n, will be dominated by the
"sort" statment, which can be done faster than O(n^2) if you do it
right.  The main drawback is that the outer loop must be executed
O(m!) times.  Some improvement on this is clearly possible (e.g. never
check both a given permutation and its reverse-ordering), but I
wouldn't use this for m! big relative to n.  How big is m in your
application?
--
T. Scott Thompson              email:  [e-mail]
Department of Economics        phone:  [phone]
University of Minnesota        fax:    [phone]