दिलचस्प पोस्ट
बिना आकार () क्या करता है? मैं jQuery के साथ HTML विशेषता नाम कैसे बदल सकता हूं? IPhone बनाम आईपैड / ब्राउज़र पर HTML5 इनलाइन वीडियो डब्लूएसडीएल का उपयोग कैसे करें मैं स्पार्क स्ट्रीमिंग में एक प्रसारण चर को कैसे अपडेट कर सकता हूं? एंड्रॉइड 3.1 यूएसबी होस्ट – ब्रॉडकास्ट रिसीवर USB_DEVICE_ATTACHED प्राप्त नहीं करता है $ .एजेएक्स उपयोगिता में JQuery त्रुटि विकल्प नल योग्य प्रकार एक नल योग्य प्रकार नहीं है? सरल टेम्पलेट वर्ग के साथ "अपरिभाषित प्रतीकों" लिंकर त्रुटि कोयोनर 2 ऐप में 'प्रवेश-नियंत्रण-अनुमति-उत्पत्ति' शीर्षलेख नहीं पायथन 2. एक्स गेचैस और लैंडमाइंस कुछ अच्छे एनएटी प्रोफाइलर्स क्या हैं? @import vs #import – आईओएस 7 पैरामीटर की व्याख्या जब नौकरियां चलती है हमारी स्ट्रीम निष्कर्षण स्थिति के रूप में ईओएफ बिट का उपयोग करने के लिए वास्तविक कारण क्या है?

Mysql / फजी खोज के लिए लेवेन्सशेटिन दूरी का कार्यान्वयन?

मैं एक मेज को खोजने के लिए सक्षम होना चाहूंगा, जैसा कि स्मिथ के लिए है, जैसा कि 1 विचरण के भीतर सब कुछ मिलता है।

डेटा:

 ओ ब्रायन
 Smithe
 डोलन
 Smuth
 वोंग
 तलाश
 गुंथर
 Smiht

मैंने लेवेन्सशेटिन दूरी का इस्तेमाल किया है, क्या किसी को पता है कि इसके साथ इसे कैसे लागू किया जाए?

Solutions Collecting From Web of "Mysql / फजी खोज के लिए लेवेन्सशेटिन दूरी का कार्यान्वयन?"

क्या यह मदद करता है? MySQL Levenshtein दूरी क्वेरी

संपादित करें: लिवेंशटीन की दूरी पर एक MySQL संग्रहीत फ़ंक्शन (Google कैश) के रूप में दूरी टूट गई है, धन्यवाद रॉबर्ट के लिए टिप्पणी में इस ओर इशारा करते हुए।

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

Damerau-levenshtein दूरी के लिए एक कार्यान्वयन यहाँ पाया जा सकता है: Damerau-Levenshtein एल्गोरिदम: Transvenations के साथ Levenshtein शुद्ध Levenshtein दूरी पर सुधार यह है कि वर्णों के गमागमन माना जाता है। मैंने इसे schnaader के लिंक की टिप्पणियों में पाया, धन्यवाद!

लेवेनशेटिन दूरी समारोह के एक MySQL UDF कार्यान्वयन है

https://github.com/jmcejuela/Levenshtein-MySQL-UDF

इसे सी में लागू किया गया है और schnaader द्वारा उल्लिखित "MySQL Levenshtein दूरी क्वेरी" से बेहतर प्रदर्शन किया है

ऊपर दिए गए लिवेनशटेन <= 1 के लिए दिया गया कार्य सही नहीं है – उदाहरण के लिए, "बिस्तर" और "बोली" के लिए गलत परिणाम देता है

मैंने ऊपर दिए गए "MySQL Levenshtein दूरी क्वेरी" को संशोधित किया है, पहले जवाब में, एक "सीमा" को स्वीकार करने के लिए जो इसे थोड़ा तेज करेगा असल में, यदि आप केवल लेवेनशटीन <= 1 की परवाह करते हैं, तो सीमा को "2" पर सेट करें और फ़ंक्शन सटीक लेवेनशेटिन दूरी लौटाएगा यदि यह 0 या 1 है; या 2 अगर सटीक लेवेन्सटीन दूरी 2 या अधिक है

यह मॉडेड 15% से 50% तेज़ बनाता है – अब आपके खोज शब्द, बड़ा फायदा (क्योंकि एल्गोरिथम पहले जमानत कर सकता है।) उदाहरण के लिए, 200,000 शब्दों के खोज के लिए शब्द के 1 दूरी के भीतर सभी मैचों को खोजने के लिए "हंसी," मूल मेरे लैपटॉप पर 3 मिनट 47 सेकंड लेता है, बनाम 1:39 "सीमा" संस्करण के लिए। बेशक, ये दोनों किसी भी वास्तविक समय उपयोग के लिए बहुत धीमी हैं

कोड:

