[12/20] 사례 연구: 데이터 구조 선택

글을 시작하기에 앞서 해당 시리즈는 Allen Downey, Ben Lauwens의 저서인 Think Julia: How to Think Like a Computer Scientist 를 바탕으로 작성된 글임을 알려드립니다.

이 포스트는 Case Study: Data Structure Selection를 한글로 요약 정리한 글입니다.

사례 연구: 데이터 구조 선택

지금까지 줄리아의 핵심 데이터 구조에 대해서 배우고 이를 사용하는 일부 알고리즘 살펴보았다. 이번 장에서는 사례 연구를 통해서 데이터 구조를 선택하고 사용하는 방법을 연습할 것이다.

단어 빈도 분석 (Word Frequency Analysis)

가능하다면, 해결책을 살펴보기 전에 아래의 연습문제를 풀어보자.

연습문제 1 파일을 읽고, 각 줄을 단어로 나누고, 단어에서 공백과 문장부호를 제거한 후 소문자로 변환하는 프로그램을 작성해라.

Tip isletter()은 문자를 알파벳인지 테스트한다.

연습문제 2 Project Gutenberg로 가서 저작권이 없는 책을 일반 텍스트 형식으로 다운로드해라. 이전에 사용했던 프로그램을 수정하여 다운로드한 책을 읽어온 후, 파일 시작 부분의 헤더 정보를 건너 뛰고 위의 프로그램을 실행하라. 그 다음 책의 총 단어 수와 각 단어가 사용된 횟수를 계산하도록 프로그램을 수정해라.

연습문제 3 책에서 가장 자주 사용되는 20개의 단어를 인쇄하도록 이전 연습문제의 프로그램을 수정해라.

연습문제 4 이전 프로그램을 수정하여 단어 목록을 읽은 후, 단어 목록에 없는 단어를 인쇄해라. 오타는 몇 개인가? 단어 목록에 있어야 하는 일반적인 단어는 몇 개이며, 실제로 모호한 단어는 몇 개인가?

랜덤 숫자

대부분의 컴퓨터 프로그램은 같은 입력이 주어지면 똑같은 결과를 출력한다. 그래서 이런 실행 흐름을 결정론적이라고 말할 수 있다. 결정론은 동일한 계산이 동일한 결과를 산출한다고 가정하기 때문에 일반적으로 좋은 이론이다. 하지만 일부 응용 프로그램의 경우 컴퓨터가 예측할 수 없는 형태이기를 원한다. 게임은 확실한 예이며, 다른 예들도 있다.

프로그램을 비결정론적으로 만드는 것은 어렵지만, 적어도 비결정론적으로 보이게 하는 방법은 있다. 그 중 하나는 '의사 난수 (pseudorandom numbers)' 생성하는 알고리즘을 사용하는 것이다. 의사 난수는 결정론적 계산에 의해 생성되기 때문에 실제로 완벽한 무작위는 아니지만, 마치 랜덤 숫자와 같은 결과를 제공한다.

rand()는 0.0과 1.0사이의 랜덤 소수를 반환한다. (0.0은 포함하지만 1.0은 포함하지 않는다) rand()를 호출할 때마다, 긴 배열 중에 다음 소수가 반환된다. 아래의 코드를 통해 결과를 확인해보자.

for i in 1:10
    x = rand()
    println(x)
end

또한 rand()는 이터레이터나 배열을 인수로서 가져올 수 있으며 결과로 랜덤 요소를 반환한다.

for i in 1:10
    x = rand(1:6)
    print(x, " ")
end

단어 히스토그램

이 장을 진행하기 전에 앞에서 제시했던 연습문제를 풀어봐야 한다. 그 다음 해당 링크에 가서 텍스트를 다운로드해라.

아래의 코드는 파일을 읽고 파일에 있는 단어의 히스토그램을 작성하는 프로그램이다.

function processfile(filename)
    hist = Dict()
    for line in eachline(filename)
        processline(line, hist)
    end
    hist
end;

