फेसबुक से Breathalyzer

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

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

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

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

टास्क की शर्तें

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

निर्णय। Iteration 1

इससे निपटने के लिए पहली समस्या एक शब्द में त्रुटियों की वास्तविक गणना है। Google में एक त्वरित खोज से पता चलता है कि सब कुछ हमारे सामने पहले ही आविष्कार किया जा चुका है, और दिए गए शर्तों के तहत शब्द अंतर का एक मात्रात्मक सूचक "लेवेंसहाइट दूरी" कहा जाता है। इस दूरी के लिए खोज एल्गोरिथ्म का वर्णन पहले से ही हैबे पर मौजूद है, इसलिए मैंने इस पर विस्तार से ध्यान नहीं दिया, मैं रूबी में इसका कार्यान्वयन दूंगा। इसलिए, हमारे निर्णय का दिल इस प्रकार है:

def calc_levenshtein_distance(s,t) n = s.length m = t.length return m if n==0 return n if m==0 d = Array.new(n+1).map!{Array.new(m+1)} for i in 0..n d[i][0]=i end for j in 0..m d[0][j]=j end for i in 1..n for j in 1..m do if s[i-1]==t[j-1] cost=0 else cost=1 end d[i][j] = [d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost].min end end return d[n][m] end 

डिक्शनरी का एक लिंक समस्या की स्थितियों में दिया गया है (केवल मामले में जब मैं इसे दोहराऊंगा ), परीक्षण के लिए स्रोत ग्रंथों के कई उदाहरण मंच पर भाग लेने वाले उत्साही ( 187.in , david_22719.in , 4.in , 12.in ) द्वारा पोस्ट किए गए थे, आप आगे बढ़ सकते हैं। छोटे के लिए मामला। हम पूरे शब्दकोश को पढ़ते हैं (क्योंकि यह प्रत्येक पंक्ति पर शब्द द्वारा आसानी से स्वरूपित होता है और वर्णानुक्रम में क्रमबद्ध होता है), हम स्रोत पाठ पढ़ते हैं, चक्र शुरू करते हैं: स्रोत पाठ से प्रत्येक शब्द के लिए हम शब्दकोश में निकटतम शब्द की तलाश करते हैं। हम कैसे देख रहे हैं? हम पूरे शब्दकोश के माध्यम से भागते हैं, लेवेंसहेटिन दूरी खोज फ़ंक्शन को लहराते हैं:

 def find_word(word, dic) result_word = '' result_cost = 999 dic.each do |dic_word| ld = calc_levenshtein_distance(word, dic_word) if ld<result_cost result_word = dic_word result_cost = ld end end return {:word => result_word, :cost => result_cost} end 

कार्यक्रम का मुख्य भाग माइनस रीडिंग डिक्शनरी:

 total_cost = 0 words.each do |word| total_cost += find_word(word, dic_words)[:cost] end 

पहले विकल्प का पूरा पाठ यहां लिया जा सकता है । यहां मुझे पहले से ही संदेह का दौरा किया गया था, लेकिन ठीक है, मेरी पसंदीदा टेस्ट फ़ाइल के साथ पहला रन जो भविष्य में मेरा पसंदीदा बन गया (मैंने पहले 187.in फाइल पर लगभग सभी पुनरावृत्तियों की जांच की ) ... हम्म। दस मिनट के इंतजार के बाद, यह स्पष्ट हो गया कि इस कार्यक्रम को समय पर प्रभावी होने की संभावना नहीं थी।

खैर, आपको यह देखना होगा कि ब्रेक कहाँ पर दफन है। तो, कार्यक्रम का मुख्य भाग लेवेंसहाइट डिस्टेंस सर्च फ़ंक्शन है, जो दो चक्रों में लिपटे हुए हैं - आने वाले पाठ और शब्दकोश के अनुसार। और शब्दकोश में लगभग 180 हजार शब्द हैं। कुछ पर काम करना है ...

निर्णय। Iteration 2

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

 return {:word => word, :cost => 0} if dic.include?(word) 

