PHP

Question

में लेवेनशेटिन/समान_टेक्स्ट को तेज करना मैं वर्तमान में ~ 50,000 की सूची के विरुद्ध स्ट्रिंग की तुलना करने के लिए similar_text का उपयोग कर रहा हूं जो तुलना करता है हालांकि तुलना की संख्या बहुत धीमी है। ~ 500 अद्वितीय तारों की तुलना करने में लगभग 11 मिनट लगते हैं।

इसे चलाने से पहले मैं यह देखने के लिए डेटाबेस जांचता हूं कि क्या इसे अतीत में संसाधित किया गया है, इसलिए इनटाइटल रन के तुरंत बाद यह तुरंत बंद हो जाता है।

मुझे यकीन है कि levenshtein का उपयोग करना थोड़ा तेज़ होगा और मैन्युअल में पोस्ट किए गए लेवेनशेटिनडिस्टेंस फ़ंक्शन को दिलचस्प लग रहा है। क्या मुझे कुछ याद आ रहा है जो इसे काफी तेज़ कर सकता है?

Answer 1

अंत में, दोनों levenshtein और similar_text दोनों भी तार के माध्यम से यह जाना था की संख्या के साथ धीमी गति से थे, यहां तक ​​कि चेक के बहुत से और केवल उन्हें एक अंतिम उपाय के रूप में उनमें से एक का उपयोग कर।

एक प्रयोग के रूप में, मैंने कुछ कोड को सी # पर पोर्ट किया ताकि यह देखने के लिए कि इंटरपरेटेड कोड पर कितना तेज़ होगा। यह उसी डेटासेट के साथ लगभग 3 मिनट में चला।

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

अंत में मैंने सबसे सरल दृष्टिकोण का चयन किया, MySQLs पूर्ण पाठ जो बहुत अच्छी तरह से काम करता था। कभी-कभी गलतियाँ होती हैं हालांकि उन्हें पहचानना और सही करना आसान होता है। इसके अलावा यह लगभग 3-4 सेकंड में बहुत तेजी से चलता है।

Answer 2

शायद आप सटीक मिलान के लिए अपनी स्ट्रिंग की तुलना करके पहली बार 'शॉर्ट-सर्किट' कर सकते हैं (और पहले लंबाई की तुलना में तुलना करके), और यदि यह अधिक महंगा similar_text कॉल छोड़ देता है।

जैसा कि @ जेसन ने नोट किया, एक ओ (एन^3) एल्गोरिदम कभी भी एक अच्छा विकल्प नहीं होने वाला है।

Answer 3

Levenshtein आटोमैटिक मशीन (आटोमैटिक मशीन है कि दूरी k के साथ एक स्ट्रिंग से मेल खाता) आप O(n), जहां n स्ट्रिंग आप जाँच कर रहे हैं की लंबाई है में मिलान का एक चेक कर सकते हैं का उपयोग करते समय। Automaton का निर्माण O(kn) ले जाएगा, जहां k अधिकतम दूरी और बेस स्ट्रिंग की n लंबाई है।