Python에서 퍼지 문자열 비교 고성능, Levenshtein 또는 difflib 사용

Python에서 퍼지 문자열 비교 고성능, Levenshtein 또는 difflib 사용

---

나는 900,000 단어 의학 사전에 대해 주어진 각 단어를 검사하는 임상 메시지 정규화 (맞춤법 검사)를하고 있습니다. 시간 복잡성 / 성능이 더 중요합니다.

퍼지 문자열 비교를 원하지만 사용할 라이브러리를 잘 모르겠습니다.

옵션 1:

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

Result: 0.625

옵션 2 :

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

Result: 0.625

이 예에서는 둘 다 같은 대답을합니다. 이 경우에 둘 다 똑같이 수행한다고 생각하십니까?

---

Levenshtein과 Difflib 유사성의 빠른 시각적 비교에 관심이 있다면 ~ 230 만 권의 책 제목에 대해 두 가지를 모두 계산했습니다.

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

그런 다음 R로 결과를 플로팅했습니다.

나는 호기심 때문에 Difflib, Levenshtein, Sørensen 및 Jaccard 유사성 값을 비교했습니다.

library(ggplot2)
require(GGally)

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

ggpairs(difflib)

결과:

Difflib / Levenshtein 유사성은 실제로 매우 흥미 롭습니다.

2018 edit: If you're working on identifying similar strings, you could also check out minhashing--there's a great overview here. Minhashing is amazing at finding similarities in large text collections in linear time. My lab put together an app that detects and visualizes text reuse using minhashing here: https://github.com/YaleDHLab/intertext

---

• difflib.SequenceMatcher uses the Ratcliff/Obershelp algorithm it computes the doubled number of matching characters divided by the total number of characters in the two strings.

• Levenshtein uses Levenshtein algorithm it computes the minimum number of edits needed to transform one string into the other

Complexity

SequenceMatcher는 최악의 경우 2 차 시간이며 시퀀스의 공통 요소 수에 따라 복잡한 방식으로 예상되는 동작을 수행합니다. ( 여기에서 )

Levenshtein은 O (m * n)이며, 여기서 n과 m은 두 입력 문자열의 길이입니다.

공연

Levenshtein 모듈 의 소스 코드 에 따르면 : Levenshtein은 difflib (SequenceMatcher)와 약간 중복됩니다. 임의의 시퀀스 유형이 아닌 문자열 만 지원하지만, 훨씬 빠릅니다.

참고 : https://stackoverflow.com/questions/6690739/high-performance-fuzzy-string-comparison-in-python-use-levenshtein-or-difflib