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

Имеется файл A длиной N байт
Есть некоторая функция F которая на вход получает файл A, а на выходе выдаёт L-битное число a=F(A) (L порядка 256-1024 бит и от длины файла не зависит).
Если в файле изменить(удалить, добавить) M байт, то результат функции в среднем будет отличаться на L*M/N*K бит, где К некоторый коэффициент зависящий от того как построена функция F.

А вопрос заключается в следующем: как хранить эти L-битные числа, чтобы для любого заданного числа x, можно было быстро найти все числа, которые отличаются от него не более чем d разрядами?!

 

Black_mirror

привет

//оффтоп...
слухай, а где ты такие задачки откапываешь.. это из реальной жизни или же... for self training?

 

Black_mirror
двоичные дерьвья и ничего больше.

 

UbIvItS
Не обязательно. Можно просто в виде отсартированного массива.

 

Pavia
угу, но если надо динамично добавлять новые хэши - лучше дерева не найти.

 

Pavia

А можно на примере, скажем для L = 3? "числа, которые отличаются от него не более чем d разрядами" - означает, что нужны все числа, которые лежат в сфере радиуса d относительно Hamming metric в L-разрядном пространстве. Не совсем представляю, как из них сделать отсортированный массив.

Black_mirror

Задачу можно сформулировать проще: дано пространство с метрикой, некоторое количество точек и сфера. Найти, какие точки попадают в эту сферу. Интересно, есть ли решение быстрее, чем O(n)

 

принять какое-то значение как нил, например 0. Число а преобразовывать из кода грея в обычный и записывать в предварительно заниленую таблицу tab[unGray(x)]=x. При поиске опять-же преобразовать из кода грея. Все значащие цифры в диапазоне tab[ (unGray(x)-d) .. (unGray(x)+d) ], где d - максимальное кол-во несовпадающих разрядов, и будут искомыми значениями.

код грея (википедия)

 

_basmp_

Неплохо Но работать естественно не будет. Посмотрим на примере: пусть L = 3, возьмем число 000 и d = 1. У числа 000 три соседа, которые отстоят от него на расстояние 1: 001, 010, 100. В твоей таблице tab[ (unGray(x)-1) .. (unGray(x)+1) ] соседей будет только два.

Grey code гарантирует только, что расстояние между кодами непосредственных соседей равно 1. Из этого вовсе не следует, что если расстояние между числами равно x, то и расстояние между кодами будет x. На самом деле оно будет меньше или равно x.

 

Такой вариант (умозрительно):
Полученые значения - адреса в булевой таблице. Принятое - труе

При поиске рассчитываем все возможные значения и проверяем их наличие в таблице. Для этого заранее создаем систему XOR масочных таблиц, по таблице на количество отличающихся битов n (n-также порядковый номер таблицы начиная с 1). Их будет N=[L/2]. В каждой будет n элементов.

Для d <= N.
При расчете ксорим X с очередной маской, затем сдвигаем ее на бит и повторяем пока очередное сдвинутое значение не совпадет с начальным из таблицы, затем берем следующее из таблицы пока номер очередной таблицы не станет > d.

