문자열 중복 검색을위한 파이썬 코드 최적화

Question

긴 목록에 문자열 (약 18k 항목)이 있습니다. 목표는 모든 유사한 문자열을 찾아 최대 유사성으로 그룹화하는 것입니다.

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

dupl = {} 

while len(a) > 0: 
    k = a.pop() 
    if k not in dupl.keys(): 
     dupl[k] = [] 
    for i,j in enumerate(a): 
      dif = diff(k, j) 
      if dif > 0.5: 
       dupl[k].append("{0}: {1}".format(dif, j)) 

이 코드는 목록에서 요소를 가지고 목록의 나머지 부분에서 중복 검색 : ("a"는 문자열 목록입니다)

나는 다음과 같은 코드를 작성했다. 유사도가 0.5 이상이면 유사한 문자열이 dict에 추가됩니다.

모든 것이 잘 작동하지만 목록 "a"의 길이 때문에 매우 느립니다. 그래서 어떻게 든이 코드를 최적화 할 수있는 방법이 있습니까? 어떤 아이디어?

Answer 1

작은 최적화의 몇 :

1. 당신은 (검색을 시작하기 전에 목록에서 중복을 제거 할 수 있습니다 예 : a = list (set (a))). 현재 'a hello'문자열에 18k 복사본이 포함되어 있으면 diff가 18k * 18k 번 호출됩니다.

2. 현재 문자열 번호 i를 문자열 번호 j와 비교하고 문자열 번호 j를 문자열 번호 i와 비교합니다. 나는 이것들이 같은 결과를 리턴 할 것이므로 여러분은 이것들 중 하나만 계산할 수 있고 아마 두 배나 빠르게 갈 것이라고 생각합니다. 물론

는 기본적인 문제는 DIFF는 시간이 호출되고 diff를의 수를 줄이는 것 길이 n과 이상적인 솔루션의 목록은 n 개의 * n 번을 호출되고 있다는 점이다. 사용 방법은 문자열의 내용에 따라 다릅니다.

1. 이 문자열이 매우 다른 길이의 가정합시다 : 여기

   다른 경우에 해당 될 것이다 가능한 방법의 몇 가지 예입니다. diff는 문자열의 길이가 2의 인수 내에있는 경우에만 0.5 이상을 반환합니다.이 경우 O (nlogn) 시간의 길이로 입력 문자열을 정렬 한 다음 비슷한 길이의 문자열을 비교할 수 있습니다.

2. 문자열이 일련의 단어로 구성되어 있고 매우 다르거 나 매우 유사 할 것으로 예상한다고 가정합니다. 단어에 대해 역 색인을 구성한 다음 동일한 비정상적인 단어가 포함 된 문자열과 비교하십시오.

3. 문자열이 소수의 그룹에 속한다고 가정하십시오. K 평균 알고리즘을 실행하여 클러스터로 그룹화 할 수 있습니다. 이것은 K * n * I를 취할 것입니다. 여기서 나는 당신이 사용하기로 결정한 K- 평균 알고리즘의 반복 횟수입니다.

n이 매우 커지면 (수백만),이 값은 적절하지 않으므로보다 근사적인 기술을 사용해야 할 것입니다. 웹 페이지를 클러스터링하는 데 사용되는 한 예는 MinHash

Answer 2

많은 항목을 반복 할 필요가있을 때 itertools!

이 스 니펫은 문자열의 모든 가능성을 순열 (permutations)하여 원본 코드와 같은 방식으로 반환합니다. not in은 불필요하게 비싼 방법으로 확인하고 파이썬이 아닌 것처럼 느낍니다. 순열은 두 개의 지정된 문자열에 대해 a-> b 또는 b-> a를 확인하는 데 가장 많이 액세스 할 수 있도록 선택되었습니다.

import difflib 
import itertools 

def diff(a, b): 
    return difflib.SequenceMatcher(None, a, b).quick_ratio() 

def calculate_ratios(strings): 
    dupl = dict() 
    for s, t in itertools.permutations(strings, 2): 
      try: 
       dupl[s].append({t: diff(s,t)}) 
      except KeyError: 
       dupl[s] = [] 
       dupl[s].append({t: diff(s,t)}) 
    return dupl 

a = ['first string', 'second string', 'third string', 'fourth string'] 
print calculate_ratios(a) 

, 제약 조건에 따라 (순열 때문에 중복 계산 및 공간 현명한), 당신은 조합 순열을 대체 할 수 있지만 다음 액세스하는 방법은 AB는 만 나열되기 때문에 (조정해야합니다 [b]가 아니라 b [a]).

코드에서 quick_ratio()를 사용하지만, 정밀도가 충분한 지 여부에 따라 ratio() 또는 real_quick_ratio()로 간단히 변경됩니다.

그리고 그러한 경우에

는 간단한 IF는 그 문제를 해결할 수 :

import difflib 
import itertools 

def diff(a, b): 
    return difflib.SequenceMatcher(None, a, b).quick_ratio() 
def diff2(a, b): 
    return difflib.SequenceMatcher(None, a, b).ratio() 

def calculate_ratios(strings, threshold): 
    dupl = dict() 
    for s, t in itertools.permutations(strings, 2): 
      if diff(s,t) > threshold: #arbitrary threshhold 
       try: 
        dupl[s].append({t: diff2(s,t)}) 
       except KeyError: 
        dupl[s] = [] 
        dupl[s].append({t: diff2(s,t)}) 
    return dupl 

a = ['first string', 'second string', 'third string', 'fourth string'] 
print calculate_ratios(a, 0.5)