DELIMITER $$ CREATE FUNCTION levenshtein_limit_n( s1 VARCHAR(255), s2 VARCHAR(255), n INT) RETURNS INT DETERMINISTIC BEGIN DECLARE s1_len, s2_len, i, j, c, c_temp, cost, c_min INT; DECLARE s1_char CHAR; -- max strlen=255 DECLARE cv0, cv1 VARBINARY(256); SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0, c_min = 0; IF s1 = s2 THEN RETURN 0; ELSEIF s1_len = 0 THEN RETURN s2_len; ELSEIF s2_len = 0 THEN RETURN s1_len; ELSE WHILE j <= s2_len DO SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1; END WHILE; WHILE i <= s1_len and c_min < n DO -- if actual levenshtein dist >= limit, don't bother computing it SET s1_char = SUBSTRING(s1, i, 1), c = i, c_min = i, cv0 = UNHEX(HEX(i)), j = 1; WHILE j <= s2_len DO SET c = c + 1; IF s1_char = SUBSTRING(s2, j, 1) THEN SET cost = 0; ELSE SET cost = 1; END IF; SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; IF c > c_temp THEN SET c = c_temp; END IF; SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; IF c > c_temp THEN SET c = c_temp; END IF; SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; IF c < c_min THEN SET c_min = c; END IF; END WHILE; SET cv1 = cv0, i = i + 1; END WHILE; END IF; IF i <= s1_len THEN -- we didn't finish, limit exceeded SET c = c_min; -- actual distance is >= c_min (ie, the smallest value in the last computed row of the matrix) END IF; RETURN c; END$$ 

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

एक प्रत्यय सरणी ( विकिपीडिया देखें ) को बनाने के बाद, यदि आप खोज स्ट्रिंग में अधिकतम कश्मीर बेमेल में एक स्ट्रिंग में दिलचस्पी रखते हैं, तो खोज स्ट्रिंग को कश्मीर + 1 टुकड़े में तोड़ दें; उनमें से कम से कम एक को बरकरार होना चाहिए। प्रत्यय सरणी पर द्विआधारी खोज द्वारा सबस्ट्रिंग ढूंढें, फिर प्रत्येक मिलान किए गए टुकड़े के आस-पास पैच के लिए दूरी कार्य लागू करें।

आप इस फ़ंक्शन का उपयोग कर सकते हैं


 फंक्शन `लेवेनशेटिन` (एस 1 टेक्स्ट, एस 2 टेक्स्ट) रिटर्न इंट (11) रिटर्न करें
     नियतात्मक
 शुरू 
     DECLARE s1_len, s2_len, i, j, c, c_temp, लागत INT; 
     DECLARE s1_char CHAR; 
     DECLARE cv0, cv1 पाठ; 
     SET s1_len = CHAR_LENGTH (s1), s2_len = CHAR_LENGTH (s2), सीवी 1 = 0x00, j = 1, i = 1, c = 0; 
     यदि s1 = s2 फिर 
       वापस 0; 
     ELSEIF s1_len = 0 फिर 
       रिटर्न S2_len; 
     ELSEIF s2_len = 0 फिर 
       रिटर्न एस 1_लेन; 
     अन्य 
       WHILE j <= s2_len DO 
         SET cv1 = CONCAT (सीवी 1, यूएन हेक्स (हेक्स (जे))), जे = जे + 1; 
       अंत में; 
       जब मैं <= s1_len DO 
         SET s1_char = SUBSTRING (s1, i, 1), c = i, cv0 = UNHEX (हेक्स (i)), जे = 1; 
         WHILE j <= s2_len DO 
           SET c = c + 1; 
           यदि s1_char = SUBSTRING (एस 2, जे, 1) तो  
             SET लागत = 0;  ELSE SET लागत = 1; 
           अगर अंत; 
           SET c_temp = CONV (हेक्स (SUBSTRING (सीवी 1, जे, 1)), 16, 10) + लागत; 
           यदि c> c_temp तब SET c = c_temp;  अगर अंत; 
             SET c_temp = CONV (हेक्स (SUBSTRING (सीवी 1, जे + 1, 1)), 16, 10) + 1; 
             यदि c> c_temp तो फिर  
               SET c = c_temp;  
             अगर अंत; 
             SET cv0 = CONCAT (cv0, यूएनएचईएक्स (हेक्स (सी)), जे = जे + 1; 
         अंत में; 
         SET cv1 = cv0, i = i + 1; 
       अंत में; 
     अगर अंत; 
     रिटर्न सी; 
   समाप्त

और इसे XX% के रूप में प्राप्त करने के लिए इस फ़ंक्शन का उपयोग करें


 फंक्शन `लेवेनशेटिन_ट्रोटो` (एस 1 टेक्स्ट, एस 2 टेक्स्ट) रिटर्न इंट (11) रिटर्न
     नियतात्मक
 शुरू 
     DECLARE s1_len, s2_len, max_len INT; 
     SET s1_len = LENGTH (s1), s2_len = LENGTH (एस 2); 
     अगर s1_len> s2_len तब  
       SET max_len = s1_len;  
     अन्य  
       SET max_len = s2_len;  
     अगर अंत; 
     रिटर्न राऊंड ((1 - लेवेनशिटिन (एस 1, एस 2) / अधिकतम_एलएन) * 100); 
   समाप्त

यदि आप केवल जानना चाहते हैं कि लेवेनशटेन-दूरी में अधिकतम 1 है, तो आप निम्न MySQL फ़ंक्शन का उपयोग कर सकते हैं।

 CREATE FUNCTION `lv_leq_1` ( `s1` VARCHAR( 255 ) , `s2` VARCHAR( 255 ) ) RETURNS TINYINT( 1 ) DETERMINISTIC BEGIN DECLARE s1_len, s2_len, i INT; SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), i = 1; IF s1 = s2 THEN RETURN TRUE; ELSEIF ABS(s1_len - s2_len) > 1 THEN RETURN FALSE; ELSE WHILE SUBSTRING(s1,s1_len - i,1) = SUBSTRING(s2,s2_len - i,1) DO SET i = i + 1; END WHILE; RETURN SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i) OR SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i+1) OR SUBSTRING(s1,1,s1_len-i+1) = SUBSTRING(s2,1,s2_len-i); END IF; END 

