[MIT_Introduction to Algorithm] 2강. 계산 모델과 문서 거리(Models of computation, document distance)

Models of computation, document distance

Intro

알고리즘이 뭘까요?

알고리즘으로 할 수 있는 것은 뭘까요?

시간이란 뭘까요?

알고리즘의 실행 시간은 무엇이고 어떻게 측정할까요?

어떤 규칙이 깔려 있을까요?

 

알고리즘의 유래

알고리즘의 유래를 알려드리겠습니다.

이 남자로부터 시작되었는데요 Al-Khwarizmi 대수학의 아버지입니다. 

오래전에 이런 책을 썼습니다. "완성과 균형 맞춤을 통한 계산에 대한 모든 것을 담은 책"이죠

특히 선형 방정식과 이차 방정식을 푸는 방법을 다루었습니다. 그것이 대수학의 시초였습니다.

 

그가 그 방법들을 직접 발명한 건 아닐 겁니다.

사람들이 문제를 어떻게 풀었는지를 서술한 일종의 교과서 저자였죠.

그 방정식들을 푸는 방법이 초기 알고리즘이라고 할 수 있습니다.

바로 여기서 대수학과 알고리즘이라는 단어가 나왔습니다. 

 

알고리즘 이란?

알고리즘이 뭘까요? 비공식적인 정의부터 보고 이 강의의 핵심으로 넘어가겠습니다.

계산 모델은 알고리즘이 무엇인지를 형식적으로 설명합니다.

하지만 저는 전문적이거나 형식적인 것보다는 근본적인 것을 알려드리고 싶습니다.

 

파이썬 코드나 의사 코드를 작성할 때 실제로 어떤 비용이 드는지 이해할 수 있도록 말입니다.

이건 새로 추가된 내용입니다. 006 수업에서 다룬 적이 없었죠

하지만 전 중요하다고 생각합니다.

 

추상적으로 생각한다면 알고리즘은 이것이라고 말할 수 있습니다.

이런 정의를 분명 본 적이 있을 텐데요.

문제를 푸는 계산이나 계산 과정을 정의하는 방법 이것이 바로 알고리즘입니다.

 

컴퓨터 코드가 실행될 때마다 또는 뒤에서 항상 실행되고 있을 때

알고리즘은 입력을 받아 출력을 합니다.

주로 어떤 문제를 풀기 위해서 그렇게 합니다.

이 숫자가 소수인가 등의 문제 말이죠.

 

이것이 알고리즘입니다.

입력을 받아서 알고리즘을 거치면 출력이 계산됩니다.

물론 컴퓨터 코드도 똑같이 할 수 있습니다.

 

알고리즘은 근본적으로 컴퓨터 프로그램의 수학적 표현입니다.

따라서 컴퓨터 프로그램이 하는 일을 추론할 때 알고리즘의 언어로 번역해보면 됩니다. 

 

반대로도 마찬가지로 어떤 문제를 풀고 싶을 때 

먼저 수학을 이용해 알고리즘을 만듭니다. 이 수업을 통해서요

그다음 컴퓨터 코드로 변환합니다.

이 과목은 그러한 상호 변환을 다룹니다.

알고리즘과 프로그램 간의 상호 변환

 

이와 같은 대응 관계를 그림으로 나타낼 수 있습니다.

알고리즘은 컴퓨터 프로그램에 대응하는 수학적 표현입니다.

컴퓨터 프로그램은 프로그래밍 언어로 만듭니다. 프로그래밍 언어로 작성하지요.

 

프로그래밍 언어에 대응하는 수학적 표현이란 건 

즉 알고리즘을 작성하는 방법은 주로 의사 코드입니다. 

세련되게 부를 때는 구조화된 영어라고도 합니다. 다른 자연 언어도 가능합니다.

 

핵심은 공식적으로 사람이 이해하고 추론할 수 있는 형태로 알고리즘을 나타내야 한다는 것입니다. 그것이 구조화입니다.

의사 코드는 여러 가지 의미가 있는데요 정식으로 기술하기 전의 일종의 초안으로

컴퓨터에서 실제로 실행 가능해야 할 필요는 없습니다.

 

교과서에 있는 의사 코드는 거의 대부분이 컴퓨터에서 실행되는 것이지만 꼭 그렇게 쓰지 않아도 됩니다.

수학을 할 줄 아는 사람에게 의미가 통하면 됩니다.

 

