使整数列表更加人性化

Question

这是我为了解决工作中无法修复的问题而进行的一个业余项目。我们的系统输出一个代码来表示一个事物与另一个事物的组合。一些示例代码是：

9-9-0-4-4-5-4-0-2-0-0-0-2-0-0-0-0-0-2-1-2-1-2-2 -2-4

9-5-0-7-4-3-5-7-4-0-5-1-4-2-1-5-5-4-6-3-7-9-72

9-15-0-9-1-6-2-1-2-0-0-1-6-0-7

到目前为止，我见过的一个插槽中的最大数量约为 150，但它们很可能会走得更高。

设计系统时，并没有要求这段代码是什么样子。但现在客户希望能够从一张纸上手动输入它，上面的代码不适合这种情况。我们已经说过我们不会对此采取任何行动，但这似乎是一个有趣的挑战。

我的问题是哪里是开始无损压缩此代码的好地方？显而易见的解决方案（例如使用较短的密钥存储此代码）不是一个选择；我们的数据库是只读的。我需要构建一种两种方法来使该代码更加人性化。

Answer 1

1）我同意你肯定需要一个校验和 - 数据输入错误很常见，除非你有训练有素的员工和带有自动交叉检查的独立重复键控。

2）我建议 http://en.wikipedia.org/wiki/Huffman_coding 转动你的列表将数字转换成比特流。为了获得所需的概率，您需要一个适当大小的真实数据样本，这样您就可以进行计数，将 Ni 设置为数字 i 在数据中出现的次数。然后我建议设置 Pi = (Ni + 1) / (Sum_i (Ni + 1)) - 这可以稍微平滑概率。另外，使用此方法，如果您看到数字 0-150，您可以通过输入数字 151-255 并将其设置为 Ni = 0 来添加一点余量。解决罕见大数字的另一种方法是添加某种转义序列。

3）找到一种方法让人们输入所得到的位序列确实是一个应用心理学问题，但这里有一些想法的建议。

3a) 软件许可证 - 只需在 64 个字符的字母表中对每个字符编码 6 位，但以一种使人们更容易保持位置的方式对字符进行分组，例如 BC017-06777-14871-160C4

3b) 英国汽车牌照。使用字母表的变化向人们展示如何对字符进行分组，例如 ABCD0123EFGH4567IJKL...

3c) 一个非常大的字母表 - 为自己准备一个 2^n 个单词的列表，用于一些大小合适的 n 并将 n 位编码为单词，例如 GREEN ENCHANTED LOGICIAN。 ..-

Answer 2

不久前我还担心这个问题。事实证明，你不能比 base64 做得更好 - 尝试为每个字符压缩更多位并不值得（一旦你进入“奇怪”的位数，编码和解码就会变得更加复杂）。但与此同时，您最终会得到一些在输入时可能出错的内容（将 0 与 O 等混淆）。一个选项是选择一组修改后的字符和字母（因此它仍然是基数 64，但是，比如说，您用“>”替换“0”。另一个选项是添加校验和。同样，为了实现简单，我觉得 不幸的是，

我没有得到任何进一步的信息 - 事情改变了方向 - 所以我无法提供代码或特定的校验和选择

PS 我意识到缺少一个我没有解释的步骤：我要压缩文本。之前转换成某种二进制形式编码（使用一些标准压缩算法），总结一下：压缩、添加校验和、base64 编码；base 64 解码、检查校验和、解压缩。

Answer 3

这与我过去使用过的类似。当然有更好的方法可以做到这一点，但我使用这种方法是因为它很容易在 Transact-SQL 中进行镜像，而这在当时是一项要求。如果您的 id 的分布是非随机的，您当然可以修改它以合并霍夫曼编码，但这可能是不必要的。

您没有指定语言，因此这是用 c# 编写的，但转换到任何语言应该很容易。在查找中，您会看到经常混淆的字符被省略。这应该会加快进入速度。我也有固定长度的要求，但是你可以很容易地修改它。

