[Algorithm] What is the N-gram?

1. N-gram 이란?

N-gram 이란 간단하게 말해서 입력한 문자열을 N개의 기준 단위로 분리하는 방법이다.

예를 들어, "Here is a dog" 라는 문장을 단어 단위의 3-gram으로 만든다면,

"Here is a", "is a dog"로 만들 수 있다. 이렇게 할 경우 각 키워드에 따른 빈도(Relative Frequency)를 분석 할 수 있고, 검색어 엔진에서 키워드를 뽑아내거나 음성 인식에서도 쓰일 수 있다고 한다.

 

2. N-gram 알고리즘

   2-1. N-gram 실행 전 문자열 다듬기

String line = value.toString().replaceAll("[^A-Za-z]"," ");

나 같은 경우 자바에서 N-gram 알고리즘을 사용했었기에 이렇게 정규표현식과 replaceAll 함수를 사용 하여 문자를 다듬어 주었다. 이때, 알파벳이 아닌것들을 모두 공백으로 만들어 주었다.

 

   2-2. N-gram 단어 단위로 만들기

String word_list ="";

// Doing N-grams according to each word
                for(i = 0; i <= num_itr - N ; i++){
                    if(words[i] != null){
                        String key_word = words[i];
                        HashMap<String, Integer> map = new HashMap<String, Integer>();
                        if (input_map.containsKey(key_word)){
                            map = input_map.get(key_word);
                        }
                        //Make N-gram words
                        for (j = i + 1 ; j < i + N; j++){
                            word_list = word_list + " " + words[j]; //concat words
                        }
                        if (map.containsKey(word_list)){
                            map.put(word_list, (int) map.get(word_list) + 1);
                        }else {
                            map.put(word_list, 1);
                        }
                        input_map.put(key_word, map);
                        word_list = "";
                    }
                }

나 같은 경우 Java의 Hash map을 사용하여 N-gram 기준 keyword와 뒤에 따라오는 word_list로 구분해주었고, keyword에 따라 word_list를 생성해 N-gram 단어를 생성했다. 그 후, Hashmap에 있는지 없는지 여부를 확인해 그 단어를 count 해주었다.

 

3. My Review

맨 처음에 N-gram 알고리즘을 공부했을 때는 그냥 단순히 알고리즘 중 하나인줄 알았는데 이렇게 블로그를 쓰면서 조사를 해보니깐 N-gram 알고리즘은 Language Model에서 사용되는 기본적인 기술 중 하나라는 것을 알았다.

또한 N-gram 기반으로 담은 단어를 확률로도 예측 할 수 있는 것이 굉장히 과학적이라고 느껴졌다.

하지만 N-gram에도 정확도 문제가 있다.

예를 들어, N-gram 언어 모델은 이전의 N개의 단어만 고려하기 때문에, 앞 문장의 맥락을 놓치는 경우가 발생 할 수 있기 때문에 정확도가 떨어질 수 있다고 한다.