최종적으로 이 프로그램은 컴퓨터에서 실행됩니다.

수학 세계에서 컴퓨터에 해당하는 것은 계산 모델입니다. 

이번 강의의 첫 번째 파트의 초점이기도 합니다.

 

계산 모델은 컴퓨터가 상수의 시간 동안 할 수 있는 일이 무엇인지 알려줍니다.

그것이 제가 오늘 하려는 이야기입니다.

 

계산 모델은 알고리즘이 할 수 있는 연산과 그 연산에 걸리는 비용을 결정합니다.

여기서 비용은 시간이겠죠

즉 각 연산에 얼만 큼의 시간이 소요되는지가 결정됩니다.

 

그러면 알고리즘이 여러 개의 연산을 수행하고 제어 흐름, for문, if문 등과 합쳐집니다.

각각의 연산의 비용을 계산하여 전부 더하면 알고리즘의 총비용이 됩니다.

 

특히 우리가 가장 관심 있는 것은 실행 시간입니다.

각 연산마다 시간 비용이 있는데 그것들을 모두 더하면 알고리즘의 실행 시간이 됩니다.

 

두 가지 계산 모델을 다룰 건데요. 사고방식의 차이라고 생각하면 됩니다.

바로 임의 접근 머신과 포인터 머신입니다.

 

임의 접근 머신(RAM, Random Access Machine)

임의 접근 머신부터 시작해봅시다. RAM(Random Access Machine)이라고도 알려져 있습니다.

RAM(Random Access Memory)은 또한 임의 접근 기억 장치를 의미합니다.

 

RAM은 동시에 두 가지를 의미하고 그 둘은 거의 같은 뜻입니다.

하지만 완전히 같지는 않습니다.

 

그림을 크게 그려보겠습니다. 여기 배열이 있습니다,

RAM(임의 접근 머신)은 0, 1, 2와 같은 주소가 있고 주로 워드로 조직되어 있습니다

 

실제로 계산은 어떻게 할까요? 아주 간단합니다.

상수의 시간 동안 알고리즘은 메모리로부터 상수 개의 워드를 읽거나 불러낼 수 있고

상수 개의 계산을 수행할 수 있으며 그것을 메모리에 기록할 수 있습니다. 흔히 저장이라고 부르죠

 

상수 개의 레지스터가 있다고 합시다.

레지스터로 워드를 불러와서 레지스터에 계산을 수행하고 그것을 기록하여

레지스터가 지정한 위치에 저장할 수 있습니다.

어셈블리 프로그래밍이 바로 이런 방식입니다.

 

캐시 같은 것들을 무시한다면 불러오고 계산하고 저장하는 일에 거의 같은 시간이 소요된다는 것이 정확한 계산 모델입니다.

전부 상수 시간이 소요됩니다. 한 번에 워드를 통째로 처리할 수 있는 것입니다.

 

그러면 워드가 정확히 뭘까요?

알다시피 현대 컴퓨터는 32비트 또는 64비트입니다.

조금 더 추상적으로 알아봅시다.

 

워드 하나는 w비트입니다.

약간 거슬릴 수 있는데 대부분의 경우에는 w가 무엇인지 신경 쓰지 않고

여러 개의 워드를 입력으로 받는다고 가정할 것입니다.

 

예를 들어 극댓값 찾기에서는 숫자 행렬이 주어졌는데 그 숫자들이 정수인지 부동 소수점인지는 언급하지 않았습니다.

그런 것들은 신경 쓰지 않고 그냥 워드라고 받아들이고 그것을 처리할 수 있다고 가정합니다.

 

특히 두 숫자를 비교할 때 어느 쪽이 큰지를 보는데

주변과의 비교를 통해 행렬의 이 원소가 극댓값이라는 것을 상수의 시간 안에 판단할 수 있습니다.

이때 상수 시간이 걸리는 이유는 이야기하지 않았습니다.

 

이제 여러분은 압니다. 그것들이 모두 워드이고

상수 개의 워드를 상수 시간 동안 처리할 수 있다면 어떤 숫자의 극댓값 여부를 상수 시간 안에 판단할 수 있는 것입니다.

 

w는 메모리 크기의 log 이상이어야 합니다.

왜냐하면 워드가 이 배열의 인덱스를 지정할 수 있어야 하기 때문입니다.

 

