파이썬에서 일치하는 퍼지 문자열

Question

나는 약간 다른 명명 규칙을 사용하여 백만 명이 넘는 2 개의 목록을 가지고 있습니다. 목표는 95 % 신뢰의 논리를 사용하여 유사한 레코드를 일치시키는 것입니다.

Python의 FuzzyWuzzy 모듈과 같이 내가 활용할 수있는 라이브러리가 있음을 알고 있습니다.

그러나 처리 측면에서 볼 때 하나의 목록에있는 모든 문자열을 다른 목록과 비교하는 데 너무 많은 리소스가 필요하며이 경우에는 백만 분의 1 회의 반복 횟수가 필요합니다.

이 문제에 대한 다른보다 효율적인 방법이 있습니까?

UPDATE : 사용 파이톤 판다 바이 그래서이 버킷 팅 기능을 만들어 공백 심볼을 제거하는 등을 소문자로 값을 변환하는 간단한 정규화를 적용

...

for n in list(dftest['YM'].unique()): 
    n = str(n) 
    frame = dftest['Name'][dftest['YM'] == n] 
    print len(frame) 
    print n 
    for names in tqdm(frame): 
      closest = process.extractOne(names,frame) 

데이터 년 단위로 그룹화 된 작은 버킷에로드 된 다음 FuzzyWuzzy 모듈을 사용하여 process.extractOne이 가장 잘 일치하는 데 사용됩니다.

결과는 여전히 다소 실망 스럽습니다. 테스트 동안 위의 코드는 약 5 천명의 이름을 포함하는 테스트 데이터 프레임에 사용되고 거의 한 시간이 걸립니다.

테스트 데이터는에 의해 나뉩니다. 출생

그리고 나는 그들의 YMS는 같은 양동이에 양동이에 의해 그들을 비교하고 날짜의

• 이름
• 년 월.

  내가 사용중인 FuzzyWuzzy 모듈로 인해 문제가 발생할 수 있습니까? 어떤 도움을 주시면 감사하겠습니다.

Answer 1

여러 가지 수준이있다 작전 이 문제를 O (n^2)에서 덜 복잡한 시간으로 바꿀 수 있습니다.

• 전처리는 각 문자열 출력 맵을 만드는 첫 번째 패스에서 목록을 정렬, 맵에 대한 그들은 키 문자열을 정상화 할 수 있습니다. 정상화를 포함 할 수있다

  • 소문자 변환,
  • 없는 공백, 특수 문자 제거,
  • 이 unicodedata.normalize 또는 unidecode 모듈을 가능하면 아스키 등가물에 유니 코드 변환 사용)

  이 초래을 "Andrew H Smith", "andrew h. smith", "ándréw h. smith" 같은 키를 생성 중 "andrewhsmith"이며 백만 개의 이름이 smalle로 줄어 듭니다. r 고유 한/유사한 그룹화 된 이름 집합.

당신은 (비록 유니 코드 부분은 포함되지 않음) 문자열을 정상화하기 위해이 utlity method을 사용할 수 있습니다

: 자신의 정규화 키 경우

def process_str_for_similarity_cmp(input_str, normalized=False, ignore_list=[]): 
    """ Processes string for similarity comparisons , cleans special characters and extra whitespaces 
     if normalized is True and removes the substrings which are in ignore_list) 
    Args: 
     input_str (str) : input string to be processed 
     normalized (bool) : if True , method removes special characters and extra whitespace from string, 
          and converts to lowercase 
     ignore_list (list) : the substrings which need to be removed from the input string 
    Returns: 
     str : returns processed string 
    """ 
    for ignore_str in ignore_list: 
     input_str = re.sub(r'{0}'.format(ignore_str), "", input_str, flags=re.IGNORECASE) 

    if normalized is True: 
     input_str = input_str.strip().lower() 
     #clean special chars and extra whitespace 
     input_str = re.sub("\W", "", input_str).strip() 

    return input_str 

• 지금과 비슷한 문자열이 이미 같은 양동이에 거짓말 것 동일합니다.

• 이 아닌 키만 비교하면됩니다. 예를 들어 andrewhsmith 및 andrewhsmeeth인데, 이는이 유사도가 위의 비교에서 정규화 된 과 다른 퍼지 문자열 매칭을 필요로하기 때문입니다.

• 버킷 팅 : 당신이 정말 95 % 일치 있는지 확인하기 위해 9 문자 키와 5 문자 키를 비교해야합니까? 아니야. 문자열 일치와 관련된 버킷을 만들 수 있습니다. 예 : 5 문자 이름은 4-6 문자 이름, 5-7 문자 등 6 문자 이름과 일치합니다. n 문자 키에 대한 n + 1, n-1 문자 제한은 가장 실용적인 일치를위한 비교적 좋은 양동이입니다.

