Temukan semua pasangan nilai yang dekat di bawah jarak Hamming

Saya memiliki beberapa juta nilai 32-bit. Untuk setiap nilai, saya ingin menemukan semua nilai lain dalam jarak hamming 5. Dalam pendekatan naif, ini membutuhkan perbandingan $O(N^2)$ , yang ingin saya hindari.

Saya menyadari bahwa jika saya hanya memperlakukan nilai-nilai 32-bit ini sebagai bilangan bulat dan mengurutkan daftar sekali, maka nilai-nilai yang berbeda hanya dalam bit paling signifikan berakhir sangat berdekatan. Ini memungkinkan saya untuk memiliki "jendela" yang lebih pendek atau kisaran angka di mana saya dapat melakukan perbandingan pasangan-bijaksana yang sebenarnya untuk jarak hamming yang tepat. Namun, ketika 2 nilai hanya bervariasi dalam bit urutan yang lebih tinggi, maka mereka berakhir di luar "jendela" ini dan muncul di ujung yang berlawanan dari daftar yang diurutkan. Misalnya

11010010101001110001111001010110

01010010101001110001111001010110

akan sangat berjauhan, meskipun jarak hamming mereka adalah 1. Karena, jarak hamming antara 2 nilai dipertahankan ketika keduanya diputar, saya pikir dengan melakukan 32 rotasi kiri dan kemudian menyortir daftar setiap waktu, kemungkinan ada 2 nilai akan berakhir cukup dekat dalam daftar yang disortir di setidaknya satu dari mereka.

Meskipun pendekatan ini memberi saya hasil yang baik, saya berjuang untuk secara formal menetapkan kebenaran dari pendekatan ini.
Mengingat bahwa saya mencari nilai yang cocok dengan jarak hamming $k$ atau kurang, apakah saya benar-benar perlu melakukan semua rotasi 32 bit? Untuk misalnya jika $k=1$ dan ukuran jendela saya adalah 1000, saya perlu melakukan rotasi maksimum 24 bit karena walaupun bit nyasar muncul di salah satu dari 8 bit urutan yang lebih rendah, angka yang dihasilkan tidak akan berbeda lebih dari 1000.

ds.algorithms co.combinatorics approximation-algorithms karterk
sumber

Hanya ide dari 20 detik pemikiran: Bagaimana dengan sortir menurut Gray-Code? Bagaimana dengan membagi daftar bitmap 32-bit menjadi empat daftar bitmap 8-bit dan kemudian menggunakan teknik Anda?

Karl Damgaard Asmussen

Bisakah Anda lebih tepat tentang jumlah bitmap yang sangat besar? Hampir

atau apa pun?

2^{20}

$2^{20}$

2^{30}

$2^{30}$

minar

@ minar: Saya punya 3-4 juta bitmap 32-bit.

karterk

Saya tidak yakin apa yang Anda tanyakan. Apakah Anda mengatakan bahwa Anda memiliki larik

dari string Boolean 32 huruf (besar tetapi tidak mengandung semua string

mungkin), dan Anda ingin menandai pasangan yang memiliki jarak Hamming paling banyak 5 dalam beberapa cara, mungkin dengan membuat daftar indeks terkait tetangga dekat untuk setiap string

A [i]

$A[i]$

4 \times 10^{9}

$4\times 10^9$ A[i].close

i

$i$

András Salamon

pikir ada konsep serupa "quadtrees" kecuali dengan hypercubes yang berlaku. Algoritma menempatkan & secara rekursif menemukan vektor dalam hypercubes, dan kemudian ketika Anda ingin mencari bitvectors "terdekat", Anda hanya mencari hypercubes "terdekat". mencurigai itu dapat dipelajari & di sebuah makalah di suatu tempat .... tidak yakin istilah yang benar ....

vzn

Jawaban:

Seperti yang dinyatakan, pendekatan Anda bermasalah, karena jika 2 bitmap memiliki perbedaan spasi secara merata maka dalam rotasi apa pun, akan ada perbedaan pada beberapa bit orde tinggi.

Anda dapat menggeneralisasi pendekatan Anda dengan mengubah posisi bit dengan cara yang lebih kompleks. Memang, jika Anda memilih permutasi acak bit, maka semua perbedaan antara 2 bitmap dengan jarak akan muncul di 16 rendah-order bit dengan probabilitas lebih baik dari . Jadi, ulangi beberapa ratus kali Anda harus menemukan proporsi yang sangat besar dari pasangan bitmap Anda. Untuk setiap percobaan, jumlah pasangan untuk menguji (dengan sama 16 bit tinggi) dekat dengan (untuk ). $5$ $1/50$ $64\cdot N$ $N\approx 2^{22}$

Namun, saya juga akan mencoba pendekatan berikut. Buat daftar bitmap Anda yang dimodifikasi paling banyak pada posisi 2 bit dan urutkan daftar ini. Jika ada tabrakan dalam daftar ini, Anda memiliki dua bitmap dalam jarak . Kemudian sebutkan semua nilai bitmap awal Anda yang dimodifikasi tiga posisi dan cari dalam daftar untuk menemukan pasangan bitmap pada jarak . Biaya memori dari pendekatan ini memerlukan menyimpan elemen dan jumlah elemen untuk mencari di tahap kedua adalah . $4$ $5$ $529\cdot N$ $4960\cdot N$

Informasi tambahan:

Probabilitas bahwa perbedaan terletak pada bit urutan rendah setelah permutasi acak dari posisi- bit hanyalah hasil bagi dari dua binomial: $5$ $16$ $32$ $\frac{(\binom{16}{5})}{(\binom{32}{5})} \approx 0,0217$ $\frac{\binom{16}{5}}{\binom{32}{5}}\approx 0.0217$
Konstruksi daftar, untuk setiap elemen dalam daftar asli, dimasukkan ke dalam daftar augmented: elemen itu sendiri, semua elemen berbeda dalam satu posisi dan semua elemen berbeda dalam dua posisi (menjaga informasi tentang elemen asli). Jumlah salinan untuk setiap elemen adalah $1+32+\binom{32}{2}=529.$ $4$
$2$ $\binom{32}{3}=4960$ $3$ $\binom{5}{3}=10$

minar
sumber

Untuk pendekatan pertama, apakah Anda mengatakan bahwa saya mengubah bitmap dalam beberapa pesanan yang telah ditentukan alih-alih melakukan rotasi bit saja? Bisakah Anda jelaskan bagaimana Anda mendapat kemungkinan 1/50? Juga, untuk pendekatan kedua, apakah saya perlu membuat indeks daftar saya terlebih dahulu dan kemudian untuk setiap elemen - menghasilkan (32C1 + 32C2) kombinasi dan memeriksa mereka terhadap indeks ini untuk mengidentifikasi semua bitmap berbeda dengan jarak 2? Akan lebih bagus jika Anda bisa menjelaskan ini lebih jauh. Terima kasih.

karterk

jawaban minar sangat bagus dan mungkin pendekatan yang tepat untuk masalah khusus ini. Namun, saya akan menyebutkan satu pendekatan lagi yang mungkin:

$H$ $x,y$ $H(x)=H(y)$ $H$ $H$

Yang mengatakan, untuk masalah khusus Anda (dengan parameter spesifik yang Anda sebutkan), saya berharap dua algoritma minar akan terbukti lebih baik dalam praktik daripada skema berbasis LSH. Saya menyebutkan ini hanya jika pembaca lain datang ke sini untuk pertanyaan ini dengan masalah yang sama, tetapi dengan parameter yang berbeda di mana LSH mungkin lebih masuk akal.

DW
sumber