하지만 아직은 신경 쓰지 마세요. 워드는 그저 워드입니다.

워드를 입력으로 받아서 처리할 수 있고 대부분은 이것에 대해 걱정할 필요가 없습니다.

4단원에서 그러한 내용을 논의할 것입니다.

 

워드에 맞지 않는 거대한 정수는 어떻게 처리해야 할까요?

덧셈과 곱셈은 어떻게 하죠? 그건 또 다른 주제입니다.

 

이 수업에서 대부분의 경우에는 한 개의 워드가 주어졌다고 가정하겠습니다.

그게 계산하기 쉽습니다. 어쨌거나 이것은 현실적인 모델이자 강력한 모델입니다.

 

그러나 배열을 사용하는 코드는 많지 않습니다. 필요가 없는 것입니다.

배열이 필요한 경우도 있고 아닌 경우도 있습니다. 

 

따라서 그만큼 강력하지는 않지만 더 간단히 사고를 할 수 있게 하는 보다 추상적인 모델이 유용합니다.

예를 들어 이 모델에는 동적 메모리 할당이 없습니다.

실제로 컴퓨터가 동적 메모리 할당을 하기 때문에 구현 가능하다는 것을 알고 있습니다.

 

그런 부분을 알아서 신경 써주는 모델이 있었으면 좋겠죠

더 높은 수준의 프로그래밍 추상화라고 할 수 있겠죠.

포인터 머신이 그러한 모델로 유용하게 쓰입니다.

 

포인터 머신(Pointer Machine)

근본적으로는 매우 간단한 형태의 객체 지향 프로그래밍에 해당합니다.

여기에는 동적으로 할당된 객체들이 있습니다. 하나의 객체는 일정한 개수의 필드를 가집니다.

필드는 워드가 될 수도 있고 여기서 워드는 정수나 입력 객체, 계산 대상, 카운터 등을 저장하는 것으로 생각하면 됩니다.

워드가 아니면 포인터가 될 수도 있습니다.

 

여기서의 포인터가 포인터 머신이라는 명칭의 유래입니다.

포인터는 다른 객체를 가리키거나 null이라는 특별한 값을 가집니다.

nil이라고도 하고 파이썬에서는 None이라고도 합니다.

 

포인터를 접한 적이 있을 겁니다. 참조라고 들어봤을 텐데요

현대 언어에서는 그것을 포인터라고 부르지 않습니다.

둘 사이에는 아주 미묘한 차이가 있습니다.

 

이 모델은 사실 참조입니다.

하지만 어떤 이유에서인지 포인터 머신이라고 부릅니다. 

상관없습니다.

 

아마 연결 리스트를 본 적이 있을 겁니다.

연결 리스트에는 각 노드마다 여러 개의 필드가 있습니다.

이전 요소를 가리키는 포인터와 다음 요소를 가리키는 포인터 그리고 어떤 값을 가질 겁니다.

 

여기 아주 간단한 연결 리스트가 있습니다. 

양쪽을 가리키는 포인터가 있기 때문에 이중 연결 리스트라고 부릅니다.

 

2개의 노드를 가진 이중 연결 리스트입니다.

리스트의 머리를 가리키는 포인터와 꼬리를 가리키는 포인터가 있다고 할 수도 있죠

이것이 포인터 머신의 구조입니다.

 

자료 구조이죠 파이썬에서는 네임드 튜플이라고 부르거나 

단순히 속성이 3개 있는 객체입니다.

그것에 값이 있고 정수와 같은 워드입니다. 그리고 다른 노드를 가리키는 포인터들이 있습니다.

새 노드를 만들 수도 있고 노드를 없앨 수도 있습니다. 그것이 동적 메모리 할당입니다.

 

이 모델을 임의 접근 머신에서 구현할 수 있는데요

포인터는 이 거대한 배열의 인덱스가 됩니다.

C 프로그램을 만들어 본 적이 있다면 C에서의 포인터와 비슷하다는 것을 알 수 있습니다.

 

포인터에 1을 더하면 다음 것을 가리키기 때문입니다.

이 모델에서는 포인터를 따라가는 것만 가능합니다.

 

포인터를 따라가는 것은 상수 시간이 소요됩니다.

이 필드 중 하나를 바꾸는 것도 상수 시간이 소요됩니다.

이 객체에 대해 수행할 수 있는 일반적인 일들이 모두 상수 시간이 걸립니다.

 

