解码包含编码模式的字符串

Question

考虑以下问题：

string s = "fffffssss" 

编码的字符串将是5xf4xs，但如果在s中有编码模式怎么办？例如s="5xfxxx"，我应该怎么做编码器以避免歧义？只要编码的字符串必须短于原始字符串。

Answer 1

要编码5xfxxx，你将获得1x51xx1xf3xx，它没有任何歧义（只有一种方法来解码这样的字符串，你必须考虑三元组）。当你的字符串中连续超过10个相似的字符时，事情会变得有点棘手，但仍然没有任何歧义。

至于编码字符串必须短于原始字符串的约束，则没有这样的保证。 x将被编码为1xx，这是三倍长。这是您最糟糕的情况：结果比原始结果长3倍。

如果你正在寻找压缩字符串的方法，我建议你看看Huffman's coding，它简单而有效（它在压缩方面几乎是最优的，并且在线性时间内运行）。您将不得不考虑二进制字符串。

Answer 2

如果你希望保持相同的编码方案，其中dxc导致c（一个字符）的d（数字）重复，那么你可以简单地用5xy51xx编码y等输入。是的，每当您在输入中找到一个数字后跟一个x时，您将支付2个额外字符的价格。

没有（无损）编码可以保证输出始终比输入短。更强大：没有编码可以保证它总是创建输入长度或更短的输出，除了根本不编码任何东西（总是会产生等于其输入的输出长度）。所有压缩方案都依赖于输入中的冗余，并且根本不会使用真正随机的数据压缩任何内容。因此，压缩方案是否良好取决于它是否可以很好地利用其预期输入中的冗余。

保证永不支付超过1个字符的惩罚的简单方案是使用初始标记来指示字符串是否编码。例如，假设第一个字符是0，如果没有执行编码，并且1，如果它被编码。然后，

encode("1x2x3x4x") = "01x2x3x4x"; // only 1 character longer than input
encode("1x2x3x4x") = "111xx21xx31xx41xx"; // not so good: 8 chars longer

Answer 3

我将假设“aaaaaaaaa”将编码为“10xa”，这意味着生成的nxc模式中的“乘数”n可能包含多个数字。

一个想法是引入一个特殊的转义字符，例如散列“＃”。每当输入具有一系列数字时，让编码算法在这样的序列之后附加散列。这样就永远不会与nxc模式混淆。在解码中，您将删除这样的尾随哈希。

每当输入本身都有一个哈希值，然后以与上面相同的方式对其进行转义：在它之后追加一个额外的哈希值。

所以在你的例子中，5xfxxx将被编码为5#xf3xx。但是，如果可以用nxc表示法写入一系列数字，则不会使用散列。所以999x1将被编码为3x91，而122x1将被编码为122#x1。同样，###将被编码为3x#，而不是任何哈希值。因此，应用nxc模式总是优先于转义。

以下是这些编码/解码函数的一些JavaScript实现，主要依赖于regular expression-based replacements。你可以玩它：

function encode(s) {
    // If a character occurs 3 or more times in sequence, encode that sequence;
    // Otherwise, append a hash after any sequence of digits, 
    //            and after each individual hash:
    return s.replace(/(.)\1\1+|\d+|#/g, (m, ch) => 
        ch ? m.length + "x" + ch : m + "#");
}

function decode(s) {
    // If a nxc sequence is found, decode it
    // Otherwise, if a character is followed by a hash, remove the hash
    return s.replace(/(\d+)x(.)|(.)#/g, (m, times, ch, esc) => 
        times ? ch.repeat(+times) : esc);
}

// I/O management of this snippet:
let elemInput = document.querySelector("#input");
let elemEncoded = document.querySelector("#encoded");
let elemDecoded = document.querySelector("#decoded");
let elemCheck = document.querySelector("#check");
elemInput.addEventListener("input", function () { // Whenever input changes:
    let encoded = encode(this.value); // Encode...
    let decoded = decode(encoded); // ...and decode the encoded string again
    elemEncoded.textContent = encoded;
    elemDecoded.textContent = decoded;
    // Check whether the decoded string is equal to the input:
    elemCheck.textContent = this.value == decoded ? "OK" : "Difference!";
});

Input: <input id="input">
<div>Encoded: <span id="encoded"></span></div>
<div>Decoded: <span id="decoded"></span></div>
<div>Check: <span id="check"></span></div>

显然，这意味着某些输入将具有比原始输入更长的编码等效项。除非您使用始终编码为与输入一样长的字符串的算法，或者除非输出可能包含永远不会出现在输入中的内容，否则无法防止输出长于输入的情况。

注意：我从正则表达式中删除了s标志，因为并非所有浏览器都支持它，但如果您的输入中出现换行符，它应该在那里。