我有一个 2D MxN 网格（或矩阵）。矩阵中的单元格可以保存一个整数。具有非零整数的单元格被称为已填充。矩阵中的一组填充单元称为“配置”。
我想提出一种编码或散列算法，它允许我通过计算其编码值（应该生成一个唯一的数字）来唯一地识别矩阵中的配置。
我更喜欢编码而不是散列，因为完全不希望发生冲突。
任何人都可以建议一种编码算法，我可以使用它来计算给定配置的唯一“id”吗？
问问题
565 次
6 回答
1
我建议使用哈希算法，它有 99.999999999% 的机会生成唯一 ID。在大多数情况下，每十亿个哈希发生一次冲突是可以接受的。我的建议是使用CRC算法，因为它生成高度分布的散列集并且具有相对较低的冲突率。
于 2009-10-07T12:22:06.037 回答
0
所以它是一个 1 和 0 的数组？该阵列的 RLE 或 LZW 压缩怎么样？
于 2009-10-07T12:04:45.220 回答
0
对于提供精确比较的表示，不可能比对表示配置的位序列的最佳压缩做得更好。
如果您需要将 MxN 布尔值唯一编码为整数，则需要 2 M*N个值。使用平台的固定精度整数是否可行取决于 M 和 N 的大小；如果不是，您将不得不使用位字符串或大整数。
因为原始数据是任何整数值而不仅仅是 1 或 0，所以朴素矩阵的朴素位串 ID 将给出8 * sizeof ( matrix::cell_type ). 针对稀疏值优化的位串可能会更好。稀疏位串的良好实现会压缩数据，因此这将减少表示的存储空间，并允许快速精确比较，这是要求。
如果保证模式稀疏到一定程度，则可以进行优化以压缩信息，但您需要提供更多信息。
例如，您是否使用稀疏矩阵表示（带状、对角线、行压缩等），并且可以访问稀疏矩阵存储的内部，然后自然而有效地映射到压缩位串。
查看您的另一篇文章，该矩阵似乎被用作游戏的网格而不是矩阵。在这种情况下，最好对位串使用游程长度压缩，因为这会产生另一个有用的属性 - 其配置是相互转换的矩阵的编码位串表示只会在编码的第一个值中有所不同。
于 2009-10-07T12:12:32.983 回答
0
目前尚不清楚您想要实现什么，但也许自定义 布隆过滤器实现可能适合您的问题。
于 2009-10-07T12:16:15.190 回答
0
根据您要解决的问题，您会想到以下内容：
- 使用查找表关联矩阵宽度 ID
- 仅存储填充字段的值；它们在矩阵中的位置可以编码为单独的每个字段值或使用整个矩阵的位图
于 2009-10-07T12:17:47.480 回答
0
是否存在碰撞无关紧要。即使发生碰撞，您也可以继续通过 int 检查矩阵 int 以查看它是否实际上相似。
只要碰撞很少发生，开销就是 0
所以散列函数可以像将所有 int 加在一起一样简单。如果这足够了，则取决于整数的可能值以及它们中有多少（因此，如果在整个矩阵中只有 1 或 2 个单元格具有值，则此散列将不起作用）
于 2009-10-07T12:24:01.163 回答