그래서 사실 임의 접근 머신보다는 약한 모델입니다.

(약한 모델이라는 것은 포인터 머신이 임의 접근 머신보다

작업이 많고 더 많은 메모리를 요구한다는 얘기 같습니다.

포인터 머신은 포인터를 따라가는 작업이 추가되고 하나의 노드에 포인터를 담을 공간이 추가되어야 하니까요.

흔히 배열과 연결 리스트를 비교했을 때 나오는 연결 리스트의 단점 같네요)

 

파이썬에서의 계산 모델

이제 이야기할 부분은 실제로 파이썬에서 적절한 모델은 무엇인가입니다.

파이썬은 어떤 의미에서는 우리가 수업에서 사용하는 계산 모델이라고 할 수 있습니다.

모든 것을 파이썬으로 구현하기 때문이죠.

 

파이썬은 배열이 있기 때문에 임의 접근 머신 관점도 갖고 있고

참조, 즉 포인터가 있기 때문에 포인터 머신 관점도 갖고 있습니다.

따라서 두 개 다 적용할 수 있습니다.

 

하지만 파이썬에는 연산이 많습니다.

불러오고 저장하고 포인터를 따라가는 것뿐만 아니라 

정렬이나 추가, 두 리스트를 이어 붙이는 등 많은 연산을 합니다.

 

각 연산마다 해당하는 비용이 있습니다.

임의 접근 머신과 포인터 머신은 이론적인 모델이라서 매우 간단하게 설계되어 있습니다.

뭐든 상수 시간이 소요되는 것은 분명합니다.

 

파이썬에서는 어떤 연산은 많은 시간이 걸립니다.

어떤 연산은 지수 시간이 걸리기도 합니다.

 

파이썬 모델에서 생각을 하든 실제 파이썬으로 알고리즘을 구현하든

여러분이 알고리즘을 만들 때 어떤 연산이 빠르고 느린지를 알아야 합니다.

 

이제 그에 대한 이야기를 할 것입니다.

매우 많은 연산이 있기 때문에 모두 다루지는 않을 겁니다. 

보충 수업에서 더 많이 다룰 것이고 강의 노트에도 많이 있습니다.

 

먼저 파이썬에서 임의 접근 방식의 연산을 할 수 있습니다.

파이썬에서 배열은 리스트라고 합니다.

파이썬의 리스트는 현실 세계의 배열과 같습니다 

 

그냥 리스트라고 생각해도 되지만 구현의 관점에서 보면 배열로 구현되어 있습니다

연결 리스트가 아닙니다. 연산을 하나 해볼게요

리스트 L을 가지고 이런 것을 한다고 해봅시다.

L은 리스트 객체입니다. L[i] = L[j]+5 이 연산은 상수 시간이 걸립니다.

연결 리스트에서는 선형 시간이 걸립니다. 왜냐하면 i위치까지 훑고 나서 j위치까지 훑고 5를 더한 후 저장하기 때문입니다.

한편 파이썬에서는 편리하게도 상수 시간이 소요됩니다. 중요한 문제입니다.

 

반면에 객체 지향 프로그래밍을 사용하여 두 번째 방식인 포인터 머신을 적용할 수도 있습니다.

객체가 상수 개의 속성을 갖고 있다고 합시다 그러면 포인터 머신 모델에 해당합니다. 백만 개나 n 개는 안됩니다.

즉 객체에 속성이 3개나 10개 정도 있으면 그게 바로 포인터 머신입니다.

그러면 그 객체를 조작하는 게 상수 시간이 걸린다고 생각할 수 있습니다.(속성이 적당히 있는 한 만만히 봐도 됩니다)

 

연결 리스트를 구현한다고 해봅시다

파이썬은 여전히 내장된 연결 리스트가 없습니다. 하지만 구현하기 상당히 쉽습니다.

포인터를 가지고 x = x.next이라고 쓰면 이게 상수 시간이 걸리는데 (포인터를 따라가는 연산)

상수 크기의 객체의 필드에 접근하는 것이 상수 시간이 걸리기 때문입니다.

 

이 상수들이 뭔지는 관심 없습니다. 그게 알고리즘의 좋은 점이죠 n에 대한 확장성에만 관심이 있습니다.

여기에는 n이 없습니다. 이것도 상수 시간이고 여기도 상수 시간입니다.

