पायथन

Question

में फ़ज़ी स्ट्रिंग मिलान में मेरे पास थोड़ा अलग नामकरण सम्मेलनों के साथ दस लाख से अधिक नामों की 2 सूचियां हैं। 95% आत्मविश्वास के तर्क के साथ, उन रिकॉर्ड्स से मेल खाने का लक्ष्य यह समान है।

मुझे पता है कि पुस्तकालयों में मैं लीवरेज कर सकता हूं, जैसे कि पाइथन में फ़ज़ीवेज़ी मॉड्यूल।

हालांकि प्रसंस्करण के मामले में ऐसा लगता है कि यह 1 से अधिक सूची में प्रत्येक स्ट्रिंग की तुलना में बहुत अधिक संसाधन लेगा, जिसमें इस मामले में 1 मिलियन की पुनरावृत्ति की आवश्यकता होती है।

क्या इस समस्या के लिए कोई और अधिक प्रभावी तरीका है?

अद्यतन:

तो मैं एक bucketing समारोह बनाया और रिक्त स्थान को, प्रतीकों को दूर करने और मूल्यों परिवर्तित लोअरकेस आदि का एक सरल सामान्य आवेदन किया ...

for n in list(dftest['YM'].unique()): 
    n = str(n) 
    frame = dftest['Name'][dftest['YM'] == n] 
    print len(frame) 
    print n 
    for names in tqdm(frame): 
      closest = process.extractOne(names,frame) 

तक अजगर पांडा का उपयोग कर, डेटा वर्षों से समूहित छोटी बाल्टी से भरा हुआ है और फिर FuzzyWuzzy मॉड्यूल का उपयोग करके process.extractOne का उपयोग सर्वोत्तम मिलान प्राप्त करने के लिए किया जाता है।

परिणाम अभी भी कुछ निराशाजनक हैं। परीक्षण के दौरान उपर्युक्त कोड का उपयोग परीक्षण डेटा फ्रेम पर किया जाता है जिसमें केवल 5 हजार नाम होते हैं और लगभग पूरे घंटे तक लगते हैं।

परीक्षण डेटा को विभाजित किया गया है।

• नाम
• वर्ष जन्म

और मैं उन्हें बाल्टी, जहां उनके YMS एक ही बाल्टी में हैं द्वारा की तुलना कर रहा हूँ की तिथि का महीना।

समस्या का उपयोग कर रहे फ़ज़ीवेज़ी मॉड्यूल के कारण समस्या हो सकती है? किसी भी मदद की सराहना करते हैं।

Answer 1

कई स्तर हैं सेशन का इस समस्या को ओ (एन^2) से कम समय जटिलता में बदलने के लिए यहां संभव है।

• Preprocessing: प्रत्येक स्ट्रिंग के लिए एक निर्गम नक्शा बनाने, पहले पास में अपनी सूची पर क्रमबद्ध, वे नक्शे के लिए कुंजी स्ट्रिंग सामान्यीकृत जा सकता है। normalizations शामिल हो सकते हैं:

  • लोअरकेस रूपांतरण,
  • कोई व्हाइटस्पेस, विशेष वर्ण हटाने,
  • , ascii समकक्ष यूनिकोड को बदलने यदि संभव हो तो unicodedata.normalize या unidecode मॉड्यूल का उपयोग)

  यह परिणाम होगा "Andrew H Smith" में, "andrew h. smith", "ándréw h. smith" समान कुंजी "andrewhsmith" उत्पन्न करता है, और आपके नामों के लाखों नामों को एक गंध में कम कर देगा अद्वितीय/समान समूह वाले नामों का सेट।

आप अपने स्ट्रिंग को सामान्य बनाने में इस utlity method उपयोग कर सकते हैं (यूनिकोड हिस्सा हालांकि शामिल नहीं है):

