Я нигде ничего не делю, энтропия считается для всего текста. Если его сжать арифметическим кодеком приложив частотный словарь слов, то ровно столько бит потребуется для сохранения. Вот со словарем я немного упростил функцию. Как раз наоборот, чем меньше слов, тем меньше энтропия текста (но больше словарь).
Минимизируешь энтропию текста деленного на слова + энтропию словаря, по всем разбиениям. Если делить посимвольно (все слова из одной буквы), словарь получаеться маленький, а текст большой. С другой стороны если взять весь текст как одно слово - тогда на сам текст будет приходиться 0 энтропии, а словарь будет стоить как весь текст без сжатия (с перплексией алфавит на символ). При этом частые сочетания (фразеологизмы) и популярные предлоги скорее всего слипнуться в одно слово. Еще можно добавить штраф за длину слов / KLD между словарем и ципфром.
Безусловно правда. Правда я не удивлюсь что на практике лучше будет работать что-то ближе к наивному (log(n), n^2 log(n)). По исходной задаче пока только смог свести к pext/pdep с глубиной log(n), что наверное не возможно.
Смотрел с точки зрения того что перестановка редко меняется и мы вольны что угодно для нее посчитать заранее. Вроде у Батчера на каждом слое мы можем смотреть на определенный бит, что то вроде 0102103210 - для 4 бит (N=16).Да, так действительно сложнее.
Первый результат почти очевидный, если я правильно понял формулировку - OUT[I] = IN[SIGMA[I]]. берем сеть бетчера из коммутаторов размера 2, отдельно сортируем в ней перестановку inv(SIGMA), выходы компораторов подаем в качестве конфигурации соответствующих коммутаторов. Кажется это должно работать точно также если SIGMA произвольное отображение, только на вход коммутаторов подается два бита вмесио одного (вместо swap_inputs, sel_0+sel_1), и сортировать что то чуть более хитрое.
Пример последовательности: 1 -2 3. Если считать правильно то получится: relu(1-2)+3=3; а если наивно: 2.
Легко понять что порядок важен: если переставить 3 в начало то переносов при сложении не возникнет, и результат совпадет, в то время как подход "сложить все" - теряет информацию о порядке.
Не, тут всегда известно что сразу после умножения на 3 последует 1 деление на 2.
Таким образом в среднем за (1/2 + 3/2)/2 = 1. Но в случае с умножением нужно брать среднее геометрическое (или перейти к логарифмам), тут уже будет результат sqrt(3)/2~0.86<1.
Парадокса нет, проблема в том что нужно доказать для каждого, а не в "среднем".
O(n^3) раз брать по модулю не нужно, промежуточные вычисления вполне помещаются в разумные типы, если модуль маленький. Даже если он большой (порядка 10^9), можно брать Uint64 и делать каждые 16 итераций одно сравнение с вычитанием (завести константу 16*Mod*Mod).
Тут либо сервер умеет расшифровывать сообщение и детектить по базе, либо кто то что то не договаривает
Как вы без ключа узнаете содержимое?
Не, все интереснее.
Для того что бы сервер не мог узнать запрос, ему нужно будет его "смешать" со всей базой данных, то есть индексы тут не помогут. Например если у Гугла поисковая база 100 терабайт, но нужно будет выполнить вычисления над запросом и всей базой.
Пример:
Клиент хочет узнать если ли слово (число) x в множестве А, которое известно серверу, но не хочет что бы сервер узнал x. Сам он множество А не знает.
Клиент отправляет $f(x)$ на сервер. Сервер считает $prod(f(x)-y | y in A) = prod(f(x-y) | y in A) = f(prod(x-y | y in A))$, здесь мы пользуемся гомоморфностью относительно сложения и умножения одновременно. Теперь это значение получает клиент, снимает шифрование и получает нулевое или не нулевое значение, по которому узнает ответ. (нулевое значение почти всегда означает что слово есть в множестве)
Если библиотека не даёт сделать $y -> f(y)$, то клиент может отправить ${b_i = f(2^i) | 0 <= i < N}$, тогда сервер может получить любую константу сложением $n < 2^N -> f(n) = f(sum(2^e | e in B)) = sum(f(2^e | e in B)) = sum(b_e | e in B)$, где B двоичное представление n.
Как реализовать байесовский (хотя бы) фильтр (с разбиением текста на отдельные токены и пр.) с помощью только сложения и умножения — это, я думаю, будет предметом еще чьей-нибудь докторской диссертации
Ну или наивный Байес, тут еще проще. Отправляем ${f(p_w) | w in U}$, bag of words,
Сервер возвращает линейную комбинацию $sum(a_w f(p_w) | w in U) =… = f(sum(a_w p_w | w in U))$. В итоге сервер не знает письма, а клиент не знает коэффициентов, все очень просто.
При желании можно и нейронку на таком входе посчитать, все упирается в функцию активации, для логистической можно экспоненту в ряд Тейлора разложить до какого-то члена, и должно нормально получиться, ну еще и делить придётся.
Естественно f должна меняться при каждом письме, иначе двух запросов с разными p_w и одинаковыми остальными значениями будет достаточно для того что бы узнать одно a_w.
Для того что бы работать с длинными словами, можно отправлять ${f(x_i) | 0 <= i < W}$, и перемножать $sum(f((x_i — y_i)^2) | 0 <= i < W)$, (вместо $(x-y)$) но тогда клиент раскрывает часть информации об $x$, но тем меньшую, чем больший размер слова доступен, и чего можно совсем избежать если преобразовать слова по принципу '{s_1,s_2,s_3} -> {(1,s_1),(2,s_2),(3,s_3)}'.
Прикол в том что укачивание — это реакция на расхождение показаний вестибулярного аппарата и глаз, что исторически связано с попаданием в организм нейротоксинов. Разумная реакция со стороны мозга в этом случае — избавиться от содержимого желудка.
Всё так, моя идея относится к коду до С++20, а более оптимальный код может получиться в дебажной сборке или например лексографическом компараторе.
Вместо: bool operator< (A const& rhs) const {
if (t < rhs.t) return true;
if (rhs.t < t) return false;
return u < rhs.u;
}
Использую: bool operator< (A const& rhs) const {
if (t != rhs.t) return t < rhs.t;
return u < rhs.u;
}
Мой вариант может быстрее если t и rhs.t лексикографические строки разной длины, тогда если для сравнения их на меньше нужно пробежать до первого расхождения, а в сравнении на неравенство — вначале стоит проверка на длину.
Чисто теоретически компилятор может все понять и соптимизировать до эквивалентного кода — но на практике это не работает: код.
Спейсшип должен решить эту проблему.
забанить 5067 ip? вроде супер-изи.
Я нигде ничего не делю, энтропия считается для всего текста. Если его сжать арифметическим кодеком приложив частотный словарь слов, то ровно столько бит потребуется для сохранения. Вот со словарем я немного упростил функцию. Как раз наоборот, чем меньше слов, тем меньше энтропия текста (но больше словарь).
Я имел в виду time complexity, у меня что-то между O(n^2) и O(n^3).
Вот тут код, я наигрался с ним, как минимум убедился что моя идея рабочая https://pastebin.com/uWnsdikr
Асимптотика не та, но я попробовал.
Что-то получилось https://pastebin.com/6xk0ZipK
Вот концовка
https://pastebin.com/fZ5eGa0U
Видно что жадность плохо работает, нужно еще и пересобирать слова.
Пример: "есл им ы" встречается 4 раза, и хотя мы добавили в словарь пару (есл, и), мы не можем ничего сделать с уже построенным "им".
log(alphabet) * сумму длин всех слов.
Я попробовал что получается на тексте полученном из статьи, написал жадный алгоритм, сейчас посмотрим что выйдет.
Начинаю с односимвольных слов, сливаю соседние жадно.
https://pastebin.com/q8Jnkfkh
Минимизируешь энтропию текста деленного на слова + энтропию словаря, по всем разбиениям. Если делить посимвольно (все слова из одной буквы), словарь получаеться маленький, а текст большой. С другой стороны если взять весь текст как одно слово - тогда на сам текст будет приходиться 0 энтропии, а словарь будет стоить как весь текст без сжатия (с перплексией алфавит на символ). При этом частые сочетания (фразеологизмы) и популярные предлоги скорее всего слипнуться в одно слово. Еще можно добавить штраф за длину слов / KLD между словарем и ципфром.
Безусловно правда. Правда я не удивлюсь что на практике лучше будет работать что-то ближе к наивному (log(n), n^2 log(n)). По исходной задаче пока только смог свести к pext/pdep с глубиной log(n), что наверное не возможно.
Смотрел с точки зрения того что перестановка редко меняется и мы вольны что угодно для нее посчитать заранее.
Вроде у Батчера на каждом слое мы можем смотреть на определенный бит, что то вроде 0102103210 - для 4 бит (N=16).Да, так действительно сложнее.По второму результату кажется что O(H) довольно много на практике, или я не понял условие.
Первый результат почти очевидный, если я правильно понял формулировку - OUT[I] = IN[SIGMA[I]]. берем сеть бетчера из коммутаторов размера 2, отдельно сортируем в ней перестановку inv(SIGMA), выходы компораторов подаем в качестве конфигурации соответствующих коммутаторов. Кажется это должно работать точно также если SIGMA произвольное отображение, только на вход коммутаторов подается два бита вмесио одного (вместо swap_inputs, sel_0+sel_1), и сортировать что то чуть более хитрое.
задержка скорее всего на арбитре возникаетможет и в правду цепочку триггеров вставили.Пример последовательности: 1 -2 3. Если считать правильно то получится: relu(1-2)+3=3; а если наивно: 2.
Легко понять что порядок важен: если переставить 3 в начало то переносов при сложении не возникнет, и результат совпадет, в то время как подход "сложить все" - теряет информацию о порядке.
Не, тут всегда известно что сразу после умножения на 3 последует 1 деление на 2.
Таким образом в среднем за (1/2 + 3/2)/2 = 1. Но в случае с умножением нужно брать среднее геометрическое (или перейти к логарифмам), тут уже будет результат sqrt(3)/2~0.86<1.
Парадокса нет, проблема в том что нужно доказать для каждого, а не в "среднем".
O(n^3)раз брать по модулю не нужно, промежуточные вычисления вполне помещаются в разумные типы, если модуль маленький. Даже если он большой (порядка10^9), можно брать Uint64 и делать каждые 16 итераций одно сравнение с вычитанием (завести константу16*Mod*Mod).Я смог сделать за 31 NAND гейт, кто меньше?
Не, все интереснее.
Для того что бы сервер не мог узнать запрос, ему нужно будет его "смешать" со всей базой данных, то есть индексы тут не помогут. Например если у Гугла поисковая база 100 терабайт, но нужно будет выполнить вычисления над запросом и всей базой.
Пример:
Клиент хочет узнать если ли слово (число) x в множестве А, которое известно серверу, но не хочет что бы сервер узнал x. Сам он множество А не знает.
Клиент отправляет $f(x)$ на сервер. Сервер считает $prod(f(x)-y | y in A) = prod(f(x-y) | y in A) = f(prod(x-y | y in A))$, здесь мы пользуемся гомоморфностью относительно сложения и умножения одновременно. Теперь это значение получает клиент, снимает шифрование и получает нулевое или не нулевое значение, по которому узнает ответ. (нулевое значение почти всегда означает что слово есть в множестве)
Если библиотека не даёт сделать $y -> f(y)$, то клиент может отправить ${b_i = f(2^i) | 0 <= i < N}$, тогда сервер может получить любую константу сложением $n < 2^N -> f(n) = f(sum(2^e | e in B)) = sum(f(2^e | e in B)) = sum(b_e | e in B)$, где B двоичное представление n.
Ну или наивный Байес, тут еще проще. Отправляем ${f(p_w) | w in U}$, bag of words,
Сервер возвращает линейную комбинацию $sum(a_w f(p_w) | w in U) =… = f(sum(a_w p_w | w in U))$. В итоге сервер не знает письма, а клиент не знает коэффициентов, все очень просто.
При желании можно и нейронку на таком входе посчитать, все упирается в функцию активации, для логистической можно экспоненту в ряд Тейлора разложить до какого-то члена, и должно нормально получиться, ну еще и делить придётся.
Естественно f должна меняться при каждом письме, иначе двух запросов с разными p_w и одинаковыми остальными значениями будет достаточно для того что бы узнать одно a_w.
Для того что бы работать с длинными словами, можно отправлять ${f(x_i) | 0 <= i < W}$, и перемножать $sum(f((x_i — y_i)^2) | 0 <= i < W)$, (вместо $(x-y)$) но тогда клиент раскрывает часть информации об $x$, но тем меньшую, чем больший размер слова доступен, и чего можно совсем избежать если преобразовать слова по принципу '{s_1,s_2,s_3} -> {(1,s_1),(2,s_2),(3,s_3)}'.
Вместо:
bool operator< (A const& rhs) const {
if (t < rhs.t) return true;
if (rhs.t < t) return false;
return u < rhs.u;
}
Использую:
bool operator< (A const& rhs) const {
if (t != rhs.t) return t < rhs.t;
return u < rhs.u;
}
Мой вариант может быстрее если t и rhs.t лексикографические строки разной длины, тогда если для сравнения их на меньше нужно пробежать до первого расхождения, а в сравнении на неравенство — вначале стоит проверка на длину.
Чисто теоретически компилятор может все понять и соптимизировать до эквивалентного кода — но на практике это не работает: код.
Спейсшип должен решить эту проблему.