दूसरे, कुछ उदाहरणों में डुप्लिकेट शब्द हैं, इसलिए प्रश्न में प्रत्येक शब्द के लिए हम खोज परिणामों को बचाएंगे:

 res = already_found.include?(word) ? already_found[word] : find_word(word, dic_words) already_found[word] ||= res 

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

निर्णय। Iteration 3

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

सबसे पहले, आवश्यक संरचना का एक शब्दकोश बनाएं:

 dictionary = {} dic_words.each do |w| dictionary[w.length] ||= [] dictionary[w.length] << w end 

फिर हमने फ़ाइल को शब्दकोश खोज फ़ंक्शन के साथ संशोधित किया ताकि यह वांछित क्रम में शब्दों से अधिक पुनरावृत्त हो जाए:

 def find_word(word, dic) if dic[word.length] return {:word => word, :cost => 0} if dic[word.length].include?(word) end result_word = '' result_cost = 999 for offset in 0..15 do return {:word => result_word, :cost => result_cost} if result_cost<=offset indexes = [word.length-offset,word.length+offset].uniq indexes.each do |index| next unless dic[index] dictionary_part = dic[index] dictionary_part.each do |dic_word| ld = calc_levenshtein_distance(word, dic_word) if ld<result_cost result_word = dic_word result_cost = ld end end end end return {:word => result_word, :cost => result_cost} end 

हुर्रे! 12.in और 4.in फाइलों पर कार्यक्रम का निष्पादन 70 सेकंड तक कम हो गया था (हम यहां पूर्ण पाठ की तलाश करते हैं )। और यह भी 187.in फ़ाइल पर निष्पादन परिणामों की प्रतीक्षा करने के लिए निकला - लगभग 17 मिनट। जैसा कि मेरे गणित शिक्षक ने कहा, यह बेहतर है, लेकिन अभी तक दो हैं। David_22719.in फ़ाइल अभी भी उपलब्ध नहीं है।

निर्णय। गर्भाधान ४

मुझे माफ़ करना रूबी-जोड़ों और अन्य व्याख्या की गई भाषाओं के प्रेमियों, लेकिन कहीं न कहीं इस स्तर पर मुझे एहसास हुआ कि उन कार्यों में जो निष्पादन के समय तक महत्वपूर्ण हैं, वे .. खराब तरीके से करते हैं। इस स्तर पर, मैंने सी में कार्य को महसूस किया और महसूस किया। 187.in फ़ाइल के लिए शब्दकोश में प्रत्येक शब्द का bruteforce सेकंड में पूरा हुआ। कुछ ही मिनटों में, कार्यक्रम ने david_22719.in फ़ाइल में भी महारत हासिल कर ली । फेसबुक बॉट को भेजा गया समाधान नोट के साथ लौटा:

श्वासनली के लिए अपने समाधान को चलाने के बाद (18 जनवरी, 2011, 10:40 बजे प्राप्त किया गया), मैंने इसे सही होने के लिए निर्धारित किया है। आपका समाधान अपने सबसे लंबे समय तक परीक्षण के मामले में 1585.775 एमएस के लिए चला।

रूबी पर समाधान एक निशान के साथ समय के बाद वापस आ गया

फेसबुक पर एक पहेली समाधान प्रस्तुत करने के लिए धन्यवाद! श्वासनली के लिए अपने समाधान को चलाने के बाद (18 जनवरी, 2011 को 12:20 बजे प्राप्त किया गया), मैंने दुर्भाग्य से कुछ कीड़े पाए और इसे गलत होने के लिए निर्धारित किया।

