큰 집합에서 해밍 거리가 낮은 이진 문자열을 효율적으로 찾습니다.

큰 집합에서 해밍 거리가 낮은 이진 문자열을 효율적으로 찾습니다.

---

문제:

부호없는 32 비트 정수의 큰 (~ 1 억) 목록, 부호없는 32 비트 정수 입력 값 및 최대 Hamming Distance가 주어지면 입력 값 의 지정된 Hamming Distance 내에있는 모든 목록 멤버를 반환합니다.

목록을 보관할 실제 데이터 구조는 공개되어 있고 성능 요구 사항은 메모리 내 솔루션을 요구하며 데이터 구조를 구축하는 데 드는 비용은 부차적이며 데이터 구조를 쿼리하는 데 드는 비용은 매우 중요합니다.

예:

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

지금까지 내 생각 :

해밍 거리가 0 인 퇴화 사례의 경우 정렬 된 목록을 사용하고 특정 입력 값에 대해 이진 검색을 수행합니다.

해밍 거리가 1 일 경우 원래 입력의 각 비트를 뒤집고 위의 32 번 반복 할 수 있습니다.

어떻게하면 전체 목록을 스캔하지 않고 Hamming Distance> 1 인 목록 구성원을 효율적으로 찾을 수 있습니다.

---

질문 : 해밍 거리 d (x, y)에 대해 무엇을 알고 있습니까?

대답:

1. 음수가 아님 : d (x, y) ≥ 0
2. 동일한 입력에 대해서만 0입니다 : d (x, y) = 0 ⇔ x = y
3. 대칭입니다 : d (x, y) = d (y, x)
4. 그것은 따르는 삼각 부등식 , D를 (X, Z) ≤ D (X, Y) + (D) (Y, z)

질문 : 우리는 왜 신경을 쓰나요?

답변 : 이 해밍 거리가 있다는 것을 의미하기 때문에 메트릭 A에 대한 메트릭 공간 . 메트릭 공간을 인덱싱하는 알고리즘이 있습니다.

• 메트릭 트리 (Wikipedia)
• BK- 트리 (Wikipedia)
• M-tree (Wikipedia)
• VP- 트리 (Wikipedia)
• 커버 트리 (Wikipedia)

당신의 공간이 유클리드 아니지만 그 또한 지식으로 무장 일반적으로 "공간 인덱싱"에 대한 알고리즘을 찾아 볼 수 있다 메트릭 공간. 이 주제에 관한 많은 책은 해밍 거리와 같은 메트릭을 사용한 문자열 인덱싱을 다룹니다.

각주 : 고정 너비 문자열의 해밍 거리를 비교하는 경우 어셈블리 또는 프로세서 내장 함수를 사용하여 상당한 성능 향상을 얻을 수 있습니다. 예를 들어 GCC ( manual )를 사용 하면 다음과 같이합니다.

static inline int distance(unsigned x, unsigned y)
{
    return __builtin_popcount(x^y);
}

그런 다음 GCC에 SSE4a로 컴퓨터를 컴파일한다고 알리면 몇 개의 opcode로 줄여야한다고 생각합니다.

편집 : 여러 소스에 따르면 이것은 때때로 / 종종 일반적인 마스크 / 시프트 / 추가 코드보다 느립니다. 벤치마킹에 따르면 내 시스템에서 C 버전이 GCC보다 __builtin_popcount약 160 % 성능이 뛰어납니다 .

부록 : 직접 문제에 대해 궁금해서 선형 검색, BK 트리 및 VP 트리의 세 가지 구현을 프로파일 링했습니다. VP와 BK 트리는 매우 유사합니다. BK 트리에서 노드의 자식은 트리의 중심에서 각각 고정 된 거리에있는 점을 포함하는 트리의 "쉘"입니다. VP 트리의 노드에는 두 개의 하위가 있습니다. 하나는 노드의 중심에있는 구 내의 모든 점을 포함하고 다른 하나는 외부의 모든 점을 포함하는 하위입니다. 따라서 VP 노드를 여러 개의 미세한 쉘 대신 두 개의 매우 두꺼운 "쉘"이있는 BK 노드로 생각할 수 있습니다.

