Cách hiệu quả để tính hệ số Dice giữa 900.000 chuỗi là gì?

Question

Tôi có một kho văn bản 900.000 chuỗi. Chúng có độ dài khác nhau, nhưng có số lượng ký tự trung bình khoảng 4.500. Tôi cần phải tìm cách hiệu quả nhất để tính toán Dice coefficient của mỗi chuỗi vì nó liên quan đến mọi chuỗi khác. Thật không may, điều này dẫn đến thuật toán hệ số Dice được sử dụng khoảng 810.000.000.000 lần.

Cách tốt nhất để cấu trúc chương trình này để tăng hiệu quả là gì? Rõ ràng, tôi có thể ngăn chặn việc tính toán Dice của các phần A và B, rồi B ​​và A - nhưng điều này chỉ làm giảm một nửa công việc cần thiết. Tôi có nên xem xét việc thực hiện một số phím tắt hoặc tạo một số loại cây nhị phân không?

Tôi đang sử dụng thực hiện sau đây của thuật toán hệ số Dice trong Java:

public static double diceCoefficient(String s1, String s2) { 
    Set<String> nx = new HashSet<String>(); 
    Set<String> ny = new HashSet<String>(); 

    for (int i = 0; i < s1.length() - 1; i++) { 
     char x1 = s1.charAt(i); 
     char x2 = s1.charAt(i + 1); 
     String tmp = "" + x1 + x2; 
     nx.add(tmp); 
    } 
    for (int j = 0; j < s2.length() - 1; j++) { 
     char y1 = s2.charAt(j); 
     char y2 = s2.charAt(j + 1); 
     String tmp = "" + y1 + y2; 
     ny.add(tmp); 
    } 

    Set<String> intersection = new HashSet<String>(nx); 
    intersection.retainAll(ny); 
    double totcombigrams = intersection.size(); 

    return (2 * totcombigrams)/(nx.size() + ny.size()); 
} 

mục tiêu cuối cùng của tôi là để đầu ra một ID cho mỗi phần có một hệ số Dice lớn hơn 0.9 với phần khác.

Cảm ơn mọi lời khuyên bạn có thể cung cấp!

Answer 1

Bạn nên đưa ra một số bất bình đẳng như: D (X1, X2)> 1-p, D (X1, X3) < 1-q và p D (X2, X3) < 1-q + p . Hay đại loại thế. Bây giờ, nếu 1-q + p < 0.9, thì có thể bạn không phải đánh giá D (X2, X3).

PS: Tôi không chắc chắn về sự bất bình đẳng chính xác này, nhưng tôi có cảm giác rằng điều này có thể đúng (nhưng tôi không có đủ thời gian để thực hiện các dẫn xuất ngay bây giờ). Hãy tìm một số bất bình đẳng với các biện pháp tương tự khác và xem liệu có bất kỳ phương pháp nào hợp lệ cho Dice đồng hiệu quả hay không.

=== Cũng ===

Nếu có một yếu tố trong tập A, và nếu ngưỡng của bạn là r (= 0,9), sau đó đặt B nên có số phần tử b nên được như vậy mà: r * a/(2-r) < = b < = (2-r) * a/r. Điều này sẽ loại bỏ nhu cầu cho rất nhiều so sánh IMHO. Bạn có thể sắp xếp các chuỗi theo chiều dài và sử dụng cửa sổ mô tả ở trên để giới hạn các so sánh.

Answer 2

Bộ ký tự của chúng có bị hạn chế không? Nếu có, bạn có thể tính số ký tự theo mã của chúng trong mỗi chuỗi và so sánh các số này. Sau khi tính toán trước (nó sẽ chiếm 2 * 900K * S byte bộ nhớ [nếu chúng ta giả sử không có ký tự nào được tìm thấy nhiều hơn thì thời gian 65K trong cùng một chuỗi], trong đó S là số ký tự khác nhau). Sau đó tính toán hệ số sẽ mất thời gian O (S). Chắc chắn, điều này sẽ hữu ích nếu S < 4500.

Answer 3

Thực hiện một lần vượt qua tất cả các chuỗi và xây dựng một HashMap ánh xạ từng bigram thành một tập hợp các chỉ mục của các Chuỗi chứa ký tự lớn đó. (Hiện tại bạn đang xây dựng khối lượng lớn được đặt 900.000 lần, dư thừa, cho mỗi Chuỗi.)

Sau đó thực hiện chuyển tất cả các tập hợp và xây dựng một HashMap của cặp [chỉ mục, chỉ mục] thành số đếm chung. (Bản đồ thứ hai không được chứa các cặp khóa thừa, như [1,2] và [2,1] - chỉ lưu trữ một hoặc hai khóa.)

Cả hai bước này có thể dễ dàng song song. Nếu bạn cần một số mã mẫu, vui lòng cho tôi biết.

CHÚ Ý một điều, mặc dù: từ 26 chữ cái trong bảng chữ cái tiếng Anh, tổng số 26x26 = 676 bigram có thể được tạo thành. Nhiều người trong số này sẽ không bao giờ hoặc gần như không bao giờ được tìm thấy, bởi vì họ không phù hợp với các quy tắc của chính tả tiếng Anh.Vì bạn đang xây dựng đặt của bigrams cho mỗi Chuỗi và các Chuỗi dài quá, có thể bạn sẽ tìm thấy hầu hết các bigram trong cùng một Chuỗi. Nếu bạn đã xây dựng danh sách của bigrams cho mỗi Chuỗi (nói cách khác, nếu tần suất của mỗi bigram được tính), có nhiều khả năng bạn thực sự có thể đo lường mức độ tương tự giữa các Chuỗi nhưng sau đó việc tính toán hệ số của Dice như được đưa ra trong bài viết trên Wikipedia sẽ không hoạt động; bạn phải tìm một công thức mới.

Tôi khuyên bạn nên tiếp tục nghiên cứu các thuật toán để xác định sự tương tự giữa các chuỗi, hãy thử triển khai một vài trong số chúng và chạy chúng trên một chuỗi nhỏ hơn để xem chúng hoạt động tốt như thế nào.

Answer 4

Tuyên bố từ chối trước: Điều này sẽ không giảm số lượng so sánh bạn sẽ phải thực hiện. Nhưng điều này sẽ làm cho một so sánh Dice nhanh hơn.

1) Không xây dựng HashSets của bạn mỗi khi bạn thực hiện cuộc gọi diceCoefficient()! Nó sẽ tăng tốc độ đáng kể nếu bạn chỉ làm điều đó một lần cho mỗi chuỗi và giữ kết quả xung quanh.

2) Vì bạn chỉ quan tâm nếu một bigram cụ thể là hiện tại trong chuỗi, bạn có thể lấy một BitSet với một bit cho mỗi bigram có thể, chứ không phải là HashMap đầy đủ. Tính toán hệ số sau đó sẽ được đơn giản hóa thành ANDing hai bộ bit và đếm số lượng các bit thiết lập trong kết quả. Hoặc, nếu bạn có một số lượng lớn các ký tự lớn có thể (Unicode, có lẽ?) - hoặc các chuỗi đơn điệu chỉ với một số lượng lớn các mảng lớn - một mảng sắp xếp các bigram có thể cung cấp các so sánh không gian hiệu quả hơn, nhanh hơn.