Для d > N.
Пока таблиц хватает считаем как если d <= N. Потом номер очередной таблицы считаем как nt' = L - nt (где nt - искомый, а nt' - реальный номер таблицы), а очередное значение маски (при nt'==0 оно == 0) инвертируем перед использованием. Все остальное также как и при d <= N.

Проверяем булевые значения в таблице принятых по адресам полученым в результате ксора искомого и очередной маски.

ЗЫ Понимаю, что далек от оптимальности как крестьянин от богатства, но надо-же хоть что-то ляпнуть после такой промашки (#7).

 

Я подумал и решил что d стоит ограничить, то есть пусть d<D.
Все числа делим на D частей по L/D бит.
Строим D деревьев.
Число x разбиваем на D частей и каждую часть ищем в соответствующем дереве.
Если L=512, D=16, L/D=32, то можно будет гарантированно найти числа которые отличаются не более чем на 15 разрядов (~3%), и при поиске придётся в среднем просмотреть N*16/2^32 записей (N - общее их число).

Хотя это конечно читерство.

 

Black_mirror

А можно на примере, для большей наглядности? Пусть L=4, D=2, как будут выглядеть деревья и как в них искать число?

 

Stiver
Я имел ввиду что создаются дополнительные индексы, а деревья там будут или хеш таблицы не особо важно. Например для 4х битных строк создаём два индекса:
1) 1101 00->3 00->3
2) 1011 00->7 00->4
3) 0000 01->5 00->5
4) 1100 10->2 01->1
5) 0100 10->6 01->6
6) 1001 11->4 11->2
7) 0011 11->1 11->7
Если нужно найти строки которые отличаются от 1000 на 1 бит, то из первого индекса по ключу 10 находим что это может быть строка 2 или 6, а из второго по ключу 00 находим что это могут быть строки 3,4 или 5. Ну а дальше сравнивая 2,3,4,5 и 6 строки с 1000 определяем что это 3,4 и 6 строки. Правда при L=4 и D=2 придётся в среднем просматривать всего в 2 раза меньше строк.

Но тут конечно нужно думать сколько в базе максумум может быть строк, какие файлы считать похожими, сколько не жалко памяти для дополнительных индексов, и после выбирать L и D.

 

А равновероятность хэшей у нас уже постулирована? Иначе, представь себе, что они все имеют очень мало (порядка d) единиц. Тогда в каждой из L/D частей ты получишь не много менее чем все хэши.

PS Эта задача хорошо известна, как и то, что хороших алгоритмов для ее решения в общем случае нет. Не пытайся изобрести неизобретаемое.

 

Ну как-то нечёткий поиск делают в генах или поисковиках. И не слишком медленно работает....

 

Решил вот по нормальному написать то, что писал выше..

Случай L==4, int тут 4х битное число, а яз - не совсем С

Код (Text):

1. #define L 4
2.  
3. bool elsT[16]; принятые труе, остальные нет
4.  
5.  
6. ...........
7.  
8.  
9. int xorMask[3][3]={
10.            {0,0,0},
11.            {1,0,0},
12.            {3,5,0}
13.      }
14.  
15. seekFunc(int el, int d, int *alikes){
16.   int xorm, xormt, dt, elt, *alikest=alikes;
17.   int i, j, not=0, stpos=1;
18.  
19.   dt = d > L/2 ? L/2 : d;
20.   do
21.     for(j=0,i=stpos; i<=dt; i++){
22.       if(xorm = i){
23.         xorm = xorMask[i][j];
24.         if(!xorm) continue;
25.       }
26.       xormt = (xorm ^= not);
27.       do
28.         if(elsT[ elt = el^xormt ]){
29.           *alikest = elt;
30.           alikest++;
31.         }
32.       while( (xormt <<= 1) != xorm ); // '<<' тут не 'shl', a 'rol'
33.     }
34.     if( d != dt ){
35.       dt = L/2;
36.       stpos = L-d;
37.       not = ~not;
38.     }
39.   while( (d -= dt) > 0 );
40. }

 

В качестве эксперимента написал небольшую прогу, которая считает для файлов 32х-битные хеши. Натравил эту прогу на каталог в котором лежало 10239 файлов. Подсчитал сколько хешей имеют 0,1,2..32 единичных бит, потом попарно проксорил все хеши, и тоже подсчитал сколько единичных бит в результатах получилось(проценты):

Код (Text):

