Функция, которая распространяет ввод

14

Я хотел бы знать, существует ли функция f от n-битных чисел до n-битных чисел, которая имеет следующие характеристики:

  • f должно быть биективным
  • Оба f и f1 должны быть вычислены довольно быстро
  • f должен вернуть число, которое не имеет существенной корреляции с его вводом.

Обоснование таково:

Я хочу написать программу, которая работает с данными. Некоторая информация данных хранится в бинарном дереве поиска, где ключ поиска является символом алфавита. Со временем я добавляю дополнительные символы в алфавит. Новые символы просто получают следующий свободный номер. Следовательно, дерево всегда будет иметь небольшой уклон к более мелким ключам, что вызывает большую перебалансировку, чем я думаю, что это необходимо.

Моя идея состоит в том, чтобы искажать номера символов с помощью f , чтобы они широко распространялись по всему диапазону [0,2641] . Поскольку номера символов имеют значение только во время ввода и вывода, что происходит только один раз, применение такой функции не должно быть слишком дорогим.

Я думал об одной итерации генератора случайных чисел Xorshift, но я не знаю, как отменить его, хотя теоретически это должно быть возможно.

Кто-нибудь знает такую ​​функцию?
Это хорошая идея?

FUZxxl
источник
1
Я не эксперт, но, возможно, вы можете использовать псевдослучайную перестановку (см., Например, шифр Фейстеля )
Vor
Если вы по сути вычисляете хеш-функцию, почему бы не использовать хеширование?
vonbrand
@vonbrand Хеширование необратимо. См. Требование № 2.
FUZxxl
Почему это должно быть обратимо? Что плохого в том, чтобы сделать его обратимым при поиске?
vonbrand
1
Вы можете сохранить (f (x), x) как ключи.
adrianN

Ответы:

6

Вы можете использовать хеширование Фибоначчи , а именно

.hF(k)=k512k512

Для вы получите n попарно различных чисел (примерно), равномерно распределенных в [ 0 , 1 ] . Масштабируя до [ 1 .. M ] и округляя (вниз), вы получите примерно равномерное распределение чисел в этом интервале.k=1,,nn[0,1][1..M]

Например, это масштабированные до [ 0..10000 ] (исходная последовательность слева, отсортированная справа):hF(1),,hF(200)[0..10000]

введите описание изображения здесь

Это пример того, что Кнут называет мультипликативным хешированием . Для размера слова компьютера, A некоторое целое число относительно простого числа w и M количество необходимых адресов, мы используемwAwM

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

как функция хеширования. Сказанное следует с (убедитесь, что вы можете вычислить его с достаточной точностью). Хотя это также работает с любым другим иррациональным числом, кромеϕ-1, это одно из двух чисел, которые приводят к «наиболее равномерно распределенным» числам.A/w=ϕ1=512ϕ1

Узнайте больше в книге «Искусство компьютерного программирования» , том 3 Дональда Кнута (глава 6.4 на стр. 513 во втором издании). В частности, вы поймете, почему полученные числа попарно различны (по крайней мере, если ) и как вычислить обратную функцию, если вы используете натуральное AnMA и вместо ϕ - 1 .wϕ1

Рафаэль
источник
1
Как эффективно рассчитать ?f1
2013 г.
1
@frafl Я надеюсь, что мое редактирование несколько решит вашу проблему. Понятно, однако, что эти методы хеширования не предназначены для эффективной обратимости.
Рафаэль
Да, это так, я буду голосовать, но я бы не рекомендовал это как принятый ответ.
2011 г.
1

Для битных входов эта функция работает:k

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

hash(hash(n))=n{n,m},n<mhash(m)<hash(n){1,,2k21}

Ссылка: обратимая хеш-функция

Реза
источник
Это выглядит просто и красиво. Я собираюсь проверить это.
FUZxxl
1
1ρ
это довольно понятно! для 64-битного (0x00000000FFFFFFFF) и вам следует сдвинуть (<<) 32 бит. Эта функция проста, практична и достаточно быстра на практике.
Реза
1
x{1,,2321}232x