Алгоритм минимизации YAML, который включает вставку ссылки - PullRequest
Новая
       35

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

0 голосов
/ 05 июня 2018

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

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

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

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

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

Возможно, я еще не рассмотрел еще кое-что.Прежде чем уделить время дальнейшему рассмотрению,

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

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

1 Ответ

0 голосов
/ 06 июня 2018

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

[foo, foo]

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

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

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

[&a foo, *a]

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

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

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

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

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

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

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

...