java - 将一组具有相似性的字符串映射到较短的字符串

Question

我有一组字符串，每个字符串长度相同(10 个字符)，具有以下属性。 该组的大小约为 5000 - 10,000 个字符串。数据集可能会经常更改。 虽然每个字符串都是唯一的，但特定模式的子字符串会出现在大多数这些字符串中，不一定在相同的位置。

Some examples are
123abc7gh0
t123abcmla
wp12123abc

123abc 是出现在大多数字符串中的子串

问题是将每个字符串映射到一个较短的字符串，这样的映射应该是确定性的。 我可以使用一个简单的枚举算法，它将遇到的每个字符串映射到一个递增的计数器值(在一组已排序的字符串上)。但是由于该集合必然会经常更改，因此我无法使用此算法以确定性的方式为各种运行计算 map 。 我还可以使用像霍夫曼编码这样的数据压缩算法来压缩每个单独的字符串。但我认为这不会有效，因为每个字符串本身的重复字符都很少。 我应该采用什么方法来利用数据集的属性来解决问题？请注意，我不想压缩整个数据集，但想将集合中的每个字符串映射到缩短的字符串。

Answer 1

1. 将“通用字符串”替换为未出现在任何字符串其他位置的字符。
2. 对所有字符串进行概率分析
3. 根据分析创建哈夫曼树，即最常见的字符位于树的顶部，从而产生短代码。
4. 根据#3 的树用它们的 hufman 编码替换样本字符串，并将结果大小与原始大小进行比较。如果大部分字符甚至在字符串之间均匀分布，那么 Hufman 编码不会减少反而会增加大小。

如果 Hufman 没有获得任何改进，您可以尝试 LZW 或任何其他基于字典的压缩方法。然而，这只适用于字符串的结构(即字符/子字符串的分布)不随时间完全改变的情况。例如，如果字符串由英语单词组成，则子字符串字典压缩 (LZW) 可能是一个不错的选择。

但是如果分布发生变化或者字符分布只是所有字符都相等，恐怕没有适合减小字符串大小的压缩方法。

但最后一个问题仍然存在:为什么？为什么要压缩 10000 个字符串？

编辑:答案是:字符串用于创建文件夹名称(路径)。总长度有限制，尽量紧凑。

您可能会尝试创建一个数据库(即字典)并将索引(例如编码为 Base64)用作压缩字符串。当假设最大字典大小为 2^32-1 时，这给你最多 5 个字符。