hash를 이용한 문장 내 단어 개수 세기

1. 개요

 기본적인 Hash에 대해서는 알것이라고 생각한다. 아래 소스코드에서 사용되는 중요 변수에 대한 설명은 다음과 같다.

(1) struct vocab_word *vocab : Vocabulary의 약자로 단어가 저장될 Array이다. 다만 정렬되어 저장되지 않고 들어온 순서대로 저장된다.

(2) Hash Function : 'word'라는 단어가 들어왔을 때 각 알파벳의 비트와 자리에 따른 값을 곱해 특정 숫자를 구한다.

(3) const int vocab_hash_size : Hash Function의 Output의 최대 크기이다.

(4) int *vocab_hash : Hash Function으로 구한 자리에 실제 단어가 vocab Array에 저장되어 있는 위치값을 저장한다.

2. Source Code - C

#include <stdio.h> #include <stdlib.h> #include <string.h> struct vocab_word { long long count; char *word; }; #define MAX_STRING 100 const int vocab_hash_size = 30000000; long long vocab_max_size = 1000; int *vocab_hash, vocab_size = 0; struct vocab_word *vocab; void InitVocab() { vocab = (struct vocab_word *)calloc(vocab_max_size, sizeof(struct vocab_word)); vocab_hash = (int *)calloc(vocab_hash_size, sizeof(int)); } // Returns position of a word in the vocabulary; if the word is not found, returns -1 int SearchVocab(char *word) { unsigned int hash = GetWordHash(word); while (1) { if (vocab_hash[hash] == -1) return -1; if (!strcmp(word, vocab[vocab_hash[hash]].word)) return vocab_hash[hash]; hash = (hash + 1) % vocab_hash_size; } return -1; } // Returns hash value of a word int GetWordHash(char *word) { unsigned long long a, hash = 0; for (a = 0; a < strlen(word); a++) hash = hash * 257 + word[a]; hash = hash % vocab_hash_size; return hash; } // Adds a word to the vocabulary int AddWordToVocab(char *word) { unsigned int hash, length = strlen(word) + 1; if (length > MAX_STRING) length = MAX_STRING; vocab[vocab_size].word = (char *)calloc(length, sizeof(char)); strcpy(vocab[vocab_size].word, word); vocab[vocab_size].count = 1; vocab_size++; // Reallocate memory if needed if (vocab_size + 2 >= vocab_max_size) { vocab_max_size += 1000; vocab = (struct vocab_word *)realloc(vocab, vocab_max_size * sizeof(struct vocab_word)); } hash = GetWordHash(word); while (vocab_hash[hash] != -1) hash = (hash + 1) % vocab_hash_size; vocab_hash[hash] = vocab_size - 1; return vocab_size - 1; } int main(int argc, char** argv) { int hashNum; char str = "myword"; InitVocab(); hashNum = SearchVocab(str); if (hashNum == -1) { AddWordToVocab(str); } else { printf("%s counted %d\n", str, vocab[vocab_hash[hashNum]]); } }