我正在阅读可以按任何顺序排列的文本行。问题是输出实际上可能与之前的输出相同。我怎样才能检测到这一点，而不先对输出进行排序？
是否有某种散列函数可以采用相同的输入，但以任何顺序，仍然产生相同的结果？
问问题
548 次
7 回答
3
最简单的方法似乎是在输入的过程中对每一行进行散列，存储散列和原始数据，然后将每个新散列与现有散列集合进行比较。如果您得到肯定，您可以比较实际数据，以确保它不是误报 - 尽管这种情况极为罕见，但您可以使用更快的哈希算法，如 MD5 或 CRC（而不是 SHA 之类的算法，速度较慢但碰撞的可能性较小），所以它很快，然后在您受到打击时比较实际数据。
于 2008-09-15T16:30:08.260 回答
0
所以你有输入
A B C D
D E F G
C B A D
并且您需要检测第一行和第三行是否相同？
于 2008-09-15T16:03:19.527 回答
0
如果您想查明两个文件是否包含相同的一组行，但顺序不同，您可以分别在每行上使用常规哈希函数，然后将它们与排序无关紧要的函数组合，例如加法。
于 2008-09-15T16:06:14.200 回答
0
如果行相当长，您可以只保留每行的哈希列表 - 对它们进行排序并与之前的输出进行比较。
如果您不需要 100% 万无一失的解决方案，您可以将每行的哈希存储在 Bloom 过滤器中（在 Wikipedia 上查找）并在处理结束时比较 Bloom 过滤器。这可能会给您带来误报（即您认为您有相同的输出，但实际上并不相同）但是您可以通过调整 Bloom 过滤器的大小来调整错误率......
于 2008-09-15T16:06:35.090 回答
0
如果将每个字符的 ASCII 值相加，无论顺序如何，都会得到相同的结果。
（这可能有点过于简单，但它可能会激发您的灵感。有关有趣的背景故事，请参阅编程珍珠，第 2.8 节。）
于 2008-09-15T16:09:27.033 回答
0
任何基于散列的方法都可能产生不好的结果，因为多个字符串可以产生相同的散列。（这不太可能，但有可能。）添加散列的建议尤其如此，因为您基本上会采用特别糟糕的散列值散列。
仅当您错过更改或发现不存在的更改并不重要时，才应尝试使用哈希方法。
最准确的方法是使用行字符串作为键来保留 Map，并将每个字符串的计数存储为值。（如果每个字符串只能出现一次，则不需要计数。）计算预期的行集。复制此集合以检查传入行，减少您看到的每行的计数。
- 如果您遇到计数为零的行（或根本没有地图条目），那么您会看到一条您没有预料到的行。
- 如果您以 Map 中剩余的非零条目结束此操作，则您没有看到预期的内容。
于 2008-09-15T19:52:18.120 回答
0
那么问题规范有点有限。
据我了解，您希望查看多个字符串是否包含相同的元素，而不管顺序如何。
例如：
A B C
C B A
是相同的。
这样做的方法是创建一组值，然后比较这些组。要创建一个集合，请执行以下操作：
HashSet set = new HashSet();
foreach (item : string) {
set.add(item);
}
然后只需通过运行其中一个集合并将其与其他集合进行比较来比较集合的内容。执行时间将O(N)代替O(NlogN)排序示例。
于 2008-09-15T22:18:20.343 回答