Temukan metrik kesamaan antara dua string

284

Bagaimana cara mendapatkan probabilitas string yang mirip dengan string lain dengan Python?

Saya ingin mendapatkan nilai desimal seperti 0,9 (artinya 90%) dll. Lebih disukai dengan Python dan pustaka standar.

misalnya

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

similar("Apple","Mango") #would have a lower prob.
python probability similarity metric tenstar
sumber
6
Saya tidak berpikir "probabilitas" adalah istilah yang tepat di sini. Dalam hal apa pun, lihat stackoverflow.com/questions/682367/…
NPE
1
Kata yang Anda cari adalah rasio, bukan probabilitas.
Inbar Rose
1
Lihatlah jarak Hamming .
Diana
2
Ungkapannya adalah 'kesamaan metrik' , tetapi ada beberapa metrik kesamaan (Jaccard, Cosine, Hamming, Levenshein, dll.) Mengatakan Anda harus menentukan yang mana. Khususnya Anda ingin metrik kesamaan antara string; @ hbprotoss mencantumkan beberapa.
smci

Jawaban:

545

Ada built in.

from difflib import SequenceMatcher

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

Menggunakannya:

>>> similar("Apple","Appel")
0.8
>>> similar("Apple","Mango")
0.0
Inbar Rose
sumber
43
Lihat jawaban yang bagus ini membandingkan SequenceMatchervs python-Levenshteinmodul. stackoverflow.com/questions/6690739/…
ssoler
1
Artikel dan alat yang menarik: chairnerd.seatgeek.com/...
Anthony Perot
7
Saya akan sangat menyarankan memeriksa seluruh dokumen doc .python.org/2/library/difflib.html difflib ada get_close_matches, meskipun saya menemukan sorted(... key=lambda x: difflib.SequenceMatcher(None, x, search).ratio(), ...)lebih dapat diandalkan, dengan sorted(... .get_matching_blocks())[-1] > min_matchpemeriksaan kustom
ThorSummoner
2
@ThorSummoner memberi perhatian pada fungsi yang sangat berguna ( get_closest_matches). Ini adalah fungsi kenyamanan yang mungkin apa yang Anda cari, AKA membaca dokumen! Dalam aplikasi khusus saya, saya melakukan beberapa pengecekan / pelaporan kesalahan dasar kepada pengguna yang memberikan input buruk, dan jawaban ini memungkinkan saya untuk melaporkan kepada mereka kemungkinan kecocokan dan apa "kesamaan" itu. Namun, jika Anda tidak perlu menampilkan kemiripannya, silakan cekget_closest_matches
svenev
Ini bekerja dengan sempurna. Sederhana dan efektif. Terima kasih :)
Karthic Srinivasan
46

Solusi # 1: Python builtin

gunakan SequenceMatcher dari difflib

pro : perpustakaan python asli, tidak perlu paket tambahan.
kontra : terlalu terbatas, ada banyak algoritma bagus lainnya untuk kesamaan string di luar sana.

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

Solusi # 2: perpustakaan ubur-ubur

ini adalah perpustakaan yang sangat bagus dengan jangkauan yang baik dan beberapa masalah. itu mendukung:
- Jarak Levenshtein - Jarak
Damerau-Levenshtein
- Jarak
Jaro - Jarak Jaro-Winkler
- Perbandingan Pendekatan Penilaian Pertandingan
- Jarak Hamming

pro : mudah digunakan, keseluruhan algoritma yang didukung, diuji.
kontra : bukan perpustakaan asli.

contoh : 

>>> 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
Iman Mirzadeh
sumber
26

Fuzzy Wuzzyadalah paket yang mengimplementasikan jarak Levenshtein dalam python, dengan beberapa fungsi pembantu untuk membantu dalam situasi tertentu di mana Anda mungkin ingin dua string berbeda dianggap identik. Sebagai contoh:

>>> 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
BLT
sumber
9

Anda dapat membuat fungsi seperti:

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))
Saullo GP Castro
sumber
tetapi serupa ('appel', 'apple') lebih tinggi daripada yang serupa ('appel', 'ape')
tenstar
1
Fungsi Anda akan membandingkan string yang diberikan dengan sengatan lainnya. Saya ingin cara mengembalikan string dengan rasio kesamaan tertinggi
answerSeeker
1
@ SaulloCastro, if self.similar(search_string, item.text()) > 0.80:berfungsi untuk saat ini. Terima kasih,
answerSeeker
9

Jarak paket termasuk jarak Levenshtein:

import distance
distance.levenshtein("lenvestein", "levenshtein")
# 3
Enrique Pérez Herrero
sumber
6

Builtin SequenceMatchersangat lambat pada input besar, begini caranya bisa dilakukan dengan 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
damio
sumber
5

Catatan, difflib.SequenceMatcher hanya menemukan urutan pencocokan berdekatan terpanjang, ini sering kali bukan yang diinginkan, misalnya:

>>> 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

Menemukan kesamaan antara dua string terkait erat dengan konsep penyelarasan urutan berpasangan dalam bioinformatika. Ada banyak perpustakaan khusus untuk ini termasuk biopython . Contoh ini mengimplementasikan algoritma Needleman Wunsch :

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

Menggunakan biopython atau paket bioinformatika lainnya lebih fleksibel daripada bagian mana pun dari pustaka standar python karena banyak skema penilaian dan algoritma yang berbeda tersedia. Anda juga bisa mendapatkan urutan yang cocok untuk memvisualisasikan apa yang terjadi:

>>> 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
Chris_Rands
sumber
0

Anda dapat menemukan sebagian besar metode kesamaan teks dan bagaimana mereka dihitung di bawah tautan ini: https://github.com/luozhouyang/python-string-similarity#python-string-similarity Berikut beberapa contoh;

  • Dinormalisasi, metrik, kesamaan dan jarak

  • (Normalisasi) kesamaan dan jarak

  • Jarak metrik

  • Herpes zoster (n-gram) berdasarkan kesamaan dan jarak
  • Levenshtein
  • Levenshtein yang dinormalisasi
  • Levenshtein tertimbang
  • Damerau-Levenshtein
  • Penyelarasan String yang Optimal
  • Jaro-Winkler
  • Pemanjangan Umum Paling Lama
  • Metrik Sub-urutan Umum Paling Lama
  • N-Gram
  • Algoritma berbasis shingle (n-gram)
  • Q-Gram
  • Kesamaan cosinus
  • Indeks Jaccard
  • Koefisien Sorensen-Dice
  • Koefisien tumpang tindih (yaitu, Szymkiewicz-Simpson)
Mike
sumber