with Cat The Cat

Читая про некое средство резервнное копирование данных...

...подумал интересную мысль.

(собственно, ссылка на средство, оно довольно любопытно)

Я вспомнил про мой недавний краткий пост про арифметическое кодирование с сохранением порядка.

Модель для кодирования является ключом. Само кодирование данных является симметричным шифрованием с ключом-моделью.

На этом всё. ;)
with Cat The Cat

zdd

Вот эти вот.

ZDD в своём построении требуют условия уникальности: если мы создаём узел с переменной i и двумя подузлами (ссылками) A и B, то ссылка на такой узел должна быть одной и той же всегда .

Обычно это выполняется с помощью хэш-таблиц для запоминания уже созданных узлов. И это ключ к использованию хэша от содержимого узла в качестве ссылки на него.

Вместо вычисления "ссылки по содержимому" мы просто создаём узел с его хэшем и добавляем его в таблицы (хэш->узел, ссылающиеся на узел хэши и тп). Последнее можно делать по завершению основной работы.

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

Если я всё правильно понимаю, это позволяет сделать довольно экономный вариант работы с ZDD на GPU.
with Cat The Cat

Про конфликты, продолжение.

Я был неправ в указании источника NP-полноты проблемы получения наименьшего конфликта.

Моё текущее понимание таково: если мы удаляем литерал l из некоторого набора путей {P}l{S}, то нам надо добавить пути {P}⨯{S} - все пути до литерала l должны вести во все пути после. Собственно, это всё то же правило разрешения, только вылезшее в другом месте.
with Cat The Cat

Продолжение про поиск наименьшего ограничения.

Начало про общую идею, необходимые структуры данных и тп.

Надо рассмотреть взаимодействие между возможностями уменьшения ограничений.

Это довольно просто.

Уменьшение ограничений выполняется через разрешение (resolution). Если у нас есть ограничение a∨b∨c и ограничение a∨!c, то мы можем разрешить эти два ограничения по переменной c и получить вместо первого ограничения в три переменных новое, в две переменных a∨b.

Разрешения могут мешать друг другу. Допустим, мы пытаемся уменьшить ограничение a∨b∨c∨d∨e∨f и у нас есть два кандидата на разрешение: a∨!b и b∨!c. Если мы применим первый, то второй применить не получится. Наоборот, в этом примере, можно, но так же можно придумать случай, когда только одно разрешение возможно.

Получается, что нам надо решить задачу перебора: какие ограничения-кандидаты мы можем применить для уменьшения нашего нового ограничения?

Упрощение этой задачи состоит в том, что ограничения-кандидаты можно разделить на пересекающиеся и не пересекающиеся. Если у нас только не пересекающиеся, то перебора нет - накатывай и радуйся. Если есть пересечение, то мы, о радость, можем формировать большее ограничение-кандидат, выполняя разрешение поверх кандидатов! После чего использовать упрощения, начиная с самого большого.

Вот эта вот радость выше, она всё ещё NP-полна, фактически, это алгоритм Davis-Putnam (от него отказались слишком рано, некоторые могут подумать): мы выбираем переменную и разрешаем по ней все ограничения, устраняя её из задачи. У нас, правда, большинство ограничений пересекаться не будет и те, что будут, будут принадлежать много более узкому подмножеству всех ограничений задачи.

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

Вспоминая SaDiCal с его "решением много более простой задачи в случае останова вывода значений переменных", мы получаем много более простую задачу и здесь.
with Cat The Cat

Полуночное размышление.

Я тут в твиттере распространялся про поиск наикратчайшего ограничения при поиске решения в алгоритме выведения ограничений из конфликтов (решение задачи логической разрешимости).

Важно найти наикратчайшее ограничение. "Сила" ограничения пропорциональна 2-длина ограничения.

При поиске ограничений мы 1) имеем дело с множеством "нарезаний" фронтов вывода и 2) нам надо применять алгоритмы разрешения (resolution) для уменьшения ограничений.

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

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

Ответив на первую неприятность, мы также может разобраться и со второй. Структуры данных типа BDD/ZDD могут успешно применяться для выполнения разрешения (resolution) по переменной (статья содержит неточности, есть доклад на эту тему, там правильные формулы, но я уже устал). Причём там вообще волшебно получается - добавляя ограничение к набору ограничений, мы одновременно получаем упрощение, если это возможно.