function processline(line, hist)
    line = replace(line, '-' => ' ')
    for word in split(line)
        word = string(filter(isletter, [word...])...)
        word = lowercase(word)
        hist[word] = get!(hist, word, 0) + 1
    end
end;

위의 프로그램은 위의 링크에서 다운받은 'emma.txt'을 읽어온다.

processfile()은 파일의 줄을 읽어오고 processline()으로 한 줄씩 보낸다. 히스토그램인 hist는 누적기(accumulator)로 사용된다.

processline()은 줄을 단어로 분리하고 문자 배열로 변경하는 split()을 사용하기 전에 -을 공백으로 바꾸기 위해서 replace()를 사용한다. 그리고 단어 배열은 filter()와 isletter로 마침표와 기타 문장기호들을 제거하고 lowercase()로 소문자로 변경한다.(정확히 말하면, 문자열은 변경된 것이 아니라 소문자로 구성된 새 문자열을 반환한 것이다)

마지막으로, processline()은 새로운 항목을 만들거나 기존 항목을 증가시켜 히스토그램을 업데이트한다.

파일의 단어가 총 몇 개인지 세어보려면 히스토그램에서 빈도가 합쳐져야 한다.

function totalwords(hist)
    sum(values(hist))
end

다른 단어들의 수는 딕셔너리에서 아이템의 수이다.

function differentwords(hist)
    length(hist)
end

결과는 아래와 같다.

julia> println("Total number of words: ", totalwords(hist))
Total number of words: 162742

julia> println("Number of different words: ", differentwords(hist))
Number of different words: 7380

가장 일반적인 단어

가장 일반적인 단어들을 찾기 위해서는 각각의 튜플이 단어와 빈도를 포함한 튜플 배열을 만들고 그 배열을 정리하면 된다. 아래의 함수는 히스토스램을 가져와 단어-빈도 튜플 배열로 반환한다.

function mostcommon(hist)
    t = []
    for (key, value) in hist
        push!(t, (value, key))
    end
    reverse!(sort(t))
end

위의 튜플은 빈도가 첫 번째 값이기 때문에 정렬도 빈도를 기준으로 배치된다. 아래의 코드는 10개의 가장 일반적인 단어를 반환한다.

t = mostcommon(hist)
println("The most common words are:")
for (freq, word) in t[1:10]
    println(word, "\t", freq)
end

위의 코드에서는 \t인 줄내림 분리기호를 사용하였다. 그 결과 단어들은 아래로 정렬된다.

The most common words are:
to  5295
the 5266
and 4931
of  4339
i   3191
a   3155
it  2546
her 2483
was 2400
she 2364

Tip 위 코드는 sort()의 rev 키워드 인수를 사용하여 단순화할 수 있다. rev에 대해서는 이 링크에서 읽을 수 있다.

선택적 매개 변수 (Optional Parameters)

지금까지는 선택적 인수를 가진 내장 함수들을 보았다. 물론 프로그래머가 직접 정의하는 함수 또한 선택적 인수를 사용하여 작성할 수 있다. 예를 들어 가장 일반적인 단어를 히스토그램으로 출력하는 함수는 아래와 같다.

function printmostcommon(hist, num=10)
    t = mostcommon(hist)
    println("The most common words are: ")
    for (freq, word) in t[1:num]
        println(word, "\t", freq)
    end
end

첫 번째 매개 변수는 필수적으로 들어가야 하지만, 두 번째 매개 변수는 선택적이다. 위 코드에서 선택적 매개 변수의 기본값은 num=10이다.

만약 하나의 인수만 넣어 실행하면

printmostcommon(hist)

num은 자동으로 기본값이 입력된다. 만약 두 개의 인수를 모두 넣으면

printmostcommon(hist,20)

num은 기본값 대신 입력한 새로운 값을 사용한다.

만약 함수에 필수적(required) 매개 변수와 선택적(optional) 매개 변수를 모두 입력하고 싶다면, 필수적 변수는 첫 번째로 입력하고 선택적 변수는 그 뒤에 써야 한다.

