我可以将字符串编码为整数,以保留字典字符串的接近度吗？

Question

我希望将不同长度的字符串(通常为1-100个字符)编码为整数,使得字典相似的字符串(它们将在字典中靠近在一起)产生紧密相连的整数,同时进一步确保这些整数在可能的整数值范围内合理均匀分布.

我认识到确保均匀分布可能需要在编码之前对可能的字符串进行某种调查.

有没有人对如何做到这一点有任何想法？

Answer 1

压缩密钥在这里可能有用。这个想法是比较一组字符串并删除所有相似的位。它产生一组几乎唯一的键，小到足以容纳一个整数。请参阅“FAST：现代 CPU 和 GPU 上的快速架构敏感树搜索”的第 6 章。

所描述的算法并不总是保留字典顺序，但可以进行增强以做到这一点。

编辑：

更通用的方法是将字符串字符拆分为独立的部分（如果可能），然后确定这些部分的概率，并应用算术编码。

编辑2：

为了在压缩密钥中容纳更多的字符串，最好使用某种熵编码，其中字符的编码涉及多个但不超过 1 .. 2 个先前字符的值（过多提高压缩率会降低性能） ）。或者，如果整数键应该足够短（例如16位），最好使用熵方法预先计算所有键并将它们放入按字符串排序的集合中；在这种情况下，编码前缀可能会更长。