1. бит:  хеш  хеш1^хеш2
2.  0:   0.08   0.02
3.  1:   0.00   0.00
4.  2:   0.01   0.00
5.  3:   0.00   0.00
6.  4:   0.01   0.00
7.  5:   0.01   0.01
8.  6:   0.03   0.03
9.  7:   0.12   0.12
10.  8:   0.52   0.35
11.  9:   1.29   0.89
12. 10:   1.99   1.98
13. 11:   3.72   3.82
14. 12:   6.22   6.37
15. 13:  10.19   9.42
16. 14:  11.74  12.15
17. 15:  13.02  13.88
18. 16:  15.58  13.99
19. 17:  12.71  12.45
20. 18:   9.72   9.78
21. 19:   5.81   6.76
22. 20:   3.84   4.14
23. 21:   2.05   2.19
24. 22:   0.88   1.02
25. 23:   0.40   0.41
26. 24:   0.07   0.14
27. 25:   0.01   0.04
28. 26:   0.00   0.01
29. 27:   0.00   0.00
30. 28:   0.00   0.00
31. 29:   0.00   0.00
32. 30:   0.00   0.00
33. 31:   0.00   0.00
34. 32:   0.00   0.00

В общем ничего неожиданного здесь нет, числа в которых мало или много единичных бит встречаюстя редко.
Потом разбил хеши на 4 байта, и подсчитал статистику по каждому байту:

Код (Text):

