找到使图像在列表中唯一的像素,你可以改善蛮力吗？

Question

假设我有一个字符串列表,其中每个字符串都是

• 正好4个字符长
• 在列表中是唯一的.

对于这些字符串中的每一个,我想识别字符串中字符的位置,使字符串唯一.

所以对于三个字符串的列表

abcd
abcc
bbcb

对于第一个字符串,我想识别第四个位置d中的字符,因为d没有出现在任何其他字符串的第4个位置.

对于第二个字符串,我想识别第四个位置c中的字符.

对于第三个字符串,我想识别第一个位置b中的字符和第四个位置的字符,也是b.

这可以简洁地表示为

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

如果您考虑相同的问题,但使用二进制数列表

0101
0011
1111

那么我想要的结果就是

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

保持二进制主题我可以使用XOR来识别哪个位在两个二进制数内是唯一的

0101 ^ 0011 = 0110

我可以解释为这意味着在这种情况下,第二和第三位(从左到右读取)在这两个二进制数之间是唯一的.这种技术可能是红鲱鱼,除非它以某种方式可以扩展到更大的列表.

蛮力方法是依次查看每个字符串,并为每个字符串迭代列表中其余字符串的垂直切片.

所以列表

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,颜色标识)仅引用一个图像,那么我找到了该图像的完美(最小)签名.

如果图像没有唯一像素,则会更复杂,但由于我知道所有图像在列表中都是唯一的,因此我应该能够组合两个或更多像素参考(但尽可能少)来推断图像.

更新

我一直在研究一种算法.我的问题与这个问题非常相似,我已经将我的算法写成了问题的答案.此更新旨在标记仍在关注的任何人的注意力(我看到五个书签).我正在孤立地研究这个问题,所以任何反馈都是受欢迎的,即使只是为了观察我没有说清楚!

Answer 1

您可以生成一个二维数组,其中包含每个字符在每个位置出现的次数(0-3).例如,arr[1,3]将包含数字/字符1在最后位置出现的次数.

然后对于每个字符串s,遍历字符串中的所有字符.根据数组在该位置只出现一次的那些是该字符串的唯一字符.换句话说,如果arr[s[i], i]==1那么字符串s在位置上是唯一的i.

这将为您提供线性时间的解决方案,而您提供的算法将采用二次时间.