딕셔너리 뺄셈 (Dictionary Subtraction)

책에서 words.txt 단어 리스트에 없는 단어를 찾는 것은 두 딕셔너리를 빼는 것 처럼 인식된다. 즉, 책에는 있지만 단어 리스트에는 없는 단어를 찾으려는 것이다.

subtract()은 딕셔너리 d1과 d2를 가져와서 d1는 있지만 d2에는 없는 키들을 포함한 새로운 딕셔너리를 반환한다. 값은 필요 없기 때문에 nothing으로 설정했다.

function subtract(d1, d2)
    res = Dict()
    for key in keys(d1)
        if key ∉ keys(d2)
            res[key] = nothing
        end
    end
    res
end

책에는 있지만 단어 리스트에 없는 단어를 찾기 위해서는 words.txt 또한 processfile()를 사용해서 히스토그램으로 만들어야 한다. 그리고 subtract()를 사용하자.

words = processfile("words.txt")
diff = subtract(hist, words)

println("Words in the book that aren't in the word list:")
for word in keys(diff)
    print(word, " ")
end

그 결과는 아래와 같다.

Words in the book that aren't in the word list:
outree quicksighted outwardly adelaide rencontre jeffereys unreserved dixons betweens ...

위의 단어들 중에서 일부는 사람 이름과 소유물이다. 또한 "rencontre"와 같은 단어는 더이상 사용하지 않는 용어이다. 그러나 몇 개의 단어는 일반적인 단어로서 리스트에 있어야 한다.

랜덤 단어 (Random Words)

히스토그램으로부터 랜덤 단어를 선택하기 위해서 사용되는 가장 간편한 알고리즘은 각 단어의 복사본을 빈도만큼 만든 후 배열을 생성하여 선택하게 하는 것이다.

function randomword(h)
    t = []
    for (word, freq) in h
        for i in 1:freq
            push!(t, word)
        end
    end
    rand(t)
end

위의 알고리즘은 작동하지만, 효율적이지는 않다. 랜덤 단어를 선택할 때마다 책만큼 큰 크기의 배열을 다시 만든다. 효율을 향상시키기 위해서 배열을 한번만 만들고 여러 번 선택하는 방법도 좋지만, 배열의 크기는 여전히 크다.

대안으로는 다음과 같다.

• 책에 있는 단어의 배열을 가져와라.
• 단어 빈도의 누적 합계를 요소로 하는 배열을 만들어라. 이 배열의 마지막 요소는 책의 총 단어 수가 되어야 한다.
• 1부터 n사이의 난수를 선택하라. 난수가 있는 위치를 찾기 위해 이분법 검색(bisection search)를 사용하여 해당 인덱스를 얻어라.
• 인덱스를 사용하여 연결되어 있는 단어를 찾아라.

대안 해결 코드 아래의 코드는 제가 직접 작성한 코드입니다. 필요하신 분들만 참고해주세요 :)

function cumulsum(t)
    cumul=[]
    for n in 1:length(t)
        temp= sum(t[1:n])
        cumul=push!(cumul,temp)
    end
return cumul
end

function searching_word(t)
    words=collect(keys(t))
    addnum=cumulsum(collect(values(t)))
    random=rand(1:length(t))
    for n in 1:(length(addnum)-1)
        if addnum[n] < random < addnum[n+1]
            return words[n]
        elseif n+1 == addnum[end]
            return words[end]
        end
    end
end

마르코프 분석 (Markov Analysis)

책에서 무작위로 단어를 선택하면, 어휘는 알 수 있지만 문장은 얻지 못할 것이다.

this the small regard harriet which knightley's it most things

위의 문장처럼 무작위로 단어를 배열하면 문법적인 문제로 어떤 의미도 갖지 못하는 경우가 많다. 예를 들어, 의미를 가진 문장이라면 "the" 다음에 명사나 형용사가 올 것으로 예상할 수 있으며 동사나 부사는 사용할 수 없다.

