This exact-substring-matching criterion, while conceptually simple, is computationally prohibitive with naive (quadratic) all-pair matching. To improve the efficiency, we concatenate all the examples of the entire dataset \(D\) into a giant sequence \(\mathcal{S}\), and construct a Suffix Array \(\mathcal{A}\) of \(\mathcal{S}\). A suffix array [20] is a representation of a suffix tree [20] that can be constructed in linear time in \(\|\mathcal{S}\|\)[13] and enables efficient computation of many substring queries; in particular, they allow us to identify duplicated training examples in linear time. Suffix arrays have the advantage over suffix trees in that they are 10-100\(\times\) more memory efficient [21], requiring just 8 bytes per input token, though they are asymptotically less efficient for some query types. They have been used widely in NLP, such as for efficient TF-IDF computation [22] and document clustering [23].
이 정확한 부분 문자열 일치 기준은 개념적으로는 간단하지만, 순진한 (이차적인) 모든 쌍의 일치를 사용하면 계산적으로 엄청난 부담이 됩니다. 효율성을 개선하기 위해 전체 데이터 집합 \(D\)의 모든 예제를 거대한 시퀀스 \(\mathcal{S}\)로 연결하고, Suffix Array \(\mathcal{A}\)를 \(\mathcal{S}\)로 구성합니다. Suffix Array[20]는 Suffix Tree[20]의 표현으로, \(\|\mathcal{S}\|\)[13]에서 선형 시간으로 구성할 수 있으며, 특히 중복된 학습 예제를 선형 시간 내에 식별할 수 있는 많은 하위 문자열 쿼리를 효율적으로 계산할 수 있습니다. Suffix Array는 Suffix Tree에 비해 10~100배 더 메모리 효율적이라는 장점이 있는데, 입력 토큰당 8바이트만 필요하기 때문에 일부 쿼리 유형의 경우 점진적으로 효율성이 떨어지지만 NLP에서 효율적인 TF-IDF 계산[22] 및 문서 클러스터링[23] 등에 널리 사용되고 있습니다.
이 정확한 부분 문자열 일치 기준은 개념적으로는 간단하지만, 순진한 (이차적인) 모든 쌍의 일치를 사용하면 계산적으로 엄청난 부담이 됩니다. 효율성을 개선하기 위해 전체 데이터 집합 \(D\)의 모든 예제를 거대한 시퀀스 \(\mathcal{S}\)로 연결하고, Suffix Array \(\mathcal{A}\)를 \(\mathcal{S}\)로 구성합니다. 접미사 배열[20]은 접미사 트리[20]의 표현으로, \(\|\mathcal{S}\|\)[13]에서 선형 시간으로 구성할 수 있으며, 특히 중복된 학습 예제를 선형 시간 내에 식별할 수 있는 많은 하위 문자열 쿼리를 효율적으로 계산할 수 있습니다. 접미사 배열은 접미사 트리에 비해 10~100배 더 메모리 효율적이라는 장점이 있는데, 입력 토큰당 8바이트만 필요하기 때문에 일부 쿼리 유형의 경우 점진적으로 효율성이 떨어지지만 NLP에서 효율적인 TF-IDF 계산[22] 및 문서 클러스터링[23] 등에 널리 사용되고 있습니다.