def process_str_for_similarity_cmp(input_str, normalized=False, ignore_list=[]): 
    """ Processes string for similarity comparisons , cleans special characters and extra whitespaces 
     if normalized is True and removes the substrings which are in ignore_list) 
    Args: 
     input_str (str) : input string to be processed 
     normalized (bool) : if True , method removes special characters and extra whitespace from string, 
          and converts to lowercase 
     ignore_list (list) : the substrings which need to be removed from the input string 
    Returns: 
     str : returns processed string 
    """ 
    for ignore_str in ignore_list: 
     input_str = re.sub(r'{0}'.format(ignore_str), "", input_str, flags=re.IGNORECASE) 

    if normalized is True: 
     input_str = input_str.strip().lower() 
     #clean special chars and extra whitespace 
     input_str = re.sub("\W", "", input_str).strip() 

    return input_str 

• अब समान तार पहले से ही एक ही बाल्टी में झूठ होगा अगर उनके सामान्यीकृत कुंजी एकजैसा हैं।

• आगे की तुलना के लिए, आपको केवल नामों की तुलना करने की आवश्यकता होगी। उदाहरण के लिए andrewhsmith और andrewhsmeeth, क्योंकि इस समानता नामों की सामान्यीकृत उपरोक्त तुलना की तुलना में अस्पष्ट स्ट्रिंग मिलान की आवश्यकता होगी।

• बकेटिंग: तुम सच में 9 वर्ण कुंजी के साथ एक 5 वर्ण कुंजी तुलना करने के लिए है कि अगर 95% मैच है यह देखने की जरूरत है? नहीं तुम नहीं। तो आप अपने तारों से मेल खाने की बाल्टी बना सकते हैं। जैसे 5 चरित्र नामों का मिलान 4-6 वर्णों के साथ किया जाएगा, 5 वर्ण वर्णों के साथ 6 वर्ण नाम इत्यादि। एन एन 1, एन-1 वर्ण कुंजी के लिए एन-1 वर्ण सीमा सबसे व्यावहारिक मिलान के लिए एक उचित रूप से अच्छी बाल्टी है।

