मनमानी मिलान फ़ंक्शन का उपयोग करके पाइथन सूचियों को कैसे अलग/संरेखित करना है?

Question

मैं difflib.Differ के समान तरीके से दो सूचियों को संरेखित करना चाहता हूं, सिवाय इसके कि मैं आइटम की तुलना करने के लिए एक मैच फ़ंक्शन को परिभाषित करने में सक्षम होना चाहता हूं, केवल स्ट्रिंग समानता का उपयोग न करें, और अधिमानतः एक मैच फ़ंक्शन जो एक संख्या वापस कर सकता है 0.0 और 1.0 के बीच, सिर्फ एक बूलियन नहीं।

तो, उदाहरण के लिए, मैं दो सूचियों था:

L1 = [('A', 1), ('B', 3), ('C', 7)] 
L2 = ['A', 'b', 'C'] 

और मैं इस तरह एक मैच समारोह में लिखने के लिए सक्षम होना चाहते हैं:

def match(item1, item2): 
    if item1[0] == item2: 
     return 1.0 
    elif item1[0].lower() == item2.lower(): 
     return 0.5 
    else: 
     return 0.0 

और उसके बाद है:

d = Differ(match_func=match) 
d.compare(L1, L2) 

और यह मैच फ़ंक्शन का उपयोग करके भिन्न है। difflib की तरह, मैं बल्कि एल्गोरिदम ने पूरी तरह से न्यूनतम लेवेनशेटिन दूरी की बजाय अधिक सहज ज्ञान युक्त रत्क्लिफ-ओबर्सहेल्प प्रकार के परिणाम दिए।

Answer 1

मैं सिर्फ Needleman-Wunsch के इस कार्यान्वयन लिखा था और यह मैं क्या चाहते हो रहा है:

def nw_align(a, b, replace_func, insert, delete): 

    ZERO, LEFT, UP, DIAGONAL = 0, 1, 2, 3 

    len_a = len(a) 
    len_b = len(b) 

    matrix = [[(0, ZERO) for x in range(len_b + 1)] for y in range(len_a + 1)] 

    for i in range(len_a + 1): 
     matrix[i][0] = (insert * i, UP) 

    for j in range(len_b + 1): 
     matrix[0][j] = (delete * j, LEFT) 

    for i in range(1, len_a + 1): 
     for j in range(1, len_b + 1): 
      replace = replace_func(a[i - 1], b[j - 1]) 
      matrix[i][j] = max([ 
       (matrix[i - 1][j - 1][0] + replace, DIAGONAL), 
       (matrix[i][j - 1][0] + insert, LEFT), 
       (matrix[i - 1][j][0] + delete, UP) 
      ]) 

    i, j = len_a, len_b 
    align_a = "" 
    align_b = "" 

    while (i, j) != (0, 0): 
     if matrix[i][j][1] == DIAGONAL: 
      align_a += a[i - 1] 
      align_b += b[j - 1] 
      i -= 1 
      j -= 1 
     elif matrix[i][j][1] == LEFT: 
      align_a += "-" 
      align_b += b[j - 1] 
      j -= 1 
     else: # UP 
      align_a += a[i - 1] 
      align_b += "-" 
      i -= 1 

    return align_a[::-1], align_b[::-1] 

Answer 2

मैंने हाल ही में patience diff नामक एल्गोरिदम की चर्चा में भाग लिया जो अपेक्षाकृत आसान लगता है। आप इसे स्वयं लागू करने का प्रयास कर सकते हैं, और फिर निश्चित रूप से आप इसे जो भी तुलना एल्गोरिदम पसंद करते हैं उसका उपयोग कर सकते हैं।