ठीक है, फिर सुधारने के अन्य तरीकों की तलाश करने का समय है। कार्यक्रम का दिल Levenshtein दूरी की गणना करने का कार्य है, एल्गोरिदम जिसके लिए एक से अधिक हैं, लेकिन उनमें से सभी को छोड़कर, सबसे सरल ... इसे कैसे कहें ... कुछ हद तक nontrivial हैं। कई घंटों तक रमने के बाद, मैंने एक और उपाय खोजने का फैसला किया। और मिल गया। दुर्भाग्यवश, मुझे अब लिंक नहीं मिल रहा है, यह एक लंबे समय से पहले चोट लगी थी, लेकिन यह विचार इस प्रकार था - किसी दिए गए शब्द के लिए सभी संभव प्रथम-क्रम त्रुटियों की एक सूची बनाने के लिए और अगर शब्दकोश में उनमें से कम से कम एक है तो जांचें। टाइपो समारोह:

 def get_possible_edits(word) letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split(//) res = [] for i in 0..(word.length-1) str = String.new(word) str[i] = '' res << str end for c in letters for i in 0..(word.length-1) next if word[i]==c str = String.new(word) str[i]=c res << str end end for c in letters for i in 0..(word.length) str = String.new(word).insert(i,c) res << str end end return res end 

और डिक्शनरी खोज फ़ंक्शन में, लाइनें जोड़ें:

  minimum_errors = 1 #     ,        edits = get_possible_edits(word) edits.each do |edit| return {:word => edit, :cost => 1} if dic[edit.length] ? dic[edit.length].include?(edit) : false end minimum_errors = 2 #          ,        

ठीक है, हम समाधान के लिए आगे की खोज को कम कर देंगे, इस तथ्य को ध्यान में रखते हुए कि इस शब्द में कम से कम एक त्रुटि है (क्योंकि हमने पहले से ही एक त्रुटि के साथ सभी विकल्पों पर विचार किया है):

  for offset in 0..15 do return {:word => result_word, :cost => result_cost} if ((result_cost<=offset) or (result_cost<=minimum_errors)) ... end 

इस तरह के बदलावों ने 187.in को 14 मिनट, 12.in से 64 सेकंड तक निष्पादित करने के परिणाम में सुधार करना संभव बनाया, और 4.in पहले से ही एक दूसरे विभाजन में पूरा हो गया है (जो आश्चर्य की बात नहीं है, इसमें एक से अधिक त्रुटि वाले शब्द नहीं हैं)। छोटी जीत। अब आप आगे भी जा सकते हैं और उसी पद्धति का उपयोग करके दूसरे क्रम तक त्रुटियों की गणना कर सकते हैं। हालांकि, यह समझा जाना चाहिए कि पहले स्तर की संभावित त्रुटियों की संख्या ज्यामितीय रूप से प्रश्न में शब्द की लंबाई के साथ बढ़ती है, और दूसरे स्तर की त्रुटियों की संख्या पहले स्तर की त्रुटियों की संख्या से बढ़ जाती है। इस प्रकार, यदि हम केवल एक कोड जोड़ते हैं:

  edits.each do |edit| edits2 = get_possible_edits(edit) edits2.each do |edit2| return {:word => edit2, :cost => 2} if dic[edit2.length] ? dic[edit2.length].include?(edit2) : false end end minimum_errors = 3 

, फिर आसानी से आने वाले 12.in फ़ाइल पर कार्यक्रम के निष्पादन समय को दस गुना तक बढ़ा सकते हैं । इस एल्गोरिथ्म को कम शब्दों में उपयोग करने की सलाह दी जाती है। मैंने प्रायोगिक रूप से यह स्थापित किया है कि इससे सबसे बड़ा लाभ उन्हें उन शब्दों के साथ जांच कर प्राप्त किया जा सकता है जिनकी लंबाई छह से अधिक नहीं है

  if word.length<=6 edits.each do |edit| edits2 = get_possible_edits(edit) edits2.each do |edit2| return {:word => edit2, :cost => 2} if dic[edit2.length] ? dic[edit2.length].include?(edit2) : false end end minimum_errors = 3 end 

फ़ाइल 187.in पर, यह तत्व आपको निष्पादन समय का एक और 10% खेलने की अनुमति देता है। इस बिंदु पर, सभी तुच्छ अनुकूलन समाप्त हो जाते हैं, जिसका अर्थ है कि यह गणित में डुबकी लगाने का समय है।

निर्णय। Iteration 5

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

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

लेवेंसहाइट दूरी की गणना करने के लिए एक तालिका की कल्पना करें। सादगी के लिए, हम उस मामले पर विचार करते हैं जब यह क्षैतिज रूप से लंबवत से अधिक लंबा होता है (हम सामान्यता नहीं खोते हैं, क्योंकि हम हमेशा शब्दों के क्रम को बदल सकते हैं)। हम तालिका के निचले दाएं सेल में मूल्य में रुचि रखते हैं। एल्गोरिथ्म के अनुसार, इसकी गणना अंतिम है। लेकिन यह पता चला है कि यह मान प्राप्त करने के लिए पूरी तालिका की गणना करना आवश्यक नहीं है! उकोकोन विधि का सार यह है कि कई विकर्णों की गणना की जाती है। किस विकर्ण की गणना करें और उन्हें सही तरीके से कैसे चुनें? यह मुख्य प्रश्न है।

हम मुख्य विकर्ण कहते हैं जो ऊपरी बाएं कोने से बाहर आता है। यदि शब्दों की तुलना में अक्षरों की संख्या समान है, तो यह हमारे वांछित निचले दाएं कोने के खिलाफ टिकी हुई है। इस विकर्ण की गणना हमेशा की जाती है, चाहे कुछ भी हो। कुल कितने विकर्णों की आवश्यकता है? मैं गणितीय औचित्य देने के लिए तैयार नहीं हूं, लेकिन आनुभविक रूप से मुझे पता चला कि कम से कम तीन विकर्ण होने चाहिए।

यदि शब्द की लंबाई में अंतर कम से कम दो अक्षर है, तो मुख्य के दाईं ओर के सभी विकर्णों की गणना केवल उस तक की जाती है जो निचले दाएं कोने में समाधान प्रदर्शित करता है (मुझे याद है, हम मानते हैं कि अलग-अलग शब्द लंबाई के साथ, अब क्षैतिज रूप से लिखा गया है)।



यदि शब्द एक अक्षर से लंबाई में भिन्न होते हैं, तो एक अतिरिक्त एक विकर्ण को मुख्य के बाईं ओर जोड़ा जाता है, यदि शब्द लंबाई में समान हैं, तो एक विकर्ण को बाईं ओर और मुख्य के दाईं ओर जोड़ा जाता है:


उदाहरणों में, मुख्य विकर्ण को हरे रंग में, पीले रंग में गणना वाले और लाल रंग में हल किया गया है।

टेबल गणना फ़ंक्शन का प्रत्येक चरण नए सेल के मूल्य की गणना करता है, जो कि उसके आस-पास के तीनों (न्यूनतम संक्रमण लागत गुणांक) के न्यूनतम के रूप में होता है, ताकि तालिका की स्किप की गई कोशिकाएं गणना को प्रभावित न करें, आपको उन्हें स्पष्ट रूप से बड़ी संख्या के साथ प्रारंभ करने की आवश्यकता है, उदाहरण के लिए 50। ऊपरी बाएं सेल, पहले की तरह, शून्य से आरंभिक है। कोड में, यह इस तरह दिखता है:

 def min3(a,b,c) m = a < b ? a : b return m < c ? m : c end def calc_levenshtein_distance(s,t) return calc_levenshtein_distance(t,s) if s.length<t.length n = s.length m = t.length return m if n==0 return n if m==0 d = Array.new(m+1).map!{Array.new(n+1).map!{50}} d[0][0]=0 p = (n==m) ? 1 : 0 #   q = (nm<=1)? 1 : 0 #   for j in 1..[(n-m+p),n].min d[0][j]=d[0][j-1]+1 end for i in 1..m do for j in (i - q)..[(i + n - m + p),n].min do if j==0 d[i][j] = d[i-1][j]+1 else cost = 1 cost = 0 if t[i-1] == s[j-1] d[i][j] = min3(d[i-1][j] + 1 , d[i][j-1] + 1 , d[i-1][j-1] + cost) end end end return d[m][n] end 

सुधार स्पष्ट हैं, 187.in सिर्फ 6 मिनट में पूरा हो गया है, और 12.in - 25 सेकंड में। लेकिन फिर भी, कुछ और के साथ आना अच्छा होगा। पांचवें पुनरावृत्ति का पूरा पाठ यहाँ है ।

निर्णय। गर्भाधान ६

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

 def arr_diff(a1,a2) res = 0 for i in 0..25 do res += (a1[i]-a2[i]).abs end return res end 

इस तरह का अंतर, ज़ाहिर है, लेवेंसहाइट दूरी की तुलना में अधिक सार है, लेकिन इसे तेजी से गणना की जा सकती है। वह कैसे मदद कर सकता है? ऐसे हैश में अंतर करने के लिए लेवन्सहाइट दूरी कैसे संबंधित हो सकती है? सबसे महत्वपूर्ण कनेक्शन यह है कि एक शब्द में एक अक्षर को जोड़ना और हटाना इन दोनों अर्थों में एक समय में एक जोड़ता है। यदि शब्द में दो अक्षर आपस में जुड़े हुए हैं, तो मूल शब्द से नए शब्द की लेवेन्सहाइट दूरी 2 हो जाएगी, हालांकि संबंधित सरणियों का अंतर शून्य होगा, क्योंकि अक्षरों की रचना संरक्षित है। और अगर हम शब्द को अक्षर को किसी अन्य में बदलते हैं, तो सरणियों में अंतर 2 से बढ़ जाएगा, जबकि लेवेंसहाइट की दूरी केवल 1 होगी। इस प्रकार, नीचे से सरणियों में अंतर पर प्रतिबंध बल्कि कमजोर है: शब्द में लंबाई के अंतर को घटाते हुए, किसी भी संख्या में क्रमपरिवर्तन हो सकते हैं। लेवेंसहाइट दूरी में वृद्धि के लिए पत्र, लेकिन सरणियों के अंतर में वृद्धि के लिए नहीं (केवल निम्न सीमा जो हम लगा सकते हैं, एक है, अगर शब्द में त्रुटियों की न्यूनतम संख्या विषम है, क्योंकि लेवेन के अनुसार त्रुटियों की विषम संख्या। मैट अक्षरों के क्रमपरिवर्तन द्वारा प्राप्त नहीं किया जा सकता है), और ऊपर - सरणियों में अंतर लेवेंसहेटिन की दोहरी दूरी से अधिक नहीं हो सकता है।

पूर्वगामी के आधार पर, हम यह कह सकते हैं कि लेवेन्सहाइटिन दूरी के साथ दो शब्दों के लिए और ऑफसेट में लंबाई में अंतर है, सरणियों में अंतर सीमा [2, अंतर * ऑफसेट] में होगा । वास्तव में, नीचे को सीमित करने के लिए, आप किसी शब्द में न्यूनतम संख्या की त्रुटियों के अनुमान का भी उपयोग कर सकते हैं (उदाहरण के लिए, यदि हमें पहले आदेश के सभी टाइपो को मानकर एक शब्द नहीं मिला है, तो हम कह सकते हैं कि इसमें पहले से ही कम से कम दो त्रुटियां हैं)। यदि त्रुटियों की न्यूनतम संख्या और शब्द लंबाई में अंतर विषम है (अर्थात, किसी शब्द में लंबाई के अंतर के अलावा, कम से कम N त्रुटियाँ और N विषम भी हैं), तो शब्द सरणियों में न्यूनतम संभव अंतर को एक से बढ़ाया जा सकता है - [ऑफसेट + (min_errors - ऑफसेट) )% 2, 2 * अंतर - ऑफसेट] (सम एन के मामले में, अतिरिक्त प्रतिबंध नहीं लगाया जा सकता है, क्योंकि लेवेंसहाइट की एक भी संख्या अक्षरों के क्रमपरिवर्तन द्वारा प्राप्त की जा सकती है जो सरणियों में अंतर को प्रभावित नहीं करती है)।