• मिलान शुरू: नामों की अधिकांश भिन्नताओं में सामान्यीकृत प्रारूप (ई।जी Andrew H Smith, ándréw h. smith, और Andrew H. Smeeth क्रमशः andrewhsmith, andrewhsmith, और andrewhsmeeth उत्पन्न करता है। वे आमतौर पर पहले वर्ण में भिन्न नहीं होंगे, इसलिए आप a से शुरू होने वाली कुंजियों के लिए मिलान कर सकते हैं जो a से शुरू होते हैं, और लंबाई बाल्टी के भीतर आते हैं। इससे आपके मिलान का समय बहुत कम हो जाएगा। किसी कुंजी andrewhsmith से bndrewhsmith से मिलान करने की आवश्यकता नहीं है क्योंकि पहले अक्षर के साथ इस तरह के नाम भिन्नता शायद ही मौजूद होगी।

तो फिर तुम इस method (या FuzzyWuzzy मॉड्यूल) की तर्ज पर कुछ का उपयोग कर सकते स्ट्रिंग समानता प्रतिशत खोजने के लिए, आप jaro_winkler या difflib में से एक को बाहर कर सकते अपनी गति और परिणाम की गुणवत्ता का अनुकूलन करने के:

def find_string_similarity(first_str, second_str, normalized=False, ignore_list=[]): 
    """ Calculates matching ratio between two strings 
    Args: 
     first_str (str) : First String 
     second_str (str) : Second String 
     normalized (bool) : if True ,method removes special characters and extra whitespace 
          from strings then calculates matching ratio 
     ignore_list (list) : list has some characters which has to be substituted with "" in string 
    Returns: 
     Float Value : Returns a matching ratio between 1.0 (most matching) and 0.0 (not matching) 
        using difflib's SequenceMatcher and and jellyfish's jaro_winkler algorithms with 
        equal weightage to each 
    Examples: 
     >>> find_string_similarity("hello world","Hello,World!",normalized=True) 
     1.0 
     >>> find_string_similarity("entrepreneurship","entreprenaurship") 
     0.95625 
     >>> find_string_similarity("Taj-Mahal","The Taj Mahal",normalized= True,ignore_list=["the","of"]) 
     1.0 
    """ 
    first_str = process_str_for_similarity_cmp(first_str, normalized=normalized, ignore_list=ignore_list) 
    second_str = process_str_for_similarity_cmp(second_str, normalized=normalized, ignore_list=ignore_list) 
    match_ratio = (difflib.SequenceMatcher(None, first_str, second_str).ratio() + jellyfish.jaro_winkler(unicode(first_str), unicode(second_str)))/2.0 
    return match_ratio 

Answer 2

ओ (एन^2) रन से बचने के लिए आपको तारों को इंडेक्स करना या सामान्य करना है। असल में, आपको प्रत्येक स्ट्रिंग को सामान्य रूप में मैप करना होगा, और संबंधित सामान्य रूपों से जुड़े सभी शब्दों के साथ एक रिवर्स डिक्शनरी बनाना होगा।

मान लें कि 'दुनिया' और 'शब्द' के सामान्य रूप समान हैं। तो, पहले Normalized -> [word1, word2, word3], उदा .: के उलट शब्दकोश का निर्माण

"world" <-> Normalized('world') 
"word" <-> Normalized('wrd') 

to: 

Normalized('world') -> ["world", "word"] 

ये लीजिए - सभी आइटम सामान्यीकृत dict जो एक से अधिक मूल्य में (सूचियों) - का मिलान नहीं हुआ शब्द हैं।

सामान्यीकरण एल्गोरिदम डेटा यानी शब्दों पर निर्भर करता है।कई में से एक पर विचार करें:

• Soundex
• metaphone
• डबल मेटाफोन
• NYSIIS
• Caverphone
• कोलोन ध्वन्यात्मक
• एमआरए कोडेक्स

Answer 3

फ़ज़ीवाज़ी के लिए विशिष्ट, ध्यान दें कि वर्तमान में प्रक्रिया .extract एक डब्लूआरएटीओओ को डिफ़ॉल्ट करता है जो उनके एल्गोरिदम के सबसे धीमे से है, और प्रोसेसर utils.full_process के लिए डिफ़ॉल्ट है। यदि आप अपने स्कोरर के रूप में fuzz.QRatio कहते हैं तो यह बहुत तेज हो जाएगा, लेकिन आप जो मिलान करने का प्रयास कर रहे हैं उसके आधार पर शक्तिशाली नहीं होंगे। यद्यपि नामों के लिए ठीक हो सकता है। मैं व्यक्तिगत रूप से token_set_ratio के साथ शुभकामनाएं देता हूं जो WRatio से कम से कम कुछ हद तक तेज है। आप पहले से अपने सभी विकल्पों पर utils.full_process() भी चला सकते हैं और फिर इसे अपने स्कोरर और प्रोसेसर के रूप में fuzz.ratio के साथ चला सकते हैं = प्रसंस्करण चरण को छोड़ने के लिए कोई भी नहीं। (नीचे देखें) यदि आप केवल मूल अनुपात फ़ंक्शन का उपयोग कर रहे हैं, तो फ़ज़ीज़वाज़ी शायद अधिकतर है। Fwiw मेरे पास एक जावास्क्रिप्ट पोर्ट (fuzzball.js) है जहां आप टोकन सेट को भी पूर्व-गणना कर सकते हैं और प्रत्येक बार पुन: गणना करने के बजाए उन लोगों का उपयोग कर सकते हैं।)

यह तुलना की भारी संख्या में कटौती नहीं करता है लेकिन इससे मदद मिलती है। (संभवतः इसके लिए बीके-पेड़? खुद को एक ही स्थिति में देख रहे थे)

यह भी सुनिश्चित करें कि पाइथन-लेवेनशेटिन स्थापित हो ताकि आप तेज़ गणना का उपयोग कर सकें।

** व्यवहार नीचे बदल सकता है, चर्चा आदि के तहत खुले मुद्दों। **

fuzz.ratio पूर्ण प्रक्रिया को चलाने नहीं करता, और token_set और token_sort कार्यों एक full_process = झूठी परम स्वीकार करते हैं, और आप हैं प्रोसेसर सेट न करें = कोई भी निकास फ़ंक्शन पूरी प्रक्रिया को चलाने की कोशिश करेगा। Funqools 'आंशिक का उपयोग fuzz.token_set_ratio में पूर्ण_प्रोसेस = अपने स्कोरर के रूप में गलत कहने के लिए कर सकते हैं, और पहले से अपने विकल्पों पर utils.full_process चला सकते हैं।