연결 리스트가 얼마나 크든 객체가 얼마나 많이 있든 항상 상수 시간입니다.

 

좀 더 어려운 것을 해봅시다.

예를 들어 L.append연산을 하면 리스트가 있고 그 리스트에 어떤 항목을 추가하고 싶은 겁니다.

이것의 비용을 알아내려면 이 기본 연산들로 어떻게 구현되어있는지를 생각해봐야 합니다.

L.append는 조금 까다롭습니다. (결과적으로 상수 시간 연산으로 생각하면 됩니다.)

특정 크기의 배열이 있는데 그 배열을 한 칸 더 크게 만들고 싶은 겁니다.

확실한 방법은 새로운 배열을 할당하여 모든 요소를 복사하는 것입니다.

그러면 선형 시간이 소요될 것입니다.

 

파이썬은 그렇게 하지 않습니다. 그럼 어떻게 할까요?

강의 9에서 다룰 것입니다. 테이블 더블링이라는 것을 합니다.

아주 간단한 아이디어인데요 이름에서부터 추측할 수 있습니다.

아홉 번째 강의에서 이게 어떻게 상수 시간 안에 되는지를 알게 될 것입니다.

 

이게 바로 여러분이 이 수업을 들어야 하는 이유입니다.

파이썬이 어떻게 작동하는지 이해하게 됩니다. 이런 것은 수십 년 전에 발명된 알고리즘의 개념을 이용하고 있지만

다른 많은 문제들을 풀기 위해 해야 하는 것입니다. 파이썬에는 알고리즘을 사용하는 특성이 많습니다.

두 리스트를 이어 붙이는 건 어떻게 할까요? 파이썬에서 이것은 비파괴 연산입니다.

L1과 L2를 복사해서 합칩니다. 물론 이들은 배열입니다. 이것을 이해하는 방법은 파이썬 코드로 재구현하는 것입니다.

처음에 비어있는 L과 L1에 있는 모든 항목 x에 대해 L.append(x)를 수행하는 것입니다.

 

파이썬 공식 문서를 보면 많은 경우에 특히 복잡한 특성에서 이런 식의 의미 서술을 볼 수 있습니다.

같은 기능을 하는 간단한 파이썬으로 보여주는 것입니다.

여기서는 이전에 본 적 없는 복잡한 연산은 쓰이지 않습니다.

 

현재 우리는 L.append가 상수 시간이 걸리는 것을 알고 있습니다. 

따라서 아래의 코드가 소요되는 시간은 O(L1의 길이)입니다.

for x in L1 :     
    L.append(x)

그리고 아래의 코드가 실행되는 시간은 O(L2의 길이입니다)

for x in L2 :     
    L.append(x)

그러므로 총시간은 O(1 + L1의 길이 + L2의 길이)입니다.

1을 더하는 것은 이 둘이 모두 0인 경우에도 처음 리스트를 생성하는 데 상수 시간이 걸리기 때문입니다.

 

대부분 이런 식으로 코드를 펼칠 수 있을 겁니다.

그러면 분석하기가 매우 쉬워집니다. 

 

아래는 강의에서 설명하시지 않은 강의 자료에 나와 있는 것입니다.(c, d)

L1 리스트에 L2리스트를 이어 붙이는 코드입니다.

L1.append가 상수의 시간을 가지므로 총시간은 O(1 + L2의 길이)입니다.

여기서 1을 더하는 이유는...?

코드를 보면 L1 += L2인데, 만약 L2가 없어도 L1 = L1 이라는 코드가 실행되기 때문인것 같네요.

L2가 있어도 L1 = L1 + L2 일테니까요.

 

L1 리스트 i부터 j까지 를 슬라이싱 해서 L2 리스트에 붙여 넣는 코드입니다.

L2 리스트가 만들어지는 시간 O(1), 슬라이싱 해서 append 하는 시간 O(j-i) 

즉 O(자르는 리스트의 길이) 만큼의 시간이 걸리네요.

 

x가 리스트에 있는 알고 싶으면 어떻게 해야 할까요?

파이썬에 in이라는 연산자가 있습니다. x in L로 씁니다.

이게 얼마만큼의 시간이 걸리까요? 선형 시간입니다.

 

최악의 경우에는 리스트 전체를 읽어야 하죠.

리스트가 꼭 정렬되어 있지는 않습니다. 알 수 없죠.