इस ज्ञान का उपयोग करने के लिए लेवेंशिन दूरी गणना फ़ंक्शन को दिए गए शब्दों को फ़िल्टर करने का प्रयास करें। शब्दकोश को पढ़ते समय शब्दकोषों की संख्या तुरंत नहीं गिना जाएगा, लेकिन आवश्यक है, ताकि शॉर्ट इनपुट फ़ाइलों के लिए अनावश्यक गणना न करें, जब पढ़ने से हम केवल संबंधित सरणियों को आरंभ करेंगे:

 dictionary = {} dic_words.each do |w| dictionary[w.length] ||= {} dictionary[w.length][w] = Array.new(26,0) end 

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

  def find_word(word, dic) if dic[word.length] return {:word => word, :cost => 0} if dic[word.length].include?(word) end minimum_errors = 1 #     ,        edits = get_possible_edits(word) edits.each do |edit| return {:word => edit, :cost => 1} if dic[edit.length] ? dic[edit.length].include?(edit) : false end minimum_errors = 2 #          ,        if word.length<=6 edits.each do |edit| edits2 = get_possible_edits(edit) edits2.each do |edit2| return {:word => edit2, :cost => 2} if dic[edit2.length] ? dic[edit2.length].include?(edit2) : false end end minimum_errors = 3 end result_word = '' result_cost = 999 wordhash = Array.new(26,0) word.each_byte{|b| wordhash[b-65]+=1} for offset in 0..15 do return {:word => result_word, :cost => result_cost} if ((result_cost<=offset) or (result_cost<=minimum_errors)) indexes = [word.length-offset,word.length+offset].uniq indexes.each do |index| next unless dic[index] dictionary_part = dic[index] if dictionary_part[dictionary_part.keys.first].max==0 #       ,    dictionary_part.each do |key, val| key.each_byte{|b| val[b-65]+=1} end end lower_bound = (minimum_errors-offset>0 ? minimum_errors-offset : 0).abs%2 + offset higher_bound = 2*result_cost - offset dictionary_part.each do |dic_word, dic_wordhash| a = arr_diff(dic_wordhash,wordhash) next if a<lower_bound or a>higher_bound ld = calc_levenshtein_distance(word, dic_word) if ld<result_cost result_word = dic_word result_cost = ld higher_bound = 2*result_cost - offset end end end end return {:word => result_word, :cost => result_cost} end 