이런 관계를 파악하는 한 가지 방법은 특정 단어 이후에 나올 단어의 확률을 분석하는 마르코프 분석을 사용하는 것이다.

Half a bee, philosophically,
Must, ipso facto, half not be.
But half the bee has got to be
Vis a vis, its entity. D’you see?

But can a bee be said to be
Or not to be an entire bee
When half the bee is not a bee
Due to some ancient injury?

위의 글에서 "half the"라는 구문 뒤에는 항상 "bee"이라는 단어가 쓰이며, "bee" 뒤에는 "has"나 "is"가 쓰이는 것을 알 수 있다.

마르코프 분석에서는 각 접두사("half the","bee")에서 가능한 모든 접미사("has","is")로 매핑한다.

이 맵이 있으면 랜덤 접두사로 시작한 후 가능한 접미사에서 임의로 선택하고 이를 반복하여 글을 생성할 수 있다.

예를 들어, 접두사 "half a"로 시작하는 경우 다음 단어는 "bee"이여야 한다. 왜냐하면 접두사 "half a"가 글에 딱 한번 나왔기 때문에 다른 확률이 없다. 다음 접두사는 "bee"이기 때문에 그 뒤에는 접미사 “philosophically”, “be” 또는 “due”가 올 수 있다.

위의 예시는 접두사 길이를 두 단어로 한정시켰다. 이처럼 마르코프 분석은 접두사 길이를 사용해서도 활용할 수 있다.

마르코프 분석 연습문제 다음 장으로 가기 전에 해당 연습문제를 꼭 시도해보기를 추천한다.

• 파일에서 텍스트를 읽고 마르코프 분석을 수행하는 프로그램을 작성하라. 결과는 접두사에서 가능한 접미사 모음으로 매핑되는 딕셔너리어야 한다. 모음은 배열, 튜플 또는 딕셔너리 어떤 것을 사용해도 상관없다. 접두사 길이와 상관없이 사용할 수 있는 프로그램을 작성하라.

• 마르코프 분석을 기반으로 임의의 텍스트를 생성하려면 이전 프로그램에 함수를 추가하라. 다음은 접두사 길이가 2인 Emma의 예이다.

“He was very clever, be it sweetness or be angry,
ashamed or only amused, at such a stroke.
She had never thought of Hannah till you were never meant for me?"
 "I cannot make speeches, Emma:" he soon cut it all himself.”

이 예시에서는 마침표를 단어로 포함했다. 결과는 거의 문법적으로 정확하지만 완벽하지는 않으며, 의미도 어느정도 있는 것 같지만 완벽하게 이해되지는 않는다. 만약 접두사의 길이를 늘리면 어떤 결과가 나오는가? 문장이 더 의미있는가?

• 프로그램이 작동한다면, '매쉬 업(mash-up)'을 시도할 수 있다. 두 권 이상의 책을 결합하여 생성한 랜덤 텍스트는 더 흥미로운 어휘와 문장을 보여줄 것이다.

데이터 구조 (Data Structures)

마르코프 분석을 사용하여 랜덤 텍스트를 만드는 것은 재미있지만 사실 연습문제에는 '데이터 구조 선택(data structure selection)'이라는 중요한 핵심이 있다. 위의 연습문제를 풀기 위해서는 아래의 내용들을 결정해야 한다.

• 접두사를 나타내는 방법
• 가능한 접미사 모음을 나타내는 방법
• 각 접두사에서 가능한 접미사 모음으로 매핑을 나타내는 방법

마지막 문제를 해결하는 방법은 쉽다. 딕셔너리 키에서 해당 값으로 매핑해주면 끝이다. 접두사의 경우 가장 좋은 방법은 문자열, 문자열 배열, 또는 문자열 튜플이다. 접미사는 배열이나 히스토그램(딕셔너리)이 적절하다.

