问题标签 [bijection]

我有一个 288 位的输入（包括 4 × 32 位恒等函数输出和 10 × 16 位整数）。我需要将其散列到 96 位，并尽可能减少冲突。目标可以被描述为具有概率碰撞的密钥压缩。

我知道 CRC 是一个双射散列，因此可以确保 100% 的均匀分布（据我所知）。在我看来，我应该能够通过输入运行 3 个并行 CRC 路径，从而产生 96 位有损散列（显然不是双射的）的最佳分布。

但是，我也知道 CRC 不用于此类应用程序。通常会使用诸如 MetroHash 之类的算法。

有人可以向我解释为什么 CRC 对这个应用程序来说是一个坏（或不是）的主意吗？

注意：这不适用于任何安全的事情。

创建一个具有相同域和范围的随机双射函数。随机双射函数是指使用随机算法（或至少是伪随机算法）将元素从域映射到范围的函数，而不是像 x=y 这样的函数。域和范围有时可能是一个非常小的集合，例如 {1,2,3,4,5}，因此配对函数不起作用。而且，计算资源是有限的，所以它应该是一个计算上可行的函数。

编辑：我在问题中的意思是，假设您有一个包含 5 个数字 A = {1,2,3,4,5} 的列表。现在你要做的是创建一个随机函数 f ，当应用于上述集合时，它会给出一个包含相同上述数字的集合，但以不同的顺序具有足够高的概率。就像我做了 f(A) = B，那么 B 可能是 {2,4,1,5,3}。所以 A 到 B 的映射是 1->2、2->4、4->1、4->5 和 5->3。但是，如果我再次执行 f(A)，那么这次的映射应该是另一个这样的随机映射，即如果 f(A) = C，那么 C 可以是 A 的任何一种可能的排列，概率均等。这可以通过计算第 n 个排列轻松实现。但我怀疑的是，如果我想在给定的特定时间间隔内找出集合A中的一个数字的映射，那么它是否可以在恒定的时间和空间中完成。

情况

我目前正在使用 AVRO 和模式存储库编写消费者/生产者。

根据我收集的信息，我序列化这些数据的选项是使用 Confluent 的 avro 序列化程序，或者使用 Twitter 的 Bijection。

双射似乎是最直接的。

所以我想以以下格式生成日期ProducerRecord[String,Array[Byte]]，这归结为 [some string ID, serialized GenericRecord]

（注意：我要使用通用记录，因为此代码库必须处理从 Json/csv/... 解析的数千个模式）

问题：

我序列化和使用 AVRO 的全部原因是你不需要在数据本身中有一个模式（就像你对 Json/XML/... 一样）。
然而，当检查主题中的数据时，我看到整个方案与数据一起包含。我做错了什么，这是设计使然，还是应该使用融合序列化程序？

代码：

虽然我知道如何生成所有 ( nchoose k) 大小n的位串，位串完全k设置为 1，但我正在努力寻找一个双射，它以和 ( choose )i之间的数字作为输入，并在一个任意排序。1nki

显然，可以简单地枚举列表中的所有向量，然后输出列表的i第 - 个条目，但不幸的是，这种方法对我的设置有很高的内存要求。

编辑：它也应该是一种有效的计算，计算每次调用双射的所有向量列表也不是一种选择。

尽管这个问题在 StackOverflow 上已经有部分答案，但这些答案与标题或标签中具有过程/概念正确名称（双射 (base-k) numeration ）的问题无关。我预计许多答案本质上将是与那些现有答案的链接。

如何在 PHP 中从 A 到 Z 列出，然后到 AA、AB、AC 等，部分回答了这个问题

双射 base-26 计数可用于计算许多电子表格程序中使用的方案中的列 ID，例如 LibreOffice Calc、Lotus-123、VisiCalc（我认为）、ProCalc 3D等。

以下是一种解决方案的 R伪代码（我还没有包含依赖项的“原始”R 代码）。返回是一个整数向量（little endian），其元素在概念上映射到用于表示双射计数的任意符号：

我需要的

我需要一种产生双射输出的算法。我有一个 31 位输入，需要一个伪随机 31 位输出。

我所考虑的

CRC 在其位宽内是双射的。

我在谷歌上看过，可以找到多项式，但找不到表格或算法。

谁能指出我正确的方向？

我需要一个使用多项式 0x737e312b 的 CRC-31 算法，或者任何可以满足我需求的双射函数。

笔记

我找到了以下代码，但不幸的是我没有编译和运行它的工具。

使用来自各种来源的示例，我编写了此方法（如下所示的相关部分），其中我从 kafka 中提取 parquet-avro 消息以用于测试应用程序。根据我可以找到的代码（其中一些来自http://aseigneurin.github.io/2016/03/04/kafka-spark-avro-produce-and-sumption-avro-messages.html )，我使用的是传入的模式，而不是从消息本身中提取的模式。我是否遗漏了某些东西，或者我是否可以从每条消息中提取模式而不是需要传递它。我对这一切都很陌生，所以我想确保我以最好的方式做到这一点。

呼叫者：

我在做一个简单的任务时遇到了麻烦：

假设我使用这些库并拥有这个数据框：

使用以下命令，我想从 df 中删除第 4、5、7、8、9、11 列。

我可以使用手动删除它们

但是，我希望算法自动执行此操作。

我首先尝试以下方法来生成包含 whichAreBijection 提出的列号的数据框 m，然后最终将其从 df 中删除，但它让我无处可去：

上面生成的 m 具有由 4、5、7、8、9、11 给出的常量条目

我看到使用一个简单的命令，比如

完美地将 m 的第一列替换为 df 的第四列。

我遇到的第二个问题是在 m 中使用与 df 中相同的列名。可能这听起来要完成简单的任务还有很长的路要走。

1. 为什么没有在 m 中完全替换列？

2. 我怎样才能自动让 m 选择要删除的 df 的列名作为列名？

3. 有没有更好的方法来避免这种混乱并直接删除 whichAreBijection 提出的列名？

所以我一直在尝试构建一个更短的 URL，但我无法生成唯一但random字符串。我到处寻找解决方案，但找不到解决方案，因此将其发布在这里。

我有一个表，我在其中获得针对插入记录的自动生成的顺序主键 (ID)。现在我拿那个 ID 并在它上面运行一个双射函数

现在的问题是生成的字符串不是随机的。例如 ：

这是非常可猜测的。我什至尝试将 ID 编码为 Base64，但生成的字符串再次可以猜测，如果我使用 GUID 并将其编码为 Base64，则生成的字符串非常大。最大字符串应为 7,8 个字符 - 理想情况下为 3,4 个字符。

我想知道 bit.ly 是如何做到的？他们生成的短 URL 始终是唯一且随机的。

我需要在 python 中表示一对一的关系。

最简单的方法是拥有一个元组列表。[(thing_one, thing_two]. 但这会给你 O(N) 的翻译/删除/插入时间。不理想。

接下来你可以使用两个字典 one_to_two, two_to_one. 这将使您获得 O(1) 翻译/插入/删除。但是很容易忘记在没有另一个的情况下更新一个，并且您现在需要将表示这种关系的内存量增加一倍。您可以将其包装在一个类中以强制执行双射，但您仍然无法解决信息重复问题。

有没有一种很好的方式来表示这样的关系？最好使用 O(1) 操作且没有数据重复？也许是一个为你处理这个的python模块？