इस प्रकार, यह पता चलता है कि 187.in फाइल को 66 सेकंड ( 12.in - 5.5 सेकंड) में निष्पादित किया जा सकता है। यह कार्यक्रम के पहले संस्करण द्वारा दिखाए गए समय (या नहीं दिखाया गया) की तुलना में काफी अच्छा है और यहां तक ​​कि आपको david_22719.in फ़ाइल के समाधान को देखने के लिए कुछ घंटों तक प्रतीक्षा करने की अनुमति देता है, लेकिन, जैसा कि यह निकला, फेसबुक बॉट के माध्यम से प्राप्त करने के लिए पर्याप्त नहीं है।

निर्णय। Iteration 7

लेकिन फिर मैंने झांसा दिया। मुझे निष्पादन में तेजी लाने के लिए किसी भी तरह से महारत हासिल नहीं है, इसलिए मुझे सामान्य रूप से रूबी और विशेष रूप से संस्करण 1.8.6 की सुविधाओं के आधार पर विशुद्ध रूप से तकनीकी साधनों का सहारा लेना पड़ा। उदाहरण के लिए, मैंने प्रयोगात्मक रूप से पाया कि टर्नरी ऑपरेटर (ए? बी: सी) पारंपरिक की तुलना में तेज है अगर-और। मैंने सीखा है कि एक पंक्ति में बदसूरत गणना आपको अस्थायी चर के निर्माण के साथ विकल्प से एक विभाजन दूसरा जीतने की अनुमति देती है। मिथक का खंडन किया कि छोटे चर नाम निष्पादन की प्रक्रिया को तेज कर सकते हैं। मुझे पता चला कि एक नियमित अभिव्यक्ति के साथ पूरी फ़ाइल को पार्स करना लाइन द्वारा इसे पढ़ने की तुलना में तेजी से काम करता है ... ऑब्जेक्ट के कुछ अनावश्यक इनिशियलाइज़ेशन या अनावश्यक मेमोरी एलोकेशन को हटाने के प्रयासों में कोड चाट के कई घंटों ने मुझे सेकंड के एक और जोड़े को खोने की अनुमति दी, लेकिन यह अभी भी पर्याप्त नहीं था बॉट के माध्यम से मिलता है। और फिर मैंने हार मान ली।