따라서 쭉 읽어나가면서 모든 항목에 대해 x가 그 항목과 같은지 확인해야 합니다.

심지어 만약 ==가 비용이 크다면 더 오래 걸리겠죠, x가 복잡한 것이라면 그 점도 고려해야 합니다.

 

리스트의 길이를 계산하는데 얼마나 걸릴까요? 상수 시간입니다.

만약 아무 정보도 없었다면 리스트를 끝까지 읽어서 항목을 세야 했을 텐데

다행히도 파이썬에는 리스트에 카운터가 내장되어 있습니다. 

항상 처음에 리스트의 길이를 저장합니다. 따라서 그냥 찾아보면 됩니다. 즉시 처리됩니다.

 

리스트를 정렬하려면 어떻게 할까요?

얼마나 걸리까요? n log n입니다. n은 리스트의 길이입니다.

여기에 두 항목을 비교하는 시간도 곱해지는데 보통 항목이 워드이므로 상수 시간입니다.

 

파이썬 정렬 알고리즘은 비교 정렬을 사용합니다. 이것은 강의 3, 4, 7의 주제입니다.

특히 바로 다음 강의에서 어떻게 n log n 시간 안에 되는지 살펴볼 것입니다.

 

변경할 수 없는 리스트와 유사합니다.

이제 딕셔너리로 넘어가 보겠습니다. 파이썬에서는 dict입니다.

이것으로 할 수 있는 일은 어떻게 보면 리스트의 일반화입니다.

인덱스 대신 0부터 길이-1까지의 정수 중 임의로 키를 넣고 값을 저장할 수 있습니다.

 

사실 이것은 컴퓨터 과학 전체에서 가장 중요한 자료 구조 중 하나입니다.

해시 테이블이라는 것인데요 강의 8에서 10까지의 주제입니다.

이것을 어떻게 상수 시간 안에 하는지 상수 시간 안에 임의의 키를 어떻게 저장하고 다시 뽑아내는지 알려줍니다.

(키가 하나의 워드라고 가정합니다)

 

키가 딕셔너리에 있는지 확인하고 어떤 값을 삭제하는 것도 모두 상수 시간입니다.

한 개의 키를 가지고 하는 일반적인 일들은 모두 그렇습니다.

 

잠깐 덧붙이면 이것은 높은 확률로 상수 시간입니다.

확률적 알고리즘인데요 항상 상수 시간은 아닙니다.

항상 정확하긴 합니다만 아주 가끔 상수 시간보다 조금 더 걸립니다.

 

dictionary, update처럼 키를 여러 개 다루는 경우에는 상수 시간이 아닙니다.

그러면 얼마나 걸릴까요? for문으로 써서 세어보면 됩니다.

 

넓은 연구 분야에서 많은 사람들이 해싱은 연구합니다.

아주 멋지고 유용합니다. 어떤 코드를 작성하든 딕셔너리를 사용하여 문제를 풀게 됩니다.

 

vals가 없는 dict와 유사합니다.

파이썬 표준 라이브러리에 있는 힙 큐는 강의 4에서 다룰 힙이라는 것을 구현합니다

long 정수입니다. 11강의 주제입니다.

 

두 정수 x, y가 있고 x의 길이가 |x|, y의 길이가 |y|일 때

두 수를 더하는데 얼마나 걸릴까요?

더하기가 정답입니다. O(|x| + |y|) 만큼의 시간이 걸립니다.

 

곱셈은 조금 더 어렵습니다.

간단한 알고리즘은 xy가 될 것인데 2차 시간이므로 비효율적입니다.

파이썬에 구현되어 있는 알고리즘의 경우에는 (x + y)의 log₂3 제곱입니다.(log₂3는 대략 1.6입니다)

 

문서 거리(Document Distance)

문서 거리 문제란 두 문서 D1, D2에 대해 둘 사이의 거리를 계산하는 것입니다.

먼저 문서 거리 계산을 왜 배워야 하는지 먼저 알려드리겠습니다.

 

여러분이 구글이고 전체 웹을 분류한다고 해봅시다.

두 웹 페이지가 기본적으로 동일한지 알고 싶을 것입니다. 그렇게 하면 덜 저장할 수도 있고 사용자에게 다르게 보여줘야 하기 때문입니다.

