Создание эффективной функции, чтобы соответствовать набору данных

Question

В основном у меня большой (может быть до 100 000-150 000 значений) набор данных с 4-байтовыми входами и соответствующими 4-байтовыми выходами. Входные данные не гарантированно являются уникальными (что на самом деле не является проблемой, потому что я полагаю, что могу генерировать псевдослучайные числа для добавления или преобразования входных значений, чтобы они стали уникальными), но выходные данные не гарантируются быть уникальным (поэтому два разных набора входов могут иметь одинаковый выход).

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

Кроме того, с моей точки зрения, полиномиальная интерполяция была бы слишком вычислительно дорогой (n значений означает, что полином мог включать в себя такие же члены, как pow (x, n-1). Для x = 4-байтовое число и n = 100 000) это просто нереально). Я уже некоторое время пытался искать в Интернете, но я не очень силен в математике и не должен знать правильные термины для поиска, потому что я до сих пор не встречал ничего подобного.

Я вижу, что это не совсем (мягко говоря) вопрос программирования, и я заранее извиняюсь. Я не ищу точное решение или даже полный ответ. Мне просто нужны указатели по темам, которые мне нужно прочитать, чтобы я мог решить эту проблему самостоятельно. Спасибо!

TL; DR - мне нужен вариант интерполяции, который должен соответствовать только первоначально заданным точкам данных, но эффективен в вычислительном отношении.

Edit: Некоторое уточнение - мне нужен точный вывод, а не приближение. Это своего рода оптимизация некоторой исследовательской работы, которую я сейчас выполняю, и мне нужно, чтобы этот поиск был реализован без фактических байтов выходных данных, присутствующих в моей программе. В настоящий момент я не могу много говорить об этом, но скажу, что для целей моей работы шифрование (или сжатие, или любая другая форма запутывания) не позволяет скрыть таблицу. Мне нужна математическая функция, которая может воссоздать вывод, если он имеет доступ к входу. Надеюсь, это немного прояснит ситуацию.

Answer 1

Вот одна идея.Сделайте вашу функцию суммой (mod 2 ³² ) линейной функции по всем 4-байтовым целым числам, кусочно-линейной функцией, части которой зависят от значения первого бита, другой кусочно-линейной функцией, чьи части зависято значении первых двух битов и т. д.

Фактические выходные значения нигде не отображаются, для их получения необходимо сложить линейные члены.Также нет прямой записи того, какие входные значения у вас есть.(Кто-то может сделать вывод об этих входных значениях, но не об их фактических значениях.)

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

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

Answer 2

Я предлагаю огромную таблицу поиска , заполненную неиспользованными записями. Это грубый метод с упорядоченной таблицей выходных данных, упорядоченной по каждому возможному значению ввода (не только по набору данных, но и по всем другим возможным 4-байтовым значениям).

Хотя все ваши данные будут там, вы можете заполнить неиспользуемые входные данные случайными, произвольными или стохастическими (случайными с потенциально сложными ограничениями) данными. Если вы сделаете это убедительно, никто не сможет извлечь из этого ваши реальные данные. Если бы «реальная» функция интерполировала все ваши данные, она также «содержала бы» всю информацию о ваших реальных данных, и любой, кто имеет к ней доступ, мог бы использовать ее для создания LUT, как описано выше .

LUT молниеносны, но очень жадны до памяти. Ваш случай находится на грани осуществимости, требуя (2 ^ 32) * 32 = 16 ГБ ОЗУ, для работы которого требуется 64-разрядная машина. Это только для данных, а не для программы, операционной системы или других данных. Лучше иметь 24, просто чтобы быть уверенным . Если вы можете себе это позволить, они - путь.

Answer 3

Поскольку вы не накладывали никаких ограничений на функцию (непрерывную, гладкую и т. Д.), Вы можете просто выполнить кусочную константу с постоянной интерполяцией:

илилинейная интерполяция:

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

РЕДАКТИРОВАТЬ: в свете вашего дополнительного требования, чтотакая функция должна «скрывать» точки данных ...

Для кусочной постоянной интерполяции постоянные интервалы должны быть рандомизированы, чтобы не показывать, где находится точка данных.Так, например, на рисунке интервалы центрированы относительно точки данных, которую он интерполирует.Вместо этого вы можете захотеть сделать что-то вроде:

[0 , 0.3) -> 0
[0.3 , 1.9) -> 0.8
[1.9 , 2.1) -> 0.9
[2.1 , 3.5) -> 0.2
etc

Конечно, это только скрывает X-координату.Чтобы скрыть координату y, вы также можете использовать линейную интерполяцию.

Просто сделайте так, чтобы «заостренная» часть находилась не там, где находится точка данных.Выберите случайные значения x, чтобы каждая соседняя точка данных имела одно из этих значений x между ними.Затем интерполируйте так, чтобы «заостренная» часть имела эти значения x.