निर्णय। सफेद झंडा

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

 #include <ruby.h> #ifndef max #define max( a, b ) ( ((a) > (b)) ? (a) : (b) ) #endif #ifndef min #define min( a, b ) ( ((a) < (b)) ? (a) : (b) ) #endif void Init_levenshtein(); VALUE distance(VALUE self, VALUE rwm, VALUE rwn); void Init_levenshtein() { VALUE cLevenshtein = rb_define_class("Levenshtein",rb_cObject); rb_define_singleton_method(cLevenshtein, "distance", distance, 2); } VALUE distance(VALUE self, VALUE rwm, VALUE rwn) { char *wm, *wn; int res; wm = StringValuePtr(rwm); wn = StringValuePtr(rwn); res = LeveDist(wm,wn); return INT2NUM(res); } int min3(int a, int b, int c) { int Min = a; if (b < Min) Min = b; if (c < Min) Min = c; return Min; } int LeveDist(char *s, char *t) { char* wm; char* wn; int m, n, q, p, cost, i, j; int loop1, loop2; char* d; int res = -1; if (strlen(s) > strlen(t)) { wm = t; wn = s; } else { wm = s; wn = t; } m = strlen(wm); n = strlen(wn); d = calloc((m + 1)*(n + 1),sizeof(char)); memset(d, 50, (m + 1)*(n + 1)); p = (n==m) ? 1 : 0; q = (nm<=1)? 1 : 0; *d = 0; loop1 = min(n, n - m + p); for (j = 1; j <= loop1; j++) *(d + j) = *(d + j - 1) + 1; for (i = 1; i <= m; i++) { loop2 = min(n, i + n - m + p); for (j = (iq); j <= loop2; j++) { if (j == 0) { *(d + i * (n + 1) + j) = *(d + (i - 1)*(n + 1) + j) + 1; } else { cost = 1; if (*(wm + i - 1) == *(wn + j - 1)) cost = 0; *(d + i * (n + 1) + j) = min3(*(d + (i - 1)*(n + 1) + j) + 1, *(d + i * (n + 1) + j - 1) + 1, *(d + (i - 1)*(n + 1) + j - 1) + cost); } } } res = *(d + m * (n + 1) + n); free(d); return res; } 

