6

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

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

对于这些字符串中的每一个，我想确定字符串中使字符串唯一的字符的位置。

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

abcd
abcc
bbcb

对于第一个字符串，我想识别第 4 个位置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

我可以解释为，在这种情况下，第 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、颜色标识）仅引用一个图像，那么我已经为该图像找到了一个完美的（最小）签名。

如果图像没有唯一像素会更复杂，但由于我知道列表中的所有图像都是唯一的，我应该能够结合两个或多个像素引用（但尽可能少）来推断图像。

更新

我一直在为此研究一种算法。我的问题与这个问题非常相似，并且我已经编写了我的算法作为该问题的答案。此更新是为了提醒仍在关注的任何人（我看到五个书签）。我正在孤立地处理这个问题，所以欢迎任何和所有的反馈，即使只是为了观察我还没有说清楚！

4

3 回答 3

9

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

然后对于每个字符串s，遍历字符串中的所有字符。根据数组在该位置仅出现一次的字符是该字符串的唯一字符。换句话说，如果arr[s[i], i]==1Then 字符串s在 position 中是唯一的i。

这将为您提供线性时间的解决方案，而您提供的算法将花费二次时间。

于 2010-05-18T17:57:42.830 回答
1

如果您的目标是稍后识别图像，您可以通过选择预定义的点作为标识像素来创建非常快速的图像散列。

例如，你可以有一个结构（类，结构，不管是什么语言），如下所示：

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

这种“不完整的哈希”将允许您识别可能的身份，然后您可以根据需要谨慎地进行昂贵的完整比较。

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

于 2010-05-18T18:03:30.910 回答
0

这个问题可以通过 trie 或前缀树来解决。

参见Trie - 维基百科，免费的百科全书

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

abcd
abcc
bbcb

将变成一棵特里树（其中 ^ 表示树的根）：

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

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

我假设字符串的顺序对您来说并不重要，您会比较所有字符串以找到唯一性，而不仅仅是相邻的字符串。

复杂度应该是 O(nxm)。但这可能会受到字符串中字符域的影响。

于 2010-05-18T19:37:32.993 回答