时间戳

首页 > 解决方案 > 解码包含编码模式的字符串

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

问题描述

考虑以下问题：

string s = "fffffssss"

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

标签： stringalgorithmencodingdecoding

解决方案

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

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

每当输入本身有一个散列时，就以与上述相同的方式对其进行转义：在其后附加一个额外的散列。

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

下面是这些编码/解码函数的一个小 JavaScript 实现，严重依赖于基于正则表达式的替换。你可以玩它：

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从正则表达式中删除了该标志，因为并非所有浏览器都支持它，但如果您的输入中可能出现换行符，它应该存在。

推荐阅读