То есть, идея следующая: для всех фронтов строим ZDD со всеми возможными выводимыми ограничениями; к этой ZDD добавляем ограничения из нашей основной задачи, следя, чтобы это добавление упрощало; после чего считываем самый короткий путь по ZDD, можно не один.
with Cat The Cat

В спортзале в Чехове стали требовать QR коды

Прикинул, во что обойдётся сделать спортзал со штангой самому.

Гриф и блины весом в 300 кг вышли в 130 тысяч рублей. Силовая рама 70-80 тысяч.

Провериться на антитела - 1700, одна тысяча семьсот рублей.

Надо всё хорошенько обдумать. ;)
with Cat The Cat

Порядок

Сперва о порядке байтов в представлении слов.

У нас есть два порядка байтов в слове: LSB, младший (наименее значимый) байт вперёд и MSB, старший (наиболее значимый) байт вперёд. В первой случае проще преобразовывать между значениями разных размеров, второй случай проще сравнивать побайтово (memcmp).

Можно считать, что для MSB порядка байтов "вес" i-го (от адреса значения, i=1..size, 1 это байт по адресу значения) байта равен 256(size-i).

Теперь о порядке строк.

Строки мы сравниваем побайтово, как "целые в кодировке старший байт вперёд". Однако от целых строки отличны наличием длины, строка может содержать и ноль байтов и теребайт. В библиотеке crit bit trees предлагают считать все строки представленными бесконечной последовательностью байтов с дополнением нулями справа.

Размер у нас бесконечный, поэтому вес i-го байта строки мы определим, как 256-i. То есть, строки можно представлять в виде бесконечных дробей.

Арифметическое кодирование так же представляет последовательности символов в виде бесконечных дробей.

Про порядок арифметически закодированных строк.

Сперва предложу рассмотреть кодирование битов. Если мы используем одну и ту же, сколь угодно динамическую модель, то конкретный i-й бит 0 всегда будут закодирован в диапазоне [0..pi), а 1 всегда будет закодирован в диапазоне [pi..1). То есть, последовательность битов, начинающаяся с 0, будет иметь закодированное представление меньшее (в смысле сравнения получившихся строк - получившаяся дробь будет меньше), чем последовательность битов, начинающихся с 1.

В случае кодирования битов мы кодируем полный алфавит.

И если мы кодируем полный алфавит, как это принято в побуквенных языковых моделях (charRNN, TDCN, побуквенная SNMLM и тп), мы сохраняем свойство выше.

Типичный PPM* подход кодирует не полный алфавит, а алфавит текущего контекста и символ неудачи. Поэтому к нему вывод выше не применим. Но если заставить PPM разворачивать вероятности всех символов в полный контекст, то мы можем сравнивать кодированные (сжатые) представления с сохранением порядка несжатых.

Итак, основной вывод: при арифметическом кодировании с использованием полного алфавита мы получаем сохранение порядка несжатых строк при сравнении сжатых представлений.

(no subject)

Fox News. Такер Карлсон: чиновники в Вашингтоне хотели, чтобы США остались в Афганистане. Чтобы этого добиться, они наврали.

В течение целых пяти лет, начиная со своей предвыборной кампании 2016-го года и до конца своего президентского срока, Дональд Трамп часто повторял, что его желание — увидеть выход войск США из Афганистана. И вот в конце правления, в свои последние месяцы в Белом Доме, Трамп, кажется, решился выполнить это обещание. Он сказал помощникам, что собирается вывести войска.

И вот, в солнечный день 26 июня прошлого года, «Нью-Йорк таймс» (NYT) не дала ему это сделать. NYT опубликовала статью о том, что американское разведывательное сообщество «пришло к заключению: российская военная разведка тайно предлагала «награду за головы» убитых солдат проамериканской коалиции в Афганистане, да еще кому — связанным с Талибаном (террористическая организация, запрещена в России) боевикам, воюющим с США в Афганистане.

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

Collapse )
https://inosmi.ru/politic/20210424/249627103.html
https://www.foxnews.com/opinion/tucker-carlson-afghanistan-russia-bounties-new-york-times-lies
---
---
---

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