5

简短版：如何将任意字符串转换为 6 位数字且冲突最少？

长版：

我正在与一个小型图书馆合作，该图书馆有一堆没有 ISBN 的书籍。这些通常是来自从未获得 ISBN 的小型出版商的较旧的绝版书籍，我想为他们生成假 ISBN 以帮助进行条形码扫描和贷款。

从技术上讲，真正的 ISBN 由商业实体控​​制，但可以使用该格式分配不属于真正出版商的编号（因此不应引起任何冲突）。

格式是这样的：

978-0-01-######-?

为您提供 6 位数字，从 000000 到 999999，使用 ? 最后是校验和。

在这种方案中，是否有可能将任意书名转换为 6 位数字，并且碰撞的可能性最小？

4

2 回答 2

1

在使用代码片段制作固定长度的哈希并计算ISBN-13 校验和之后，我设法创建了看起来很丑的 C# 代码。它将采用任意字符串并将其转换为有效（但假的）ISBN-13：

       public int GetStableHash(string s)
       {
           uint hash = 0;
           // if you care this can be done much faster with unsafe 
           // using fixed char* reinterpreted as a byte*
           foreach (byte b in System.Text.Encoding.Unicode.GetBytes(s))
           {   
               hash += b;
               hash += (hash << 10);
               hash ^= (hash >> 6);    
           }
           // final avalanche
           hash += (hash << 3);
           hash ^= (hash >> 11);
           hash += (hash << 15);
           // helpfully we only want positive integer < MUST_BE_LESS_THAN
           // so simple truncate cast is ok if not perfect
           return (int)(hash % MUST_BE_LESS_THAN);
       }

       public int CalculateChecksumDigit(ulong n)
       {
           string sTemp = n.ToString();
           int iSum = 0;
           int iDigit = 0;

           // Calculate the checksum digit here.
           for (int i = sTemp.Length; i >= 1; i--)
           {
               iDigit = Convert.ToInt32(sTemp.Substring(i - 1, 1));
               // This appears to be backwards but the 
               // EAN-13 checksum must be calculated
               // this way to be compatible with UPC-A.
               if (i % 2 == 0)
               { // odd  
                   iSum += iDigit * 3;
               }
               else
               { // even
                   iSum += iDigit * 1;
               }
           }
           return (10 - (iSum % 10)) % 10;
       }


       private void generateISBN()
       {
           string titlehash = GetStableHash(BookTitle.Text).ToString("D6");
           string fakeisbn = "978001" + titlehash;
           string check = CalculateChecksumDigit(Convert.ToUInt64(fakeisbn)).ToString();

            SixDigitID.Text = fakeisbn + check;
       }
于 2012-10-11T10:16:08.257 回答
0

这 6 位数字允许大约 10M 的可能值，这对于大多数内部使用来说应该足够了。在这种情况下，我会使用序列，因为 6 位校验和发生冲突的可能性相对较高。

因此，您可以将所有字符串插入散列，并在排序后或不使用索引号作为 ISBN。
这应该使冲突几乎不可能发生，但它需要保留一些“已分配”的 ISBN 以避免将来发生冲突，并保留已经存储的标题列表，但无论如何您很可能希望保留这些信息。

另一种选择是打破 ISBN 标准并使用十六进制/uuencoded 条形码，这可能会将可能的范围增加到可以与截断以适合的加密哈希一起使用的程度。

我建议，由于您正在处理旧书名，可能有几个版本的大写和标点符号不同，我会在比较之前去除标点符号、重复的空格并将所有内容转换为小写，以尽量减少技术重复的机会，即使字符串是不同（除非您希望不同的版本具有不同的 ISBN，在这种情况下，您可以忽略这一段）。

于 2012-10-11T08:08:10.957 回答