1. байт 1:
2.   88    2   73    1   86    2   84   37   68    1   67    1  105    1   76    0
3.  100    1   70    1   62    0   73    3   60    0   65    3   66    1   75    2
4.   89    1   83    5   69    2   77    4   77    1   83   19   72    0   93    1
5.   58    1   75    1   68    5   86    2   75    1   71    2   66    0   83    5
6.   56    3   66    2   54    2  131    1   65    0   81    2   59    0   69    6
7.   76   30   79    2   62    1   60    4   78    0   73    1   68    2  104    0
8.   63    2   82    2   74    1   86    2   71    2   79    3   74    2  112    1
9.   72    2  112    1   78    1   64    1   49    1   79    2   77    1   77    4
10.   79    0   71    1   67    5   80    2   70    0   67    2  102    6   69    1
11.   74    1   68    2   70    0   71    4  132    2   96    0   76    0   69    2
12.   68    7   68    4   75    3   82    0   68    4   64   11   47    2   83    2
13.   72    1   71    0   76    3   85    0   61    2   77    1   79    1   87    1
14.  114    3  111    1   92    2   62    3   79    1   75    1   87    0   88    2
15.   65    2   87    1   75    0   69    5   62    1   81    1   87    0   66    3
16.   61   11  105    2   81    3   77    1   64    0   62   62   64    0   90    6
17.   58    2   95    3   60    3   62    1  134    0   70    1   71    3  104    0
18. байт 2:
19.   44   43   33   47   44   59   41   52   30   36   39   39   66   36   37   33
20.   30   49   53   38   29   43   30   39   42   47   37   36   33   53   39   36
21.   30   24   43   38   44   35   77   31   28   36   30   25   43   28   32   25
22.   50   49  127   39   42   37   29   71   37   23   35   43   40   48   48   47
23.   42   32   37   35   33   38   34   39   34   35   38   37   33   36   30   35
24.   36   47   31   38   43   38   43   46   29   77   34   45   34   46   51   42
25.   37   35   37   25   75   35   35   32   44   36   43   43   38   73   42   29
26.   25   42   49   64   28   47   35   43   24   31   36   44   32   35   35   42
27.   32   35   32   71   42   33   77   47   40   29   62   30   29   41   34   36
28.   59   53   42   31   34   41   40   29   51   35   24   39   44   35   67   38
29.   68   28   23   34   30   28   31   52   37   27   29   37   39   38   35   37
30.   30   44   64   38   35   42   44   39   31   37   38   33   30   30   39   61
31.   45   41   74   33   39   46   23   37   21   40   49   34   32   45   40   22
32.   49   46   37   42   79   37   44   41   28   37   37   36   42   35   34   28
33.   26   40   94   49   31   32   38   40   34   46   67   40   26   43   26   52
34.   20   38   46   39   49   23   26   35   36   39   44   37   34   41   36   33
35. байт 3:
36.   58   35   35   44   25   36   61   75   26   69   30   44   26   33   47   45
37.   36   47   60   43   35   44   46   50   34   42   39   42   38   40   45   37
38.   40   36   72   44   35   33   26   67   38   46   39   40   23   63   25   75
39.   72   38   35   46   47   51   24   33   20   32   32   40   36   45   35   32
40.   60   46   28   37   50   32   33   30   40   31   65   45   28   43   39   35
41.   70   56   42   50   39   38   31   55   31   37   32   40   22   38   29   35
42.   29   32   51   34   33   42   47   37   40   41   34   45   28   30   69   35
43.   36   31   42   42   31   49   34   59   38   31   36   31   50   48   22   20
44.   39   34   49   51   42   31   36   45   33   49   34   31   37   35   66   42
45.   33   35   36   41   42   34   37   45   43   35   64   41   27   74   35   35
46.   48   34   33   41   43   41   25   40   37   36   28   50   26   35   20   38
47.   39   47   55   41   40   37   31   33   29   31   27   39   32   29   33   38
48.   42   38   39   80   27   35   34   42   34   38   26   37   33  101   39   48
49.   67   46   35   46   37   42   35   42   65   41   33   48   26   38   37   36
50.   45   52   32   38   33   33   29   38   43   29   33   29   34   40   20   43
51.   70   31   48   41   38   42   33   62   42   34   28   53   22   33   19   37
52. байт 4:
53.   49   77   29   32   40   44   29   33   33   44   34   36   38   40   34   38
54.   34   37   26   49   39   44   42   31   36   43   74   55   41   44   31   43
55.   40   30   44   36   31   32   41   42   34   55   26   32   31   38   40   37
56.   41   37  103   35   35   42   39   73   68   40   35   62   36   36   41   28
57.   34   52   33   40   49   47   34   36   43   38   46   38   33   47   45   36
58.   77   39   36   42   31   32   49   42   42   51   25   37   37   43   35   38
59.   82   34   30   36   34   35   67   42   39   33   33   33   39   60   22   48
60.   38   35   38   51   46   43   36   38   40   27   41   36   42   46   44   45
61.   38   32   35   31   44   44   42   38   38   28   42   43   26   95   25   70
62.   53   34   39   34   29   38   45   47   27   40   31  101   37   47   32   74
63.   58   25   33   28   50   33   39   41   35   31   33   43   36   33   37   35
64.   45   32   50   36   41   32   27   31   43   36   32   42   38   29   43   32
65.   44   39   40   35   48   33   42   40   34   44   43   44   30   44   31   34
66.   60   68   32   35   36   38   36   20   30   31   25   39   32   25   40   33
67.   60   38   42   23   34   50   41   29   35   40   42   31   42   48   24   28
68.   45   39   36   34   22   41   34   33   29   46   43   37   44   44   38   45

Тут почему-то для первого байта чётные значения встречаются чаще чем нечётные, в общем функция явно с багой и причина пока не понятна.

Но самое интересное было искать хеши которые отличаются на 1 бит:

Код (Text):

