Поиск похожих файлов

Почти наверняка можно что-то быстрое придумать =) Задача сильно упрощается от того, что нет вставок и удалений при поиске разницы...

 

а что сложного: все хэши суём в бин. дерево и ищем по нему.

 

Возникла следующая задача:
Есть число x. Необходимо перечислить все числа, которые отличаюстя от него не более чем на k разрядов. На форуме вроде был код, перечисляющий все числа в которые содержится ровно n единиц, только я даже не представляю по каким словам его можно найти.

 

Black_mirror

А мой код не идет?

 

_basmp_
Честно говоря я не понимаю принцип построения таблиц.
Например если L=6, во второй таблице должны быть числа 3,5,9 или так и останутся 3 и 5?
А что в этом случае будет в третьей таблице?

Я просто хочу сделать разбиение хеша на части и построение по ним индексов. Если мы ищем хеши отличающиеся не более чем на L/K разрядов, то хотя бы одна половина тоже должна отличаться не более чем на L/2K разрядов. Если левая половина отличается на L/2K разрядов, то правая половина не может отличаться более чем на L/2K разрядов, а вот если левая половина точно совпадает, то правая половина может отличаться на L/K разрядов и в этом случае проще перебирать все элементы с заданной левой половиной.

 

Black_mirror

Из таблиц убрано все, что можно получить вращением, те 9 = 3 ror 1; 6 = 3 rol 1; 12 = 3 rol 2; 10 = 5 rol 1;

Таблицы выше L/2 получаются из предыдущих путем инвертирования значащих элементов таблицы n' = L-n (можно этого не делать, а представить их явно)

Те таблица 3 должна иметь один элемент - 14.

Когда строил таблицу получилось, что
1 отличие - 4 числа
2 отличия - 6 чисел
3 отличия - 4 числа
4 отличия - 1 число
При нечетном кол-ве разрядов (3х) будет 3, 3, 1.
Половин или удвоений имхо не выйдет.

А что стоит разложить сперва по коротким хешам, отобрать подобные. Для них построить более точную таблицу, опять отобрать итд. Отборов 3х должно быть достаточно.

 

_basmp_

Я вообще спрашивал про таблицу для L=6.

При L=32 чисел которые содержат ровно 8 единиц 10518300 штук. Сколько из них попадут в 8ю таблицу?

 

Вот накатал как мог. Для массива это посложнее делать придётся. Да и непонятно зачем)) Неужели перебором что-то делать надо?

Код (Text):

1.     uint r=rand();
2.     for(;;) {
3.         uint t=(r&-r)+r;
4.         if(!t) break;
5.         r=r&~t;
6.         while(!(r&1)) r>>=1;
7.         r=(r>>1)|t;
8.         BinaryDump(r);
9.     }

 

Можно как вариант на первое время проиндексировать все двух пары чисел из двух байт.
В каждом хеше взять все пары байт, которые стоят рядом, и которые стоят через одну позицию. Если хеши не различаются больше чем на половину байт, то это поможет относительно быстро их опознавать.

 

Black_mirror

да, вроде, просто: lg2(x-y)<>k or lg2(x)+k

 

Прога, что перечисляет и выводит все числа с кол-вом единиц 1 <= K <= L

Код (Text):

1. #include <stdio.h>
2.  
3. #define L 32
4. #define K 8
5.  
6. int m[L];
7.  
8. int Step(int n, int k){
9.     if( m[n] == (1 << (L-1-n)) ){
10.         if( n == k-1 ) return 0;
11.         if( !Step(n+1, k) ) return 0;
12.         m[n] = m[n+1] << 1;
13.     }else if( !m[n] )
14.         m[n] = 1;
15.     else
16.         m[n] <<= 1;
17.     return 1;
18. }
19.  
20. void main(){
21.     int i,j,r;
22.  
23.     for( i = 0; i<L; i++) m[i] = 0;
24.  
25.     j=0;
26.     while(Step(0,K)){
27.         r = 0;
28.         for(i=0; i<K; i++) r |= m[i];
29.  
30.         j++;
31.         printf("%d) xor mask == %xh\n", j, r);
32.     }
33.  
34. }

При L=32 и K=от 1 до 8, таких чисел 15033172

 

Black_mirror
твою задачу примерно так можно решить: хэши суём в бин. дерево; затем ищем хэши, у коих самые верхние d бит различаются с эталоном; дальше убиваем поддерево по полученной маски и повторяем цикл пока поддеревьев больше не будет. как сделать счётчик сам разберёшься.
ПРИМЕР:

эталон - 1101001. ищем два различия:
1101001
0111001
1010001
0110101
первый цикл найдёт 0111001 и удалит поддерево 011.

 

ну, и замечу: "убить поддерево" не значит, что его надо убивать фактически - на каждом шаге производить сортировку не есть подход разумный. можно все "убиваемые" поддеревья метить как неиспользуемые с сохранением указателей на них. на каждой итерации просто производиться восстановление древа без сортировки засчёт сохранёных указателей.

ЗЫ

мля, можно было и покороче написать

 

Версия программы с дополнительными индексами:

Код (Text):