어떻게 선택해야 할까? 첫 번째 단계는 각 데이터 구조를 위해 구현해야 하는 작업에 대해 생각하는 것이다. 접두사의 경우 사용한 접두사를 제거하고 새로운 접두사를 추가할 수 있어야 한다. 예를 들어 현재 접두사가 "half a"이고 다음 단어가 "bee"인 경우 다음 접두사 "bee"를 생성할 수 있어야 한다.

배열은 요소를 쉽게 추가하고 제거할 수 있기 때문에 사용하기 적절하다.

접미사 모음의 경우, 새 접미사 추가 및 기존 접미사 빈도 증가, 랜덤 접미사 선택 등의 일들을 수행해야 한다.

새 접미사를 추가하는 것은 배열 구현이나 히스토그램 둘 다 쉽다. 하지만 랜덤 요소를 선택하는 것은 히스토그램보다 배열이 더 쉽다.

지금까지는 어떤 구조가 구현하기 편한지에 대해서 이야기했지만 사실 데이터 구조를 선택할 때 고려해야 할 다른 중요한 부분들이 있다. 첫 번째는 런타임이다. 각각의 데이터 구조마다 소요되는 시간은 이론적으로 차이가 있다. 예를 들어 in 연산자는 요소가 많을 때 배열보다 딕셔너리에서 더 빠르다.

그러나 어떤 구현이 더 빠른지 미리 알지 못하는 경우가 종종 있다. 이럴 경우 두 가지의 선택으로 나뉘는데, 그 중 하나는 모두 구현해본 다음에 어느 것이 더 나은지를 경험해보는 것이다. 이 접근법을 벤치마킹(benchmarking)이라고 한다. 또 다른 실용적인 대안은 구현하기 가장 쉬운 데이터 구조를 선택한 다음 프로그램에 적합한 속도인지를 확인하는 것이다. 만약 적합하다면, 굳이 다른 데이터 구조를 만들 필요가 없다. 적합하지 않다면, 시간이 가장 많이 걸리는 프로그램 위치를 알려주는 Profile 모듈과 같은 도구들을 사용하면 된다.

고려해야 할 두번째 요소는 저장 공간이다. 예를 들어, 접미사 모음에 히스토그램을 사용하면 텍스트에 여러 번 나타나는지에 관계없이 각 단어를 한 번만 저장하면 되므로 저장 공간을 덜 차지할 수 있다. 경우에 따라 저장 공간을 절약하면 프로그램 실행 속도가 빨라질 수 있으며, 메모리가 부족할 경우에는 프로그램이 실행되지 않을 수 있다. 하지만 많은 응용프로그램들에서는 런타임을 우선적으로 고려한다.

지금까지는 마르코프 분석과 텍스트 생성을 동시에 하는 데이터 구조를 생각했다. 하지만 분석과 텍스트 생성을 별도의 단계로 나눈 각각의 데이터 구조를 사용하는 것도 가능하다. 만약 통합된 데이터 구조보다 별도로 나눈 데이터 구조가 더 빠르다면 나누는 것이 바람직하다.

Tip 줄리아 패키지 DataStructures는 다양한 데이터 구조를 구현한다.

디버깅

프로그램을 디버깅할 때, 특히 어려운 버그를 만났을 때 아래의 5가지를 시도해보라.

• 읽기(Reading) 코드를 검사하고 스스로 다시 코드를 읽은 후 무엇을 원하는지 확인하라.

• 실행(Running) 변경한 다른 버전을 실행하면서 실험해보라. 코드를 올바른 위치에 잘 작성하면 문제가 명확하게 보이지만, 때로는 스캐폴딩을 만들어 문제를 확인해야 한다.

• 반추(Ruminating) 시간을 두고 생각해보라. 문법, 런타임, 의미 오류가 무엇인가? 오류 메시지 또는 프로그램 출력에서 무엇을 얻을 수 있나? 어떤 종류의 문제가 발생할 수 있는가? 문제가 나타나기 전에 변경한 사항은 무엇인가?

