किसी सर्वर पर डेटा (संभवतः JSON) के diffs को कैसे दबाया जाए?

Question

मैं समय-समय पर वेब-पेज से पर एक सर्वर, जो JSON के रूप में पाठ-आधारित डेटा का एक सेट दबा रहा हूं।

प्रत्येक धक्का के लिए, कोई नहीं, कुछ या सभी डेटा बदल सकते हैं। तार पर भेजने के लिए मुझे कितनी मात्रा में डेटा भेजना है, मैं केवल प्रत्येक धक्का में बदलावों का एक अंतर भेजना चाहता हूं।

आप किसी भी पूर्व निर्मित समाधान/उपकरण/पुस्तकालयों इस बात का पता है:

• गतिशील रूप से JSON के एक diff निर्माण के रूप में परिवर्तन यह (करने के लिए बना रहे हैं oldJson और newJson भंडारण और एक पूर्ण कर से बचने के लिए प्रत्येक धक्का को अलग करें) यानी क्लाइंट-साइड के लिए लिखा गया है (यानी क्लाइंट-साइड के लिए)
• जेएसओएन के मौजूदा हिस्से को जेएसओएन diff सर्वर साइड पर पैच करें, जो किसी भी प्लेटफॉर्म पर लिखा गया है जो जावा या .NET^(ज़रूरत नहीं है) लिनक्स पर चलाने के लिए, जावा एनवी के लिए एक विकल्प नहीं है, न ही मोनो है)।

इसके अलावा, क्या यह इस विशेष समस्या के बारे में जाने का सबसे अच्छा तरीका भी है? क्या टेक्स्ट डेटा के हिस्सों को धक्का देने का कोई बेहतर तरीका है?

संपादित करें: कुछ स्पष्टीकरण:

• संभावित डेटा संरचना मूल रूप से एक काफी फ्लैट होगा (इस अर्थ में कि यह hightly कनेक्ट हो, तो किसी भी लिंक आईडी के आधार पर संदर्भ हो जाएगा में नहीं वास्तविक नेस्टेड डेटा) नोड्स का संग्रह। नोड्स में पेड़ों का संग्रह होता है, इन पेड़ों की पत्तियों में वास्तविक 'मूल' डेटा होता है, जैसे संख्याएं, तार और आईडी। अधिकांश डेटा परिवर्तन पत्तियों में होगा।
  • अधिकांश पत्ते का डेटा बहुत छोटा होगा (मूल या पाठ के अनुच्छेद से कम) लेकिन कुछ बहुत लंबे होंगे ("समृद्ध" पाठ के पृष्ठ)।
• इस पल के लिए हम इसे सख्ती से एक-दूसरे पर विचार कर सकते हैं, यानी किसी भी विशेष डेटा संरचना में केवल एक क्लाइंट जुड़ा हुआ है (पढ़ने/लिखने में)।
• जटिलता के मामले में सर्वर को यथासंभव न्यूनतम रखना अच्छा लगेगा - विचार है कि जितना संभव हो सके सर्वर से दूर जाना। एचटीएमएल 5 अभी भी ज्यादातर असमर्थित है जबकि मैं अभी भी एक यद्यपि के साथ डाटा स्टोर करने की जरूरत है ...

^ यह हुआ कि यदि यादृच्छिक साझा होस्टिंग पर उम्मीद करेंगे। मैं आपके अच्छे दोस्तों PHP, पायथन, पर्ल, रुबी, उन फुलस से बात कर रहा हूं। या, कुछ ऐसा जो यादृच्छिक साझा होस्टिंग पर आसानी से स्थापित किया जा सकता है।

Answer 1

यह कुछ ऐसा है जो मैं भी साथ संघर्ष कर रहा हूं। अगर किसी और को मेरा तुलना में एक बेहतर जवाब प्रदान करता है मैं गौर से दिलचस्पी होगी, लेकिन कुछ समय के लिए ...

पहले, वहाँ है http://www.xn--schler-dya.net/blog/2008/01/15/diffing_json_objects/

मैं व्यक्तिगत रूप से काम करने के लिए इस पुस्तकालय प्राप्त करने में सक्षम नहीं किया गया , लेकिन आपका मिलेज भिन्न हो सकता है।

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

diff की कोशिश करने से पहले अगला स्टॉप, परिवर्तनों को ट्रैक करने वाले "प्राप्त करें", "सेट" और "हटाएं" विधियों में अपना डेटा एक्सेस लपेटकर है। आपके द्वारा तार पर भेजे गए डेटा अनिवार्य रूप से इन विधि के उपयोग का अनुक्रमिक लॉग होगा, जिसे आप प्रत्येक सफल संचरण पर ग्राहक पक्ष से फ़्लश करते हैं। सर्वरसाइड पर आप इस लॉग को अपने सर्वर एक्सेस डेटा पर सर्वर डेटा एनालॉग के साथ अपने डेटा एक्सेस विधियों पर लागू करते हैं। यह एक भिन्नता से थोड़ा हल्का समाधान है जिसे काफी प्रोसेसिंग पावर की आवश्यकता नहीं होती है।

अंत में, यदि आप diff करने जा रहे हैं, तो सबसे प्रभावी तरीका मैं सोच सकता हूं कि यदि आप अपने डेटासेट को अलग-अलग "भाग" में विभाजित कर सकते हैं, प्रत्येक एक अद्वितीय आईडी के साथ। फिर जब आप diff चलाते हैं, तो diff का courseness बिल्कुल "खंड" स्तर पर है। यही है, केवल एक ही तुलना जो आप करेंगे आईडी आईडी के लिए है। यदि आप एक हिस्सा बदलते हैं, तो इसे एक नई आईडी दें। Courser आप diff एल्गोरिदम बनाने के लिए बर्दाश्त कर सकते हैं, कम समय में चलाने के लिए ले जाएगा।

