Lấy một biểu diễn int của một String

Question

Tôi đang tìm cách tạo một biểu diễn int dài của một chuỗi số alpha tùy ý. Mã băm sẽ không làm điều đó, bởi vì tôi không thể đủ khả năng va chạm băm tức là biểu diễn phải là duy nhất và có thể lặp lại.

Biểu diễn dạng số sẽ được sử dụng để thực hiện các so sánh hiệu quả (hy vọng) hiệu quả. Việc tạo khóa số sẽ mất một thời gian, nhưng nó chỉ phải xảy ra một lần, trong khi tôi cần thực hiện một số lượng lớn các so sánh với nó - hy vọng sẽ nhanh hơn nhiều so với các chuỗi thô.

Bất kỳ ý tưởng nào khác về việc so sánh chuỗi nhanh hơn cũng sẽ được đánh giá cao nhất ...

Answer 1

Chuỗi của bạn dài bao lâu? Trừ khi bạn chọn một biểu diễn int dài hơn chuỗi, các xung đột sẽ luôn có thể bất kể chuyển đổi bạn đang sử dụng là gì. Vì vậy, nếu bạn đang sử dụng một số nguyên 32 bit, bạn chỉ có thể đại diện cho các chuỗi tối đa 4 byte.

Answer 2

Bạn không thể bắt đầu bằng mã băm và nếu mã băm phù hợp, hãy thực hiện so sánh nhân vật?

Answer 3

Chuỗi của bạn lớn đến mức nào? Chuỗi dài tùy ý không thể nén thành định dạng 32/64 bit.

Answer 4

Nếu bạn không muốn va chạm, hãy thử điều gì đó điên rồ như SHA-512. Tôi không thể đảm bảo sẽ không có va chạm, nhưng tôi không nghĩ rằng họ đã tìm thấy bất kỳ được nêu ra.

Answer 5

Giả sử "chữ và số" có nghĩa là chữ cái và số, bạn có thể coi mỗi chữ cái/số dưới dạng chữ số cơ sở-36. Thật không may, các chuỗi lớn sẽ làm cho số lượng phát triển nhanh chóng và bạn phải sử dụng các số nguyên lớn, hầu như không hiệu quả.

Nếu chuỗi của bạn thường khác khi bạn so sánh (ví dụ: tìm kiếm một chuỗi cụ thể), hàm băm có thể là lựa chọn tốt nhất của bạn. Một khi bạn nhận được một hit tiềm năng, bạn có thể làm so sánh chuỗi để chắc chắn. Một băm được thiết kế tốt sẽ làm cho va chạm cực kỳ hiếm.

Answer 6

Dường như một mã băm MD5 sẽ hoạt động tốt. Nguy cơ xảy ra va chạm băm sẽ rất khó xảy ra. Tùy thuộc vào độ dài của chuỗi của bạn, một băm tạo ra một int/long sẽ chạy vào vấn đề giá trị tối đa rất nhanh chóng.

Answer 7

Tại sao bạn không làm điều gì đó như 1stChar + (10 x 2ndChar) + 100 x (3rdChar) ...., nơi bạn sử dụng giá trị số nguyên đơn giản của mỗi ký tự, tức là a = 1, b = 2 v.v. , hoặc chỉ là giá trị số nguyên nếu nó không phải là một chữ cái. Điều này sẽ cung cấp cho một giá trị duy nhất cho mỗi chuỗi, ngay cả đối với 2 chuỗi chỉ là cùng một chữ cái theo thứ tự khác nhau.

Tất nhiên nếu trở nên phức tạp hơn nếu bạn cần phải lo lắng về Unicode hơn là chỉ ASCII và các con số có thể lớn nếu bạn cần sử dụng chuỗi dài.

Các hàm so sánh chuỗi Java chuẩn có chắc chắn không đủ hiệu quả không?

Answer 8

