मिलान निकटतम फ़ाइल फ़ाइलें

Question

समस्या:

मैं करीब 20 ASCII पाठ फ़ाइलें, जिनमें से प्रत्येक का एक आकार कम से कम 10^9 बाइट्स .Another ASCII पाठ फ़ाइल (FOO कहते हैं) दिया जाता है । कार्यक्रम रणनीतिक रूप से दी गई 20 फाइलों के साथ खाद्य पदार्थों की सामग्रियों से मेल खाता है और अंतिम मिलान फ़ाइल का नाम प्रिंट करता है। फूड की सामग्री केवल आंशिक रूप से मिल सकती है।

के बाद से फ़ाइल आकार बहुत बड़ा है, मैं सोच रहा हूँ:

1.How सूचना पुनर्प्राप्ति उपयोग करने के लिए (के बाद से मैं आईआर के बारे में ज्यादा पता नहीं है)

2.which डेटा संरचना मैं का उपयोग करना चाहिए ऐसी जानकारी स्टोर करने के लिए

3. इसे लागू करने के लिए सबसे अच्छा एल्गोरिदम क्या होगा।

मुझे पता है कि मैं बहुत ज्यादा पूछ रहा हूं, लेकिन वास्तव में मैं इस समस्या पर फंस गया हूं और यह जानने में सक्षम नहीं हूं कि कैसे पहुंचे। किसी भी मदद की सराहना की जाएगी। धन्यवाद!

Answer 1

तो मुझे लगता है कि एक फ़ाइल में कुछ टेक्स्ट है। तो हम कह सकते हैं कि फ़ाइल में से प्रत्येक एक बड़ी स्ट्रिंग है। अब 20 वैक्टर या सरणी बनाओ। फ़ाइल के माध्यम से जाओ और वेक्टर में प्रत्येक शब्द को तत्व के रूप में रखें। अब प्रत्येक फ़ाइल के मिलान को स्टोर करने के लिए 20 के आकार वाले वैक्टर बनाएं, अब दिए गए फ़ाइल के लिए एक शब्द वेक्टर बनाएं। अब इन वैक्टरों के माध्यम से चलाने के लिए एक लूप बनाएं यदि किसी दिए गए इंडेक्स में आपको इनमें से किसी भी 20 वैक्टर और आपके दिए गए वैक्टर के साथ एक मैच मिला है। मैच भंडारण वैक्टर में संबंधित फ़ाइल के लिए मूल्य बढ़ाएं। अंत में, वेक्टर भंडारण मैच में उच्चतम मूल्य फ़ाइल को सर्वश्रेष्ठ मैच के साथ इंगित करेगा।

Answer 2

पिशाच कोडर द्वारा समाधान मानता है कि दस्तावेज़ शब्दों के बैग हैं, जिसका अर्थ है शब्दों का क्रम कोई फर्क नहीं पड़ता। लेकिन "आंशिक रूप से मिलान" से, आप कुछ वाक्य मिलान का मतलब रखते हैं, तो यह कोई अच्छा नहीं करेगा।

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

प्रत्येक दस्तावेज़ के लिए, एक बार जब आप संभावित मैचों को कम कर देते हैं, तो आप उस संकल्प को बढ़ा सकते हैं जिस पर आप अपने दस्तावेज़ों को विभाजित करते हैं। मान लें कि आपने शुरुआत में उन्हें दो में बांटा है, अब आप उन्हें 10 में विभाजित कर सकते हैं। यह चलने वाले समय को कम करना है।

इसके अलावा, आप की तरह इलाके संवेदनशील हैशिंग एल्गोरिथ्म का उपयोग करना चाहिए: "निकटतम" पर http://en.wikipedia.org/wiki/Nilsimsa_Hash

Answer 3

मेरा अनुमान है, 2 फ़ाइलों के बीच सबसे छोटा diff के साथ फ़ाइल है।

मैं एक diff एल्गोरिथ्म के लिए विचार करेंगे, या सबसे लंबे समय तक आम subsequence https://en.m.wikipedia.org/wiki/Longest_common_subsequence_problem