결과는 내 3.2GHz PC에서 캡처되었으며 알고리즘은 다중 코어를 사용하려고 시도하지 않습니다 (쉬울 것임). 나는 100M 의사 난수 정수의 데이터베이스 크기를 선택했습니다. 결과는 거리 1..5에 대한 1000 개의 쿼리, 6..10 및 선형 검색에 대한 100 개의 쿼리의 평균입니다.

• 데이터베이스 : 100M 의사 난수 정수
• 테스트 수 : 거리 1..5의 경우 1000, 거리 6..10 및 선형의 경우 100
• 결과 : 평균 쿼리 히트 수 (매우 근사치)
• 속도 : 초당 쿼리 수
• 적용 범위 : 쿼리 당 검사 된 데이터베이스의 평균 비율

                -BK 트리--VP 트리--선형-
거리 결과 속도 Cov 속도 Cov 속도 Cov
1 0.90 3800 0.048 % 4200 0.048 %
2 11300 0.68 % 330 0.65 %
3130 56 3.8 % 63 3.4 %
4970 18 12 % 22 10 %
5 5700 8.5 26 % 10 22 %
6 2.6e4 5.2 42 % 6.0 37 %
7 1.1e5 3.7 60 % 4.1 54 %
8 3.5e5 3.0 74 % 3.2 70 %
9 1.0e6 2.6 85 % 2.7 82 %
10 2.5e6 2.3 91 % 2.4 90 %
2.2 100 %

귀하의 의견에서 다음과 같이 언급했습니다.

다른 루트 노드를 가진 BK- 트리를 여러 개 생성하고이를 확산시킴으로써 BK- 트리를 개선 할 수 있다고 생각합니다.

이것이 바로 VP 트리가 BK 트리보다 (약간) 더 잘 수행되는 이유라고 생각합니다. "얕은"보다는 "깊이"이기 때문에 더 적은 포인트에 대해 더 세밀한 비교를 사용하는 대신 더 많은 포인트와 비교합니다. 나는 그 차이가 더 높은 차원의 공간에서 더 극단적이라고 생각합니다.

마지막 팁 : 트리의 리프 노드는 선형 스캔을위한 정수의 평평한 배열이어야합니다. 작은 세트 (아마도 1000 포인트 이하)의 경우 더 빠르고 메모리 효율성이 높습니다.

---

나는 2 ³² 비트의 비트 세트로 입력 숫자를 나타내는 솔루션을 작성하여 특정 숫자가 입력에 있는지 O (1)에서 확인할 수 있습니다. 그런 다음 쿼리 된 숫자와 최대 거리에 대해 해당 거리 내의 모든 숫자를 재귀 적으로 생성하고 비트 세트와 비교하여 확인합니다.

예를 들어 최대 거리 5의 경우 242825 숫자입니다 ( sum _{d = 0 ~ 5} {32 choose d} ). 비교를 위해 Dietrich Epp의 VP-tree 솔루션은 예를 들어 1 억 개의 숫자 중 22 %, 즉 2 천 2 백만 개의 숫자를 통과합니다.

저는 Dietrich의 코드 / 솔루션을 기반으로 내 솔루션을 추가하고 그의 솔루션과 비교했습니다. 최대 10 개의 거리에 대한 초당 쿼리 속도는 다음과 같습니다.

Dist     BK Tree     VP Tree         Bitset   Linear

   1   10,133.83   15,773.69   1,905,202.76   4.73
   2      677.78    1,006.95     218,624.08   4.70
   3      113.14      173.15      27,022.32   4.76
   4       34.06       54.13       4,239.28   4.75
   5       15.21       23.81         932.18   4.79
   6        8.96       13.23         236.09   4.78
   7        6.52        8.37          69.18   4.77
   8        5.11        6.15          23.76   4.68
   9        4.39        4.83           9.01   4.47
  10        3.69        3.94           2.82   4.13