Chuỗi dài bao lâu? Nếu chúng rất ngắn, thì có thể tạo ID duy nhất bằng cách xem các ký tự dưới dạng chữ số trong cơ sở 36 (26 + 10) tạo thành một số n -digits, trong đó n là độ dài của chuỗi. Mặt khác, nếu các chuỗi này đủ ngắn để cho phép điều này, thì so sánh trực tiếp sẽ không phải là vấn đề.

Nếu không, bạn sẽ phải tạo băm không có va chạm và điều này chỉ có thể được thực hiện khi không gian vấn đề đầy đủ được biết trước (tức là nếu bạn biết tất cả các chuỗi có thể xảy ra).Bạn sẽ muốn có một cái nhìn tại perfect hashing, mặc dù thuật toán khả thi duy nhất để tìm một hàm băm hoàn hảo mà tôi biết là xác suất để va chạm vẫn còn về mặt lý thuyết có thể.

Có thể có các cách khác để tìm một chức năng như vậy. Knuth gọi đây là câu đố “khá thú vị…” trong TAoCP nhưng anh cũng không đưa ra thuật toán.

Nói chung, bạn cung cấp thông tin quá ít để tìm một thuật toán không yêu cầu thăm dò toàn bộ không gian vấn đề theo một cách nào đó. Điều này luôn luôn có nghĩa là vấn đề có thời gian chạy theo cấp số nhân nhưng có thể được giải quyết bằng cách sử dụng chẩn đoán máy học. Tôi không chắc chắn nếu điều này là khuyến khích trong trường hợp của bạn.

Answer 9

lẽ:

String y = "oiu291981u39u192u3198u389u28u389u"; 
BigInteger bi = new BigInteger(y, 36); 
System.out.println(bi); 

Answer 10

Một vài câu hỏi trong đầu:

1. Bạn có kiểm tra đơn giản so sánh chuỗi là quá chậm?
2. Cách so sánh trông giống như ('ABC' == 'abc' hoặc 'ABC'! = 'Abc')?
3. Bạn cần so sánh bao nhiêu chuỗi?
4. Bạn cần phải so sánh bao nhiêu lần so sánh?
5. Cách chuỗi của bạn trông như thế nào (độ dài, chữ hoa chữ thường)?

Theo tôi nhớ Chuỗi trong Java là một đối tượng và hai chuỗi giống nhau trỏ đến cùng một đối tượng.

Vì vậy, có thể sẽ đủ để so sánh các đối tượng (có thể so sánh chuỗi đã được triển khai theo cách này).

Nếu nó không giúp bạn có thể cố gắng sử dụng Pascal thực hiện đối tượng chuỗi khi yếu tố đầu tiên là chiều dài và nếu chuỗi của bạn có chiều dài khác nhau này nên tiết kiệm một số thời gian CPU.

Answer 11

Trừ khi chuỗi của bạn bị giới hạn về độ dài, bạn không thể tránh va chạm.

Có 4294967296 giá trị có thể cho một số nguyên (2^32). Nếu bạn có một chuỗi gồm hơn 4 ký tự ASCII hoặc nhiều hơn hai ký tự unicode, thì có nhiều giá trị chuỗi có thể có hơn giá trị số nguyên có thể có. Bạn không thể có giá trị số nguyên duy nhất cho mỗi chuỗi ký tự 5 có thể. Giá trị dài có nhiều giá trị có thể hơn, nhưng chúng sẽ chỉ cung cấp một giá trị duy nhất cho mỗi chuỗi có thể có 8 ký tự ASCII.

Mã băm hữu ích dưới dạng quy trình gồm hai bước: trước tiên hãy xem mã băm có phù hợp không, sau đó kiểm tra toàn bộ chuỗi. Đối với hầu hết các chuỗi không khớp, bạn chỉ cần thực hiện bước đầu tiên và thực sự rất nhanh.

Answer 12

Độ dài chuỗi có thể thay đổi, nhưng giả sử 10 ký tự bây giờ.

