क्या राबिन-कार्प स्ट्रिंग खोज एल्गोरिदम में उपयोग किए जाने वाले रोलिंग हैश फ़ंक्शन का कोई कामकाजी कार्यान्वयन है?

Question

मैं रोलिंग हैश फ़ंक्शन का उपयोग करने के लिए देख रहा हूं, इसलिए मैं बहुत बड़ी स्ट्रिंग के एन-ग्राम के हैंश ले सकता हूं।

"stackoverflow", 5 ग्राम में टूट किया जाएगा:

उदाहरण के लिए

"ढेर", "Tacko", "ackov", "ckove", "kover", "overf", "verfl", "erflo", "rflow"

यह एक रोलिंग हैश फंक्शन के लिए आदर्श है क्योंकि के बाद मैं पहली बार एन-ग्राम हैश की गणना, निम्नलिखित लोगों क्योंकि मैं गणना करने के लिए अपेक्षाकृत सस्ती हैं बस पहले हैश के पहले अक्षर को छोड़ना है और जोड़ना है दूसरे हैश का नया अंतिम पत्र।

मुझे पता है कि सामान्य रूप में इस हैश समारोह उत्पन्न होता है के रूप में:

एच = ग एक ^{कश्मीर - 1} + स एक ^{कश्मीर - 2} + स एक ^{के - 3} + ... + सी _के जहां एक स्थिर और सी 1 है, ..., सीके इनपुट वर्ण हैं।

यदि आप Rabin-Karp string search algorithm पर इस लिंक का पालन करते हैं, तो यह कहता है कि "ए" आमतौर पर कुछ बड़ा प्रधान होता है।

मैं चाहता हूं कि मेरे हैंश को 32 बिट पूर्णांक में संग्रहीत किया जाए, तो एक प्रमुख को कितना बड़ा होना चाहिए, जैसे कि मैं अपने पूर्णांक को ओवरफ़्लो नहीं करता?

क्या इस हैश फ़ंक्शन का मौजूदा कार्यान्वयन कहीं भी मौजूद है जिसका मैं पहले से उपयोग कर सकता हूं?

public class hash2 
{ 

    public int prime = 101; 

    public int hash(String text) 
    { 
     int hash = 0; 

     for(int i = 0; i < text.length(); i++) 
     { 
      char c = text.charAt(i); 
      hash += c * (int) (Math.pow(prime, text.length() - 1 - i)); 
     } 

     return hash; 
    } 

    public int rollHash(int previousHash, String previousText, String currentText) 
    { 

     char firstChar = previousText.charAt(0); 
     char lastChar = currentText.charAt(currentText.length() - 1); 

     int firstCharHash = firstChar * (int) (Math.pow(prime, previousText.length() - 1)); 
     int hash = (previousHash - firstCharHash) * prime + lastChar; 

     return hash; 
    } 

    public static void main(String[] args) 
    { 
     hash2 hashify = new hash2(); 

     int firstHash = hashify.hash("mydog"); 
     System.out.println(firstHash); 
     System.out.println(hashify.hash("ydogr")); 
     System.out.println(hashify.rollHash(firstHash, "mydog", "ydogr")); 
    } 

} 

मैं अपने प्रधानमंत्री के रूप में 101 का उपयोग कर रहा:

---

यहाँ एक कार्यान्वयन मैं बनाया है। क्या इससे कोई फर्क पड़ता है कि मेरे हैंश बह जाएंगे? मुझे लगता है कि यह वांछनीय है लेकिन मुझे यकीन नहीं है।

क्या यह इस बारे में जाने का सही तरीका प्रतीत होता है?

Answer 1

के रूप में मैं समझता हूँ इसके लिए एक समारोह न्यूनतम है:

2^31 - sum (maxchar) * A^kx 

जहां maxchar = 62 (A-Za-z0-9 के लिए)। मैंने अभी इसे एक्सेल (ओओ कैल्क, बिल्कुल) द्वारा गणना की है :) और एक अधिकतम संख्या यह 76, या 73 है, जो एक प्रमुख संख्या के लिए है।

Answer 2

मुझे थोड़ा अलग कार्यान्वयन याद है जो कि सेडगेविक की एल्गोरिदम किताबों में से एक है (इसमें उदाहरण कोड भी शामिल है - इसे देखने का प्रयास करें)। यहां 32 बिट पूर्णांक में समायोजित सारांश है:

आप प्रत्येक ऑपरेशन के बाद अपने पूर्णांक को बहने से रोकने के लिए मॉड्यूलो अंकगणित का उपयोग करते हैं।

शुरू में सेट करें:

• c = पाठ ("stackoverflow")
• एम = "एन-ग्राम"
• घ की लंबाई = अपने वर्णमाला के आकार (256)
• क्ष = एक बड़ी प्रधानमंत्री ताकि (घ +1) * क्ष अतिप्रवाह नहीं करता है (8,355,967 एक अच्छा विकल्प हो सकता है)
• dM = घ ^{एम -1} आधुनिक क्ष

पहले पहली n ग्राम के हैश मूल्य की गणना:

h = 0 
for i from 1 to M: 
    h = (h*d + c[i]) mod q 

और हर निम्नलिखित एन-ग्राम के लिए:

for i from 1 to lenght(c)-M: 
    // first subtract the oldest character 
    h = (h + d*q - c[i]*dM) mod q 

    // then add the next character 
    h = (h*d + c[i+M]) mod q 

कारण है कि आप को घटाकर पहले d * क्ष जोड़ने के लिए सबसे पुराना चरित्र इसलिए है क्योंकि पिछले मॉड्यूलो ऑपरेशन के कारण छोटे मूल्यों के कारण आप नकारात्मक मूल्यों में भाग ले सकते हैं।

त्रुटियों में शामिल थे, लेकिन मुझे लगता है कि आपको विचार प्राप्त करना चाहिए। विवरण, कम त्रुटियों और बेहतर विवरण के लिए sedgewick की एल्गोरिदम किताबों में से एक को खोजने का प्रयास करें। :)

Answer 3

सुनिश्चित नहीं है कि आपका उद्देश्य क्या है, लेकिन यदि आप प्रदर्शन सुधारने की कोशिश कर रहे हैं, तो math.pow का उपयोग करके आप रोलिंग हैश मान की गणना करके बचत से कहीं अधिक खर्च करेंगे।

मेरा सुझाव है कि आप सरल और कुशल रखकर शुरू करें और आपको लगता है कि यह पर्याप्त तेज़ है।