대규모 문자열 비교

Question

큰 문자열 세트에서 비슷한 문자열 쌍을 찾으려고합니다. 저는 약 1 억 개의 문자열을 가지고 있으며 문자열 유사성은 편집 거리로 측정됩니다. 예를 들어, "이것은 문장"이고 "이것은 또한 문장"입니다.

각 두 문자열 간의 유사성을 계산하는 것은 실용적이지 않으므로 100M x 100M 계산이 가능합니다. 먼저 문자열을 "대략 비슷한"하위 집합으로 그룹화 한 다음 하위 집합 내의 각 문자열 쌍을 계산하는 분할 및 정복 전략을 고려합니다. 예를 들어,

str1 = "this is a sentence" 
str2 = "this is also a sentence" 
str3 = "Mary loves elephants" 
str4 = "Mary loves an elephant" 
str5 = "Mark loves elephants" 

가 나는 부분 집합 [STR1, STR2] 다른 부분 집합 [STR3, STR4, STR5]를하도록 노력하겠습니다, 나는 다음과 같은 5 문자열을 말한다. 그런 다음 str1과 str2를 비교하여 이들이 유사한 지 확인합니다. 또한 str3, str4, str5를 비교하여 유사한 쌍을 찾습니다. 총 계산은 C^2_5 = 10에서 C^2_2 + C^2_3 = 4로 감소합니다.

나누기가 빠르기 때문에 정확할 필요는 없습니다. 부분 집합은 겹칠 수 있습니다. 때로는 문자열의 비슷한 쌍이 같은 하위 집합에 포함되어 있지 않은 경우 허용 가능합니다. 그러면 가까운 하위 집합을 스캔합니다.

문자열을 정수로 대략적으로 매핑하기 위해 (순서는 중요하지 않음) 순서 보존 된 해시 메서드를 찾으려고 시도했으며 각 문자열을 가까운 정수로 후보 문자열과 비교하여 검사했습니다. 그러나 나는 그런 알고리즘을 찾지 못한다.

저는 파이썬을 사용하고 있습니다. 솔루션이 다른 프로그래밍 언어에서만 적용 가능하면 시도해 볼 수 있습니다.

대단히 감사합니다.

Answer 1

정렬 할 때 주요 기능으로 Levenshtein 거리를 사용할 수 있습니다.

import requests 
import Levenshtein as L 

def download_moby_dick(): 
    moby_dick_url = 'https://www.gutenberg.org/files/2701/2701-0.txt' 
    return requests.get(moby_dick_url).text 

def sentences_in_book(book): 
    sentences = (s for s in re.split(r'[.;?!]\s|\r\n\r\n', moby_dick)) 
    sentences = (re.sub('\s+', ' ', s).strip() for s in sentences) 
    sentences = (s for s in sentences if len(s) > 10) 
    return list(sentences) 

sentences = sentences_in_book(download_moby_dick()) 

# sort by length 
sentences.sort(key=len) 

# median length sentence 
target = sentences[len(sentences)//2] 

# sort by levenshtein distance to target 
def keyfunc(sentence): 
    return L.distance(target, sentence) 

sentences.sort(key=keyfunc) 

이렇게하면 유사한 문장이 함께 그룹화되는 대략적인 순서가됩니다. 속도를 높이려면 작업을 추가로 분할해야 할 수도 있습니다. 예를 들어, 각 단어의 일부 문자, 대략 길이가 같은 검색 문장 만 사용하여 입력 된 문장을 줄여서 입력하십시오.