Cách tính hiệu quả tương tự cosin giữa hàng triệu chuỗi

Question

Tôi cần tính toán độ tương tự cosin giữa các chuỗi trong một danh sách. Ví dụ, tôi có một danh sách hơn 10 triệu chuỗi, mỗi chuỗi phải xác định sự giống nhau giữa chính nó và mọi chuỗi khác trong danh sách. Thuật toán tốt nhất mà tôi có thể sử dụng để thực hiện tác vụ đó hiệu quả và nhanh chóng như thế nào? Thuật toán phân chia và chinh phục có được áp dụng không?

EDIT

Tôi muốn xác định chuỗi là giống nhất với một chuỗi nhất định và có thể có một biện pháp/số điểm liên quan đến sự tương đồng. Tôi nghĩ rằng những gì tôi muốn làm rơi phù hợp với clustering nơi số lượng các cụm không được biết ban đầu.

Answer 1

Làm việc với ma trận transposed. Đó là những gì Mahout thực hiện trên Hadoop để thực hiện loại công việc này nhanh chóng (hoặc chỉ sử dụng Mahout).

Về cơ bản, tính toán độ tương đồng của cosin cũng rất tệ. Bởi vì bạn kết thúc tính toán rất nhiều 0 * một cái gì đó. Thay vào đó, bạn làm việc tốt hơn trong các cột và để lại tất cả 0 ở đó.

Answer 2

Bạn có thể thử SimString.

Đây là thư viện C++ (có gắn kết Python hoặc Ruby) để đối sánh chuỗi gần đúng.

Tuyên bố tìm các chuỗi có độ tương tự cosin cao dưới 1 mili giây cho cơ sở dữ liệu là 13 triệu chuỗi.

Thuật toán được sử dụng được mô tả here dựa trên việc cắt tỉa danh sách ngược.