चोरी चोरी का पता लगाना - विनोइंग एल्गोरिदम - फिंगरप्रिंट टकराव

Question

मैं बड़ी टेक्स्ट फ़ाइलों में चोरी चोरी के लिए आवेदन लिखता हूं। इसके बारे में कई लेख पढ़ने के बाद मैंने Winnowing algorithm (कार्प-राबिन रोलिंग हैश फ़ंक्शन के साथ) का उपयोग करने का निर्णय लिया, लेकिन मुझे इसके साथ कुछ समस्याएं हैं।

डाटा:

मैं दो सरल पाठ फ़ाइलों है - पहला, एक बड़ा है दूसरा पहले एक से सिर्फ एक पैरा है।

प्रयुक्त एल्गोरिथ्म:

इस एल्गोरिथ्म जो मैं सभी हैश से मेरी उंगलियों के निशान का चयन करने के लिए प्रयोग किया जाता है।

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)); 
      } 
     } 
    } 
} 

इसके बाद, अगर हम मैं सिर्फ अगर हम मैच की जांच करने के दोनों textes से उंगलियों के निशान की तुलना दोनों फ़ाइलों में टेक्स्ट समान है पता लगाने के लिए। इसलिए साहित्य चोरी का पता लगाने के लिए, एल्गोरिदम को हैश लेना है जो पाठ में एक ही स्थान पर ठीक से शुरू होगा, उदाहरण के लिए:

टेक्स्ट 1: ए रन रन | टी^उसकी मेरी जांच करें।

टेक्स्ट 2: मेरा ब्लैक लॉल | टी^उसका मेरा दास चिकन।

सही हैश प्राप्त करने के लिए, जिसमें समान मूल्य होंगे (जिसका अर्थ यह भी है कि हमारे पास एक ही पाठ है), एल्गोरिदम को उन स्थानों से फिंगरप्रिंट लेना चाहिए जिन्हें मैंने '|' या '^' (मुझे लगता है कि हम स्पेस के बिना हैश की गणना करने के लिए 5 वर्ण लेते हैं)। यह '|' से हैश नहीं ले सकता टेक्स्ट 2 में टेक्स्ट 1 और '^' में क्योंकि इन दो हैंश अलग होंगे और साहित्य चोरी का पता नहीं लगाया जाएगा।

समस्या: अगर यह अनुच्छेद पाठ संख्या 1 से कॉपी किया गया था मैं दो ही उंगलियों के निशान के लिए है, दोनों ग्रंथों में कहीं

पता लगाने के लिए। समस्या एल्गोरिदम चुनती है कि फिंगरप्रिंट, जो एक दूसरे के साथ फिट नहीं होते हैं, मेरा मतलब है कि वे बहुत बड़े ग्रंथों में भी याद करते हैं।

प्रश्न:

आप किसी भी विचार कैसे मैं इस एल्गोरिथ्म (जो वास्तव में उंगलियों के निशान takin के एल्गोरिथ्म सही करने के लिए नीचे लाता है) सुधार कर सकते हैं मिल गया है, कि यह plagiarisms पाने की अधिक संभावना होगी?

मेरे विचार:

मैं रन के बारे में सोचा समारोह दो बार फटकना, अलग विंडो आकार के लिए (जो कारण होगा कि विभिन्न हैश लिया जाएगा), लेकिन बड़े ग्रंथों के लिए, जिस पर इस कार्यक्रम काम करना होगा (2 एमबी बस पाठ की तरह) इसमें बहुत अधिक समय लगेगा।

Answer 1

यदि आपके पास हैश पर कंप्यूटिंग करने वाली विंडो चल रही है, तो आप खिड़की की चाल के दौरान निरंतर समय में हैश मान अपडेट कर सकते हैं। विधि Rabin fingerprint (see also) कहा जाता है। यह आपको ओ (एन) रनिंग समय में आकार एक्स के सभी फिंगरप्रिंट की गणना करने की अनुमति दे सकता है (एन इनपुट दस्तावेज़ का आकार है)। मुझे लगता है कि आपके द्वारा उद्धृत पेपर इस विधि का कुछ उन्नत विस्तार है और जब सही ढंग से कार्यान्वित किया जाता है तो आपको भी एक समान चलने वाला समय देना चाहिए। हैश को अद्यतन करने के लिए कुंजी को पुन: सम्मिलित करना है।