Perbandingan string fuzzy berperforma tinggi dengan Python, gunakan Levenshtein atau difflib [tertutup]

Saya melakukan normalisasi pesan klinis (pemeriksaan ejaan) di mana saya memeriksa setiap kata yang diberikan dengan 900.000 kata kamus medis. Saya lebih memperhatikan kompleksitas waktu / kinerja.

Saya ingin melakukan perbandingan string fuzzy, tetapi saya tidak yakin perpustakaan mana yang akan digunakan.

Pilihan 1:

import Levenshtein
Levenshtein.ratio('hello world', 'hello')

Result: 0.625

Pilihan 2:

import difflib
difflib.SequenceMatcher(None, 'hello world', 'hello').ratio()

Result: 0.625

Dalam contoh ini keduanya memberikan jawaban yang sama. Apakah menurut Anda keduanya bekerja sama dalam kasus ini?

Jika Anda tertarik dengan perbandingan visual singkat kemiripan Levenshtein dan Difflib, saya menghitung keduanya untuk ~ 2,3 juta judul buku:

import codecs, difflib, Levenshtein, distance

with codecs.open("titles.tsv","r","utf-8") as f:
    title_list = f.read().split("\n")[:-1]

    for row in title_list:

        sr      = row.lower().split("\t")

        diffl   = difflib.SequenceMatcher(None, sr[3], sr[4]).ratio()
        lev     = Levenshtein.ratio(sr[3], sr[4]) 
        sor     = 1 - distance.sorensen(sr[3], sr[4])
        jac     = 1 - distance.jaccard(sr[3], sr[4])

        print diffl, lev, sor, jac

Saya kemudian memplot hasilnya dengan R:

Khusus untuk yang penasaran, saya juga membandingkan nilai kesamaan Difflib, Levenshtein, Sørensen, dan Jaccard:

library(ggplot2)
require(GGally)

difflib <- read.table("similarity_measures.txt", sep = " ")
colnames(difflib) <- c("difflib", "levenshtein", "sorensen", "jaccard")

ggpairs(difflib)

Hasil:

Kemiripan Difflib / Levenshtein sebenarnya cukup menarik.

Edit 2018: Jika Anda bekerja untuk mengidentifikasi string yang serupa, Anda juga dapat melihat minhashing - ada gambaran umum yang bagus di sini . Minhashing luar biasa dalam menemukan kesamaan dalam koleksi teks besar dalam waktu linier. Lab saya mengumpulkan aplikasi yang mendeteksi dan memvisualisasikan penggunaan ulang teks menggunakan minhashing di sini: https://github.com/YaleDHLab/intertext

• difflib.SequenceMatcher menggunakan algoritma Ratcliff / Obershelp yang menghitung dua kali lipat jumlah karakter yang cocok dibagi dengan jumlah total karakter dalam dua string.

• Levenshtein menggunakan algoritma Levenshtein yang menghitung jumlah minimum pengeditan yang diperlukan untuk mengubah satu string menjadi yang lain

Kompleksitas

SequenceMatcher adalah waktu kuadrat untuk kasus terburuk dan memiliki perilaku kasus yang diharapkan bergantung secara rumit pada berapa banyak elemen yang dimiliki urutan tersebut. ( dari sini )

Levenshtein adalah O (m * n), di mana n dan m adalah panjang dari dua string input.

Performa

Menurut kode sumber modul Levenshtein: Levenshtein memiliki beberapa tumpang tindih dengan difflib (SequenceMatcher). Ini hanya mendukung string, bukan jenis urutan sewenang-wenang, tetapi di sisi lain itu jauh lebih cepat.