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

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

닫혔습니다. 이 질문은.여론에 입각한현재 답변을 수락하고 있지 않습니다.

---

이 질문을 개선하고 싶으십니까?이 게시물을 편집하여 사실과 인용문으로 답변할 수 있도록 질문을 업데이트합니다.

7년 전에 문을 닫았습니다.

이 질문을 개선합니다.

저는 90만 단어의 의학 사전과 대조하여 각각의 단어를 확인하는 임상 메시지 정규화(스펠 체크)를 하고 있습니다.시간 복잡성/성능이 더 걱정됩니다.

퍼지 문자열 비교를 하고 싶은데 어떤 라이브러리를 사용해야 할지 모르겠어요.

옵션 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년 편집:유사한 문자열을 식별하는 작업을 수행하는 경우 마이매싱도 확인할 수 있습니다. 여기에는 훌륭한 개요가 나와 있습니다.Minhashing은 선형 시간 내에 대규모 텍스트 컬렉션에서 유사점을 찾는 데 탁월합니다.제 연구소는 여기에 민매싱을 사용하여 텍스트 재사용을 감지하고 시각화하는 앱을 만들었습니다. https://github.com/YaleDHLab/intertext

• 디플립의SequenceMatcher는 Ratcliff/Obershelp 알고리즘을 사용하여 일치하는 문자 수를 두 문자열의 총 문자 수로 나눈 값을 계산합니다.

• Levenshtein은 Levenshtein 알고리즘을 사용하여 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 수를 계산합니다.

복잡성

SequenceMatcher는 최악의 경우에 대한 2차 시간이며 시퀀스에 공통된 요소가 몇 개 있는지에 대해 복잡한 방식으로 의존하는 예상 사례 동작을 갖습니다. (여기서부터)

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

성능

Levenshtein 모듈의 소스 코드에 따르면 Levenshtein은 difflib(SequenceMatcher)와 일부 겹칩니다.임의의 시퀀스 유형이 아닌 문자열만 지원하지만 다른 한편으로는 훨씬 빠릅니다.

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