예를 들어 어떤 페이지가 있고 똑같은 여분이 많으면 기본적인 것만 필요하겠죠

 

또는 위키피디아를 생각해봅시다. 모든 위키피디아 미러 사이트의 목록이 있습니다.

수백만 개가 있는데요. 손으로 일일이 찾는 대신에 문서 거리를 이용할 수 있습니다.

예를 들면 시작이나 끝 부분 외에 동일한가? 이런 문제를 해결할 수 있죠

 

아니면 여러분이 수업을 가르치면서 두 연습문제 풀이가 베낀 것인지 알고 싶을 수도 있습니다.

 

다른 예시입니다. 웹 탐색이 있네요 다시 한번 여러분이 구글이라고 해봅시다.

검색 기능을 구현하려고 합니다. 예를 들어 제가 알고리즘 개론이란 두 단어를 검색한다고 해봅시다.

알고리즘 개론이라는 검색어를 하나의 짧은 문서로 생각할 수 있습니다.

그 문서와 웹의 다른 문서들이 유사한 정도를 계산하여 그중 가장 유사한 것

즉 거리가 가장 짧은 것을 맨 위에 보여줄 것입니다.

 

물론 구글이 이렇게 하는 건 아니고 구글이 하는 것의 일부가 이렇다는 것입니다.

이런 것들을 위해 문서 거리 계산이 필요하죠

이런 간단한 문제들을 통해 수업을 진행하면서 많은 기법들을 설명할 수 있습니다.

 

이제부터 문서를 단어들의 나열로 생각하겠습니다. 조금 더 형식적으로 접근해서 문서의 의미를 따져보겠습니다.

우선 단어란 영어와 숫자로 이루어진 문자열입니다. a~z와 0~9까지겠죠

문자열이라고도 할 수 있는 문서에서 공백과 문장 부호 같은 것들을 모두 지운다고 합시다

그러면 그 사이사이에 있는 모든 것들이 단어입니다. 이것이 문서로부터 단어를 얻는 간단한 정의입니다.

 

이제 D1과 D2가 유사한지를 알고 싶습니다. 앞서 문서를 단어들의 모임으로 간주했습니다.

공통으로 갖고 있는 단어가 많으면 유사하다고 할 수 있습니다.

이러한 생각을 근간으로 해서 공통 단어를 이용하여 문서 거리를 정의하는 것입니다. 이것이 거리를 정의하는 유일한 방법입니다.

 

이제부터 문서를 단어들의 나열이자 하나의 벡터로 생각할 것입니다.

어떤 문서 D와 단어 w에 대해 D[w]는 그 단어가 문서에 등장하는 횟수를 말합니다.

즉 문서 D에서의 w의 발생 횟수입니다. 따라서 음이 아닌 정수가 되겠죠.

 

이것을 하나의 거대한 벡터로 보면 그 벡터는 단어로 색인됩니다.

또한 각 단어에 대한 빈도가 있을 것인데 많은 경우 0일 것이고 몇몇은 양의 발생 횟수가 있을 것입니다.

 

매우 중요한 문서 두 개를 예로 들어봅시다. (D1 = "the cat", D2 = "the dog")

두 단어로 이루어진 문서들이 있습니다.

이것을 그림으로 그려보면 서로 다른 단어가 세 개밖에 없기 때문에 3차원 공간으로 그릴 수 있습니다.

 

이렇게 두 벡터입니다.

두 벡터가 얼마나 다른지를 어떻게 측정하나요? 벡터의 내적을 계산하면 됩니다.

 

d'은 D1과 D2를 내적 한 것입니다. 모든 단어에 대해 D1[W]⋅D2[W]를 더한 것과 같습니다

아까의 예시를 가지고 내적을 계산해보면

the가 일치하므로 여기서 1점을 얻고 cat과 dog는 0에 곱해져서 더해지는 것이 거의 없을 것입니다.

 

이것을 하나의 거리 측정 방식으로 볼 수도 있지만 사실은 공통성을 측정하는 것입니다. 따라서 거리의 반대가 되겠죠

내적 결과가 높으면 공통 단어가 많은 것입니다.

 

사실 이건 양수 곱하기 양수입니다. 공통 단어가 많으면 좋아 보입니다.

문제는 이게 100만 개의 단어가 있는 긴 문서이고 역시 100만 단어로 이루어진 다른 문서와 99% 일치한다면 아주 유사할 것입니다.

 

