Нахождение пикселей, которые делают изображение уникальным в рамках списка, можно ли изменить к лучшему грубую силу?
Предположим, что у меня есть список строк, где каждая строка
- точно 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] => {
image17,
image23,
...
}
sprawl[Tuple] => {
image11
...
}
и затем с помощью той карты для идентификации минимального набора пикселей подписи для каждого изображения.
Если пиксель (определенный x, y, цветом) ссылки всего одно изображение затем я нашел идеальную (минимальную) подпись для того изображения.
Это более сложно, если изображение не имеет никаких уникальных пикселей, но так как я знаю, что все изображения уникальны в рамках списка, я должен смочь объединить ссылки на два или больше пикселя (но как можно меньше) для выведения изображения.
Обновление
Я работал над алгоритмом для этого. Моя проблема очень похожа на этого, и я описал свой алгоритм как ответ на тот вопрос. Это обновление должно отметить внимание любого все еще после (я вижу пять закладок). Я работаю над этим в изоляции, таким образом, любому и всей обратной связи рады, даже если только заметить, что я не ясно выразился!
3 ответа
Вы можете сгенерировать двумерный массив, который будет содержать, сколько раз каждый символ появляется в каждой позиции (0–3). Например, arr [1,3] будет содержать, сколько раз цифра / символ 1 появляется в последней позиции.
Затем для каждой строки s пройдитесь по всем символам в строке. Те, которые появляются только один раз в этой позиции в соответствии с массивом, являются уникальными символами для этой строки. Другими словами, если arr [s [i], i] == 1 , то строка s уникальна в позиции i .
Это даст вам решение за линейное время, в то время как алгоритм, который вы указали, займёт квадратичное время.
Эту проблему можно решить с помощью дерева префиксов или дерева префиксов.
См. Trie - Википедия, бесплатная энциклопедия
Для трех строк в вашем примере:
abcd
abcc
bbcb
будет преобразовано в дерево trie (где ^ обозначает корень дерева):
^--a-b-c-d
\ \
\ c
\
b-b-c-b
путь к узлу, где он ответвляется, - это общий префикс. Узел после последней точки ветвления - это то, что делает конкретную строку уникальной. В данном случае это d, c, b.
Я предполагаю, что порядок строк для вас не важен, что вы сравниваете все строки, чтобы найти уникальность, а не только соседнюю строку.
Сложность должна быть O (n x m). Но это, вероятно, будет зависеть от домена символов в вашей строке.
Если ваша цель - идентифицировать изображения позже, вы можете создать очень быстрый хэш изображения, выбрав предопределенные точки для идентификации пикселей.
например, у вас может быть структура (класс, структура, не имеет значения, на каком языке) следующим образом:
structure ImageHash {
int x_pixels, y_pixels;
u_long hash;
void createHash(Image img) {
x_pixels = img.x_pixels;
y_pixels = img.y_pixels;
for(int i = 1; i < 5; i++) {
int x = x_pixels / i;
for(int j = 1; j < 5; j++) {
int y = y_pixels / j;
int r = img.getPixelRed(x,y);
int g = img.getPixelGreen(x,y);
int b = img.getPixelBlue(x,y);
hash = (hash * 31) ^ (r^g^b);
}
}
}
}
Этот вид «неполного хеша» позволит вам идентифицировать возможные личности, а затем вы сможете сделать дорогостоящие , полное сравнение по мере необходимости.
При необходимости разверните неполный хэш.