查找使图像在列表中独特的像素，您能改善蛮力吗？

Question

假设我有每个字符串的字符串列表

• 正好4个字符长，
• 列表中的唯一。

对于这些字符串，我想确定字符串中字符串独特的字符的位置。

因此，对于三个字符串的列表

abcd
abcc
bbcb

对于第一个字符串，我想识别第四位的字符 d 自从 d 在任何其他字符串中均未出现在第四位。

对于第二个字符串，我想识别第四位的字符 C.

对于第三个字符串，我想确定第一个位置的字符 b 和第四位置的角色 b.

这可以简洁地表示为

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

如果您考虑相同的问题，但是有二进制数字列表

0101
0011
1111

那我想要的结果就是

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

我可以使用二进制主题来识别哪些位在其中独特 二 从那以后的二进制数字

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.

这将为您提供线性时间的解决方案，而您给出的算法将需要二次时间。

Answer 2

如果您的目标是稍后识别图像，则可以通过选择预定义的点作为身份像素来创建图像的快速哈希。

例如，您可以拥有一个结构（类，结构，无关紧要的语言）如下：

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);
            }
        }
    }
}

这种“不完整的哈希”将使您确定可能的身份，然后您可以根据需要进行昂贵的，全面的比较。

根据需要扩展不完整的哈希。

Answer 3

Trie或前缀树可以解决此问题。

看 特里 - 维基百科，免费百科全书

对于您的示例中的3个字符串：

abcd
abcc
bbcb

将变成三角树（其中 ^表示树的根）：

^--a-b-c-d
 \      \
  \      c
   \
    b-b-c-b

通往其分支的节点的路径是常见的前缀。最后一个分支点之后的节点是使特定字符串唯一的原因。在这种情况下，它们是d，c，b。

我认为字符串的顺序对您来说并不重要，您可以比较所有字符串以找到独特性，而不仅仅是相邻的字符串。

复杂性应为O（NXM）。但这可能会受到字符串中字符域的影响。