क्या कोई हैशिंग एल्गोरिदम है जो मामूली मतभेदों का सहिष्णु है?

मैं कुछ वेब क्रॉलिंग प्रकार की चीज़ें कर रहा हूं जहां मैं वेबपृष्ठों में कुछ शर्तों की तलाश कर रहा हूं और पेज पर अपना स्थान ढूंढ रहा हूं, और उसके बाद इसे बाद में उपयोग के लिए कैशिंग कर रहा हूं। मैं किसी भी बड़े बदलाव के लिए समय-समय पर पृष्ठ की जांच करने में सक्षम होना चाहता हूं। एमडी 5 की तरह कुछ पेज पर वर्तमान दिनांक और समय डालकर फॉइल किया जा सकता है।क्या कोई हैशिंग एल्गोरिदम है जो मामूली मतभेदों का सहिष्णु है?

कोई हैशिंग एल्गोरिदम कि कुछ इस तरह के लिए काम कर रहे हैं?

स्रोत

2011-04-13 Jason Baker

नहीं, यह सभी हैशिंग एल्गोरिदम का बिंदु है कि जब इनपुट केवल कुछ ही बदलता है तो वे _a lot_ बदलते हैं। – halfdan

@ अर्धदान - [विकिपीडिया आपके साथ असहमत होगा] (http://en.wikipedia.org/wiki/Hash_function#Finding_similar_records)। बहुत बुरा वे ध्वनिक फिंगरप्रिंटिंग के अलावा इस के लिए किसी भी एल्गोरिदम का उल्लेख नहीं करते हैं। –

[हैशिंग समानता] के संभावित डुप्लिकेट (http://stackoverflow.com/questions/4834301/hashing- समानता) –

दस्तावेज़ समानता करने के लिए एक आम तरीका है जो hashing की तुलना में कुछ अधिक शामिल है shingling है। दस्तावेज़ को विभाजित करने के तरीके के लिए सामग्री परिभाषित चंकिंग पर भी देखें।

मैं समानता का पता लगाने के लिए Bloom filters का उपयोग कर के बारे में कुछ साल पहले एक पत्र पढ़ें। Using Bloom Filters to Refine Web Search Results। यह एक दिलचस्प विचार है, लेकिन मैं इसके साथ प्रयोग करने के लिए कभी नहीं मिला।

स्रोत

2011-04-13 22:23:01

-4

मुझे खेद है, लेकिन हैश एल्गोरिदम ठीक हैं। मामूली मतभेदों के प्रति सहिष्णु होने में सक्षम कोई भी नहीं है। आपको एक और दृष्टिकोण लेना चाहिए।

स्रोत

2011-04-13 22:23:26

ठीक है, तो शायद इसे * एक हैशिंग एल्गोरिदम * नहीं कहा जाएगा। लेकिन ऐसा लगता है कि मैं जो खोज रहा हूं उसके बारे में कोई भ्रम नहीं है। केवल तभी इसे एक हैशिंग एल्गोरिदम कहा जाना चाहिए। –

मैंने अभी आपके प्रश्न का उत्तर दिया है। आपने पूछा "क्या कोई हैशिंग एल्गोरिदम है जो मामूली मतभेदों का सहिष्णु है?" और मैंने नहीं कहा। शायद आपको एक और बात पूछनी चाहिए थी। –

यह Levenshtein distance metric का उपयोग करने के लिए एक अच्छी जगह हो सकती है, जो एक अनुक्रम को दूसरे में बदलने के लिए आवश्यक संपादन की मात्रा को प्रमाणित करता है।

इस दृष्टिकोण का दोष यह है कि आप प्रत्येक पृष्ठ का पूरा पाठ रखने के लिए इतना है कि आप उन्हें बाद में की तुलना कर सकते आवश्यकता होगी है। दूसरी ओर, हैश-आधारित दृष्टिकोण के साथ, आप बस कुछ प्रकार के छोटे गणना वाले मूल्य को स्टोर करते हैं और तुलना के लिए पिछले पूर्ण पाठ की आवश्यकता नहीं होती है।

आप कुछ प्रकार के हाइब्रिड दृष्टिकोण भी आज़मा सकते हैं - एक हैशिंग एल्गोरिदम आपको बताएगा कि कोई भी बदलाव किया गया है, और इसे अधिक कठोर (लेवेनशेटिन) तुलना के लिए दस्तावेज़ की एक अभिलेखीय प्रति पुनर्प्राप्त करने के लिए ट्रिगर के रूप में उपयोग करें।

स्रोत

2011-04-13 23:38:01

http://www.phash.org/ छवियों के लिए कुछ इस तरह से किया था। जिस्ट: एक छवि लें, इसे धुंधला करें, इसे ग्रेस्केल में परिवर्तित करें, एक अलग कोसाइन ट्रांसफॉर्म करें, और परिणाम के ऊपरी बाएं चतुर्भुज को देखें (जहां महत्वपूर्ण जानकारी है)। फिर औसत से कम प्रत्येक मान के लिए 0 और औसत से अधिक प्रत्येक मान के लिए 1 रिकॉर्ड करें। परिणाम छोटे बदलावों के लिए बहुत अच्छा है।

मिन-हैशिंग एक और संभावना है। अपने पाठ में विशेषताओं को ढूंढें और उन्हें एक मान के रूप में रिकॉर्ड करें। हैश स्ट्रिंग बनाने के लिए उन सभी मानों को संयोजित करें।

ऊपर के दोनों के लिए, ताकि आप के पास हिट के लिए खोज कर सकते हैं एक सुविधाजनक मोरचा पेड़ का उपयोग करें।

स्रोत

2011-05-17 08:34:44 Eyal

क्या कोई हैशिंग एल्गोरिदम है जो मामूली मतभेदों का सहिष्णु है?

उत्तर

संबंधित मुद्दे