Prepare     4.1s       21.0s          1.52s  0.13s
times (for building the data structure before the queries)

작은 거리의 경우 bitset 솔루션이 4 개 중 가장 빠릅니다. 질문 작성자 Eric은 아래에서 가장 큰 관심 거리는 아마도 4-5 일 것이라고 말했습니다. 당연히 내 bitset 솔루션은 더 먼 거리에서 느리고 선형 검색보다 느립니다 (거리 32의 경우 2 ^{32 개의} 숫자를 통과 합니다). 그러나 거리 9의 경우 여전히 쉽게 이어집니다.

I also modified Dietrich's testing. Each of the above results is for letting the algorithm solve at least three queries and as many queries as it can in about 15 seconds (I do rounds with 1, 2, 4, 8, 16, etc queries, until at least 10 seconds have passed in total). That's fairly stable, I even get similar numbers for just 1 second.

My CPU is an i7-6700. My code (based on Dietrich's) is here (ignore the documentation there at least for now, not sure what to do about that, but the tree.c contains all the code and my test.bat shows how I compiled and ran (I used the flags from Dietrich's Makefile)). Shortcut to my solution.

One caveat: My query results contain numbers only once, so if the input list contains duplicate numbers, that may or may not be desired. In question author Eric's case, there were no duplicates (see comment below). In any case, this solution might be good for people who either have no duplicates in the input or don't want or need duplicates in the query results (I think it's likely that the pure query results are only a means to an end and then some other code turns the numbers into something else, for example a map mapping a number to a list of files whose hash is that number).

---

A common approach (at least common to me) is to divide your bit string in several chunks and query on these chunks for an exact match as pre-filter step. If you work with files, you create as many files as you have chunks (e.g. 4 here) with each chunk permuted in front and then sort the files. You can use a binary search and you can even expand you search above and below a matching chunk for bonus.

You then can perform a bitwise hamming distance computation on the returned results which should be only a smaller subset of your overall dataset. This can be done using data files or SQL tables.

So to recap: Say you have a bunch of 32 bits strings in a DB or files and that you want to find every hash that are within a 3 bits hamming distance or less of your "query" bit string:

1. create a table with four columns: each will contain an 8 bits (as a string or int) slice of the 32 bits hashes, islice 1 to 4. Or if you use files, create four files, each being a permutation of the slices having one "islice" at the front of each "row"

2. slice your query bit string the same way in qslice 1 to 4.

3. query this table such that any of qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. This gives you every string that are within 7 bits (8 - 1) of the query string. If using a file, do a binary search in each of the four permuted files for the same results.

4. for each returned bit string, compute the exact hamming distance pair-wise with you query bit string (reconstructing the index-side bit strings from the four slices either from the DB or from a permuted file)

The number of operations in step 4 should be much less than a full pair-wise hamming computation of your whole table and is very efficient in practice. Furthermore, it is easy to shard the files in smaller files as need for more speed using parallelism.

Now of course in your case, you are looking for a self-join of sort, that is all the values that are within some distance of each other. The same approach still works IMHO, though you will have to expand up and down from a starting point for permutations (using files or lists) that share the starting chunk and compute the hamming distance for the resulting cluster.

If running in memory instead of files, your 100M 32 bits strings data set would be in the range of 4 GB. Hence the four permuted lists may need about 16GB+ of RAM. Though I get excellent results with memory mapped files instead and must less RAM for similar size datasets.

There are open source implementations available. The best in the space is IMHO the one done for Simhash by Moz, C++ but designed for 64 bits strings and not 32 bits.

This bounded happing distance approach was first described AFAIK by Moses Charikar in its "simhash" seminal paper and the corresponding Google patent:

5. APPROXIMATE NEAREST NEIGHBOR SEARCH IN HAMMING SPACE

[...]

Given bit vectors consisting of d bits each, we choose N = O(n 1/(1+ ) ) random permutations of the bits. For each random permutation σ, we maintain a sorted order O σ of the bit vectors, in lexicographic order of the bits permuted by σ. Given a query bit vector q, we find the approximate nearest neighbor by doing the following:

For each permutation σ, we perform a binary search on O σ to locate the two bit vectors closest to q (in the lexicographic order obtained by bits permuted by σ). We now search in each of the sorted orders O σ examining elements above and below the position returned by the binary search in order of the length of the longest prefix that matches q.

Monika Henziger expanded on this in her paper "Finding near-duplicate web pages: a large-scale evaluation of algorithms":

3.3 The Results for Algorithm C

We partitioned the bit string of each page into 12 non- overlapping 4-byte pieces, creating 20B pieces, and computed the C-similarity of all pages that had at least one piece in common. This approach is guaranteed to find all pairs of pages with difference up to 11, i.e., C-similarity 373, but might miss some for larger differences.

This is also explained in the paper Detecting Near-Duplicates for Web Crawling by Gurmeet Singh Manku, Arvind Jain, and Anish Das Sarma:

3. THE HAMMING DISTANCE PROBLEM

Definition: Given a collection of f -bit fingerprints and a query fingerprint F, identify whether an existing fingerprint differs from F in at most k bits. (In the batch-mode version of the above problem, we have a set of query fingerprints instead of a single query fingerprint)

[...]

Intuition: Consider a sorted table of 2 d f -bit truly random fingerprints. Focus on just the most significant d bits in the table. A listing of these d-bit numbers amounts to “almost a counter” in the sense that (a) quite a few 2 d bit- combinations exist, and (b) very few d-bit combinations are duplicated. On the other hand, the least significant f − d bits are “almost random”.

Now choose d such that |d − d| is a small integer. Since the table is sorted, a single probe suffices to identify all fingerprints which match F in d most significant bit-positions. Since |d − d| is small, the number of such matches is also expected to be small. For each matching fingerprint, we can easily figure out if it differs from F in at most k bit-positions or not (these differences would naturally be restricted to the f − d least-significant bit-positions).

The procedure described above helps us locate an existing fingerprint that differs from F in k bit-positions, all of which are restricted to be among the least significant f − d bits of F. This takes care of a fair number of cases. To cover all the cases, it suffices to build a small number of additional sorted tables, as formally outlined in the next Section.

Note: I posted a similar answer to a related DB-only question

---

You could pre-compute every possible variation of your original list within the specified hamming distance, and store it in a bloom filter. This gives you a fast "NO" but not necessarily a clear answer about "YES."

For YES, store a list of all the original values associated with each position in the bloom filter, and go through them one at a time. Optimize the size of your bloom filter for speed / memory trade-offs.

Not sure if it all works exactly, but seems like a good approach if you've got runtime RAM to burn and are willing to spend a very long time in pre-computation.

---

How about sorting the list and then doing a binary search in that sorted list on the different possible values within you Hamming Distance?

---

One possible approach to solve this problem is using a Disjoint-set data structure. The idea is merge list members with Hamming distance <= k in the same set. Here is the outline of the algorithm:

• For each list member calculate every possible value with Hamming distance <= k. For k=1, there are 32 values (for 32-bit values). For k=2, 32 + 32*31/2 values.

  • For each calculated value, test if it is in the original input. You can use an array with size 2^32 or a hash map to do this check.

  • If the value is in the original input, do a "union" operation with the list member.

  • Keep the number of union operations executed in a variable.

You start the algorithm with N disjoint sets (where N is the number of elements in the input). Each time you execute an union operation, you decrease by 1 the number of disjoint sets. When the algorithm terminates, the disjoint-set data structure will have all the values with Hamming distance <= k grouped in disjoint sets. This disjoint-set data structure can be calculated in almost linear time.

참고URL : https://stackoverflow.com/questions/6389841/efficiently-find-binary-strings-with-low-hamming-distance-in-large-set