Tạo ISBN giả từ tên sách? (Hoặc: Cách băm chuỗi thành ID số gồm 6 chữ số)

Question

Phiên bản ngắn: Làm cách nào để biến chuỗi tùy ý thành số có 6 chữ số với các va chạm tối thiểu?

phiên bản Long:

Tôi đang làm việc với một thư viện nhỏ mà có một loạt các cuốn sách không có ISBN. Đây thường là các tiêu đề cũ hơn, không còn xuất bản từ các nhà xuất bản nhỏ mà không bao giờ có ISBN để bắt đầu, và tôi muốn tạo các ISBN giả để họ có thể giúp quét mã vạch và cho vay.

Về mặt kỹ thuật, ISBN thực được kiểm soát bởi các thực thể thương mại, nhưng có thể sử dụng định dạng để gán số không thuộc về nhà xuất bản thực (và do đó không nên gây ra bất kỳ xung đột nào).

Định dạng là như vậy mà:

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

Cung cấp cho bạn 6 chữ số để làm việc với, 000.000-999.999, với sự? cuối cùng là một kiểm tra.

Bạn có thể chuyển tựa đề sách tùy ý thành số có 6 chữ số trong lược đồ này với cơ hội va chạm tối thiểu không?

Answer 1

6 chữ số cho phép khoảng 10M giá trị có thể, là đủ cho hầu hết các mục đích sử dụng nội bộ. Tôi đã sử dụng một chuỗi thay vì trong trường hợp này, bởi vì kiểm tra 6 chữ số có cơ hội va chạm tương đối cao.

Vì vậy, bạn có thể chèn tất cả các chuỗi vào một băm và sử dụng các số chỉ mục làm ISBN, sau khi sắp xếp hoặc không có nó.
Điều này sẽ gây ra va chạm gần như không thể, nhưng nó đòi hỏi phải giữ một số ISBN "được phân bổ" để tránh va chạm trong tương lai và giữ danh sách các tựa đề đã có trong kho, nhưng đó là thông tin mà bạn có thể muốn giữ dù sao.

lựa chọn khác là để phá vỡ các tiêu chuẩn ISBN và sử dụng hệ thập lục phân/mã vạch UUEncoded, có thể tăng phạm vi có thể đến một điểm mà nó có thể làm việc với một băm mật mã cắt ngắn để phù hợp.

Tôi sẽ đề nghị rằng vì bạn đang xử lý các tiêu đề sách cũ, có thể có nhiều phiên bản viết hoa và dấu câu khác nhau, tôi sẽ phân cách dấu chấm câu, sao trắng và chuyển đổi mọi thứ thành chữ thường trước khi so sánh để giảm thiểu cơ hội trùng lặp kỹ thuật mặc dù chuỗi khác (Trừ khi bạn muốn các ấn bản khác nhau có các ISBN khác nhau, trong trường hợp đó, bạn có thể bỏ qua đoạn này).

Answer 2

Sau khi sử dụng đoạn mã cho making a fixed-length hash và tính toán ISBN-13 checksum, tôi đã quản lý để tạo mã C# thực sự xấu xí dường như hoạt động. Nó sẽ lấy một chuỗi tùy ý và chuyển đổi nó thành một hợp lệ (nhưng giả) 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; 
     }