• 고무오리(Rubberducking) 다른 사람에게 문제를 설명하면, 말이 끝나기도 전에 답을 찾을 때가 있다. 만약 다른 사람이 없다면, 우리는 고무오리와도 대화할 수 있다. 이 전략을 고무오리 디버깅이라고 한다. 이 전략을 자세히 알고 싶다면 이 링크를 참고해라.

• 후진(Retreating) 어떨 때는 오류가 나기 전의 프로그램으로 돌아오는 것이 가장 좋은 방법이다. 즉, 변경사항들을 취소한 후 프로그램을 다시 구현하는 것이다.

초보 프로그래머들은 위의 5가지 방법 중 하나에 갇혀서 다른 방법들을 잊어버리곤 한다. 상황에 따라 문제에 최적화된 방법은 다르다는 것을 기억하자.

예를 들어, 문제가 인쇄상의 오류인 경우에는 코드를 읽는 것이 도움이 될 수 있지만 개념 오해로 비롯된 문제라면 읽는 방법은 도움이 되지 않는다. 프로그램이 어떻게 작동하는지 이해하지 못하면, 100번을 읽어도 오류를 찾을 수 없다.

실험 방법은 작고 간단한 테스트일 때 도움이 된다. 하지만 코드를 생각하거나 읽지 않고 실험만 진행하면 아무거나 바꿔보는 랜덤 워크 프로그래밍(random walk programming)에 빠질 수 있다. 이것은 시간이 오래 걸린다.

생각하려면 시간이 소요된다. 디버깅은 실험과학과 같다. 문제가 무엇인지에 대한 가설이 하나 이상은 있어야 한다. 둘 이상의 가능성이 있다면, 그 중 하나를 제거할 수 있는 테스트를 생각해보라.

그러나 오류가 너무 많거나 수정하려는 코드가 너무 크고 복잡하면 최고의 디버깅 기술조차 실패한다. 때로는 후진하는 것이 최선의 방법이며, 프로그램이 이해되고 작동될 때까지 단순화해야 한다.

초보 프로그래머는 종종 코드 라인을 삭제하는 후퇴를 꺼려한다. 불안하다면 프로그램 코드를 복사해둔 후 하나씩 수정해보라.

어려운 버그를 찾으려면 읽고, 실행하고, 반추하고 때로는 후진해야 한다. 한 가지 방법에서 막힌다면 다양한 방법을 시도해보라.

연습문제 코드 아래의 코드는 제가 직접 작성한 코드입니다. 필요하신 분들만 참고해주세요 :)

• 연습문제 1

function letterfilter(f)
    words=[]
    for word in split(f)
        word=lowercase(word)
        word=string(filter(isletter, word))
        push!(words,word)
    end
    return words
end

function sentencetoword(t)
    fin = open(t)
    temp = []
    for line in eachline(t)
    f=readline(fin)
    replace(f,"-" => " ")
    replace(f,"," => " ")
    t=letterfilter(f)
    temp=append!(temp,t)
    temp[""]=0
    end
    return temp
end

• 연습문제 2

function sentencetoword(t)
    fin = open(t)
    temp = Dict()
    for line in eachline(t)
    f=readline(fin)
    replace(f,"-" => " ")
    replace(f,"," => " ")
    letterfilter(f,temp)
    temp[""]=0
    end
    return temp
end

function letterfilter(f,temp)
    for word in split(f)
        word=lowercase(word)
        word=string(filter(isletter, word))
        temp[word]=get!(temp,word,0)+1
    end
end

function numofword(t)
    ml= sentencetoword(t)
    wordnum=sum(values(ml))
    print(wordnum)
end

• 연습문제 3

function change(t)
    m=[]
    for (key,value) in t
        push!(m,(value,key))
    end
    reverse!(sort(m))
end

function topword(t, n)
    words=change(t)
    top=words[1:n]
    print(top)
end

• 연습문제 4

wordlist=sentencetoword("words.txt")

function findweird(t1,t2)
    word1=keys(t1)
    word2=keys(t2)
    final=[]
    for word in word1
        if word ∉ word2
        push!(final,word)
        end
    end
    return final
end