वैकल्पिक रूप से, परिवर्तन पर एक नई आईडी निर्दिष्ट करने के बजाय, आप यह जांचने के लिए diff चला सकते हैं कि कोई विशिष्ट ऑब्जेक्ट "बदल गया" है, जैसे ही आप एक परिवर्तन का पता लगाते हैं, और बस उस खंड को फिर से चिह्नित करें एक ही आईडी के साथ सर्वर पक्ष पर खंड को अद्यतन करने के लिए, इसकी entirity में। यदि आपके पास अपने हिस्से के लिए कुछ प्रकार का त्वरित हैशिंग एल्गोरिदम है, तो इसे और भी अधिक कुशल बनाया जा सकता है जिसका उपयोग आप समानता को जल्दी से स्थापित करने के लिए कर सकते हैं।

यदि आपके हिस्सों का अनुक्रम कोई फर्क नहीं पड़ता है, या यदि आप भाग के भौतिक अनुक्रम द्वारा मॉडलिंग के बजाय अनुक्रम को स्वयं की संपत्ति के रूप में संग्रहीत कर सकते हैं, तो आप आईडी द्वारा अपने हिस्सों को भी कुंजी दे सकते हैं । फिर मतभेदों की खोज करना ऑब्जेक्ट ए की चाबियों को सूचीबद्ध करने का विषय है, और उन्हें ऑब्जेक्ट बी, और फिर वाइस वर्सा पर देखना है। यह "वास्तविक" diff एल्गोरिदम की तुलना में लागू करने के लिए बहुत आसान है, इसमें ओ (ए + बी) प्रदर्शन है जो (मुझे लगता है) वास्तविक diff एल्गोरिदम के लिए सबसे खराब स्थिति परिदृश्य से बेहतर है, जो आपको मिलने की संभावना है इसे स्वयं लागू करने की कोशिश कर रहे हैं, या खराब कार्यान्वयन प्राप्त कर रहे हैं।

Answer 2

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

Answer 3

कहीं भी एक ग्रेड थासिस है, एक समाधान खोजने के लिए जो "नया क्या है" का एक कुशल संचरण है और जो वेब आर्किटेक्चर (सर्वर पर न्यूनतम मात्रा में राज्य को कैश करना और सहेजना) के साथ अच्छा खेलता है।

मैं उत्सुक हूं कि वहां क्या है; मैं इस सवाल के साथ झुका रहा हूं, ब्रेटन के जवाब में "खंड" विचार थोडा है जहां मैं जा रहा हूं, लेकिन यह सुनिश्चित नहीं करता कि कैसे।

संपादित करें: प्रतीक्षा करें - मुझे यह पिछला मिला है, मैंने सोचा था कि आप क्लाइंट को भेजने के लिए सर्वर की गणना करने वाले सर्वर के बारे में बात कर रहे थे।

शायद आप अस्पष्ट विवरण में सर्वर पर भेजे गए क्लाइंट पर डेटा की संरचना का वर्णन कर सकते हैं।यदि संभव हो तो मैं जेएसओएन पाठ के आधार पर ऐसा नहीं करूँगा; जावास्क्रिप्ट के भीतर से अंतर करें। यदि यह ज्ञात संरचना वाले आइटमों की एक सूची है, तो ट्रैक करें कि आपने सर्वर पर कौन से भेजे हैं और बाकी भेज दें। यदि यह एक अधिक जटिल डेटासेट है, तो सुनिश्चित करें कि आपकी मदद कैसे करें।

Answer 4

EtherPad प्रत्येक स्रोत परिवर्तन को गणितीय ऑपरेशन में बदलकर ऐसा कुछ हल किया जो कम्यूटिव, सहयोगी आदि हो सकता है। मैं इसे एक गैर-मामूली समस्या मानता हूं, हालांकि, और ईथरपैड समाधान के आसपास एक व्यवसाय बनाने में सक्षम था इस समस्या के लिए।

संपादित करें: दिलचस्प रूप से पर्याप्त, यह वास्तव में समस्या है कि एक अच्छा DVCS जैसे गिट tackles, बस ब्राउज़र पर नहीं।

Answer 5

आज मैं दो जेएस ऑब्जेक्ट्स के बीच एक अंतर कर एक छोटी jQuery प्लगइन प्रकाशित करता हूं। http://plugins.jquery.com/project/jquery-diff

मैं इसे सर्वर बैकएंड को केवल संशोधित डेटा भेजने के लिए एक एप्लिकेशन में उपयोग करता हूं।

Answer 6

यह जेएसओएन जागरूक नहीं है, लेकिन डॉक्स के लिए Google का उपयोग करने की विधि (उपर्युक्त ईथरपैड समस्या का उनका संस्करण) है।

http://code.google.com/p/google-diff-match-patch/

यह JSON यह जानकारी नहीं होगी, लेकिन यह आप जावास्क्रिप्ट में एक कुशल diff क्लाइंट साइड उत्पन्न करने की अनुमति होगी, और सर्वर लागू यह एक उचित कार्यान्वयन (जावा, जावास्क्रिप्ट, सी ++ का उपयोग कर, सी #, उद्देश्य सी, लुआ, या पायथन)।

एक और सवाल करने के लिए इस सवाल का जवाब गूगल-diff मैचों की पैच का एक संशोधित संस्करण के बारे में विशेष रूप से भाग उपयोगी हो सकता है,: Textually diffing JSON

Answer 7

"अब मैं दो JSON ऑब्जेक्ट के बीच संरचनात्मक अंतर लौटने के लिए एक विधि बनाया है। "

http://www.xn--schler-dya.net/blog/2008/01/15/diffing_json_objects/