Предположим, у меня есть список строк, где каждая строка

ровно 4 символа иуникальный в списке.

Для каждой из этих строк я хочу определить положение символов в строке, которые делают строку уникальной.

Итак, для списка из трех строк

abcd
abcc
bbcb

Для первой строки я хочу идентифицировать символ в 4-й позицииd посколькуd не появляется в 4-й позиции в любой другой строке.

Для второй строки я хочу идентифицировать символ в 4-й позицииc.

Для третьей строки я хочу идентифицировать символ в 1-й позицииb И персонаж в 4-й позиции, такжеb.

Это может быть сжато представлено как

abcd -> ...d
abcc -> ...c
bbcb -> b..b

Если вы рассматриваете ту же проблему, но со списком двоичных чисел

0101
0011
1111

Тогда желаемый результат будет

0101 -> ..0.
0011 -> .0..
1111 -> 1...

Оставаясь с бинарной темой, я могу использовать XOR, чтобы определить, какие биты являются уникальными вдва двоичные числа с

0101 ^ 0011 = 0110

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

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

Так что для списка

abcd
abcc
bbcb

Я бы начал с

abcd

и перебирать вертикальные ломтики

abcc
bbcb

где эти вертикальные срезы будут

a | b | c | c
b | b | c | b

или в форме списка, "ab", "bb", "cc", "cb".

Это привело бы к четырем сравнениям

a : ab -> . (a is not unique)
b : bb -> . (b is not unique)
c : cc -> . (c is not unique)
d : cb -> d (d is unique)

или кратко

abcd -> ...d

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

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

Можете ли вы улучшить грубую силу?

редактировать Подход, который я использую, заключается в построении карты пикселей для изображений.

sprawl[Tuple<x=10, y=33,color=f1fefd>] => {
     image17,
     image23,
     ...
}

sprawl[Tuple<x=10, y=34,color=f1fef0>] => {
     image11
     ...
}

а затем с помощью этой карты идентифицировать минимальный набор пикселей подписи для каждого изображения.

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

Сложнее, если у изображения нет уникальных пикселей, но, поскольку я знаю, что все изображения в списке уникальны, я смогу объединить две или более ссылок на пиксели (но как можно меньше), чтобы вывести изображение.

Обновить

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