1

Topic: Search of numbers similar on 60 % (bit lines)

Is huge (hundreds ) the list of 64 bit numbers. It is necessary to find in this list of the number which bits coincide with the given number at least on 60 %. For example, here these two bit lines (five-bit) coincide on 60 %: 10001 11011 bits on positions 1, 5 ("1) and 3 ("0) Here coincide. Here these two bit lines are similar to 80 % and too should be produced by algorithm: 00001 00000 Prompt, what data structure and algorithms for this purpose to use? A problem in the big size of the list on which numbers are searched; clearly, what any artful index, but what is necessary? Basically, for this task any probability method which would return the found numbers + a small amount of false coincidence approaches also.

2

Re: Search of numbers similar on 60 % (bit lines)

3

Re: Search of numbers similar on 60 % (bit lines)

Hello, malphunction, you wrote: M> Is huge (hundreds ) the list of 64 bit numbers. M> it is necessary to find in this list of the number which bits coincide M> with the given number at least on 60 %. M> For example, here these two bit lines (five-bit) coincide on 60 %: M> M> 10001 M> 11011 M> M> bits on positions 1, 5 ("1") and 3 ("0") Here coincide. M> Here these two bit lines are similar to 80 % and too should be produced by algorithm: M> M> 00001 M> 00000 M> M> Prompt, what data structure and algorithms for this purpose M> to use? M> a problem in the big size of the list on which M> numbers are searched; clearly, what any artful index, M> but what is necessary? M> basically, for this task the method which would return the found numbers + small amount M> false coincidence approaches also any probability M>. By my calculations, you accept approximately 12 % of all numbers, instead of 30 %, as appears from the message kov_serg. But, all the same, no sense in an index is present - to sort out all array, cheaply enough, in comparison with additional calculations on any index. Here, if it is required more split-hair accuracy of coincidence (> = 65 %), will be to think of what...

4

Re: Search of numbers similar on 60 % (bit lines)

Hello, Chorkov, you wrote: the C> By my calculations, approaches you approximately 12 % of all numbers, instead of 30 %, as appears from the message kov_serg. At me the result (the total on i=0 to 25 With (64, i)/2^64) turned out 5,17 %.