При разработке алгоритмов уточнение разбиения — это метод представления разбиения множества в виде структуры данных, которая позволяет разбивать его множества на большее количество меньших множеств. В этом смысле уточнение разбиения двойственно системе непересекающихся множеств, которая также поддерживает разбиение на непересекающиеся множества, но в которой операции объединяют пары наборов. В некоторых приложениях уточнения разбиения, таких как лексикографический поиск в ширину, структура данных поддерживает также порядок наборов в разделе.
Уточнение разбиения является ключевым компонентом нескольких эффективных алгоритмов на графах и конечных автоматах, включая минимизацию ДКА, алгоритм Коффмана – Грэма для параллельного планирования и лексикографический поиск в ширину.[1][2][3]
Алгоритм уточнения разбиения поддерживает семейство непересекающихся множеств Si . В начале алгоритма это семейство содержит единственное множество всех элементов в структуре данных. На каждом шаге алгоритм получает множество X, и каждое множество Si в семействе, содержащем элементы X, разбивается на два множества: пересечение Si ∩ X и разность Si \ X
Этот алгоритм может быть эффективно реализован с помощью структур данных, представляющих следующую информацию:[4][5]
Чтобы выполнить операцию уточнения, алгоритм перебирает элементы данного множества X. Для каждого такого элемента x он находит множество Si которое содержит x, и проверяет, произведено ли пересечение Si ∩ X. Если нет, он создает второе множество и добавляет Si в список L множеств, разделенных операцией. Затем, независимо от того, было ли сформировано новое множество, алгоритм удаляет x из Si и добавляет его к Si ∩ X В представлении, в котором все элементы хранятся в одном массиве, перемещение x из одного множества в другое может выполняться путем обмена x местами c последним элементом Si а затем уменьшения концевого индекса Si и начального индекса нового множества. Наконец, после того, как все элементы X были обработаны таким образом, алгоритм проходит через L, разделяя каждое текущее множество Si на два, рассматривая оба этих множества как сформированные в результате операции уточнения.
Оценка времени для выполнения одной операции уточнения таким образом составляет O(|X|), независимо от количества элементов в семействе множеств, а также независимо от общего количества множеств в структуре данных. Поэтому время исполнения последовательности уточнений пропорционально общему размеру множеств, заданных алгоритму на каждом этапе уточнения.