home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / sys / mac / programm / 20750 < prev    next >
Encoding:
Text File  |  1993-01-06  |  1.9 KB  |  58 lines
  1. Newsgroups: comp.sys.mac.programmer
  2. Path: sparky!uunet!stanford.edu!nntp.Stanford.EDU!Ramon.M.Felciano
  3. From: felciano@summit.stanford.edu (Ramon M. Felciano)
  4. Subject: (Q) Need bit manipulation algorithm
  5. Message-ID: <1993Jan6.022430.19469@leland.Stanford.EDU>
  6. X-Posted-From: InterNews1.0b3@nntp.stanford.edu
  7. Sender: ?@leland.Stanford.EDU
  8. Organization: Stanford University Medical Media and Information 
  9.  Technologies
  10. Date: Wed, 6 Jan 93 02:24:30 GMT
  11. Xdisclaimer: No attempt was made to authenticate the sender's name.
  12. Lines: 44
  13.  
  14.  
  15. Happy New Year, all!
  16.  
  17. I've got an interesting bit-manipulation problem for you. I need to
  18. know how to match a given bit pattern into a stored array of patterns.
  19. In particular, I need to come up with a "fuzzy match" if no exact one
  20. is found.
  21.  
  22. For example, I want to match 00110101 into the following array:
  23.  
  24.      1.  00000000
  25.      2.  00000010
  26.      3.  01000100
  27.      4.  00110101
  28.      5.  00001110
  29.      6.  00010110
  30.      7.  00101010
  31.      8.  00011000
  32.      9.  00000110
  33.      10. 00010010
  34.  
  35. A simple loop will match it with #4. 
  36.  
  37. If I want to match 00110110, there is no exact match. In this case,
  38. I want it to return #6, which is only 1 bit off. If #6 weren't there,
  39. I would want it to return #9, which is 2 bits off, then #10, which is
  40. also 2 bits off, then #2 (1 bit off), then #1 (default)
  41.  
  42. So: I need an algorithm that will find a consistent fuzzy match by
  43. subtracting bits. It needs to deal with ambiguities like #9 and #10.
  44. Thus if two matches have 90% of the bits in common, I need both of
  45. them back, one after the other (the order doesn't matter).
  46.  
  47. Any ideas?
  48.  
  49. Thanks!
  50.  
  51. Ramon
  52.  
  53. +----------------------------------------------------------------+
  54. | Ramon M. Felciano                felciano@summit.stanford.edu  |
  55. | Associate Director, SUMMIT       (415) 723-9688                |
  56. | Stanford University Medical Media and Information Technologies |
  57. +----------------------------------------------------------------+
  58.