고요한 하늘

기계학습에서 성능을 평가하기 위한 방법으로 BLEU라는 방법을 사용한다. 간단히 요약하면 하나의 영어 문장이 있다고 할때 이 문장을 여러사람이 번역한다. 이것을 각각 ref1, ref2라고 하고 기계번역으로 번역한것을 mt라고 했을때 mt의 결과를 unigram, bigram, trigram으로 각각 ref1, ref2에 몇번 ..

Longest Common Subsequence( not Longest Common SubString )http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/ 위 URL에 들어가면 재귀호출로 구현한것과 동적프로그래밍으로 구현한 두개의 C 코드가 있다. 아래는 이해하는데 도움이 될것 같아 간단히 위 URL에서 예로 사용한 것을 excel에 있는 ..

N개의 숫자 배열이 존재할때 상위 또는 하위 k를 선택하는 알고리즘으로 많이 알려진 max sort를 사용한다. max heap sort는 average case에 대해 O( nLOGm )정도의 시간 복잡도를 가지는데 이것보다 빠른 quick select라는 방법론이 있어서 간단히 소개한다.( average case 에 O(n) ) 우선 배열에 아래와 같이 10..

Sun Wu라는 분과 Uni manber라는 분이 논문의 공동 저자라서 아마도 알고리즘 이름을 Wu-manber라고 한것 같다. 기본적인 방법론은 boyer-moore 알고리즘에 기반한다. 일반적인 문자열 방법과 다르게 패턴의 뒤에서 부터 매칭하는 부분과 문자열 비교가 실패했을때 비교한 문자열 길이만큼 jump하는 ..

aho corasick와 함께 multi pattern matching 방법론 대가 현재 google vice president http://en.wikipedia.org/wiki/Udi_Manber Udi manber Publications : http://manber.com/publications.html http://www.academypublisher.com/proc/isip09/papers/isip09p404.pdf Commentz-Walter algorithm : aho corasick 보다 빠르다고 알려진 알고리즘 multi pattern compare : http://www...

smoothing(평탄화) ngram으로 Language Model을 구축할때 데이터 부족으로 출현하지 않은 엔트리에 대해서 어떤 확률 값을 부여할지에 대한 것이 smoothing이다. 데이터가 출현하지 않았기 때문에 확률값은 0인데 0/100000 과 0/10은 다를수 있다. 따라서 분모가 되는 수에 대한 고려를 해야한다. 10만개..

http://norvig.com/spell-correct.html

paper : Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus.pdf excel : suffix_array.xlsx suffix array를 구하는 것은 간단하다. 문자열이 "to be$or$not to be$"라고 주어졌을때( $를 기준으로 3개의 문서로 간주 ) string = [ 0] [to be$or$not to be$] [ 1] [o be$or$not to be$] [ 2] [ be$or$not to be$] [ 3]..

TRIE를 구현할때 ARRAY로 구현하면 RANDOM INDEX가 가능하기 때문에 속도 측면에서 엄청난 이득을 얻을수 있다. 다만 array를 사용하게 되면 많은 메모리를 차지하는 문제가 발생하는데 이 문제를 array를 중복사용할수 있도록한 아이디어와 sparse matrix를 세개의 배열( triple array : base, next, check )로 ..

희소 행렬을 표현하는 여러가지 방법이 있다. 그 중 Yale format에 대해 알아보자 예일포맷(Yale format) Yale format The Yale Sparse Matrix Format stores an initial sparse m×n matrix, M, in row form using three one-dimensional arrays. Let NNZ denote the number of nonzero entries of M. The first array is A, which is of length NNZ, and holds all nonzer..