Взаимоисключающие смежные диапазоны из нескольких битовых полей

(Это не домашнее задание класса CS, даже если оно похоже на одно)

Я использую битовые поля для представления диапазонов от 0 до 22. В качестве входных данных, например, у меня есть несколько разных диапазонов (порядок не имеет значения). Я использовал . для 0 и X для 1 для лучшей читаемости.

.....XXXXX..............
..XXXX..................
.....XXXXXXXXXXXXXXX....
........XXXXXXX.........
XXXXXXXXXXXXXXXXXXXXXXXX

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

XX......................
..XXX...................
.....X..................
......XX................
........XX..............
..........XXXXX.........
...............XXXXX....
....................XXXX

(опять же, порядок вывода не имеет значения, они просто должны быть взаимоисключающими и смежными, т.е. в них не может быть дыр. .....XXX.......XXXXX.... необходимо разделить на два отдельных диапазона).

Я попробовал несколько алгоритмов, но все они оказались довольно сложными и неизящными. Что очень помогло бы мне, так это способ обнаружить, что .....XXX.......XXXXX.... имеет дыру, и способ определить индекс одного из битов в дыре.

Изменить: диапазон битового поля представляет уровни масштабирования на карте. Они предназначены для использования для вывода таблиц стилей XML для Mapnik (системы рендеринга листов, которая, среди прочего, используется OpenStreetMap).


c++ range bit-fields
person kkaefer    schedule 02.02.2011    source источник
comment
Не могли бы вы подробнее рассказать о том, как вы пытаетесь разделить биты на диапазоны? Я хотел бы помочь, но я не совсем понимаю, как вы пришли к диапазонам в своем примере.   -  person templatetypedef    schedule 02.02.2011
comment
Я проголосую за вопрос, потому что вы пробудили у меня любопытство. Вы готовы поделиться, для чего это нужно?   -  person xelco52    schedule 02.02.2011
comment
Я пришел к желаемому решению примерно так: возьмите вертикальный столбец и сравните его со следующим, если он одинаковый во всех строках, он все еще находится в пределах диапазона предыдущих столбцов. Если хотя бы один элемент отличается, начинается новый диапазон. Проблема в том, что на входе потенциально может быть около 100 строк.   -  person kkaefer    schedule 02.02.2011
comment
Согласитесь с xelco52, проблема мне кажется интересной, но полностью разобраться не удалось. Я вижу первый блок с 5 битовыми полями (в 5-м - все единицы) шириной 22 каждое. Каким образом «взаимоисключающее преобразование смежных диапазонов» попадает во второй блок из 8 битовых полей шириной 22 каждое?   -  person Arun    schedule 02.02.2011

Ответы (2)


arrow_upward
0
arrow_downward

Я предполагаю, что решение, которое вы упоминаете в комментарии, выглядит примерно так:

Начните слева или справа (так индекс = 0) и просканируйте, какие биты установлены (до 100 операций). Назовите этот набор x. Также установите переменную block = 0.

При index = 1 повторите и сохраните, чтобы установить y. Если x XOR y = 0, оба являются идентичными наборами, поэтому перейдите к index = 2. Если это x XOR y = z! = 0, тогда диапазон [блок, индекс) является непрерывным. Теперь установите x = y, block = index и продолжайте.

Если у вас есть 100 битовых массивов длиной 22 каждый, это займет порядка 2200 операций.

Это оптимальное решение, потому что операция не может быть сокращена дальше - на каждом этапе ваш диапазон нарушается, если другой набор не соответствует вашему набору, поэтому, чтобы проверить, не нарушен ли диапазон, вы должны проверить все 100 бит.

person Vanwaril    schedule 04.02.2011

arrow_upward
0
arrow_downward

Я постараюсь хотя бы разобраться с твоей подзадачей ..

Что очень помогло бы мне, так это способ обнаружить, что .....XXX.......XXXXX.... имеет дыру, и способ определить индекс одного из битов в дыре.

Нахождение младшего и самого высокого набора («1») битов в битовой маске - довольно решенная проблема; См., Например, ffs(3) в glibc или см., Например, http://en.wikipedia.org/wiki/Bit_array#Find_first_one

Учитывая первый и последний индексы растрового изображения, назовите их i и j, вы можете вычислить растровое изображение, в котором все биты между i и j установлены, используя M = ((1 << i) - 1) & (~((1 << j) - 1)) (извинения за любые единичные ошибки).

Затем вы можете проверить, есть ли в исходном растровом изображении дыра, сравнив его с M. Если он не совпадает, вы можете использовать ввод xor M, чтобы найти дыры и повторить.

person nelhage    schedule 02.02.2011