C++: Gợi ý về một hàm băm cho một chuỗi các chuỗi nơi thứ tự của chuỗi là không thích hợp

Question

Hãy nói rằng bạn có hai chuỗi những các chuỗi

abc cba bc

bc abc cba

Tôi đang cố gắng để tạo một ánh xạ cho các chuỗi như vậy (chuỗi cũng là một chuỗi) sao cho hai chuỗi trên được ánh xạ vào cùng một nhóm.

Suy nghĩ ban đầu của tôi là thêm kết quả của hàm băm được áp dụng cho từng chuỗi riêng biệt. Theo cách này, thứ tự của họ sẽ không thành vấn đề. Nếu tôi áp dụng hàm băm cho chuỗi chuỗi như một tổng thể, thì tất nhiên kết quả băm sẽ khác nhau.

Tuy nhiên tôi rất mới với thế giới của các hàm băm chuỗi và tôi không biết liệu phương pháp này có hiệu quả hay không.

Trong trang web này http://www.partow.net/programming/hashfunctions/index.html

tôi tìm thấy nhiều hiện thực khác nhau cho chuỗi băm, tuy nhiên tôi không chắc chắn cái nào sẽ là "tốt nhất" cho nhu cầu của tôi.

Một số chi tiết kỹ thuật về từng chuỗi trong chuỗi là mỗi chuỗi trong số đó sẽ không có nhiều hơn 25 ký tự. Ngoài ra, mỗi chuỗi sẽ không có nhiều hơn 3 chuỗi.

Câu hỏi

1. sẽ tiếp cận này thêm kết quả của một hàm băm chuỗi cho mỗi chuỗi các công việc tự?

2. Nếu có chức năng băm chuỗi nào tôi nên sử dụng, điều đó sẽ cho ra một lượng va chạm thấp và cũng có hiệu quả về thời gian?

Cảm ơn bạn trước

Answer 1

Chỉ cần ý tưởng trình diễn (rất không hiệu quả chuỗi sao chép), độ phức tạp O (NlogN) trong đó N là kích thước của phím (=== O (1) nếu phím của bạn có độ dài không đổi được biết đến tại thời gian biên dịch), tôi không nghĩ rằng bạn có thể làm phức tạp hơn:

#include <boost/functional/hash.hpp> 
#include <set> 
#include <algorithm> 

std::size_t make_hash(
    std::string const& a, 
    std::string const& b, 
    std::string const& c) 
{ 
    std::string input[] = {a,b,c}; 
    std::sort(input, input + (sizeof(input)/sizeof(*input))); 
    return boost::hash_range(input, input + (sizeof(input)/sizeof(*input))); 
} 

#include <iostream> 
// g++ -I.../boost_1_47_0 string_set_hash.cpp 
int main() 
{ 
    std::cout << make_hash("abc", "bcd", "def") << std::endl; // 46247451276990640 
    std::cout << make_hash("bcd", "def", "abc") << std::endl; // 46247451276990640 
} 

Một mảnh của tăng/functional/hash.hpp để tham khảo:

template <class T> 
inline void hash_combine(std::size_t& seed, T const& v) 

{ 
    boost::hash<T> hasher; 
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); 
} 

template <class It> 
inline std::size_t hash_range(It first, It last) 
{ 
    std::size_t seed = 0; 

    for(; first != last; ++first) 
    { 
     hash_combine(seed, *first); 
    } 

    return seed; 
} 

Answer 2

Dù băm functio n chọn nào, bạn muốn một nhà điều hành cho sự kết hợp cuối cùng của mỗi băm cá nhân đó sẽ là:

• hoán
• kết

tổng, sản phẩm, và độc quyền hoặc đến tâm làm ứng cử viên cho các giá trị tích phân. Vì vậy, có, thêm sẽ làm việc. Bạn vẫn sẽ có xung đột về chuỗi không liên quan cần phải được giải quyết, vì vậy bạn sẽ cần một hàm so sánh chuỗi, nhưng hoán vị của cùng một tập hợp các chuỗi sẽ kết thúc trong cùng một nhóm.

Bạn cũng có thể đảo ngược thứ tự hoạt động: thêm chuỗi ký tự khôn ngoan với nhau trước tiên (ví dụ:thêm "ab" và "cba" trở thành ('a' + 'c') ('b' + 'b') ('\ 0' + 'a') với việc truyền bá thực cho tổng hoặc sản phẩm, vì vậy có lẽ xor là một ứng cử viên thú vị ở đây), và sau đó áp dụng một hàm băm. Bạn thậm chí có thể kết hợp hai hoạt động này trong khi thực hiện chúng (mã giả sau):

int hash(string a, string b, string c){ 
    int r = 0, k; 
    int m = max(a.length(), max(b.length(), c.length())); 
    for (int i = 0; i < m; i++) { 
     k = (i < a.length()? a[i] : 0)^
       (i < b.length()? b[i] : 0)^
       (i < c.length()? c[i] : 0); 
     r = hash(r,k); 
    } 
    return r; 
} 

Với hash hàm băm gia tăng. Một modulo đơn giản so với số nguyên tố đủ lớn (ví dụ: lớn hơn kích thước dự kiến ​​của mảng nhóm) sẽ không sao cho các mục đích thông thường. Một giải pháp hoàn toàn khác (và tốt hơn?) Đơn giản là sắp xếp chuỗi (3 mục có nghĩa là thời gian không đổi), sau đó tạo một bản đồ có thứ tự với hàm so sánh xem xét các chuỗi là "chữ số" của một số có 3 chữ số . Nhưng điều này nằm ngoài phạm vi của câu hỏi.

Answer 3

Tôi sẽ băm từng phần tử riêng lẻ.

Sau đó, sắp xếp các băm đó. Sắp xếp 3 size_t là nhanh.

Sau đó, chuỗi các băm đó. Thư viện của bạn có thể có chức năng chuỗi băm hoặc thậm chí sử dụng hash(a+b+c) với gói tràn.

Tránh xor, vì xor hai giá trị băm giống hệt nhau là 0. Và băm của các chuỗi giống nhau là giống hệt nhau. Vì vậy, một xor ngây thơ có thể dẫn đến (a,a,b) và (c,c,b) có cùng một đầu ra băm, mà hút.