1. Эти два файла ничего общего не имеют:
2. AC56C310 d:\_new\Rowan\20 - Moskvovudu.mp3
3. A456C310 d:\_new\tem2\NP-10-Black_minstrel.mp3
4.  
5. Тут в начале rtf идёт всякая муть, ну и в тексте тоже попадается, хотя не поспоришь, файлы действительно по содержанию одинаковые:
6. DB8E0B26 d:\_unsorted\RICHARD\Orlovsky_Richard_Dlinnye_Ruki-pfaltzgraf(Ballady_o_Richarde_Dlinnye_Ruki-13).rtf
7. D98E0B26 d:\_unsorted\RICHARD\Orlovsky_Richard_Dlinnye_Ruki-pfaltzgraf(Ballady_o_Richarde_Dlinnye_Ruki-13).txt
8.  
9. Тут программа опять попала мимо, но точные копии нашла(хеш-то всего 32 бита!):
10. 583B38DA d:\_new\Мириада\(2006) - Иллюзия любви\01 - Млечный путь (Интро).mp3
11. 583BB8DA d:\_new\Скоренко Тим\Памяти генерала Линдберга.mp3
12. 583B38DA d:\_temp\Мириада\(2006) - Иллюзия любви\01 - Млечный путь (Интро).mp3
13. 583BB8DA d:\_temp\Скоренко Тим\Памяти генерала Линдберга.mp3
14. 583B38DA d:\_unsorted\Мириада\(2006) - Иллюзия любви\01 - Млечный путь (Интро).mp3
15.  
16. А вот выкачанное с инета вместе с web-страничками:
17. 71F0072B d:\_text\Король и Шут\Жаль, нет ружья.files\163
18. 71F0072B d:\_text\Король и Шут\Проклятый старый дом.files\Медведь.files\163
19. 70F0072B d:\_text\Король и Шут\Хозяйка старинных часов.files\163
20. 71F0072B d:\_Алькор\Логово Черной Кошки - Алькор.files\163.htm
21. 71F0072B d:\_Алькор\Логово Черной Кошки - Алькор1.files\163.htm
22. 71F0072B d:\Алькор\Логово Черной Кошки - Алькор.files\163.htm
23. 71F0072B d:\Алькор\Логово Черной Кошки - Алькор1.files\163.htm
24. 70F007AB d:\Алькор\Логово Черной Кошки - ТууТикки1.files\163.htm
25. 70F0072B d:\Алькор\Логово Черной Кошки - ТууТикки4.files\163.htm
26.  
27. F3ECF9FE d:\_text\RealMusic_ru - Тампль, рок-орден.files\urchin.js
28. F3E4F9FE d:\Алькор\Стихи Алькор.files\urchin.js

В архиве лежат файлы urchin.js и часть из 163х, и самое интересное, что в них действительно что-то общее есть

 

Провёл еще один эксперимент, взял 20 файлов в формете doc(word.6) и rtf.
Сохранил их все в формате txt.
Подсчитал 32х-битные хеши.
Не более чем на 2 бита хеши отличались у 15 пар файлов (оригинальный файл и соответствующий txt).
Два из rtf файлов содержали картинку и отличались на 8-9 бит.
А в 3х doc файлах 10-15% объёма занимали его таблицы и отличия были 3-5 разрядов. Вроде бы 10% не много, но по сравнению с текстами, которые писал один и тот же автор, их можно рассматривать как случайные данные, которые хеш могут изменить очень сильно.

А веду я это всё к тому, что мне стало ясно что нужно искать. Если файлы одинаковые, то их хеши отличаются на 0 разрядов. Если разные, то хеши в среднем будут отличаться в половине разрядов (L/2). Ну а границу похож-непохож можно провести где-то посередине, то есть считать похожими файлы, которые отличаются не более чем на L/4 разрядов. Но как искать не перебирать все хеши пока не представляю.

 

Black_mirror

да, это-то понятно, только хэш - это отображение большего множества в меньшее, т. ч. есть бесконечное кол-во файлов с тем же хэшем. впрочем, при достаточно большой битности хэша, думаю, 256 бит достаточно, ну, потокая параное, можно взять 512 бит, можно забить на эту проблему. или дать юзеру выбор в битности хэшей.

а с чего ты их считаешь похожими?????? только различия в 0 бит может говорить о похожести файлов, а коли, вообще, параноя заела, можно файлы с одинаковым хэшем сравнивать побайтно.

 

Можно параллельно md5 считать, для большей верности. Если он тоже совпадает, то файлы похожие. (ну а если не похожие, то срочно отправлять их в музей)....

 

Proteus

любым другим хэшем помимо текущего или увеличить битность хэша, выдаваемого текущим алгосом.