स्ट्रिंग्स के दो अनुक्रमों के बीच समानता मापने के लिए एल्गोरिदम

Question

मैं तारों के दो अनुक्रमों के बीच समानता-प्रतिशत कैसे माप सकता हूं?

मैं दो पाठ फ़ाइलों है और फाइलों में वहाँ दृश्यों

पहले फाइल की तरह लिखा जाता है:

एएए बीबीबी DDD सीसीसी GGG MMM एएए MMM

दूसरा फ़ाइल:

बीबीबी डीडीडी सीसीसी एमएमएम एएए एमएमएम

तारों के क्रम में इन दो फ़ाइलों के बीच समानता को मापने के लिए कैसे?

उदाहरण के लिए उपरोक्त उदाहरण में तारों के क्रम के कारण दोनों फाइलों की समानता समान है हालांकि कुछ स्ट्रिंग फ़ाइल -2 में गायब हैं। इस समस्या को हल करने के लिए क्या एल्गोरिदम सबसे उपयुक्त है ताकि मैं माप सकूं कि तारों के क्रम में तारों की आवृत्ति कितनी समान नहीं है?

Answer 1

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

कॉपी पेस्ट:

1. Set n to be the length of s. ("GUMBO") 
    Set m to be the length of t. ("GAMBOL") 
    If n = 0, return m and exit. 
    If m = 0, return n and exit. 
    Construct two vectors, v0[m+1] and v1[m+1], containing 0..m elements. 
2. Initialize v0 to 0..m. 
3. Examine each character of s (i from 1 to n). 
4. Examine each character of t (j from 1 to m). 
5. If s[i] equals t[j], the cost is 0. 
    If s[i] is not equal to t[j], the cost is 1. 
6. Set cell v1[j] equal to the minimum of: 
    a. The cell immediately above plus 1: v1[j-1] + 1. 
    b. The cell immediately to the left plus 1: v0[j] + 1. 
    c. The cell diagonally above and to the left plus the cost: v0[j-1] + cost. 
7. After the iteration steps (3, 4, 5, 6) are complete, the distance is found in the cell v1[m]. 

Answer 2

आप अजगर के SequenceMatcher.ratio समारोह जो सीमा [0, 1] में एक नाव के रूप में दृश्यों समानता उपायों का उपयोग कर सकते हैं। यदि टी दोनों अनुक्रमों में तत्वों की कुल संख्या है, और एम मैचों की संख्या है, यह 2.0 * M/T है। मुख्य कोड निम्नानुसार है:

from difflib import SequenceMatcher 
text1 = 'AAA BBB DDD CCC GGG MMM AAA MMM' 
text2 = 'BBB DDD CCC MMM AAA MMM' 
s = SequenceMatcher(None, text1, text2) 
similarity = s.ratio() * 100 

मुझे उम्मीद है कि यह आपकी मदद कर सकता है!