The simplest technique to find duplicate examples would be to perform exact string matching between all example pairs, but as we will show, this is insufficient. We introduce two complementary methods for performing deduplication. First, using a suffix array Manber and Myers (1993), we remove duplicate substrings from the dataset if they occur verbatim in more than one example. Second, we use MinHash Broder (1997), an efficient algorithm for estimating the \(n\)-gram similarity between all pairs of examples in a corpus, to remove entire examples from the dataset if they have high \(n\)-gram overlap with any other example.
중복 예제를 찾는 가장 간단한 방법은 모든 예제 쌍 사이에서 정확한 문자열 일치를 수행하는 것이지만, 우리가 보여줄 것처럼 이는 불충분합니다. 우리는 중복 제거를 수행하기 위한 두 가지 보완적인 방법을 소개합니다. 첫째, Manber와 Myers (1993)의 접미사 배열을 사용하여, 한 예제에서 그대로 여러 번 발생하는 중복 문자열을 데이터셋에서 제거합니다. 둘째, Broder (1997)의 MinHash를 사용하여, 코퍼스 내 모든 예제 쌍 사이의 \(n\)-그램 유사성을 효율적으로 추정하고, 다른 예제와 높은 \(n\)-그램 중복을 가지는 전체 예제를 데이터셋에서 제거합니다.
중복 예제를 찾는 가장 간단한 방법은 모든 예제 쌍 간에 정확한 문자열 일치를 수행하는 것이지만, 다음에서 보여드리듯이 이것만으로는 충분하지 않습니다. 중복 제거를 수행하기 위한 두 가지 상호 보완적인 방법을 소개합니다. 첫째, 접미사 배열 Manber와 Myers(1993)를 사용하여 데이터 집합에서 두 개 이상의 예제에서 축어적으로 발생하는 중복 하위 문자열을 제거합니다. 둘째, 말뭉치의 모든 예제 쌍 간의 \(n\)-그램 유사성을 추정하는 효율적인 알고리즘인 MinHash Broder(1997)를 사용하여 다른 예제와 \(n\)-그램이 많이 겹치는 경우 전체 예제를 데이터 집합에서 제거합니다.