Jak uzyskać prawdopodobieństwo, że ciąg znaków będzie podobny do innego ciągu w Pythonie?

Chcę uzyskać wartość dziesiętną, taką jak 0,9 (co oznacza 90%) itp. Najlepiej ze standardowym Pythonem i biblioteką.

na przykład

similar("Apple","Appel") #would have a high prob.

similar("Apple","Mango") #would have a lower prob.

Jest wbudowany.

from difflib import SequenceMatcher

def similar(a, b):
    return SequenceMatcher(None, a, b).ratio()

Użyj tego:

>>> similar("Apple","Appel")
0.8
>>> similar("Apple","Mango")
0.0

Myślę, że może szukasz algorytmu opisującego odległość między łańcuchami. Oto niektóre, do których możesz się odwoływać:

1. Odległość Hamminga
2. Odległość Levenshteina
3. Odległość Damerau – Levenshtein
4. Odległość Jaro – Winkler

Rozwiązanie nr 1: Wbudowane Python

użyj SequenceMatcher z difflib

zalety : natywna biblioteka Pythona, nie potrzebujesz dodatkowego pakietu.
Wady : zbyt ograniczone, istnieje wiele innych dobrych algorytmów podobieństwa ciągów.

>>> from difflib import SequenceMatcher
>>> s = SequenceMatcher(None, "abcd", "bcde")
>>> s.ratio()
0.75

Rozwiązanie 2: Biblioteka meduz

jest to bardzo dobra biblioteka z dobrym zasięgiem i kilkoma numerami. obsługuje:
- Odległość Levenshtein - Odległość
Damerau-Levenshtein
- Odległość
Jaro - Odległość Jaro-Winkler
- Porównanie podejścia do oceny dopasowania
- Odległość Hamminga

zalety : łatwy w użyciu, gama obsługiwanych algorytmów, przetestowane.
Minusy : nie rodzima biblioteka.

przykład :

>>> import jellyfish
>>> jellyfish.levenshtein_distance(u'jellyfish', u'smellyfish')
2
>>> jellyfish.jaro_distance(u'jellyfish', u'smellyfish')
0.89629629629629637
>>> jellyfish.damerau_levenshtein_distance(u'jellyfish', u'jellyfihs')
1

Fuzzy Wuzzyto pakiet, który implementuje odległość Levenshteina w pythonie, z niektórymi funkcjami pomocniczymi, które pomagają w pewnych sytuacjach, w których możesz chcieć, aby dwa różne łańcuchy były uważane za identyczne. Na przykład:

>>> fuzz.ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    91
>>> fuzz.token_sort_ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    100

Możesz utworzyć funkcję taką jak:

def similar(w1, w2):
    w1 = w1 + ' ' * (len(w2) - len(w1))
    w2 = w2 + ' ' * (len(w1) - len(w2))
    return sum(1 if i == j else 0 for i, j in zip(w1, w2)) / float(len(w1))

Odległość paczki obejmuje odległość Levenshteina:

import distance
distance.levenshtein("lenvestein", "levenshtein")
# 3

Wbudowane SequenceMatcherjest bardzo powolne przy dużych wejściach, oto jak można to zrobić za pomocą diff-match-patch :

from diff_match_patch import diff_match_patch

def compute_similarity_and_diff(text1, text2):
    dmp = diff_match_patch()
    dmp.Diff_Timeout = 0.0
    diff = dmp.diff_main(text1, text2, False)

    # similarity
    common_text = sum([len(txt) for op, txt in diff if op == 0])
    text_length = max(len(text1), len(text2))
    sim = common_text / text_length

    return sim, diff

Uwaga: wyszukuje difflib.SequenceMatcher tylko najdłuższe ciągłe pasujące podciągi, często nie jest to pożądane, na przykład:

>>> a1 = "Apple"
>>> a2 = "Appel"
>>> a1 *= 50
>>> a2 *= 50
>>> SequenceMatcher(None, a1, a2).ratio()
0.012  # very low
>>> SequenceMatcher(None, a1, a2).get_matching_blocks()
[Match(a=0, b=0, size=3), Match(a=250, b=250, size=0)]  # only the first block is recorded

Znalezienie podobieństwa między dwoma łańcuchami jest ściśle związane z koncepcją parowania sekwencji w bioinformatyce. Istnieje wiele dedykowanych bibliotek do tego, w tym biopython . Ten przykład implementuje algorytm Needlemana Wunscha :

>>> from Bio.Align import PairwiseAligner
>>> aligner = PairwiseAligner()
>>> aligner.score(a1, a2)
200.0
>>> aligner.algorithm
'Needleman-Wunsch'

Korzystanie z biopython lub innego pakietu bioinformatyki jest bardziej elastyczne niż jakakolwiek część standardowej biblioteki Pythona, ponieważ dostępnych jest wiele różnych schematów oceniania i algorytmów. Ponadto możesz uzyskać pasujące sekwencje, aby wizualizować, co się dzieje:

>>> alignment = next(aligner.align(a1, a2))
>>> alignment.score
200.0
>>> print(alignment)
Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-
|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-
App-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-el

Większość metod podobieństwa tekstu i sposobu ich obliczania można znaleźć pod tym linkiem: https://github.com/luozhouyang/python-string-similarity#python-string-similarity Oto kilka przykładów;

• Znormalizowane, metryczne, podobieństwo i odległość

• (Znormalizowane) podobieństwo i odległość

• Odległości metryczne

• Półpasiec (podgrupa) oparty na podobieństwie i odległości
• Levenshtein
• Znormalizowany Levenshtein
• Ważona Levenshtein
• Damerau-Levenshtein
• Optymalne wyrównanie ciągów
• Jaro-Winkler
• Najdłuższa wspólna kolejność
• Najdłuższa wspólna sekwencja metryczna
• N-Gram
• Algorytmy oparte na gontach (n-gram)
• Q-Gram
• Cosinus podobieństwo
• Indeks Jaccard
• Współczynnik Sorensen-Dice
• Współczynnik nakładania się (tj. Szymkiewicz-Simpson)