• 시작 일치 : 대부분의 변형은 정규화 된 형식 (예 :.g Andrew H Smith, ándréw h. smith 및 Andrew H. Smeeth은 각각 andrewhsmith, andrewhsmith 및 andrewhsmeeth 키를 생성합니다. 그들은 일반적으로 첫 번째 문자가 다르지 않으므로 a으로 시작하는 키와 a으로 시작하고 길이 버킷에 속하는 다른 키와의 일치를 실행할 수 있습니다. 이것은 귀하의 매치 시간을 대폭 감소시킵니다. andrewhsmith을 bndrewhsmith과 일치시킬 필요가 없으므로 첫 글자와 같은 이름 변형이 거의 존재하지 않습니다.

  def find_string_similarity(first_str, second_str, normalized=False, ignore_list=[]): 
      """ Calculates matching ratio between two strings 
      Args: 
       first_str (str) : First String 
       second_str (str) : Second String 
       normalized (bool) : if True ,method removes special characters and extra whitespace 
            from strings then calculates matching ratio 
       ignore_list (list) : list has some characters which has to be substituted with "" in string 
      Returns: 
       Float Value : Returns a matching ratio between 1.0 (most matching) and 0.0 (not matching) 
          using difflib's SequenceMatcher and and jellyfish's jaro_winkler algorithms with 
          equal weightage to each 
      Examples: 
       >>> find_string_similarity("hello world","Hello,World!",normalized=True) 
       1.0 
       >>> find_string_similarity("entrepreneurship","entreprenaurship") 
       0.95625 
       >>> find_string_similarity("Taj-Mahal","The Taj Mahal",normalized= True,ignore_list=["the","of"]) 
       1.0 
      """ 
      first_str = process_str_for_similarity_cmp(first_str, normalized=normalized, ignore_list=ignore_list) 
      second_str = process_str_for_similarity_cmp(second_str, normalized=normalized, ignore_list=ignore_list) 
      match_ratio = (difflib.SequenceMatcher(None, first_str, second_str).ratio() + jellyfish.jaro_winkler(unicode(first_str), unicode(second_str)))/2.0 
      return match_ratio 
  

  :

그런 다음 당신은 당신의 속도와 결과의 품질을 최적화하기 위해, 당신은 jaro_winkler 또는 difflib 중 하나를 제외 할 수 문자열 유사성 비율을 찾으려면이 method (또는 FuzzyWuzzy 모듈)의 라인에 뭔가를 사용할 수 있습니다

Answer 2

O (n^2) 실행을 피하려면 문자열을 색인화하거나 정규화해야합니다. 기본적으로 각 문자열을 일반 형식으로 매핑하고 모든 정규 표현식과 연결된 역 사전을 작성해야합니다.

정상적인 형태의 '세계'와 '단어'가 동일하다고 가정 해 보겠습니다. 그래서 먼저 Normalized -> [word1, word2, word3], 예컨대 :의 반전 사전을 구축 거기 가서

"world" <-> Normalized('world') 
"word" <-> Normalized('wrd') 

to: 

Normalized('world') -> ["world", "word"] 

- 하나 개 이상의 값을 정규화 DICT의 모든 항목 (목록) - 일치하는 단어입니다.

정규화 알고리즘은 데이터 즉 단어에 의존합니다.많은 중 하나를 고려하십시오

• Soundex와
• 메타 폰
• 더블 메타 폰
• NYSIIS
• Caverphone
• 쾰른 소리 나는
• MRA의 사본을

Answer 3

fuzzywuzzy와 관련하여 현재 process.extractOne의 기본값은 알고리즘 중에서 가장 느린 WRatio이며 프로세서의 기본값은 utils.full_process입니다. 당신이 fuzz.QRatio를 당신의 득점 원으로 말하면, 당신은 당신이 뭘하려고하는지에 따라 훨씬 빠르지 만 강력하지 않을 것입니다. 이름은 괜찮을 지 모르지만. 필자는 개인적으로 WRatio보다 다소 빠른 token_set_ratio를 가지고 행운을 빕니다. 사전에 모든 선택 사항에 대해 utils.full_process()를 실행 한 다음 스코어러로 fuzz.ratio를 사용하고 processor = None을 사용하여 처리 단계를 건너 뛸 수도 있습니다. (아래 참조) 기본 비율 함수를 사용하고 있다면 fuzzywuzzy가 아마도 과장 될 것입니다. Fwiw 토큰 세트를 미리 계산할 수 있고 매번 다시 계산하는 대신 JavaScript 포트 (fuzzball.js)를 사용합니다.

이것은 비교의 수를 줄이지는 않지만 도움이됩니다. (BK-tree for this? 아마도 같은 상황을 직접 들여다 보았습니다.)

더 빠른 계산을 사용하려면 python-Levenshtein도 설치해야합니다.

** 동작은 아래에 변경 될 수 있습니다, 토론 등 아래 개방 문제를 해결합니다. **

fuzz.ratio 전체 프로세스를 실행하지 않으며, token_set 및 token_sort 기능이 full_process = 거짓 PARAM을 허용하고 만약 설정하지 마십시오 프로세서 = 없음 추출 기능은 어쨌든 전체 프로세스를 실행하려고합니다. Functools의 부분을 사용하여 fuzz.token_set_ratio에서 full_process = False를 기록원으로하고, 미리 선택에 따라 utils.full_process를 실행할 수 있습니다.