将字符串映射为替换字符串的算法

我正在寻找方法来确定性地用唯一且最佳的短替换替换唯一字符串。所以我有一个有限的字符串集合，迄今为止我能达到的最好的压缩方式是通过枚举算法，在那里我命令输入集合，然后用扩展字母表中的字符串枚举来替换字符串（a..z ，A ... Z，aa ... zz，aA ... zZ，a0 ... z9，Aa ...，aaa ... zaa，aaA ... zaaA，....）。将字符串映射为替换字符串的算法

就压缩而言，它的工作原理非常奇妙，但有严重的缺点，即它在任何给定的输入字符串上都不是原子的。相反，其结果取决于知道全部输入字符串从一开始，并在订购的输入集。

任何人都知道具有相似压缩但不需要知道所有输入字符串的算法？！哈希例如对我来说是行不通的，因为根据输入集的大小，我需要哈希长度为8-12，以便哈希值是唯一的，并且这将会太长，因为替换（当前，替换字符串我的使用案例长度为1-3个字符（< 10,000个输入字符串））。另外，如果我们中的理论家知道这是浪费精力，我会有兴趣听到:-)。

来源

2011-02-23 ThomasH

从什么字母表可能输入的字符是绘制？例如小写字母;大写和小写字母;字母数字;等等。另外，我认为你的意思是'确定性的'，你有'原子'的地方。 – AakashM 2011-02-23 17:58:49

除非您提供有关类型输入字符串的更多详细信息，否则很难回答。不能有一个通用的算法，它可以在没有碰撞的情况下在单个字符串上工作考虑一个巨大的文件作为单个字符串。现在你试图用3个字节来表示...... – 2011-02-23 18:11:21

@AakashM输入字符串基本上是（？u）[a-zA-z _ $] [\。\ w $] *，所以unicode alphanums有一些额外的字符。使用'原子'我的意思是我无法自己计算给定输入字符串的替换，并放弃它，因为是的，它不是确定性的。 – ThomasH 2011-02-23 18:11:53

您可以使用您的枚举方案，但按照您第一次遇到输入字符串的顺序进行排序。

例如，您曾经处理的第一个字符串可以映射到“a”。下不同的字符串将被映射到“B”等

每次处理字符串的时候，你需要看看它，看它是否已被映射。

来源

2011-02-23 18:05:33 mbeckish

哦，是的，查找放松订购问题。谢谢！ – ThomasH 2011-02-23 18:20:51

“最短”取决于从中抽取样本的字符串的数量。在群体中没有系统冗余的情况下，您会发现只有一小部分任意字符串可以被压缩（例如，考虑尝试压缩随机位串）。

如果您可以对数据做出假设，例如“字符串预期主要由英语单词组成”，那么您可以根据字母频率做一些简单而有效的事情（例如，对于英语，相对频率顺序就像ETAOINSHRDLUGCY ...，所以你会想用更少的位来表示Es，而更多的位用来表示不常见的字母，如Q）。

干杯。

来源

2011-02-23 23:09:25 Rafe

谢谢，但它不是一个编码，必须在某个时候解码（也许我应该避免使用'compression'这个术语）。这实际上是关于从字符串到（几乎）任意短字符串的双射映射。我想典型的字符串压缩算法会给我留下比1-3字符长得多的替换。 – ThomasH 2011-02-24 12:17:49

@ThomasH - 呃，从任意长字符串到短字符串的双射*是压缩！ – Rafe 2011-02-25 03:41:02

同意:)。只是人们经常认为它是一个必须在某个时候被颠倒的过程（又称“解压缩”），这不是我所需要的。 – ThomasH 2011-02-25 10:31:26

将字符串映射为替换字符串的算法

回答

相关问题