Trong trường hợp đó, để đảm bảo tính duy nhất, bạn phải sử dụng một số loại đại diện số nguyên lớn. Tôi nghi ngờ rằng việc so sánh các số nguyên lớn sẽ nhanh hơn đáng kể so với so sánh chuỗi ở vị trí đầu tiên. Tôi sẽ thứ hai những gì người khác đã nói ở đây, sử dụng một số loại băm, sau đó trong trường hợp của một trận đấu băm kiểm tra các chuỗi ban đầu để loại bỏ bất kỳ va chạm.

Trong mọi trường hợp, nếu chuỗi của bạn có khoảng 10 ký tự, tôi nghi ngờ rằng so sánh, nói rằng, một loạt các băm 32 bit sẽ nhanh hơn nhiều so với so sánh chuỗi trực tiếp. Tôi nghĩ rằng bạn phải tự hỏi mình liệu nó có thực sự đáng giá thêm phức tạp không.

Answer 13

Vào cuối ngày, một ký tự chữ và số có ít nhất 36 giá trị có thể. Nếu bạn bao gồm dấu câu, chữ thường, vv thì bạn có thể dễ dàng chuyển 72 giá trị có thể.

Số không va chạm cho phép bạn nhanh chóng so sánh các chuỗi nhất thiết sẽ tăng theo cấp số nhân với độ dài của chuỗi.

Vì vậy, bạn trước tiên phải quyết định chuỗi dài nhất bạn đang mong đợi để so sánh. Giả sử N có chiều dài ký tự và giả sử bạn CHỈ cần chữ hoa và các chữ số 0-9 thì bạn cần phải có một số nguyên đại diện có thể cao tới 36^N

Đối với chuỗi dài 25 trường tên) sau đó bạn sẽ cần một số nhị phân với 130 bit.

Nếu bạn soạn thành số 32 bit, bạn sẽ cần 4. Sau đó, bạn có thể so sánh từng số (bốn số nguyên so sánh sẽ không mất thời gian so với khi đi bộ chuỗi). Tôi sẽ giới thiệu một thư viện số lớn, nhưng đối với trường hợp đặc biệt này, tôi khá chắc chắn bạn có thể viết của riêng bạn và có được hiệu suất tốt hơn.

Nếu bạn muốn xử lý 72 giá trị có thể cho mỗi ký tự (chữ hoa, chữ thường, chữ số, dấu câu ...) và bạn cần 10 ký tự, thì bạn cần 62 bit - hai số nguyên 32 bit (hoặc 64 bit nếu bạn đang sử dụng hệ thống hỗ trợ tính toán 64 bit)

Nếu, bạn không thể hạn chế số trong chuỗi (ví dụ: có thể là bất kỳ 256 chữ cái/số/ký tự/v.v ...) không thể xác định kích thước của chuỗi, sau đó so sánh các chuỗi trực tiếp là cách duy nhất để đi, nhưng có một phím tắt.

Truyền con trỏ của chuỗi tới mảng số nguyên không dấu 32 bit và so sánh chuỗi 4 byte tại một thời điểm (hoặc 64 bit/8byte tại một thời điểm trên bộ xử lý 64 bit). Điều này có nghĩa là một chuỗi ký tự 100 chỉ yêu cầu 25 so sánh tối đa để tìm chuỗi nào lớn hơn.

Bạn có thể cần phải xác định lại bộ ký tự (và chuyển đổi chuỗi) để các ký tự có mức ưu tiên cao hơn được gán giá trị gần bằng 0 và giá trị ưu tiên thấp hơn gần 255 (hoặc ngược lại, tùy thuộc vào cách bạn đang so sánh chúng).

Chúc may mắn!

-Adam

Answer 14

Chừng đó là một hàm băm, có thể là String.hashCode(), MD5 hoặc SHA1, va chạm là không thể tránh khỏi, trừ khi bạn có một giới hạn nhất định về chiều dài của chuỗi. Nó là toán học không thể có một-một ánh xạ từ một nhóm vô hạn cho một nhóm hữu hạn.

Quay lại, tránh va chạm hoàn toàn cần thiết?