단어가 100만 개이고 그중 절반이 일치한다고 해봅시다. 그러면 점수가 50만입니다.

그다음 100개의 단어로 이루어진 두 개의 똑같은 문서를 생각해보면 그 점수는 100밖에 되지 않습니다.

그 둘이 똑같음에도 불구하고 규모에 따라 결과가 변합니다. 따라서 완벽한 지표라고 할 수 없습니다.

 

어떻게 바꿔야 할까요? 벡터의 길이로 나누면 됩니다.(단어의 개수로 정규화)

여기서 벡터의 길이는 등장하는 단어의 개수입니다.

이것을 기하학적으로 해석(재구성)하면 다음과 같습니다.

이건 두 벡터 사이의 각도를 측정하는 방법입니다.

0이면 두 벡터가 완전히 동일한 것이고 90도이면 둘은 매우 다른 것이죠.

 

문서 거리 알고리즘

1. 각 문서를 단어들로 쪼갠다 .

2. 단어 빈도를 센다. (문서 벡터)

3. 내적을 계산한다. (&나눈다)

 

문서 거리 계산의 파이썬 구현

강의 노트에서 서로 다른 8개의 알고리즘을 실행시켜 볼 수 있습니다.

이 동일한 알고리즘에 대한 서로 다른 구현들의 실행 시간을 볼 것입니다.

1MB 정도의 문서 한 쌍에 대해 걸리는 시간입니다.

첫번째 수행에 비해 1000분의 1로 줄었습니다. 더 큰 문서를 볼수록 이 숫자는 극적으로 변할 것입니다.

대부분이 2차 시간 알고리즘에서 선형 또는 log n 시간 알고리즘으로 개선된 것이기 때문입니다.

따라서 1MB에 대해서는 합리적인 개선이지만 1GB로 넘어가면 엄청난 개선입니다.

 

몇몇 개선과 알고리즘에 대해 이야기하겠습니다.

문서들을 단어들로 어떻게 쪼갤까요?

문자열을 쭉 돌다가 영어나 숫자가 아닌 것이 나오면 새로운 단어를 시작합니다. 그러면 선형 시간이 걸리겠네요.

이렇게 정규 표현식을 사용하면 문서 안의 모든 단어를 찾을 수 있습니다.

 

문제는 re가 보통 지수 시간이 걸린다는 것입니다. 알고리즘을 생각할 때 이런 점을 주의해야 합니다.

re가 어떻게 구현되었는지 모르면 이게 선형 시간이 걸릴 수도 있습니다.

하지만 알기 힘듭니다 re는 복잡한 일을 할 때 쓰세요. 뭔지 모르면 신경쓰지 않아도 됩니다. 사용하지 마세요.

이게 뭔지 안다면 re를 사용할 때 주의하세요. 항상 선형 시간은 아니니까요

 

하지만 우리에겐 쉬운 알고리즘이 있습니다.

쭉 훑으면서 영어와 숫자를 찾아 단어로 엮으면 됩니다.

파이썬에서 문서를 단어들로 어떻게 쪼갤까요? 문서의 단어들을 반복하면서 딕셔너리에 넣습니다.

count[word] += 1이라고 합시다. 그게 아니라면 이 단어가 딕셔너리에 있는지 확인하여 없으면 1로 만들고 있으면 1을 더해야 합니다.

즉 딕셔너리에 있는 각 단어의 빈도를 셉니다.

 

딕셔너리는 높은 확률로 상수 시간 동안 실행됩니다.

단어가 매우 길 수도 있으니까 단어를 기계 워드로 줄이면 워드의 길이만큼 시간이 걸립니다.

그러면 실행 시간은 문서에 있는 단어들의 길이의 합이 되고 이것은 문서의 길이이기도 합니다.

높은 확률로 선형 시간이니까 좋은 알고리즘입니다.

 

다른 방법도 있습니다. 예를 들어 단어들을 정렬한 후 정렬된 리스트를 돌면서 

각 단어가 연속으로 몇 개 있는지를 세는 겁니다. 정렬되어 있다면 같은 단어들은 바로 옆에 위치할 테니까요. 그러면 세기 쉽곘죠.

 

Ref

[MIT] 파이썬을 이용한 알고리즘의 이해 : https://www.edwith.org/introalgorithm

MIT 6.006 Introduction to Algorithms : https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/index.htm