static public class CodeGenerator
{
    static Dictionary<int, char> _lookupTable = new Dictionary<int, char>();

    static CodeGenerator()
    {
        PrepLookupTable();
    }

    private static void PrepLookupTable()
    {
        _lookupTable.Add(0,'3');
        _lookupTable.Add(1,'2');
        _lookupTable.Add(2,'5');
        _lookupTable.Add(3,'4');
        _lookupTable.Add(4,'7');
        _lookupTable.Add(5,'6');
        _lookupTable.Add(6,'9');
        _lookupTable.Add(7,'8');
        _lookupTable.Add(8,'W');
        _lookupTable.Add(9,'Q');
        _lookupTable.Add(10,'E');
        _lookupTable.Add(11,'T');
        _lookupTable.Add(12,'R');
        _lookupTable.Add(13,'Y');
        _lookupTable.Add(14,'U');
        _lookupTable.Add(15,'A');
        _lookupTable.Add(16,'P');
        _lookupTable.Add(17,'D');
        _lookupTable.Add(18,'S');
        _lookupTable.Add(19,'G');
        _lookupTable.Add(20,'F');
        _lookupTable.Add(21,'J');
        _lookupTable.Add(22,'H');
        _lookupTable.Add(23,'K');
        _lookupTable.Add(24,'L');
        _lookupTable.Add(25,'Z');
        _lookupTable.Add(26,'X');
        _lookupTable.Add(27,'V');
        _lookupTable.Add(28,'C');
        _lookupTable.Add(29,'N');
        _lookupTable.Add(30,'B');          
    }


    public static bool TryPCodeDecrypt(string iPCode, out Int64 oDecryptedInt)
    {
        //Prep the result so we can exit without having to fiddle with it if we hit an error.
        oDecryptedInt = 0;

        if (iPCode.Length > 3)
        {
            Char[] Bits = iPCode.ToCharArray(0,iPCode.Length-2);

            int CheckInt7 = 0; 
            int CheckInt3 = 0;
            if (!int.TryParse(iPCode[iPCode.Length-1].ToString(),out CheckInt7) ||
                !int.TryParse(iPCode[iPCode.Length-2].ToString(),out CheckInt3))
            {
                //Unsuccessful -- the last check ints are not integers.
                return false;
            }
            //Adjust the CheckInts to the right values.
            CheckInt3 -= 2;
            CheckInt7 -= 2;

            int COffset = iPCode.LastIndexOf('M')+1;


            Int64 tempResult = 0;
            int cBPos = 0;
            while ((cBPos + COffset) < Bits.Length)
            {
                //Calculate the current position.
                int cNum = 0;
                foreach (int cKey in _lookupTable.Keys)
                {
                    if (_lookupTable[cKey] == Bits[cBPos + COffset])
                    {
                        cNum = cKey;
                    }
                }
                tempResult += cNum * (Int64)Math.Pow((double)31, (double)(Bits.Length - (cBPos + COffset + 1)));
                cBPos += 1;
            }

            if (tempResult % 7 == CheckInt7 && tempResult % 3 == CheckInt3)
            {
                 oDecryptedInt =  tempResult;
                return true;    
            }


            return false;

        }
        else
        {
            //Unsuccessful -- too short.
            return false;
        }
    }
    public static string PCodeEncrypt(int iIntToEncrypt, int iMinLength)
    {
        int Check7 = (iIntToEncrypt % 7) + 2;
        int Check3 = (iIntToEncrypt % 3) + 2;

        StringBuilder result = new StringBuilder();
        result.Insert(0, Check7);
        result.Insert(0, Check3);

        int workingNum = iIntToEncrypt;

        while (workingNum > 0)
        {
            result.Insert(0, _lookupTable[workingNum % 31]);
            workingNum /= 31;
        }

        if (result.Length < iMinLength)
        {
            for (int i = result.Length + 1; i <= iMinLength; i++)
            {
                result.Insert(0, 'M');
            }
        }

        return result.ToString();
    }

}