यह मूल रूप से लेवेनशेटिन दूरी के रिकर्सिव विवरण में एक कदम है। फ़ंक्शन 1 देता है, यदि दूरी में अधिकतम 1 है, और फिर यह 0 देता है।

चूंकि यह फ़ंक्शन पूरी तरह से लेवेनशेटिन-दूरी की गणना नहीं करता है, इसलिए यह बहुत तेज है।

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

मेरे पास कश्मीर दूरी की खोज का एक विशिष्ट मामला था और MySQL में डेमेरा-लेवेनशेटिन यूडीएफ को स्थापित करने के बाद यह पाया गया कि क्वेरी बहुत अधिक समय ले रही थी। मैं निम्नलिखित समाधान के साथ आया था:

  • मेरे पास एक बहुत ही प्रतिबंधात्मक खोज स्थान है (संख्यात्मक मानों तक सीमित 9 वर्ण स्ट्रिंग)।

अपने लक्षित क्षेत्र में प्रत्येक चरित्र की स्थिति के लिए कॉलम के साथ एक नई तालिका बनाएं (या अपनी लक्ष्य तालिका में कॉलम जोड़ें)। अर्थात। मेरा VARCHAR (9) 9 टिनइंटी कॉलम + 1 आईडी कॉलम के रूप में समाप्त हुआ जो मेरी मुख्य सारणी से मेल खाता है (प्रत्येक कॉलम के लिए अनुक्रमित जोड़ें)। मैंने यह सुनिश्चित करने के लिए ट्रिगर जोड़ा है कि जब मेरा मुख्य टेबल अपडेट हो जाए तो ये नए कॉलम हमेशा अपडेट हो जाएंगे

K-distance क्वेरी करने के लिए निम्न निश्चय का उपयोग करें:

(स्तंभ 1 = एस [0]) + (स्तंभ 2 = एस [1]) + (स्तंभ 3 = एस [2]) + (स्तंभ 4 = एस [3]) + …> = मी

जहां एस आपकी खोज स्ट्रिंग है और मी मिलान वाले पात्रों की आवश्यक संख्या (या मेरे मामले में एम = 9 – घ है जहां डी सबसे अधिक दूरी है जो मैं लौटूंगा)।

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

हालांकि यह दमेरा-लेवेनशेटिन नहीं है (प्रतिस्थापन के लिए खाता नहीं है) यह मेरे उद्देश्यों के लिए पर्याप्त है

यद्यपि यह समाधान संभवतः एक बड़े (लम्बाई) खोज स्थान के लिए अच्छी तरह से स्केल नहीं करता है, लेकिन यह इस प्रतिबंधात्मक मामले के लिए बहुत अच्छी तरह से काम करता है।

Chella के जवाब और रयान Ginstrom के लेख के आधार पर, एक फजी खोज के रूप में लागू किया जा सकता है:

 DELIMITER $$ CREATE FUNCTION fuzzy_substring( s1 VARCHAR(255), s2 VARCHAR(255) ) RETURNS INT DETERMINISTIC BEGIN DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT; DECLARE s1_char CHAR; -- max strlen=255 DECLARE cv0, cv1 VARBINARY(256); SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0; IF s1 = s2 THEN RETURN 0; ELSEIF s1_len = 0 THEN RETURN s2_len; ELSEIF s2_len = 0 THEN RETURN s1_len; ELSE WHILE j <= s2_len DO SET cv1 = CONCAT(cv1, UNHEX(HEX(0))), j = j + 1; END WHILE; WHILE i <= s1_len DO SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1; WHILE j <= s2_len DO SET c = c + 1; IF s1_char = SUBSTRING(s2, j, 1) THEN SET cost = 0; ELSE SET cost = 1; END IF; SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; IF c > c_temp THEN SET c = c_temp; END IF; SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; IF c > c_temp THEN SET c = c_temp; END IF; SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; END WHILE; SET cv1 = cv0, i = i + 1; END WHILE; END IF; SET j = 1; WHILE j <= s2_len DO SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10); IF c > c_temp THEN SET c = c_temp; END IF; SET j = j + 1; END WHILE; RETURN c; END$$ DELIMITER ;