[LSH]K Shingling(K gram)이란?(Locality Sensitive Hashing#1)

 

목차

 

 

 

 

Shingling이란?

"Shingling"이라는 용어는 문서(Document) 를 집합(Set)으로 변환하는 과정을 말합니다. 이 과정은 문서의 내용을 분석하고, 비교하고, 유사성(Similarity)을 측정하는 데 유용한 방법입니다. 여기서 '집합'이라는 것은 문서 내의 모든 유니크한 요소(예: 단어, 문자열, 토큰 등)의 모임을 의미합니다.

 

 

Shingling 과정

• 문서 정의: 우리가 비교하고 싶은 텍스트 또는 문서가 무엇인지 정의합니다.
• 토큰화(Tokenization): 문서를 더 작은 단위(토큰)로 나눕니다. 이 토큰들은 문자, 단어, 문장 등이 될 수 있습니다.
• Shingling: 이제 토큰화된 문서에서 연속적인 토큰의 시퀀스(쉬잉글)를 생성합니다. 각 쉬잉글은 k개의 연속적인 토큰으로 구성되며, 이 k는 우리가 선택하는 값입니다(예: k=3일 경우 3개의 연속된 토큰으로 이루어진 쉬잉글을 생성합니다).
• 집합으로 변환: 생성된 쉬잉글을 모아서 집합으로 만듭니다. 이 집합은 문서의 '지문'처럼 작용하여 문서의 고유한 내용을 나타냅니다. 중복된 쉬잉글은 제거되므로, 각 문서는 유니크한 쉬잉글의 집합으로 표현됩니다.

 

Shingling의 이점

• 유사도(Similarity) 측정: 두 문서의 쉬잉글 집합을 비교함으로써, 우리는 두 문서가 얼마나 유사한지를 정량적으로 측정할 수 있습니다. 즉, 집합 간의 교집합과 합집합을 사용하여 유사도 점수를 계산할 수 있습니다.
• 중복 내용 탐지: 특히 대용량의 데이터에서 중복되거나 매우 유사한 문서를 식별하는 데 유용합니다. 예를 들어, 인터넷 상의 콘텐츠에서 표절을 탐지하는 데 사용될 수 있습니다.
• 효율성: 쉬잉글을 사용하면 전체 문서를 비교하는 것보다 더 빠르고 효율적으로 문서를 비교할 수 있습니다. 짧은 쉬잉글의 집합만을 비교함으로써 계산 비용을 크게 줄일 수 있습니다.

 

 

 

 

 

K Shingling 예제 실습

 

D1 = "abcab" Document에서 k = 2인 Shingles로 Set을 구하면 아래와 같습니다. 

 

S(D1) = {ab, bc, ca}

 

다음으로 hash로 Shingles를 간단하게 표현하겠습니다.

 

0 = aa

1 = ab

2 = ac

3 = ba

.

.

.

7 = cc

 

위와 같이 hash를 정의하면 아래와 같이 표현할 수 있습니다.

 

S(D1)  ⇒ h(D1) = {1, 5, 7}

 

 

 

문서 D2의 h(D2) = {1, 3, 4, 7}이라고 가정하고 D1과 D2의 Similarity를 Jaccard로 구하면 아래와 같습니다.

 

 

sim(D1, D2) = 2 / 5