मैं सॉफ्टवेयर का एक टुकड़ा विकसित कर रहा हूं जिसे डुप्लिकेट छोटे टेक्स्ट की जांच करने की आवश्यकता है (आमतौर पर 2 केबी से कम) का उपयोग करते हुए पूर्व-गणना हस्ताक्षर (4bytes)। वर्तमान में, मैंने सीआरसी 32 (4byte) को कार्यान्वित किया हैइस उद्देश्य को प्राप्त करें लेकिन मुझे संदेह है कि सीआरसी 32 बहुत सारे नकल मूल्य उत्पन्न करेगा। मुझे पता है कि यह वास्तव में अद्वितीय बनाना असंभव है लेकिन कम से कम मैं इस संभावना को कम करना चाहता हूं।
- अद्यतन 1 -
ध्यान दें: मैं हैश बाइट्स के आकार में वृद्धि नहीं कर सकता। यह मुझे बहुत भंडारण खर्च करता है। मैं 1,000,000 से अधिक प्रविष्टियों के आकार के बारे में बात कर रहा हूं। उदाहरण के लिए 1,000,000 * 4 बाइट = 4,000,000 बाइट्स। मैं एमडी 5 का उपयोग नहीं कर सकता क्योंकि इसमें 16 बाइट्स लगते हैं!
- अद्यतन 2 - मैं पूरी समस्या नहीं खोलना चाहता था लेकिन अब मुझे यह करना है।
मेरा प्रोजेक्ट एक शब्दकोश इंजन है जो खोज सकता हैउपयोगकर्ताओं को "पूछे जाने वाले वाक्यांश" को खोजने के लिए बहुत से स्वतंत्र डेटाबेस। सभी परिणाम तत्काल तैयार किए जाने चाहिए (ऑटो-पूर्ण सुविधा)। सभी टेक्स्ट डेटा संपीड़ित किए गए हैं, इसलिए मैं डुप्लीकेट परिणामों की जांच करने के लिए उन्हें डिकंप्रेस नहीं कर सकता। मुझे हैश मानों को स्टोर करना होगा मेरे में संपीड़ित पाठ सूची। तो हैश बाइट इंडेक्स आकार बढ़ाते हैं और डिस्क I / O इंडेक्स ब्लॉक को पढ़ने, डीकंप्रेस और डीकोड करने के लिए(सूचकांक ब्लॉक भी संपीड़ित है)। हैश मान आम तौर पर अप्र-संपीड़ित होते हैं। इस सॉफ़्टवेयर के डिज़ाइन ने मुझे उपयोगकर्ता की ज़रूरतों को पूरा करने के लिए सब कुछ संपीड़ित करने के लिए मजबूर किया (इनका उपयोग करना एम्बेडेड सिस्टम)। अब, मैं हैश मानों का उपयोग करके खोज परिणाम से डुप्लिकेट टेक्स्ट को हटाना चाहता हूं (अन) संपीड़ित पाठ तुलना (जो डिस्क I / O के कारण मेरे मामले में अनुचित है)।
ऐसा लगता है कि हम एक कस्टम चेकसम डिजाइन कर सकते हैं जो शर्तों को पूरा करता है। उदाहरण के लिए, मैं दो बाइट्स में टेक्स्ट लम्बाई संग्रहीत करता हूं और डुप्लिकेट संभावना की जांच के लिए 2-बाइट चेकसम उत्पन्न करता हूं?
मैं अग्रिम में किसी भी सुझाव की सराहना करता हूं।
- अद्यतन 3 -
बहुत सारी जांच के बाद और उत्तर द्वारा प्रदान की जाने वाली जानकारी का उपयोग करने के बाद, आप सभी को धन्यवाद, मैंने पाया CRC32 मेरे मामले में काफी अच्छा है। डुप्लिकेट मानों की जांच करने के बाद, मैंने अपने जेनरेट किए गए सीआरसी पर कुछ सांख्यिकीय मानक चलाए, परिणाम संतोषजनक था।
आप सभी को धन्यवाद।
मैं सभी उत्तरों को अप-वोट दूंगा।
उत्तर:
जवाब के लिए 3 № 1के बारे में और जानकारी के बिना small text, सर्वोत्तम है कि आप प्रत्येक हैश मान के लिए उम्मीद कर सकते हैंसमान रूप से संभावित, और 2³² 4-ऑक्टेट-मूल्यों का अधिकांश उपयोग किया जाता है। फिर भी, आप लगभग 77000 ग्रंथों के साथ टकराव नहीं होने की अपेक्षा अधिक संभावना रखते हैं, अकेले अकेले रहने दें। कुछ अपवादों के साथ (एडलर 32 दिमाग में आ रहा है), प्रसिद्ध हैश फ़ंक्शन टकराव की संभावना में बहुत कम हैं। (वे उद्देश्यों पर टकराव / दिए गए मान, और गणना / सर्किट लागत में उत्पादन करने में कठिनाई में भिन्न हैं।)
→ टकराव की संभावना और भंडारण आवश्यकताओं के बीच समझौता करें।
आसानी से गणना की गई चेकसम के लिए, एक नज़र डालें फ्लेचर "रों - Adler32 बहुत समान है, लेकिन कम इनपुट के साथ एक टक्कर संभावना बढ़ गई है।
उत्तर № 2 के लिए 1
यदि आप हैश टक्कर में आते हैं तो आपको करना होगाजांचें कि पाठ बराबर है या नहीं। सबसे अच्छा तरीका यह समझना होगा कि टकराव होने के कितने समय में कुछ आंकड़े होते हैं और यदि यह खराब अनुकूलन दिखता है। मुझे यह विचार मिला कि आप 2 अलग हैश मान क्रैक 32 और एमडी 5 (या लुहान या जो कुछ भी आपको पसंद करते हैं) का निर्माण कर सकते हैं और केवल समानता की जांच करें यदि दोनों हैंश के समान मूल्य हैं।
उत्तर № 3 के लिए 1
मैंने अपनी परियोजनाओं में से एक में कुछ ऐसा ही किया। मेरी परियोजना में मैंने कुछ कहा था ब्लूम फिल्टर , घड़ी यहां पूरी चीज और इसे कार्यान्वित करने के बारे में, ब्लूम फ़िल्टर की संभावना कम हो जाती है हश कॉलेज कई हैशिंग के उपयोग के लिए बड़े पैमाने पर धन्यवादएल्गोरिदम (हालांकि, केवल एक हैशिंग फ़ंक्शन का उपयोग करके कई हैश फ़ंक्शंस को अनुकरण करना संभव है लेकिन यह कि हम यहां क्या हैं।) .. इसे आज़माएं !! यह मेरे लिए काम करता है और आपके लिए भी काम करेगा
एक ब्लूम फ़िल्टर का एक वास्तविक कामकाजी कार्यान्वयन