खैर, फिर यह नीचे आया:

 require 'levenshtein' ... Levenshtein.distance(word,dic_word) 

उसके बाद, यह पता चला कि छठे पुनरावृत्ति में वर्णित मेरा स्वयं का अनुकूलन, मुख्य ब्रेक बन गया, और इसे अनिच्छा से इनकार करना पड़ा (इसे आविष्कार करने में बहुत समय लगा)।

निर्णय। जीत!

मुझे स्वीकार करना चाहिए, मैंने अंततः विंडोज के लिए परिणामी समाधान में महारत हासिल नहीं की। लिनक्स के तहत एक वर्चुअल मशीन में संकलित और बॉट में भेजा जाता है, और कुछ घंटों के बाद मेलबॉक्स पर निम्न फॉर्म का संदेश प्राप्त होता है:

फेसबुक पर एक पहेली समाधान प्रस्तुत करने के लिए धन्यवाद! श्वासनली के लिए अपने समाधान को चलाने के बाद (25 जनवरी, 2011 को 3:04 बजे प्राप्त किया गया), मैंने इसे सही होने के लिए निर्धारित किया है। आपका समाधान 5097.469 एमएस के लिए अपने सबसे लंबे समय तक परीक्षण के मामले में चला।

यह, निश्चित रूप से, सी में पूर्ण खोज की तुलना में तीन गुना धीमा है, लेकिन फिर भी सेट करने के लिए पर्याप्त तेज़ है

निष्कर्ष

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

• (Core-i7 2.66 GHz)
• ,
• , , - , Ruby -
• , facebook-
• facebook-
• snack- ( thrift-), ,
• सी में आप एक प्रोग्राम लिख सकते हैं जो 187.in फाइल को सेकंड के कुछ दसवें हिस्से में संभाल सकता है, लेकिन मैं सफल नहीं हुआ
• किसी भी प्रोग्रामिंग भाषा का उपयोग करते हुए टिप्पणियों में समय मापन का स्वागत है