단어 개수 세는 프로그램 만들기

7 min readDec 23, 2018

책을 읽다보면 어떤 단어를 가장 많이 사용 하였는지 궁금할 때가 있다. 한 페이지 정도는 사람이 셀 수도 있다. 만약 한 권 혹은 여러 권의 책이라면 굉장히 오랜 시간이 걸릴 것이다. 나는 소프트웨어 개발자 임으로 직접 프로그래밍을 해보기로 했다.

프로그래밍을 하기 전에 어떤 프로그래밍 언어를 사용할지 골라야 한다. 나는 Go (혹은 Golang)를 사용하기로 하였다. Go 언어는 배우기 쉽고 가독성이 상대적으로 좋기 때문이다. (라고 썼지만 내가 좋아해서다 ^-^)

다음으로 책이 필요하다. 인터넷에 공개 되어있는 성경 파일을 발견하였고 그 중 창세기 1장을 복사해왔다. 각 절앞에 숫자가 있으므로 프로그래밍 시 제거해야한다.

1태초에 하나님이 천지를 창조하시니라 2땅이 혼돈하고 공허하며 흑암이 깊음 위에 있고 하나님의 영은 수면 위에 운행하시니라 3하나님이 이르시되 빛이 있으라 하시니 빛이 있었고 4빛이 하나님이 보시기에 좋았더라 하나님이 빛과 어둠을 나누사 5하나님이 빛을 낮이라 부르시고 어둠을 밤이라 부르시니라 저녁이 되고 아침이 되니 이는 첫째 날이니라
6하나님이 이르시되 물 가운데에 궁창이 있어 물과 물로 나뉘라 하시고 7하나님이 궁창을 만드사 궁창 아래의 물과 궁창 위의 물로 나뉘게 하시니 그대로 되니라 8하나님이 궁창을 하늘이라 부르시니라 저녁이 되고 아침이 되니 이는 둘째 날이니라
9하나님이 이르시되 천하의 물이 한 곳으로 모이고 뭍이 드러나라 하시니 그대로 되니라 10하나님이 뭍을 땅이라 부르시고 모인 물을 바다라 부르시니 하나님이 보시기에 좋았더라 11하나님이 이르시되 땅은 풀과 씨 맺는 채소와 각기 종류대로 씨 가진 열매 맺는 나무를 내라 하시니 그대로 되어 12땅이 풀과 각기 종류대로 씨 맺는 채소와 각기 종류대로 씨 가진 열매 맺는 나무를 내니 하나님이 보시기에 좋았더라 13저녁이 되고 아침이 되니 이는 셋째 날이니라
14하나님이 이르시되 하늘의 궁창에 광명체들이 있어 낮과 밤을 나뉘게 하고 그것들로 징조와 계절과 날과 해를 이루게 하라 15또 광명체들이 하늘의 궁창에 있어 땅을 비추라 하시니 그대로 되니라 16하나님이 두 큰 광명체를 만드사 큰 광명체로 낮을 주관하게 하시고 작은 광명체로 밤을 주관하게 하시며 또 별들을 만드시고 17하나님이 그것들을 하늘의 궁창에 두어 땅을 비추게 하시며 18낮과 밤을 주관하게 하시고 빛과 어둠을 나뉘게 하시니 하나님이 보시기에 좋았더라 19저녁이 되고 아침이 되니 이는 넷째 날이니라
20하나님이 이르시되 물들은 생물을 번성하게 하라 땅 위 하늘의 궁창에는 새가 날으라 하시고 21하나님이 큰 바다 짐승들과 물에서 번성하여 움직이는 모든 생물을 그 종류대로, 날개 있는 모든 새를 그 종류대로 창조하시니 하나님이 보시기에 좋았더라 22하나님이 그들에게 복을 주시며 이르시되 생육하고 번성하여 여러 바닷물에 충만하라 새들도 땅에 번성하라 하시니라 23저녁이 되고 아침이 되니 이는 다섯째 날이니라
24하나님이 이르시되 땅은 생물을 그 종류대로 내되 가축과 기는 것과 땅의 짐승을 종류대로 내라 하시니 그대로 되니라 25하나님이 땅의 짐승을 그 종류대로, 가축을 그 종류대로, 땅에 기는 모든 것을 그 종류대로 만드시니 하나님이 보시기에 좋았더라 26하나님이 이르시되 우리의 형상을 따라 우리의 모양대로 우리가 사람을 만들고 그들로 바다의 물고기와 하늘의 새와 가축과 온 땅과 땅에 기는 모든 것을 다스리게 하자 하시고 27하나님이 자기 형상 곧 하나님의 형상대로 사람을 창조하시되 남자와 여자를 창조하시고 28하나님이 그들에게 복을 주시며 하나님이 그들에게 이르시되 생육하고 번성하여 땅에 충만하라, 땅을 정복하라, 바다의 물고기와 하늘의 새와 땅에 움직이는 모든 생물을 다스리라 하시니라
29하나님이 이르시되 내가 온 지면의 씨 맺는 모든 채소와 씨 가진 열매 맺는 모든 나무를 너희에게 주노니 너희의 먹을 거리가 되리라 30또 땅의 모든 짐승과 하늘의 모든 새와 생명이 있어 땅에 기는 모든 것에게는 내가 모든 푸른 풀을 먹을 거리로 주노라 하시니 그대로 되니라 31하나님이 지으신 그 모든 것을 보시니 보시기에 심히 좋았더라 저녁이 되고 아침이 되니 이는 여섯째 날이니라

