Fungsi yang menyebar input

14

Saya ingin tahu apakah ada fungsi f dari nomor n-bit ke nomor n-bit yang memiliki karakteristik berikut:

  • f harus bijective
  • Baik f dan f1 harus dapat dihitung dengan cukup cepat
  • f harus mengembalikan nomor yang tidak memiliki korelasi signifikan dengan inputnya.

Alasannya adalah ini:

Saya ingin menulis sebuah program yang beroperasi pada data. Beberapa informasi data disimpan dalam pohon pencarian biner di mana kunci pencarian adalah simbol alfabet. Seiring waktu, saya menambahkan simbol lebih lanjut ke alfabet. Simbol baru dengan mudah mendapatkan nomor gratis berikutnya. Oleh karena itu, pohon akan selalu memiliki bias kecil untuk kunci yang lebih kecil yang menyebabkan penyeimbangan kembali dari yang saya pikir seharusnya diperlukan.

Ide saya adalah untuk memotong angka simbol dengan f sehingga mereka tersebar luas di seluruh rentang [0,2641] . Karena angka simbol hanya penting selama input dan output yang terjadi hanya sekali, menerapkan fungsi seperti itu seharusnya tidak terlalu mahal.

Saya berpikir tentang satu iterasi dari generator angka acak Xorshift, tetapi saya tidak benar-benar tahu cara untuk membatalkannya, meskipun secara teori hal itu harus dimungkinkan.

Apakah ada yang tahu fungsi seperti itu?
Apakah ini ide yang bagus?

FUZxxl
sumber
1
Saya bukan ahli, tetapi mungkin Anda dapat menggunakan permutasi pseudorandom (lihat misalnya cipher Feistel )
Vor
Jika pada dasarnya Anda menghitung fungsi hash, mengapa tidak menggunakan hashing?
vonbrand
@vonbrand Hashing tidak dapat dibalik. Lihat nomor persyaratan 2.
FUZxxl
Mengapa harus dibalik? Apa yang salah dengan membuatnya reversibel dengan pencarian?
vonbrand
1
Anda dapat menyimpan (f (x), x) sebagai kunci.
adrianN

Jawaban:

6

Anda dapat menggunakan hashing Fibonacci , yaitu

.hF(k)=k512k512

Untuk Anda mendapatkan n angka berbeda berpasangan (sekitar) yang tersebar secara merata di [ 0 , 1 ] . Dengan penskalaan ke [ 1 .. M ] dan pembulatan (bawah), Anda mendapatkan angka yang tersebar secara merata dalam interval itu.k=1,,nn[0,1][1..M]

Misalnya, ini adalah diskalakan ke [ 0..10000 ] (urutan asli kiri, disortir kanan):hF(1),,hF(200)[0..10000]

masukkan deskripsi gambar di sini

Ini adalah contoh dari apa yang Knuth sebut hashing multiplikatif . Untuk kata ukuran komputer, A beberapa bilangan bulat yang relatif prima terhadap w dan M jumlah alamat yang dibutuhkan, kita menggunakanwAwM

h(k)=M((kAw)mod1)

sebagai fungsi hashing. Di atas diikuti dengan (pastikan Anda dapat menghitungnya dengan presisi yang cukup). Meskipun ini juga berfungsi dengan bilangan irasional lainnya selainϕ-1A/w=ϕ1=512ϕ1 , ini adalah salah satu dari hanya dua angka yang mengarah ke angka "terdistribusi paling seragam".

Temukan lebih banyak di The Art of Computer Programming , Volume 3 oleh Donald Knuth (bab 6.4 dari halaman 513 dalam edisi kedua). Khususnya Anda akan menemukan mengapa angka-angka yang dihasilkan berbeda secara berpasangan (setidaknya jika ) dan bagaimana menghitung fungsi terbalik jika Anda menggunakan natural A dan w bukannya ϕ - 1 .nMAwϕ1

Raphael
sumber
1
Bagaimana cara menghitung efisien? f1
frafl
1
@frafl Saya harap edit saya membahas masalah Anda. Namun, jelas bahwa teknik hashing ini tidak dirancang khusus agar tidak dapat dibalik secara efisien.
Raphael
Ya, saya akan menjawabnya, namun saya tidak akan merekomendasikannya sebagai jawaban yang diterima.
frafl
1

Untuk input bit, fungsi ini berfungsi:k

hash(n)=(nmod2k2)2k2+ndiv2k2

Ini dapat dibalik, dalam , dan memiliki pasangan tidak berurutan { n , m } , n < m , di mana h a s h ( m ) < h a s h ( n ) . Waspadalah bahwa output dan input mungkin berkorelasi, terutama jika input Anda dalam { 1 , , 2 khash(hash(n))=n{n,m},n<mhash(m)<hash(n){1,,2k21} .

Ref: Fungsi hash yang dapat dibalik

Reza
sumber
Ini terlihat sederhana dan menyenangkan. Saya akan menguji yang itu.
FUZxxl
1
1. Bergantung pada input, ini dapat menghasilkan korelasi berat (hingga untuk Spearman ρ ) 2. Ini untuk 32 bit, bukan untuk 64 bit 3. Bisakah Anda menulis ini dengan cara yang tidak tergantung bahasa? 1ρ
frafl
cukup jelas! untuk 64-bit (0x00000000FFFFFFFFFF) dan Anda harus menggeser (<<) 32 bit. Fungsi ini sederhana, praktis dan cukup cepat dalam praktiknya.
Reza
1
Tetapi mengapa Anda tidak menggunakan permutasi bit, yang tidak memetakan setiap hingga 2 32 x ? Sebagaimana dinyatakan di atas ini jelas melanggar kondisi korelasi yang dituntut oleh OP. x{1,,2321}232x
frafl