1. #include <windows.h>
2. #include <stdio.h>
3.  
4. unsigned myrand()
5. {
6.     static DWORD seed=777;
7.     return seed=seed*134775813+1;
8. }
9.  
10. #define N 0x1000000 //число хешей
11. unsigned H[N]; //хеши
12. unsigned V[N]; //признак что хеш уже обрабатывался
13. unsigned mark=0;
14. int IH[65536]; //IH[i] - индекс первого хеша, старшая часть которого равна i
15. int LH[N]; //H[LH[i]] - следующий хеш, имеющий совпадающую с H[i] старшую часть
16. int IL[65536]; //IL[i] - индекс первого хеша, младцая часть которого равна i
17. int LL[N]; //H[LL[i]] - следующий хеш, имеющий совпадающую с H[i] младшую часть
18. int _mask[65536+17];
19. int* masks[17];
20.  
21. int bits(unsigned v)
22. {
23.     int r=0;
24.     while(v)
25.     {
26.         v&=v-1;
27.         r++;
28.     }
29.     return r;
30. }
31.  
32. int cc;
33.  
34. int findH(unsigned *hash, unsigned key, int *list,int *index,unsigned k2, int d)
35. {
36.     int d2=d/2;
37.     int r=0;
38.     for(int i=0;i<=d2;i++)//выбираем количество отличающихся бит
39.     {
40.         int* m=masks[i];//m=список масок с i разрядами
41.         while(*m>=0)//перебираем маски
42.         {
43.             int k=index[k2^*m];//xor-им половину ключа с выбранной маской
44.             while(k>=0)//перебираем хеши у которых одна половина совпадает с k2^*m
45.             {
46.                 cc++;
47.                 if(V[k]!=mark&&bits(hash[k]^key)<=d)//проверяем, что хеш отличается не более чем на d разрядов
48.                 {
49.                     V[k]=mark;//помечаем что такой хеш уже встречался
50.                     r++;
51.                 }
52.                 k=list[k];
53.             }
54.             m++;
55.         }
56.     }
57.     return r;
58. }
59.  
60. int find(unsigned *hash, unsigned key, int d)
61. {
62.     return findH(hash,key,LH,IH,key>>16,d)+findH(hash,key,LL,IL,key&65535,d);
63. }
64.  
65. int main()
66. {
67.     int i=0;
68. //подготовка xor-масок
69.     for(int d=0;d<17;d++)
70.     {
71.         masks[d]=_mask+i;
72.         for(int j=0;j<65536;j++)
73.         {
74.             if(bits(j)==d)
75.                 _mask[i++]=j;
76.         }
77.         _mask[i++]=-1;
78.     }
79. //генерация случайных хешей
80.     for(i=0;i<N;i++)
81.         H[i]=myrand();
82. //инициализация списков хешей с одинаковыми левыми и правыми половинами
83.     for(i=0;i<65536;i++)
84.         IH[i]=IL[i]=-1;
85.     for(i=N;i--;)
86.     {
87.         LL[i]=IL[H[i]&65535];
88.         IL[H[i]&65535]=i;
89.         LH[i]=IH[H[i]>>16];
90.         IH[H[i]>>16]=i;
91.     }
92. //ищем хеши отличающиеся от заданного на D бит
93. for(int D=0;D<=16;D++)
94. {
95.     mark++;
96.     cc=0;
97.     int r=0;
98.     int t1=GetTickCount();
99. //линейный поиск
100.     for(i=0;i<N;i++)
101.     {
102.         if(bits(H[i]^H[0])<=D)
103.         {
104.             r++;
105.         }
106.  
107.     }
108.     int t2=GetTickCount();
109.     t1=t2-t1;
110. //немного оптимизированная функция
111.     r=find(H,H[0],D);
112.     t2=GetTickCount()-t2;
113. //r=A/B/n=C
114. //A - сколько хешей нашла функция
115. //B - сколько хешей функция проверяла
116. //C - общее количество
117.     printf("d=%d t1=%d t2=%d r=%d/%d/n=%d\n",D,t1,t2,r,cc,N);
118. }
119.     getchar();
120.     return 0;
121. }
122.  
123. Замеры:
124. d=0 t1=1735 t2=0 r=1/495/n=16777216
125. d=1 t1=1718 t2=0 r=1/495/n=16777216
126. d=2 t1=1719 t2=16 r=1/8670/n=16777216
127. d=3 t1=1734 t2=0 r=18/8670/n=16777216
128. d=4 t1=1719 t2=31 r=157/70393/n=16777216
129. d=5 t1=1719 t2=31 r=944/70393/n=16777216
130. d=6 t1=1719 t2=125 r=4523/357302/n=16777216
131. d=7 t1=1719 t2=125 r=17588/357302/n=16777216
132. d=8 t1=1734 t2=469 r=58669/1289751/n=16777216
133. d=9 t1=1734 t2=469 r=168280/1289751/n=16777216
134. d=10 t1=1719 t2=1281 r=420209/3525806/n=16777216
135. d=11 t1=1719 t2=1312 r=924219/3525806/n=16777216
136. d=12 t1=1735 t2=2765 r=1804514/7625670/n=16777216
137. d=13 t1=1766 t2=2797 r=3163772/7625670/n=16777216
138. d=14 t1=1781 t2=4812 r=5004911/13479765/n=16777216
139. d=15 t1=1797 t2=4860 r=7214212/13479765/n=16777216
140. d=16 t1=1797 t2=6968 r=9563344/20070447/n=16777216

Вместо хешей использовались псевдослучайные числа длиной 32 разряда в количестве 2^24 штук. Хеши имеющие одинаковые левые или правые части были объеденены в списки. Программа перебирала все возможные левые и правые части, которые отличаются от заданного ключа не более чем на d/2 разряда, потом просматривала соответствующие списки.
Выводы в общем не особо утешительные, для d=L/4-1 выигрыш получается всего лишь в 10 раз. Хотя может будет достаточно и d=L/8-1. Там выигрыш примерно в пару тысяч раз, правда если учесть что для каждого из N файлов нужно будет искать похожие, то есть сложность N^2, всё равно в итоге получится многовато.
Может попарно сравнивать хеши и не нужно?! Может разбиение на группы похожих можно провести каким-то другим алгоритмом?!