책과 프로그래밍 언어가 준비되었다. 이제는 알고리즘을 고민해야 한다. 우선 생각나는 것을 적어보자.

숫자를 제거한다. 성경에는 숫자는 장이나 절을 표시 하므로 굳이 셀 필요가 없다.
공백으로 단어를 구분하고 Hash Map을 이용해서 각 단어별 출현횟수를 기록한다. 단어의 개수가 n 이라고 하면 시간복잡도는 O(n) 이다.
공간복잡도는 모든 단어를 저장해야 하므로 단어의 개수를 n, 단어의 최대길이를 m이라고 할 때 O(n * m)이다. 한 가지 생각해봐야 할 점은, 유사한 단어를 모두 다른 단어로 저장해야 한다는 것이다. 예컨대 ‘생물과'과 ‘생물을'은 한 글자만 다르지만 다른 단어로 저장 해야만 한다.
여러 권의 책을 읽는 다면 메모리의 한계에 다다를 것이다. 적당히 읽고 기록하는 과정을 반복해야 한다. 물론 창세기 1장을 처리하는 것은 문제 없다.
Hash Map을 이용하지 말고 Trie를 이용하게 되면 read와 write의 성능이 O(1) → O(m)으로 떨어지는 문제가 있지만 공간복잡도를 낮출 수 있지 않을까? 저장해야 하는 데이터가 한글이므로 Trie의 각 노드는 ‘가'부터 ‘핳'까지 길이를 갖는 배열을 지니고 있어야 한다! 다행인건, 성경에서 나오는 단어의 길이는 아무리 길어봤자 10자를 넘지 않을 것이다.

우선 Hash Map을 이용해서 간단하게 구현해보자.

import (
   "bufio"
   "fmt"
   "os"
   "sort"
   "strings"
)

type Pair struct {
   Word string
   Count int
}

func main() {
   bookString := readBook("genesis1.txt")
   words := strings.Split(bookString, " ")
   counter := countWords(words)
   showTopN(counter, 5)
}

func countWords(words []string) map[string]int {
   counter := map[string]int{}
   for _, word := range words {
      counter[word]++
   }
   return counter
}

func readBook(fileName string) string {
   var builder strings.Builder

   f, _ := os.Open(fileName)
   defer f.Close()
   sc := bufio.NewScanner(f)
   for sc.Scan() {
      builder.WriteString(sc.Text())
   }

   return builder.String()
}

func showTopN(counter map[string]int, limit int) {
   pairs := make([]Pair, len(counter))
   for k, v := range counter {
      pairs = append(pairs, Pair{k , v})
   }
   sort.Slice(pairs, func(i, j int) bool {
      return pairs[i].Count > pairs[j].Count
   })
   for i := 0; i < limit; i++ {
      pair := pairs[i]
      fmt.Printf("%d. %s - %d번\n", i+1, pair.Word, pair.Count)
   }
}

위 코드에는 숫자(절)를 제거하는 코드는 없는데 최대한 코드를 간단하게 표현하고 싶었다. 단어를 세는 로직은 map에 계속 더하는 것 외에는 없다. 오히려 TOP N을 표시하기 위해 count를 기준으로 정렬하는 과정에서 Pair라는 구조체를 추가 해야만 했다.

결과는 아래와 같다.

다음에는 Trie를 이용해서 구현해 볼 예정이다.

단어 개수 세는 프로그램 만들기

Written by Jeong Dowon