Tôi viết ứng dụng phát hiện đạo văn trong các tệp văn bản lớn. Sau khi đọc nhiều bài viết về nó, tôi quyết định sử dụng Winnowing algorithm (với hàm băm Karp-Rabin), nhưng tôi có một số vấn đề với nó.Phát hiện đạo văn - thuật toán chiến thắng - dấu vân tay xung đột
dữ liệu:
Tôi có hai tập tin văn bản đơn giản - đầu tiên là lớn hơn một, thứ hai là chỉ một đoạn từ đầu tiên.
đã qua sử dụng thuật toán:
Đây là thuật toán mà tôi sử dụng để chọn dấu vân tay của tôi từ tất cả băm.
void winnow(int w /*window size*/) {
// circular buffer implementing window of size w
hash_t h[w];
for (int i=0; i<w; ++i) h[i] = INT_MAX;
int r = 0; // window right end
int min = 0; // index of minimum hash
// At the end of each iteration, min holds the
// position of the rightmost minimal hash in the
// current window. record(x) is called only the
// first time an instance of x is selected as the
// rightmost minimal hash of a window.
while (true) {
r = (r + 1) % w; // shift the window by one
h[r] = next_hash(); // and add one new hash, if hash = -1, then it's end of file
if(h[r] == -1)
break;
if (min == r) {
// The previous minimum is no longer in this
// window. Scan h leftward starting from r
// for the rightmost minimal hash. Note min
// starts with the index of the rightmost
// hash.
for(int i=(r-1)%w; i!=r; i=(i-1+w)%w)
if (h[i] < h[min]) min = i;
record(h[min], global_pos(min, r, w));
} else {
// Otherwise, the previous minimum is still in
// this window. Compare against the new value
// and update min if necessary.
if (h[r] <= h[min]) { // (*)
min = r;
record(h[min], global_pos(min, r, w));
}
}
}
}
Tiếp theo, để phát hiện nếu chúng ta có cùng một văn bản trong cả hai tập tin tôi chỉ so sánh dấu vân tay từ cả hai textes để kiểm tra xem chúng tôi có trận đấu. Vì vậy, để phát hiện đạo văn, thuật toán phải lấy băm sẽ bắt đầu chính xác ở cùng một vị trí trong văn bản, ví dụ:
Text1: A do run | t^kiểm tra của tôi.
Text2: bla của tôi lol gà tía của tôi.
Để nhận các giá trị băm chính xác, giá trị này sẽ có cùng giá trị (cũng có nghĩa là chúng tôi có cùng văn bản), thuật toán sẽ lấy dấu vân tay từ những địa điểm mà tôi chỉ bởi '|' hoặc '^' (tôi giả định rằng chúng tôi lấy 5 ký tự để tính toán băm, không có dấu cách). Nó không thể lấy băm từ '|' trong văn bản 1 và '^' trong văn bản 2 vì hai băm này sẽ khác nhau và đạo văn sẽ không được phát hiện.
Vấn đề:
Để phát hiện nếu đoạn này đã được sao chép từ số văn bản 1 tôi phải có hai dấu vân tay cùng, ở đâu đó trong cả hai văn bản. Vấn đề là thuật toán chọn dấu vân tay, mà không phù hợp với nhau, tôi có nghĩa là họ chỉ bỏ lỡ, ngay cả trong các văn bản lớn hơn nhiều.
Câu hỏi:
Các bạn có bất kỳ ý tưởng làm thế nào tôi có thể cải thiện thuật toán này (mà thực sự mang xuống để sửa thuật toán của takin dấu vân tay), rằng nó sẽ có khả năng hơn trong việc tìm kiếm plagiarisms?
những suy nghĩ của tôi:
Tôi nghĩ về chạy vỗ vài chức năng lần, cho kích thước cửa sổ khác nhau (mà sẽ gây ra điều đó băm khác nhau sẽ được thực hiện), nhưng đối với các văn bản lớn mà chương trình này sẽ phải làm việc (như 2MB chỉ văn bản) điều này sẽ mất quá nhiều thời gian.
Thuật toán này (ví dụ mã của bạn) có thực sự hoạt động không?Tôi có giấy từ Schleimer và những người khác bao gồm mã này nhưng tôi không thể sử dụng nó để nhân rộng các kết quả trong bài báo. Bạn có chắc chắn thuật toán này thực sự đang làm những gì bạn mong đợi? –
@MadCompSci - vâng. Tôi đã thực hiện ứng dụng của mình và nó đã hoạt động. – Blood