Алгоритм миниатюры YAML, включающий эталонную вставку

smartcaveman спросил: 12 мая 2018 в 04:27 в: algorithm

Существует ли существующий инструмент, библиотека или алгоритм, который реализует миниатюру YAML с эталонной вставкой? Я не хочу изобретать колесо, если уже существует общее решение этой проблемы.

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

  • Основной алгоритм минимизации YAML без ссылочной вставки , MinifyYamlBasic, было бы изоморфно минимизации JSON, но заменило бы любой примитив JSON наименьшим многословным эквивалентным синтаксисом узла YAML. Я нашел онлайн-пример реализации MinifyYamlBasic на https://onlineyamltools.com/minify-yaml.

  • Алгоритм минимизации YAML со ссылкой insert , MinifyYamlWithReferences сделает все, что делает MinifyYamlBasic, но затем создаст привязки для любых узлов YAML, которые происходят несколько раз, и заменит дублированные узлы YAML ссылками на сгенерированный якорь , в порядке убывания длины текста узла YAML.

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

Там, вероятно, больше, что я еще не рассматривал. Прежде чем уделить время времени, чтобы рассмотреть его,

  1. Существуют ли доступные ресурсы, которые предоставляют существующую реализацию MinifyYamlWithReferences (или что-то похожее) ?

  2. Существует ли обычно используемое имя для алгоритма (или категории алгоритмов), которое я назвал "minification with reference insertion"?


1 ответ

flyx ответил: 13 мая 2018 в 09:39

Что вы хотите сделать, это преобразование . Полученный YAML такой операции семантически не будет эквивалентен исходному YAML. Возьмем, к примеру, этот маленький YAML:

[foo, foo]

Этот YAML представляет следующий граф документа:

    +----------------------+
    | Sequence (root node) |
    +--|----------------|--+
       |                |
    +--v--+          +--v--+
    | foo |          | foo |
    +-----+          +-----+

Используя ваш MinifyYamlWithReferences, это будет выглядеть примерно так:

[&a foo, *a]

Что представляет следующий граф документа:

    +----------------------+
    | Sequence (root node) |
    +--|----------------|--+
       |                |
    +--v--+             |
    | foo |<------------+
    +-----+

Итак, вы создали семантически отличный документ YAML! Вызов этой minification будет вводить в заблуждение, поскольку минимизация обычно рассматривается как процесс преобразования источника в меньший, но семантически эквивалентный источник. То, что вам нужно, - это дедупликация (наряду с минимизацией), которая является семантическим преобразованием.

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

  1. Какой из !!str a, "a", 'a' и a эквивалентны?
  2. Являются ли эти два эквивалента: &a [ *a ], [*a]?

(Объяснение: В 1. у нас есть два каскадных скаляра, которые оцениваются скалярным узлом с тегом !. ! для скаляров получает разрешение !!str, используя Ядерная схема YAML. a - это скаляр, который не соответствует регулярному выражению для чего-то более конкретного, чем строка, поэтому он также получит !!str в соответствии с основной схемой. используется базовая схема? В 2. мы имеем последовательность с прямым циклом и последовательность, которая просто связывается с этим циклом, но (теоретическое) сравнение бесконечной рекурсией говорит о том, что они равны. )

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