DBPIA-NURIMEDIA

Transcription

1 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 283 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 (An Efficient Frequent Melody Indexing Method to Improve Performance of Query-By-Humming System) 유진희 박상현 (Jinhee You) (Sanghyun Park) 요약최근방대한양의음악데이타를효율적으로저장하고검색하기위한방법의필요성이증대되고있다. 현재음악데이타검색에서가장일반적으로쓰이는방법은텍스트기반의검색방법이다. 그러나이러한방법은사용자가키워드를기억하지못할경우검색이어려울뿐만아니라키워드와정확하게일치하는정보만검색해주기때문에유사한내용을가진정보를검색하기에부적절하다. 이러한문제점을해결하기위해본논문에서는내용기반인덱싱방법 (Content-Based Indexing Method) 을사용하여사용자가부정확한멜로디 (Humming) 로질의하였을경우라도원하는음악을효율적으로찾아주는허밍질의처리시스템 (Query-By-Humming System) 을설계한다. 이를위해방대한음악데이타베이스에서한음악을대표하는의미있는멜로디를추출하여인덱싱하는방법을제안한다. 본논문에서는이러한의미있는멜로디를사용자가자주질의할가능성이높은멜로디로서하나의음악에서여러번나타나는빈번멜로디와긴쉼표후에시작되는쉼표단위멜로디로정의한다. 실험을통해사용자들이이들멜로디를자주질의한다는가정을증명하였다. 본논문은성능향상을위한 3 가지방법을제안한다. 첫번째는검색속도를높이기위해인덱스에저장할멜로디를문자열형태로변환한다. 이때사용되는문자변환방법은허밍에포함된에러를허용한방법으로써검색결과의정확도를높일수있다. 두번째는사용자가자주질의할가능성이높은의미있는멜로디를인덱싱하여검색속도를높이고자한다. 이를위해신뢰도가높은의미있는멜로디를생성하는빈번멜로디추출알고리즘과쉼표단위멜로디추출방법을제안한다. 세번째로는정확도를향상시키기위한 3 단계검색방법을제안한다. 이는데이타베이스접근을최소화하여정확한검색결과를얻기위하여제안되었다. 또한기존의허밍질의처리시스템의대표적인인덱싱방법으로제안되었던 N-gram 방법과의성능비교를통해본논문이제안하는방법의성능이보다더향상되었음을검증하였다. 키워드 : 멀티미디어데이타베이스, 허밍질의처리시스템, 음악정보검색, 내용기반검색, 인덱싱 Abstract Recently, the study of efficient way to store and retrieve enormous music data is becoming the one of important issues in the multimedia database. Most general method of MIR (Music Information Retrieval) includes a text-based approach using text information to search a desired music. However, if users did not remember the keyword about the music, it can not give them correct answers. Moreover, since these types of systems are implemented only for exact matching between the query and music data, it can not mine any information on similar music data. Thus, these systems are inappropriate to achieve similarity matching of music data. In order to solve the problem, we propose an Efficient Query-By-Humming System (EQBHS) with a content-based indexing method that efficiently retrieve and store music when a user inquires with his incorrect humming. For the purpose of accelerating query processing in EQBHS, we design indices for significant melodies, which are 1) frequent melodies occurring many times in a single music, on the assumption that users are to hum what they can easily remember and 2) melodies partitioned by rests. In addition, we propose 본연구는문화관광부및한국문화콘텐츠진흥원의문화콘텐츠기술연구소 (CT) 육성사업의연구결과로수행되었음 학생회원 : 연세대학교컴퓨터과학과 jhyou@cs.yonsei.ac.kr 종신회원 : 연세대학교컴퓨터과학과교수 sanghyun@cs.yonsei.ac.kr 논문접수 : 2006년 10월 24일심사완료 : 2007년 5월 14일

2 284 정보과학회논문지 : 데이타베이스제 34 권제 4 호 (2007.8) an error tolerated mapping method from a note to a character to make searching efficient, and the frequent melody extraction algorithm. We verified the assumption for frequent melodies by making up questions and compared the performance of the proposed EQBHS with N-gram by executing various experiments with a number of music data. Key words :Multimedia Database, Query-By-Humming System, Music Information Retrieval, Content-Based Searching Method, Indexing 1. 서론최근멀티미디어정보의활용이일반화되면서방대한양의멀티미디어정보를효율적으로저장하는방법들의필요성이증대되고있다. 또한사용자들은기존의멀티미디어정보검색방법들보다더욱쉽고빠른방법을필요로하고있다. 이와같은사용자들의요구에맞추어현재멀티미디어정보를효율적으로저장하고빠르게검색하는방법에관한연구가활발히진행되고있다. 멀티미디어정보검색방법중기존의가장일반적인방법으로텍스트기반검색방법 (Text-Based Retrieving Method) 이있다. 이방법은사용자가미리선정해놓은키워드를사용하여원하는정보를검색하는방식이다. 그러나이는사용자가키워드를기억하지못할경우검색이어려울뿐만아니라키워드와정확하게일치하는정보만검색할수있기때문에유사한내용을가진정보는검색하기어렵다. 특히음악정보검색 (Music Information Retrieval) 에서가장일반적으로사용되는검색방법도마찬가지로텍스트기반검색방법이다. 이는사용자가음악의제목, 가수명, 앨범명등과같은키워드형식의메타정보를사용하여원하는음악을검색하는방식이다. 그러나사용자가위와같은메타정보를기억하지못할경우검색이어려울뿐만아니라키워드를알고있더라도유사한멜로디를가진음악을검색하는데어려움이발생하게된다. 이러한문제점을해결하기위해서제안된방법으로멀티미디어데이타의내용을사용하여검색하는내용기반검색방법 (Content-Based Searching Method) 이있다. 이는음악정보검색뿐만아니라멀티미디어정보검색과관련된모든분야에서큰이슈가되고있다 [1]. 특히, 음악정보검색에서사용되는내용기반검색은주어진음악의내용에해당하는멜로디를기반으로검색을수행하는방법이다 [2]. 이는기존의텍스트기반검색과달리내용을직접비교하여사용자가원하는내용을가진결과값을얻을수있다. 또한내용의유사성을파악할수있기때문에유사한멜로디를검색하는데적합하다. 음악정보검색에서대표적인내용기반검색의연구분야로는허밍질의처리 (Query-By-Humming) 방식이있다 [3]. 이방식은사용자가부른허밍 (Humming) 을질의로사용하여이와유사한멜로디를포함하고있는음악을얻어내는것이다. 이러한허밍질의처리방식의장점은정확하지않은멜로디로질의하였을경우에도검색이가능하기때문에노래실력이없는사람들이나언어장애를가진사람들도효과적으로음악을검색할수있다는것이다. 그러나기존의허밍질의처리방식의단점은방대한음악데이타베이스에서비슷한멜로디를찾는작업이복잡한계산과오랜검색시간을요구한다는것이다. 이는데이타베이스에저장된방대한크기의멜로디들과질의사이의유사성을판별하기위해서숫자데이타를사용하여순차적으로거리를구해야하기때문이다. 따라서본논문은내용기반검색방법을사용하면서발생되는검색비용을줄이기위해숫자형태로표현된멜로디를문자형태로변화하여검색하는방법을사용한다. 이러한문자변환방법은사용자의질의에포함될수있는에러를허용 (False Tolerance) 함으로써정확도를보장해준다. 또한, 본논문은검색시간을줄이기위해의미있는멜로디를추출하여인덱싱하는효과적인내용기반인덱싱방법 (Efficient Content-Based Indexing Method) 을제안한다. 여기서의미있는멜로디란사용자가자주질의할가능성이높은멜로디이다. 본논문에서는의미있는멜로디를두가지로분류하였는데첫번째멜로디는하나의음악에서여러번나타나는빈번멜로디이고두번째멜로디는긴쉼표후에시작되는쉼표단위멜로디이다. 본논문은신뢰도가높은의미있는멜로디를추출하기위해효과적인빈번멜로디추출방법과쉼표단위멜로디추출방법제안한다. 현재허밍질의처리시스템의인덱싱에관련된연구활동중대표적인방법으로 N개의음표가하나의단위가되도록하여이들을인덱싱하는 N-gram방법이있다 [4-6]. 이방법은인덱싱이쉽다는장점을가지고있지만음악의모든멜로디를저장하기때문에사용자의질의와유사한부분을검색하기위해서는저장된모든멜로디를차례로비교해야한다는단점이있다. 또한정확도측면에서좋은검색결과를보장하지못한다는단점도가지고있다. 이는 N-gram에서사용한특징데이타를문자형태로변환할때부정확한멜로디라는허밍의특징을고려하지않고에러허용없이변환하므로

3 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 285 결국사용자가부른허밍의부정확한정도가클수록검색결과의정확도가급속도로떨어지기때문이다. 본논문은이러한기존의 N-gram 방법과성능비교를통해본논문이제안하는인덱스방법이 N-gram방법보다향상된성능을보임을증명한다. 본논문에서제안하는시스템은크게두단계로나뉘어진다. 첫번째는허밍질의처리시스템구축단계이고두번째는질의처리단계이다. 시스템구축단계에서는미디 (MIDI) 형식의음악을입력받아특징데이타를추출한후이를특징데이타베이스에저장하고, 3개의인덱스를생성한후특징데이타를문자형태로변환하여인덱스에저장함으로써전체시스템을구축한다. 질의처리단계에서는우선적으로질의전처리과정을통해질의를특징데이타베이스에저장된데이타형태와인덱스에저장된형태와같도록변환하는작업이필요하다. 이러한질의전처리과정이후에는 3개의인덱스와데이타베이스를단계별로검색하는 3단계검색방법을실행한다. 본논문에서제안하는 3단계검색방법의목표는특징데이타베이스의접근을최소화하여검색속도를향상시키는것이다. 본논문의구성은다음과같다. 2장에서는관련연구를통하여기존의음악정보검색에사용되는특징데이타의종류와기존의내용기반인덱싱기법에대해기술한다. 3장에서는허밍질의처리시스템의구축과정을단계별로설명한다. 4장에서는질의처리과정을보이고 5장에서는실험과성능평과결과를기술한다. 마지막으로 6장에서는본논문을요약하고결론을기술한다. 2. 관련연구 2.1 허밍질의처리시스템현재내용기반음악정보검색시스템에서질의특성에따라효과적인특징데이타를찾는연구가활발히진행되고있다. 이는음표의정확한높이와길이를가진원음악과같은정확한질의를처리하기위한것과허밍과같은부정확한질의를처리하기위한것으로나뉘어진다. 특히, 부정확한질의를처리하기위한대표적인시스템으로허밍질의처리시스템이있다 [3,7]. 이시스템에서멜로디를표현하기위해일반적으로사용되는특징데이타로 UDS 문자열 [8] 이있는데이는인접한두음표의높이를사용하여뒤의음표가앞의음표보다높으면 U(Up), 낮으면 D(Down), 같으면 S(Same) 로표현한다. 그러나이와같은데이타는단지음높이의곡선을이용할뿐음의길이는무시한정보이므로정확도측면에서효율적이지않다. 또다른허밍질의처리시스템으로는음악의템포 (Tempo) 를사용하여검 색하는방법이있다 [9]. 그러나템포데이타도많은특징정보를가지고있지않기때문에부정확한허밍을처리할경우정확도가떨어지게된다. 이와같은단점을보완하기위해부정확한멜로디인허밍질의의특징을고려한효과적인특징데이타를사용해야할필요가있다. 기존의여러특징데이타들중인접한두음표의높이변화량 (Pitch Interval) 과길이변화율 (Duration Ratio) 을사용하였을경우가장정확한검색결과를보인다는연구결과가발표되었다 [6]. 이는음표의높이와박자를모두고려하였으며멜로디의변화곡선이아니라변화의정도를정확한수치로표현하였기때문이다. [6] 의연구결과를바탕으로, 본논문에서는허밍질의처리시스템에적합한특징으로써두음표의높이변화량과길이변화율을사용한다. 2.2 음악인덱스구조음악정보검색과관련된또다른연구활동으로는효율적인인덱스구조에관한것이있다. 이러한연구가활발한이유는방대한음악데이타베이스를순차적으로검색함으로써발생하는오랜검색시간과방대한비교계산량을줄이기위해서이다. 이를보완하기위한기존의대표적인인덱스방법으로 N-gram이있다 [10,11]. 이방법은 N개의음표들을하나의단위로취급하여한음표씩오른쪽으로이동시키며인덱싱하는방법으로이는크기가 N인슬라이딩윈도우 (Sliding Window) 와같은개념이다. 이러한인덱스설계방식으로인하여 N-gram은인덱스크기가크고검색비용면에서좋지않은성능을보인다. 또한검색속도를향상시키기위해숫자형태의특징데이타를문자열로변환하지만이는부정확한멜로디인허밍의특징을고려하지않은문자열로서질의가부정확할수록정확도가급격히떨어지게된다. 또다른인덱스방법으로는공간접근방식 (Spatial Access Method) 을사용하는경우가있다 [12,13]. 이방법은한음표의높이와길이정보를이용하여이를 2차원공간상의하나의점으로표현한후연속된점들의위치정보를인덱싱하는방법이다. 대표적으로 R- Tree를사용하는방법이있는데, 이는검색속도가빠르지만질의를포함한최소영역사각형 (Minimum Bounding Rectangle) 안에질의와거리가가까운음악들이많이나타나기때문에정선도 (Selectivity) 가좋지않다는단점을가지고있다 [12]. 2.3 내용기반멜로디인덱싱방법음악정보검색에서사용되는내용기반인덱싱기법은음악의특정멜로디를인덱싱하여검색속도를줄이는방법이대부분이다 [14-16]. 이는한음악에서어떤부분의멜로디를인덱싱하느냐에따라음악검색시스템의성능이달라지기때문에성능을향상시킬수있는

4 286 정보과학회논문지 : 데이타베이스제 34 권제 4 호 (2007.8) 의미있는멜로디를선택하는것이중요하다. 대표적으로음악의시작부분을인덱싱함으로써검색속도를향상시킨방법이있다 [14]. 이는사용자가음악의시작부분을자주질의할가능성이높다는것을이용하였다. 그러나이방법은사용자가음악의시작부분을질의하지않을경우빠른검색속도를보장하지못한다. 또한사용자가음악의시작부분을자주질의한다는것에대한충분한근거를제시하지못하였다. 또다른내용기반인덱싱방법으로는일정하게반복된멜로디를인덱싱한연구가있다 [15]. 그러나이방법은일정한단위없이반복멜로디를찾기때문에반복멜로디추출과정이너무복잡하고후보빈번멜로디가많이발생하여인덱스크기가커지는단점을가지고있다. 앞의두방법과는반대로데이타베이스에저장된음악을인덱싱하지않고사용자의질의를인덱싱하는방법이있다 [16]. [16] 은사용자질의멜로디가입력되면이를 UDS 문자열로변환한후질의들을서로비교하여자주질의되는멜로디를인덱싱하는방법이다. 이는사용자가자주질의한음악은빠르게검색해주는장점을가지고있지만만약자주질의하지않는멜로디가입력이되면데이타베이스에직접접근해야하는단점이있다. 또한음의박자를고려하지않고음높이의곡선만을이용한 UDS 문자열방법을사용하였기때문에정확도측면에서낮은성능을나타낸다. 3. 허밍질의처리시스템구축이장에서는그림 1과같이허밍질의처리시스템을구축하는과정을설명한다. 허밍질의처리시스템을구축하는과정은다음과같다. (1) 미디 (MIDI) 형태의음악파일을입력받은후미디음표 (Note) 의높이 (Pitch) 와길이 (Duration), 쉼표 (Rest) 의길이, 마디 (Bar) 의경계를추출한다. (2) 추출한음표들과쉼표들의높이와박자정보를사용하여특징데이타 (Feature Data) 를추출한다. 본논그림 1 허밍질의처리시스템구축과정 문에서지정한특징데이타는멜로디를표현할수있는연속된음표와쉼표들의변화수치이다. (3) 생성한특징데이타를특징데이타베이스 (Feature Database) 에저장한다. (4) 인덱스를생성하기위해특징데이타를문자형태로변환한다. (5) 문자형태로변환한후의미있는멜로디를추출한다. 의미있는멜로디란사용자가질의할가능성이높은멜로디를말한다. (6) 추출한멜로디를서픽스트리 (Suffix Tree) 에저장하여 3개의인덱스를구축한다. 3장은다음과같이이루어져있다. 3.1절에서는특징데이타추출과정과저장방법을기술하고 3.2절에서는특징데이타를문자형태로변환하는과정에대해설명한다. 3.3절에서는의미있는멜로디인빈번멜로디와쉼표단위멜로디를추출하는과정에대해설명하고 3.4 절에서는인덱싱과정에대해설명한다. 3.1 특징데이타추출과저장본논문이구축할허밍질의처리시스템은데이타베이스에저장된멜로디와사용자의질의멜로디를서로비교하여사용자가원하는음악을검색해주는시스템이므로멜로디를추출하는과정이가장우선적으로진행되어야한다. 이를위해서우선미디형식의음악파일들을입력받은후음표의높이와길이, 쉼표의길이, 마디경계를추출해야한다. 이들을추출하는이유는연속된음표와쉼표들의높이변화량과길이의변화율이멜로디를표현하기에가장적절한데이타이기때문이다 [6,17]. 음표의높이정보를얻기위하여미디에서음의높이를미리정의해놓은값으로써옥타브 (Octave) 를사용한다. 옥타브의표기는알파벳형태의음계와숫자로이루어져있고값의범위는 0부터 127까지이다. 예를들어옥타브가 F5 인음표는그높이값이 65 이다. 본논문은이러한숫자값을사용하여음표의높이를표현한다. 다음으로음표와쉼표의길이를추출한다. 미디음악에서음표의길이는 4분음표즉, 한박자의길이 (Time Base) 를기준으로계산된다. 그러나미디음악마다한박자의길이가다를수있기때문에같은음표라도그음의길이는음악마다다른값이될수있다. 그러므로모든음악의한박자길이를동일한값으로변환해주는작업이필요하다. 이와같은방법을통해모든음표의높이와길이를추출한다. 또한이단계에서마디경계를추출하는데이를추출하는이유는한음악에서빈번하게발생하는빈번멜로디를발견할때일정한길이를가진단위로서마디를사용하기위해서이다. 마디의경계는입력된미디음악의전체박자즉, 몇분의몇박자정보 (Time Signature) 와한박자의길이,

5 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 287 그리고음표와쉼표의길이를통해계산이가능하다. 사용자가입력한허밍은음표의정확한높이와길이가아닌부정확한멜로디이다. 다시말해사용자는원음악과다르게전체음조를높게부르거나낮게부를수있고원음악보다빠르게부르거나느리게부를수도있다. 이러한특징을고려하여정확도가높은음악검색시스템을구축하기위해서는음표의높이변화량과길이변화율을특징데이타로사용하는것이바람직하다. 음표의높이변화량이란인접한두음표사이에서뒤의음표의높이와앞의음표의높이의차를의미한다. 즉, 음표의높이가얼마만큼증가, 감소했는지또는동일한지를정확한수치로표현하는것이다. 길이의변화율은인접한두음표사이에서뒤음표의길이를앞음표의길이로나누어계산한다. 그림 2와같이두개의인접한음표사이에 2차원벡터형태의특징데이타를계산하고이값을앞음표에대한정보로서저장한다. 만약인접한두음표를 N i 와 N i+1 이라면 N i 의특징데이타를추출하기위한수식은아래와같다. 만일연속된음표사이에쉼표가있다면그림 3과같이처리한다. 많은허밍질의처리연구에서는쉼표를무시한경우가대부분이지만본논문에서는사용자가쉼표를포함하여불렀을경우를고려하여쉼표정보를특징데이타에포함시킨다. 또한일정한길이이상의쉼표후에시작되는멜로디를질의할가능성이높다는가정을바탕으로하였기때문에쉼표의위치를중요하게취급한 다. 쉼표는음표와는달리길이정보만가지고있다. 그렇기때문에쉼표의높이를널값 (Null) 으로저장하고그림 3과같이 # 으로표현한다. 다음으로쉼표의특징데이타를추출하기위해높이의변화량과길이의변화율을계산한다. 이때쉼표의위치에따라두가지의경우로나누어처리할수있다. 첫번째경우는음표뒤에쉼표가나오는경우이다. 이때계산되어야할특징데이타는앞음표의데이타가되며그값은그림 3과같이높이의변화량은변화가없음을의미하는 0.00 으로저장하고길이의변화율을음표의길이와쉼표의길이를사용하여 0.5 의변화율로계산함으로써쉼표의정보를앞음표의정보에포함시킨다. 이때만일쉼표대신에길이와박자가각각 67과 30인음표가이어진다면위의경우와마찬가지로 (0.00, 0.5) 라는특징데이타값이계산될것이다. 이는쉼표의정보가신뢰성이없다는문제점이될수있지만사용자가허밍을부를경우쉼표를정확히지키지못하고음표로인식하여음을계속이어서부를경우가발생할수있기때문에위와같은두가지경우를분리하지않고생각한다. 다음으로그림 3과같이쉼표뒤에음표가나온다면이때계산되어야할특징데이타는쉼표의데이타가되는데이는무시한다. 그이유는무시된길이변화율은멜로디를표현하지못하는무음의멜로디이기때문이다. 지금까지설명한방법을통해하나의미디음악에서연속된 2차원벡터형태의특징데이타들을모두생성한후그림 2와같이이들을특징데이타베이스에저장한다. 그림 2 특징데이타추출과정 그림 3 쉼표처리과정 3.2 문자변환 2차원벡터형태로특징데이타가저장된데이타베이스를검색할경우모든음악을순차적으로비교하여검색해야한다. 이때데이타베이스에저장된 2차원벡터는숫자값으로되어있고검색을위한질의와의비교방법은일반적으로유클리디안거리 (Euclidean Distance) 계산방법을사용한다. 그러므로이러한검색방법은데이타베이스의크기가증가될수록검색속도가느려지게된다. 이를보완하기위해특징데이타를문자열형태로변환하여저장해놓은인덱스의필요성이대두되었다. 즉, 특징데이타를문자열로변환하는이유는숫자형태로이루어진 2차원벡터를비교하는것보다문자로바꾼후문자열매칭 (String Matching) 알고리즘을사용하는것이계산복잡도를줄일수있는방법이기때문이다. 2차원벡터형태의숫자값을문자값으로변환하기위해그림 4와같이 2차원의공간을 35개의구간으로

6 288 정보과학회논문지 : 데이타베이스제 34 권제 4 호 (2007.8) 그림 4 문자변환기준의예 나누고각구간을하나의문자로할당하는문자변환기준을적용한다. 따라서비슷한 2차원벡터값은같은문자로치환되게된다. 이는허밍이부정확하다는특징을반영한것으로서변환된문자는부정확한허밍이가지고있는에러를허용한값이된다. 그림 4에서 X축은높이의변화량을의미하고 Y축은길이의변화율을의미한다. X축에서 0값을기준으로오른쪽은높이의변화량이양수값을보인다. 이는인접한두음표사이에서뒤음표의높이가앞음표의높이보다높은경우를의미하고오른쪽으로갈수록그차이는점점더커짐을의미한다. 반대로 X축의 0값을기준으로왼쪽은높이의변화량이음수값을보인다. 이는뒤음표의높이가앞음표의높이보다낮음을의미하고왼쪽으로갈수록그차이는점점커짐을의미한다. 마찬가지로 Y축에서 1값을기준으로위쪽은뒤음표의길이가앞음표의길이보다긴경우이고그길이의비율차이는위쪽으로갈수록점점더커짐을의미한다. 반면 Y축의 1값을기준으로아래쪽은뒤음표의길이가앞음표의길이보다짧은경우이고그길이의차이는아래로갈수록점점더커짐을의미한다. 위의기준에서 -4 와 +4 사이의높이변화량은같은문자로변환되는데이는사용자가실제음악의한음을부를때실제음의높이보다 4만큼높게부르거나낮게불러도그만큼의오차는허용됨을뜻한다. 마찬가지로박자의변화율에서 0.5와 2사이는같은문자로변환된다. 이는사용자가실제음악의한음을부를때실제길이보다 2배의길이로부르거나 0.5배의길이로불러도그만큼의오차를허용한다는의미이다. 그림 5는위의문자변환기준을사용하여연속된 2차원벡터값들을문자로변환한결과이다. 문자변환기준은 2차원구간의크기에따라정확도가달라진다. 그러므로최적의성능을내는문자변환 그림 5 문자변환결과기준을지정하여야한다. 그러므로본논문은 5.5절에서여러가지문자변환기준을생성하여실험을통해그중최적의성능을보이는기준을선택하였다. 3.3 의미있는멜로디추출한음악은여러개의멜로디로이루어져있다. 멜로디란음악적인표현과인간의감정을가장잘나타내는요소로서다양한음높이와길이정보를담고있는음표와쉼표의결합을의미한다. 이와같이한음악을이루는여러멜로디중그음악을대표할수있는멜로디는큰의미를갖게된다. 본논문에서는의미있는멜로디를 2가지로나누었다. 이들은사용자가자주질의할가능성이높은멜로디로서인덱스를생성하기위해사용된다 의미있는멜로디정의우선첫번째의미를갖는멜로디는한음악에서여러번반복되어나타나는임의의길이를가진멜로디이다. 이는사용자가음악을들었을경우자주반복하여나타난멜로디를기억하기쉽다는가정을토대로하여정의한것이다. 즉, 사용자가원하는음악을검색하기위해서그음악의멜로디들중에쉽게기억할수있는멜로디를흥얼거릴경우가많다는가정하에본논문에서는빈번하게발생한멜로디를의미있는멜로디로지정한다. 두번째의미를갖는멜로디는일정길이이상의쉼표사이에있는멜로디이다. 일정길이이상의긴쉼표는멜로디를나누는경계로볼수있다. 실제음악데이타를분석해본결과멜로디의흐름이긴쉼표를경계로나뉘어진다는것을알수있었다. 대부분의음악에서긴

7 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 289 쉼표는시작부분전, 후렴부분전, 2절이시작되기전등에많이나타난다. 즉, 음악의후렴부분과처음부분을사용자가기억하기쉬울것이라는가정하에쉼표의의미를적용함으로써일정길이이상의쉼표로나누어지는멜로디를의미있는멜로디로지정한다. 이와같은가정은성능평가장에서실제사용자들의허밍질의를대상으로검증하였다 빈번멜로디추출과정한음악에서여러번반복되는멜로디를찾기위해우선마디단위로문자열패턴분석을수행한다. 마디를사용하여빈번멜로디를추출하는이유는마디란동일한박자를가지고있는물리적이고객관적인단위이므로이를기준으로빈번멜로디를추출하면정확하고간결한빈번멜로디를얻을수있기때문이다. 문자열패턴분석을수행하기위해문자열형태인하나의음악을그림 6과같이마디경계인 / 로나눈다. 마디단위로나눈문자열들을문자열패턴매칭알고리즘을통해일치되는문자열들을분석하여마디안의문자열, 마디위치정보 (BarId), 일치되는마디들의개수 (C) 그리고 C를내림차순으로정렬한순위 (R) 를얻는다. 예를들어 그후로오랫동안 이란제목을가진음악을입력하여문자열을마디단위로나눈후마디단위문자열패턴분석을수행하면표 1과같은결과를얻을수있다. 표 1을보면문자열 <j, x, k, j, i, x> 는 18, 22, 35, 39번째마디에서나타났고발생횟수 C는 4임을확인할수있다. 또한이문자열은위의음악에서가장많이발생한것 이므로순위 R은 1이된다. 마디단위문자열패턴분석을모두마친후다음단계로빈번멜로디를생성한다. 알고리즘 1은한음악에서빈번멜로디를생성하는과정을나타낸다. 빈번멜로디생성의첫단계는그룹을생성하는것이다 ( 단계 1). 빈번멜로디생성알고리즘의입력데이타는표 1과같이 4개의속성으로구성된리스트의집합이다. 즉, 마디단위로문자열을저장한리스트, 마디위치를저장한리스트, C를저장한리스트, R을저장한리스트를모두입력받은후 R값이 1인마디의 C값만큼그룹을생성한다. 그리고 C개의 BarId를각그룹의대표마디 (Key Bar) 로선정한다 ( 단계 2). 그림 7은표 1의데이타를이용해그룹을생성한결과이다. 표 1에서 R이 1인마디의 C값은 4이므로그림 7과같이 4개의그룹이생성된다. 그림 7의수직선은하나의음악을의미하고각눈금은하나의마디를의미한다. 또한검은색이칠해져있는눈금은빈번멜로디의시작마디인각그룹의대표마디를의미한다. 그림 7과같이첫번째그룹의대표마디는 18번째마디인 Bar18, 두번째그룹의대표마디는 Bar22, 세번째그룹의대표마디는 Bar35, 마지막으로네번째그룹의대표마디는 Bar39이다. 이들대표마디를기준으로첫번째그룹부터마지막그룹까지양옆의마디중 C값이높은마디를합쳐나가면서빈번멜로디를생성해나간다. 본논문에서는빈번멜로디를생성하기위해 2개의변수가필요하다. 첫번째변수는어떤마디를빈번멜 그림 6 마디단위문자열패턴분석 표 1 음악 그후로오랫동안 의마디단위문자열패턴분석결과 Sequence in Bar Bar Position (BarId) Count (C) Rank (R) <j, x, k, j, i, x> 18, 22, 35, <k, k, j, x, g> 19, <j, x, j, k, k, k> 20, <k, j, j, w, g> 21, <j, x, g, k, E, x, i, x> 17,

8 290 정보과학회논문지 : 데이타베이스제 34 권제 4 호 (2007.8) Input: Output: 알고리즘 1. 빈번멜로디생성알고리즘 마디단위문자열리스트 (Seq_list), 마디위치를저장한리스트 (BarId_list), 일치되는마디개수리스트 (C_list), 순위리스트 (R_list), 마디선택임계값 (BST), 빈번멜로디길이임계값 (FMLT) 문자열형태의빈번멜로디 1; R값이 1인마디의 C값만큼그룹을생성한다. ( 그룹의개수 = C) 2: R값이 1인마디들을각그룹의대표마디 (Key Bar) 로선정한다. 3: 1부터 C까지의각 I에대하여단계 4부터단계 8까지를차례로실행한다. 4: 그룹안의대표마디를 KB라지정한다. 그리고대표마디의양쪽마디들을각각 KB right, KB left 이라지정하고현재마디라부른다. 또한마디합 (BSum) 의초기값을 0으로할당한다. 5: BSum이빈번멜로디길이임계값 FMLT이하이면계속진행하고, 초과하면단계 3으로돌아간다. 6: 현재마디인 KB right 와 KB left 의각 C값과이미정의된 BST값을비교하여 BST값이상의 C값을가진마디를선택한후아래의경우중한가지를수행한다. 그러나두개의 C값이모두 BST값보다작으면단계 3으로돌아간다. - 경우 1 : 현재마디중하나의마디가선택되었다면선택된현재마디의문자열을 KB마디의문자열과합친다. - 경우 2 : 두개의현재마디가모두선택되었다면각 C값을서로비교하여큰값을가진현재마디의문자열을 KB마디의문자열과합친다. - 경우 3 : 두개의현재마디가모두선택되었고그마디들의 C값이같으면두개의현재마디문자열을 KB마디의문자열과합친다. 7: 합쳐진현재마디의 R값과 KB마디의 R값의차를기존의 BSum에더한다. 8: 현재마디중오른쪽마디가합쳐졌다면오른쪽의다음마디인 KB right+1 을현재마디로지정하고왼쪽마디가합쳐졌다면왼쪽의다음마디인 KB left-1 을현재마디로지정한후단계 5로돌아가계속수행한다. 9: 그룹개수만큼의빈번멜로디가생성된후, 겹쳐지거나이웃하는빈번멜로디들이있으면이들을하나고합친다. 그림 7 그룹생성 로디에포함시킬지결정하기위한선택임계값 BST (Bar Selection Threshold) 이다. 만일 BST값이 2라면 C값이 2이상인마디들만사용하여빈번멜로디를생성함을의미한다. 그러나 BST값이작을수록빈번멜로디의길이는길어질수있다는단점이있기때문에두번째변수로서빈번멜로디의길이를결정하는빈번멜로디길이임계값 FMLT(Frequent melody Length Threshold) 을사용한다. 이는빈번멜로디를생성하면서마디가추가될때마다계산되는마디합 (BSum) 의크기를결정해준다. BSum의계산방법은대표마디의 R값과이전에합쳐진마디의 R값의차를계산하여이전까지계산된 BSum에더해가는방식이다. 이때 BSum의상한값을결정하기위해사용하는것이 FMLT 로서 BSum이 FMLT이하일때까지반복하여빈번멜로디를생성해나간다. 그림 8 첫번째그룹에서의멜로디추출초기단계그림 8은 BST값과 FMLT값이각각 2와 6으로주어진상황에서표 1을기반으로각그룹안에서빈번멜로디를생성하는초기단계를그림으로표현한것이다. 우선첫번째그룹을보면대표마디인 KB가 Bar18로지정되어있다. 대표마디의양쪽마디인 Bar17과 Bar19

9 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 291 는각각 KBleft 와 KBright로할당되어진다. Bar17의 C값은 1로서 BST값보다작기때문에조건을만족시키지못하므로무시한다. 다시말해 Bar17은충분히여러번반복되어나타난마디가아니기때문에대표마디인 Bar18과합쳐질수없다. 반면 Bar19의 C값은 2로서 BST값이상이므로 Bar18과합쳐진다. 마디를합쳤다면그다음으로그그룹의 BSum을계산한다. 합쳐진 Bar19의 R값은 2로서대표마디인 Bar18의 R값과의차를구하면 1이된다. 이값을기존의 BSum값에더하여다시 BSum에저장한다. 다음으로 Bar20의 C값을 BST값과비교함으로써위의과정을반복한다. 이때대표마디를기준으로왼쪽방향은 Bar17의 C값이 BST 값이상이되지못하였으므로빈번멜로디를생성하는데무시된다. 오른쪽방향으로마디를증가시켜가며 BSum이 FMLT를넘지않을때까지또는 C값이 BST 값보다작은마디가나타날때까지빈번멜로디를생성하게된다. BSum을계산하기위해마디개수인 C값이아닌순위 R을사용하는이유는다음과같다. 표 2와같은정렬순서를가진두개의음악이있고 BSum을계산하기위해 R값대신 C값을사용한다고가정한후각각빈번멜로디생성알고리즘을적용해보자. 만약 BST값은 2 그리고 FMLT값은 6으로지정해놓는다면음악 1의첫번째그룹은 6번째마디부터 13번째마디까지 8개의마디로이루어진빈번멜로디를생성하게된다. 이는음악 1에서빈번하게발생한마디들을최대한고려하여 BSum이 FMLT를초과하지않을때까지빈번마디를합쳐나감으로써빈번멜로디를생성한것이다. 또한이는순위 R값을사용하여 BSum을계산하여도같은빈번멜로디가생성됨을알수있다. 반면, BSum을계산하기위해 C값을사용하여음악 2에서첫번째그룹의빈번멜로디를생성해보면 4번째마디부터 6번째마디까지 3개의마디로이루어진빈번멜로디를얻을수있다. 그러나 7번째마디또한음악 2에서는빈번하게나타난마디임에도불구하고빈번멜로디로취급되지않 았다. 즉, 빈번하게발생한마디를최대한고려하지못하기때문에부정확한빈번멜로디를생성하게된다. 반면 R값을사용하여빈번멜로디를생성하면 3번째마디부터 10번째마디까지 8개의마디로이루어진빈번멜로디를생성할수있다. 이는음악 2에서빈번하게발생한마디들을최대한고려하여빈번멜로디를생성한결과라할수있다. 이들두음악은각각다른특성을갖는음악이므로각음악에나타난빈번마디의횟수가다를수있다. 음악 1에서가장빈번한마디개수가 3인반면음악 2에서는 6이다. 그러나이들마디개수의순위 R은 1로동일하다. 즉, 각각다른마디개수를가진음악들의빈번멜로디를생성하기위해서는그들의마디개수를객관적인수치로표현하기위해순위를적용하였고, 이값을사용하여 BSum을계산함으로써빈번멜로디를생성해나가는것이다. 모든그룹에서빈번멜로디생성이완료되면각그룹안에는빈번하게발생한마디들로이루어진빈번멜로디가생성되어있을것이다. 하지만그림 9와같이두개의그룹이겹쳐지는상황이발생할수있다. 각그룹안에있는빈번멜로디를각각따로저장한다면중복된데이타가많이발생할것이다. 그러므로이를막기위해겹쳐지는그룹들을하나의그룹으로합침으로써중복된멜로디를하나의멜로디로취급한다. 그림 9는표 1을사용하여빈번멜로디를생성하는마지막단계를보여준다. 첫번째그룹과두번째그룹은상당한부분이중복되어저장되어있다. 이렇듯두개의그룹안에있는데이타가서로중복되거나이웃하면하나의그룹으로합친다. 그림 9의마지막단계를보면첫번째그룹과두번째그룹이하나의그룹으로합쳐진것을볼수있다. 이렇게합쳐진그룹안의멜로디를하나의빈번멜로디로취급한다. 표 1의예제를사용하여빈번멜로디생성을모두마치면그림 10과같이 2개의빈번멜로디를얻을수있다. 빈번멜로디의문자열은다음절에서설명할빈번멜로디인덱스에저장되고사용자가이들멜로디의일부 표 2 두개음악의마디개수와순위비교 Music 1 Music 2 Sequence in Bar BarId C R Sequence in Bar BarId C R c, c, a, d, d 6, 9, a, e, e, s, d 4, 9, 15, 27, 30, c, d, a, a, d 7, c, e, s, a 5, 16, a, d 8, a, g, c, d 6, 10, a, a, c, s 10, e, s, c, c, d, s 3, 7, b, e, h, z 11, c, e, a 8, b, b, k, u 12, c, c, d 13, c, c, a 13, a, d, b, b 29,

10 292 정보과학회논문지 : 데이타베이스제 34 권제 4 호 (2007.8) 그림 11 멜로디를한박자이상의쉼표로나누는과정 그림 9 중복된멜로디처리그림 10 빈번멜로디생성결과분을질의하였다면인덱스를통해빠른시간안에검색이수행될수있다 쉼표단위멜로디추출과정본논문은하나의음악을일정한길이이상의쉼표로나눔으로써생성된각각의멜로디를빈번멜로디와마찬가지로의미있는멜로디로정의한다. 허밍질의처리시스템의구축을위한초기단계에서쉼표의길이정보를추출할때일정길이이상의긴쉼표의위치정보를따로저장해놓았다. 그위치를경계로하여하나의음악을나눔으로써여러개의쉼표단위멜로디를생성한다. 여기서일정길이이상의쉼표란멜로디의연속된흐름이끊어지는부분으로서일정길이를어떤값으로선택하느냐에따라쉼표단위멜로디의길이가달라질수있다. 예를들어한박자즉, 4분쉼표를기준으로멜로디를나눈다면, 한박자이상의길이를갖는쉼표가나타난곳을경계로멜로디를나눈다. 그림 11은짧은멜로디를한박자이상의쉼표로나누어본예제이다. 이때한박자의쉼표는앞음표의특징데이타를생성하는데사용되고, 쉼표의특징데이타는무시되면서단지그위치정보만저장한다. 그리고문자형태로변환한후저장해놓은쉼표위치를경계로멜로디를나눈다. 3.4 인덱스본논문은그림 12와같이서픽스트리구조를갖는 3개의인덱스를생성한다. 여기서서픽스트리를사용하는이유는사용자가트리에저장된멜로디안의임의의부분부터질의하여도검색이가능하도록하기위해서이다. 우선모든음악을문자형태로변환한후음표단위로서픽스트리에저장하는데이를 1차인덱스라부른다. 1차인덱스를생성하는이유는사용자가빈번멜로디부분을질의하지않거나긴쉼표후에시작되는멜로디를질의하지않는다면빈번멜로디인덱스또는쉼표단위인덱스에서검색이수행되지못하고데이타베이스로접근해야하는데이를최소화하기위해서이다. 다음으로 3.3절에서추출한빈번멜로디를음표단위로서픽스트리에저장하는데이를 2차인덱스또는빈번멜로디인덱스라고한다. 이는음표단위로트리에저장함으로써빈번멜로디의부분멜로디를질의하여도검색이가능할수있도록하였다. 마지막으로세번째인덱스인쉼표단위인덱스는어느일정한길이이상의쉼표를경계로하여멜로디를자른후쉼표단위로서픽스트리에저장한것을의미하고이를 3차인덱스라한다. 그림 12에서세번째문자열을보면일정길이이상의긴쉼표인 를경계로멜로디들이나뉘어져있다. 모든인덱스의단말노드에는음악아이디와마디위치, 그리고음표위치를저장해둔다. 이서픽스트리의구성에필요한비용은각인덱스마다저장할멜로디의길이즉, 시퀀스의길이가 m이고알파벳의개수가 Σ일경우트리를생성하는데 O(mlog Σ ) 이소요된다. 또한저장공간은 O(m) 이필요하다. 또한인덱스에저장할멜로디의전체길이가 m이고 n 길이의멜로디를삽입, 삭제할때유지비용은각각 O(nlog(n+m)), O(nlogm) 이소요된다.

11 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 293 그림 12 인덱스생성 4. 질의처리이절에서는사용자의허밍질의를처리하는과정에대해설명한다. 질의처리는크게두단계로나뉘어진다. 첫번째단계는질의전처리단계로서입력된질의를데이타베이스와인덱스에저장된데이타형태와같도록변경해준다. 다음으로두번째단계는검색단계로서원하는음악이검색될때까지미리생성한인덱스를차례로검색해나간다. 그림 13은질의처리과정을보여준다. 우선데이타베이스검색의첫번째단계인질의전처리과정에대해서설명한다. 입력데이타인질의는사용자가직접마이크를통해흥얼거린허밍이다. 이는데이타베이스를생성할때음악데이타의입력형태인미디와다른웨이브 (Wave) 형태를지니고있다. 그러므로웨이브형태의음악에서미디형태와같이음의높이와길이그리고쉼표의길이를추출해야한다. 추출한이정보를통해데이타베이스에저장된형태와마찬가지로특징데이타를계산한다. 즉, 높이의변화량과길이의변화율을계산하는것이다. 다음으로인덱스를검색하기 그림 13 질의처리과정

12 294 정보과학회논문지 : 데이타베이스제 34 권제 4 호 (2007.8) 표 3 단계별검색방법단계검색방법 1단계검색 2차인덱스와 3차인덱스병렬검색 2단계검색 1차인덱스검색 3단계검색특징데이타베이스검색위해특징데이타를문자형태로변환한다. 이는인덱스에입력된문자열들과같은문자변환기준을사용하여야한다. 이러한질의전처리과정이끝나면다음으로검색을진행한다. 검색단계는표 3과같이 3단계로나누어진다. 우선질의전처리의마지막단계에서문자열형태로만든질의를입력하여빈번멜로디인덱스인 2차인덱스와쉼표단위멜로디인 3차인덱스를병행하여검색하는 1단계검색이있다. 이는사용자가빈번멜로디를흥얼거렸거나일정길이이상의쉼표다음에시작하는멜로디를흥얼거렸다면이단계에서검색이완료되어사용자에게가장빠른시간내에결과를전달할수있다. 이때비교방법으로문자열의정확매칭 (String Exact Matching) 알고리즘을사용한다. 이단계에서사용자가원하는검색결과를얻었다면검색을종료시킨다. 그러나 1 단계에서검색이완료되지못하고검색결과를얻지못할경우 2단계검색으로들어간다. 2단계검색의목적은모든음악을저장한인덱스를사용함으로써사용자가빈번멜로디또는쉼표다음에시작하는멜로디를질의하지않았을경우에검색이완료될수있도록하려는것이다. 이러한검색 2단계에서사용자가원하는음악을검색하였다면사용자는원하는음악을전달받고검색을종료시키면된다. 하지만 2단계검색에서도검색이완료되지못할경우특징데이타베이스를접근하는 3단계검색을통해검색을수행한다. 이때비교방법으로유클리디안거리함수를사용하여가까운거리의음악을얻어낸다. 본논문이제안하는시스템은 2단계검색과 3 단계검색을최소화하고 1단계검색에서정확한검색결과를얻어낼수있기때문에검색속도가상대적으로우수하다. 5. 성능평가본장에서는제안하는허밍질의처리시스템의효율성과정확도등의실험결과를기술한다. 5.1절에서는데이타및질의생성방법등을설명하고 5.2절에서는실제사용자의질의를입력받아사용자들이한음악에서어떤부분을자주질의하는지분석하였다. 5.3 절에서는빈번멜로디를생성하기위해필요한두가지변수인 BST와 FMLT 중 BST값을변화시켜가며검색시간과정확도를분석하여가장최적의 BST값을 결정하였고 5.4절에서는 FMLT값을변화시켜가며성능을분석하여최적의 FMLT값을결정하였다. 또한 5.5절에는문자변환기준인 2차원공간의범위를변화시켜가며정확도분석을통해가장적절한기준을결정하였다. 5.6절에서는데이타베이스의크기와질의의길이에따른검색속도를검증하였고 5.7절에는질의의부정확한정도에따른검색결과의정확도를검증하였다. 5.1 데이타및질의생성방법본논문은실험에사용할데이타로서데이타베이스와인덱스에저장하기위한미디형식의음악과검색을위한웨이브형식의허밍질의가필요하다. 우선데이타베이스와인덱스에저장할음악데이타로서한국가요 3000곡을수집한후이들의특징데이타를추출하여특징데이타베이스를구축하였고이들을문자형태로변환하여 3개의인덱스를생성하였다. 또한성능평가를위해사용할질의는표 4, 5와같이생성하였다. 우선표 4는사용자질의와실제멜로디사이의거리를증가시켜가며각 30개씩생성한것이다. 예를들어실제멜로디와의거리가 2인질의란사용자가입력한허밍질의와실제멜로디와의특징데이타를사용하여유클리디안거리를계산한결과값이 2인경우를의미한다. 표 5는질의시간을 5초단위로증가시켜가며길이가다른여러종류의질의들을생성한것이다. 그리고각질의시간당 30번씩질의를함으로써질의시간동안발생한음표수를평균화하였다. 표 4 실제멜로디와의거리정도에따른질의 Type of Query (The distance of between query and target melody) count 표 5 허밍질의시간에대응되는평균음표수 Query time (sec.) Average value of the number of notes Count

13 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 사용자질의패턴분석본절에서는실제사용자에게직접허밍을부르게하여사용자가한음악의어떤부분을자주질의하는지분석해보았다. 본실험에서사용한음악수는현재데이타베이스에저장된 3000곡이고참여한사용자수는 30명이며총질의수는중복을허락하여약 700곡이다. 본실험은각음악마다음악의시작부분, 빈번멜로디부분, 한박자이상의쉼표후에시작되는멜로디부분그리고그외의부분으로나누어그림 14와같이해당하는부분의질의횟수를그래프로표현해보았다. 그림 14 사용자질의패턴그림 14에서사용자는전체질의중빈번멜로디부분을약 76% 정도질의하였음을알수있다. 이는사용자가빈번멜로디를가장자주질의한다는가정을뒷받침해주는증거가된다. 그리고시작멜로디와긴쉼표이후에나타나는멜로디또한많은수가질의되었음을알수있다. 음악의시작멜로디를질의한경우는전체음악의약 40% 를차지하고시작멜로디를질의한경우의 35% 가빈번멜로디와일치한다. 또한일정길이이상의쉼표후에시작되는멜로디를질의한경우는전체음악의약 38% 를차지하고이들질의의약 49% 가빈번멜로디와일치한다. 반면그외나머지부분의멜로디는전체질의중약 6% 만이질의되었다. 5.3 최적의 BST 값결정빈번멜로디를생성하기위해서필요한 2가지변수인 BST와 FMLT는빈번멜로디의길이를결정하는데큰역할을한다. 본절에서는두개의변수중마디선택임계값인 BST의값을변화시켜가며빈번멜로디의크기와검색시간그리고정확도를분석하여가장최적의성능을보여주는값을결정하였다. 그림 15는 BST값을 1부터 4까지 1씩증가해가며빈번멜로디인덱스에저장된문자수를비교한것이다. 이때특징데이타베이스에저장된음악의수는 3000곡으로지정하였고질의는 15초의길이를갖는빈번멜로디부분으로표 4과같이실제멜로디와의거리당 30개씩생성하였다. 또한 FMLT값은 15초인질의의길이보다긴빈번멜로디를만들어낼수있는값으로검증된 6으로지정하였다. 이에대한검증은 5.4절에서보여줄것이다. 빈번멜로디의크기를분석해본결과 BST값이 1인경우다른값들에비해빈번멜로디인덱스크기가가장크다는것을확인할수있었다. 즉, 상대적으로길이가긴빈번멜로디가생성된다는의미이다. 이는한음악에서 1번이상발생한마디들로이루어진빈번멜로디가생성되었기때문이다. 반면 BST값이커질수록빈번멜로디의인덱스크기가감소함을확인할수있었다. 이는대부분의음악에서짧은길이의빈번멜로디가생성될뿐만아니라빈번멜로디가생성되지못하는음악들도발생하기때문이다. 예를들어 BST값이 3인경우입력된 3000곡의음악중에빈번멜로디를생성하지못하는음악이 332곡이고, 4인경우는 1369곡임을확인할수있었다. 이는 C의값이 3이상인마디를포함하지않는음악이 332곡이고 4이상인마디를포함하지않는음악이 1369곡이라는의미이다. 또한 3 또는 4이상의마디를가지고있는음악이라도그마디의개수가작기때문에길이가짧은빈번멜로디가생성되는것이다. 그림 16은 BST의값에따라빈번멜로디인덱스의검색시간을비교해본것이다. 이때입력된음악수를 그림 15 BST 의값에따른빈번멜로디인덱스크기 그림 16 BST의값에따른빈번멜로디인덱스의검색시간

14 296 정보과학회논문지 : 데이타베이스제 34 권제 4 호 (2007.8) 그림 17 BST 값에따른재현율비교 그림 18 BST 값에따른정밀도비교 500곡에서 3000곡까지 500곡단위로늘려가며실험하였다. 그결과입력된음악수에상관없이 BST의값이작을수록검색시간이느려짐을확인할수있다. 이는 BST값이작을수록빈번멜로디인덱스의크기가증가하기때문이다. 다음으로 BST값에따른정확도를측정하여성능을분석해본결과그림 17, 18과같은결과를얻었다. 두그래프를보면재현율과정밀도는 BST의값이작을수록높게측정됨을확인할수있다. 그리고 BST값이 1과 2인경우의재현율과정밀도는비슷한수치를보였지만 3과 4인경우는그수치가상당히떨어짐을보여준다. 이러한결과에대한이유는 2가지로나누어볼수있다. 첫번째이유는 BST가 3과 4일때에생성된빈번멜로디의길이가질의의길이보다짧은경우가많이발생하기때문이다. 본실험은질의의길이를 15초로고정시켰는데이에해당하는평균문자수는표 5과같이 20개이고 BST의값에따라생성되는하나의빈번멜로디평균문자수는표 6과같다. 즉, BST값이 3과 4일때생성되는대부분의빈번멜로디의길이가질의의길이보다짧기때문에검색결과를얻지못하는경우가발생한다. 두번째이유는 BST값이커질수록빈번하게반복된마디들을포함하지못하여부정확한빈번멜로디가생성되기때문이다. 예를들어 BST값이 4인경우빈번마디값이 4이상인마디들로만이루어진빈번멜로디가생성되는데이는사용자가한음악에서 3번반복된부분을질의하였다면검색결과를얻지못하게된다. 위의실험들을통해최적의성능을보이는 BST값은 2임을확인할수있었다. 그이유는 BST값이 2인경우가 3과 4인경우보다빈번멜로디인덱스의크기가크 고검색시간이느리지만정확도측면에서향상된성능을보였고 BST값이 1인경우보다검색시간이빠르고인덱스크기가작기때문이다. 5.3 최적의 FMLT 값결정본절에서는빈번멜로디길이의임계값인 FMLT를변경해가며빈번멜로디인덱스크기와검색시간, 그리고정확도를분석하여최적의 FMLT값을결정한다. FMLT는빈번멜로디의길이를결정하기위해마디의순위 (R) 를사용하여계산된 BSum의임계값을의미한다. 그러므로 FMLT값에따라빈번멜로디의길이와빈번멜로디인덱스의크기가달라진다. 본실험은 5.3 절과마찬가지로 3000곡의음악을사용하였고질의는 15초의길이를갖는빈번멜로디부분을입력하였다. 그리고빈번멜로디인덱스를생성하기위한또다른변수 BST는 2값을사용하였다. 그림 19는 FMLT를 2부터 10까지 2단위로증가시켜가며빈번멜로디인덱스를생성한후그크기를분석한그래프이다. 또한그림 20은 FMLT값에따른검색시간을비교한그래프이다. 이는 FMLT값이증가할수록빈번멜로디의길이가길어지기때문에인덱스크기가점점커지고이로인하여검색시간이증가하는것이다. 다음으로 FMLT값마다질의의부정확한정도에따른정확도를분석하였다. 그림 21과 22는각각재현율과정밀도를분석한그래프이다. 두개의그래프는 FMLT 값이증가할수록정확도가높게나타나고이에따른각 표 6 BST 값에따른하나의빈번멜로디의평균길이 BST 빈번멜로디의평균길이 ( 문자수 ) 그림 19 FMLT 값에따른빈번멜로디인덱스크기

15 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 297 표 7 FMLT값에따른하나의빈번멜로디의평균길이 FMLT 빈번멜로디의평균길이 ( 문자수 ) 그림 20 FMLT의값에따른빈번멜로디인덱스의검색시간그림 21 FMLT값에따른재현율비교그림 22 FMLT값에따른정밀도비교정확도는질의의부정확한정도가증가할수록그수치가감소함을보여준다. 이는 FMLT값이작을수록빈번멜로디의길이가짧아지므로 15초의질의를입력하였을경우검색되지못하는경우가증가하기때문이다. 표 7 은각 FMLT값에따라생성되는빈번멜로디의평균문자수를보여준다. FMLT값이 2와 4일경우에생성되는빈번멜로디의평균길이는질의의길이보다짧음을확인하였다. 그리고 FMLT값이 6, 8, 10인경우는비슷한정확도를보였다. 이는질의를포함한신뢰성높은빈번멜로디가생성되었기때문에만족스런검색결과를얻게된것이다. 위의실험을통해가장최적의성능을보여주는 FMLT 의값은 6임을확인할수있었다. 이는높은정확도를 보여준값인 6, 8, 10중에가장검색속도가빠르고인덱스의크기가작기때문이다. 그리고고정된질의의길이보다긴빈번멜로디를생성하여야좋은성능을보여줌을확인할수있었다. 그러므로이는질의의길이에따라적절한 FMLT값을사용하여야함을알려준다. 또한적절한 BST값과 FMLT값을사용하여야신뢰성있는빈번멜로디가생성된다는것을증명해준다. 5.5 정확도분석을통한적절한문자변환기준결정본절에서는 2차원공간의범위를변경해가며정확도를분석해봄으로써가장정확도가높은최적의기준을결정한다. 본실험에서는그림 23과같이 4가지형태의문자변환기준을각각적용하여정확도를분석해보았다. 이때사용되어진질의는표 4와같이질의의부정확한정도를변화시켜가며생성한멜로디들이다. 본실험은원하는음악한곡을찾으면검색을종료한다. 실험에앞서파라메타인 FMLT값은 6으로, BST값은 2로지정하여허밍질의처리시스템을구축해둔다. 또한 3000 곡이저장되어있는특징데이타베이스를사용하였고허밍질의의길이를 15초로고정시켜놓았다. 그림 24와 25는실제멜로디와의거리당 30개의질의를입력하여얻어낸정확도이다. 그림 24는 4가지의문자변환기준을적용한결과의재현율을비교분석한그래프이다. 그림과같이재현율은모든범위에서질의가부정확할수록그값이감소되어짐을알수있다. 그러나네개의범위중 Range 4 가재현율이가장높게나타남을확인할수있는데이는하나의문자열로할당되는구간의크기가다른범위보다크기때문에부정확한질의라도실제멜로디와같은문자열로변환됨으로써원하는음악이검색되어지는경우가많이발생하기때문이다. 반면 Range 1은가장재현율이낮게나타났는데이는하나의문자열로할당되는구간의크기가다른범위에비해상대적으로작기때문에사용자가허밍을부정확하게부를수록사용자가찾고자하는음악과다른문자열로변환되는경우가많이발생하므로원하는음악이검색되어지는경우가줄어들게된다. 다음으로그림 25는질의의부정확한정도를증가시키며 4가지종류의문자변환기준을적용한결과의정밀도를측정하였다. 이때질의가부정확할수록모든문자변환기준에서정밀도가감소되어지는것

16 298 정보과학회논문지 : 데이타베이스제 34 권제 4 호 (2007.8) 그림 23 문자변환기준범위종류 그림 24 문자변환기준에따른재현율 그림 25 문자변환기준에따른정밀도 을확인할수있었다. 이는질의의부정확한정도가커질수록원하지않은음악들의검색횟수가증가하기때문이다. 특히문자변환기준의 2차원공간상의범위가가장큰 Range 4의경사가가장급함을알수있다. 이는다른범위보다질의가부정확할수록원하지않는음악들이더많이검색됨을알려준다. 위의실험을통해정밀도와재현율모두가상대적으로가장최적의값을나타낸경우가 Range 3임을발견할수있었다. 5.6 검색시간비교본절에서는특징데이타베이스에저장된음악수를증가시키면서검색시간을비교한다. 또한질의의길이를증가시키며같은방법으로검색시간을비교한다. 비교대상과그에해당하는표현법은표 8과같이정하였다. 우선첫번째검색방법은오직특징데이타베이스만을순차적으로검색하는검색방법이다. 이는유클리디안거리함수를사용하여음악의처음부터원하는음악이검색될때까지거리계산을수행한다. 두번째검색 표 8 비교대상검색방법종류와표현법 Compared search method Expression 1. 특징데이타베이스검색 Naïve DB scan 2. 1차인덱스검색추가 2 step search method 3. 2 차인덱스와 3 차인덱스병렬검색추가 Our search method (3 step search method) 4. N-gram N-gram 방법으로모든음악을문자형태로변환하여저장한 1 차인덱스를추가한검색방법이다. 이검색방법은 1차인덱스를검색한후검색이성공하지못하면특징데이타베이스를접근하는방식이다. 이는사용자가빈번멜로디또는긴쉼표후에나오는멜로디질의에전혀상관없이검색을수행한다. 세번째검색방법으로는본논문이제안하는방법으로빈번멜로디인덱스인 2차인덱스와쉼표단위인덱스인 3차인덱스를추가한검색방법이다. 마지막으로비교할검색방법으로는 N- gram방법이다.

17 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 299 그림 26 데이타베이스크기와비교시스템별인덱스크기그림 26은특징데이타베이스에저장한음악의수에따라생성되는인덱스의크기를비교한그래프이다. 이는본논문이제안하는시스템의각인덱스크기를하나의막대로표현하였고 N-gram의인덱스크기를다른막대로표현하였다. 본논문이생성한 3개의인덱스의전체크기는 N-gram의크기보다약 2.5배크지만검색속도의향상을위하여인덱스의크기증가에대한비용을감수하였다. 다음으로그림 26은특징데이타베이스에저장된음악수에따른검색시간을비교한그래프이다. 데이타베이스크기는 500곡을시작으로 3000곡까지 500곡단위로증가시켰다. 이때사용한질의의개수는 30개이고각질의의길이는 15초로고정시켜놓았다. 또한각질의의부정확한정도는 4로지정하였다. 분자변환기준은 Range 3을사용하였고기본면수인 FMLT와 BST는각각 6과 2로지정하여검색을수행하였다. 그림 28은질의의길이를증가시켜가며검색시간을비교한그래프이다. 5초동안흥얼거렸을경우를시작으로 30초까지 5초단위로증가시켰다. 이때사용한데이타베이스크기는 3000곡으로고정시켜놓았고문자변환기준과변수값은위와동일하다. 그림 27에서데이타베이스길이가증가할수록본논문이제안하는검색방법의검색속도 가다른검색방법보다상대적으로향상됨을알수있다. 이는 1차검색단계에서검색이완료되는경우가많이발생하기때문이다. 반면 N-gram 검색방법이본논문의검색방법보다약 2배가량느림을알수있었다. 그이유는 N-gram의인덱스크기가본논문이제안하는 2차인덱스와 3차인덱스크기보다크기때문이고 1 차인덱스보다는크기가작지만서픽스트리를사용하는본논문의검색방법과달리순차적으로문자열을비교해가면일치되는문자열을찾아야하는검색방법을사용하기때문이다. 마지막으로데이타베이스를순차적으로검색한방법은검색속도가가장느림을보여준다. 이는데이타베이스에저장된모든음악의음표들의특징데이타를통해유클리디안거리함수를사용하여검색하는방법으로많은계산량을필요로하기때문이다. 만약하나의음악에 m개의음표가있다면한음표는높이변화량과길이변화율이라는두개의정보를가지고있으므로 2m개의숫자형태의특징데이타가생성된다. 그리고질의의음표개수가 n개라면이도마찬가지로 2n개의숫자형태의특징데이타가생성된다. 이들은서로의거리를계산하기위해음표단위로질의를이동시켜가면 (m-n+1)*2n개의계산량이필요하게된다. 다음으로그림 28은질의의길이를증가시켜가며검색시간을측정해보았다. 이때도위의실험과비슷한형태의검색결과를얻을수있었다. 5.7 정확도비교본절에서는사용자질의의부정확한정도에따른정확도를 4개의검색방법에적용하여비교해보았다. 그림 29는재현율을그림 30은정밀도를그래프로표현하였다. 이때데이타베이스에는 3000곡을저장하였고질의의길이는 15초를기준으로하였다. 또한위의실험들과마찬가지로문자변환기준은 Range 3을사용하였고기본파라메타인 FMLT와 BST는각각 6과 2로지정하여검색을수행하였다. 본실험은각질의의부정확한정도마다데이타베이스에서원하는음악이모두검색되도록하였다. 방법은질 그림 27 데이타베이스크기에따른검색시간 그림 28 질의길이에따른검색시간

18 300 정보과학회논문지 : 데이타베이스제 34 권제 4 호 (2007.8) 그림 29 질의의부정확한정도에따른재현율 그림 30 질의의부정확한정도에따른정밀도 의의부정확한정도가 2일때실제멜로디와의거리가 2 인 30개의서로다른종류의질의를입력하여검색하였다. 이와같은방법을사용한이유는만약질의와의거리차이가 2인모든음악을검색하도록하였을때원하는음악이검색되도록하였다면이때인덱스를사용한검색방법인두번째검색방법과세번째검색방법그리고타검색방법인 N-gram을이용한검색방법의정확도는상대적으로어떠한결과가나오는지를비교한것이다. 그러므로질의의부정확한정도가늘려가면서매번위와같은실험을통해서로의상대적인정확도를비교하였다. 두개의그래프에서중점적으로보아야할점은본논문이제안하는방법이기존 N-gram 방법보다질의가부정확할수록원하는음악이검색되어지는경우가많은반면원하지않는음악이보다적게된다는점이다. 5.8 장르별성능분석본절에서는음악데이타를장르별로나뉘어검색시간과정확도를분석하였다. 본실험에서사용한장르는 3가지로재즈, 락, 클래식이며이들을사용한이유는각리듬의특징이다른어떤장르보다잘구분되기때문이다. 본실험을위해각장르별로최적의성능을보여주는파라미터값을정하였다. 이때데이타베이스에저장할음악수는장르별로각각 225곡을사용하였고, 질의는표 9와같이생성하였고모든질의의길이는 5초로고정하였다. 각장르별로데이타베이스의크기가증가함에따른검색시간과질의의부정확한정도가변함에따른정확도를분석한결과표 10과같이 3개의최적의파라미터값이결정되었다. 재즈와락은장르를구분하지않은음악셋을입력한실험과같은파라미터값이요구되지만클래식은 BST값이 3, 문자변환기준이 Range 2로써약간의차이를보였다. 우선클래식의 BST값이다른장르보다높게나타난이유는클래식마디의반복횟수가평균적으로다른장르인재즈와락에비해높기때문이다. 이는클래식이다른장르에비해음악의길이가길기때문인이유도있다. 다음으로클래식의문자변환기준이 Range 2로나타난이유는그림 31과같이 표 9 실제멜로디와의거리정도에따른질의 Type of Query (The distance of between query and The number target melody) 표 10 장르별최적의파라미터값 장르 Parameter BST FMLT 문자변환범위 Jazz 2 6 Range 3 Rock 2 6 Range 3 Classical 3 6 Range 2 음의높이변화량의절대값과길이변화율의절대값이작은경우가다른장르에비해많이나타나기때문이다, 그러므로이들을같은문자로변화되는경우를줄이기위하여 Range 3보다벡터영역이좀더세밀하게나눠진 Range 2일경우좀더높은정확도를보이며 Range 1보다허밍의부정확한정도가커질수록정확도가덜감소한다. 위와같은파라미터값을입력하여장르별검색시간과정확도를측정하였다. 그림 32는데이타베이스크기를 50곡씩증가시켜가며측정한검색시간을보여준다. 이그림을통해세개의장르모두비슷한검색속도를보여줌을알수있다. 다음으로그림 33과 34는정확도를보여주고있다. 이또한비슷한성능을보여줌을그래프를통해확인할수있다. 이와같이세개의장르는각다른특성의리듬을가지고있지만이에맞는적절한파라미터값을시스템에적용해주면어떤장르든간에비슷한성능을보여줌을알수있다. 그러므로검색시음악의장르를미리파악하고그에맞는적절한파라미터를적용하면좀더향상된성능을가진시스템이구축될것이다.

19 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 301 그림 31 장르별특징데이타발생비율 (a) 재즈, (b) 락, (c) 클래식 그림 32 장르별데이타베이스크기에따른검색시간 그림 33 질의의부정확한정도에따른장르별재현율 그림 34 질의의부정확한정도에따른장르별정밀도 6. 결론및향후연구본논문은방대한양의음악데이타베이스에서사용자가원하는음악을빠르게검색하기위하여내용기반검색방법을기반으로하였다. 즉, 사용자가음악을대표하는키워드가아닌멜로디를질의하여유사한멜로디를갖는음악을데이타베이스에서검색해주는검색방법을적용한것이다. 이때멜로디를표현하는특징데이타로는음표의높이의변화량과길이의변화율인 2차원벡터로서이들을특징데이타베이스에저장하였고, 질의와의유사성은유클리디안거리함수를사용하여 비교하였다. 그러나이러한방법은특징데이타베이스에저장된모든음악을순차적으로비교해야하므로많은계산비용과검색시간이필요하다. 그러므로이러한비효율적인검색방법을보완하기위해효과적인인덱스를설계하였다. 본논문은사용자가자주질의할가능성이높은멜로디를의미있는멜로디로취급하여이들을인덱싱하는방법을제안하였다. 이때의미있는멜로디를두가지로나누어취급하였다. 첫번째의미있는멜로디란빈번멜로디로서이는한음악에서빈번하게나타나는멜로디를사용자가자주질의한다는점을기반으로선정하였다. 본논문은빈번멜로디추출알고리즘을제안하여신뢰성이높은빈번멜로디를추출하였다. 두번째의미있는멜로디란일정한길이이상의쉼표후에시작되는쉼표단위멜로디로써이는대체적으로음악의시작부분, 간주가끝나고다음절이시작되는부분, 그리고후렴의시작부분등에나타난다. 이러한멜로디는사용자가자주질의한다는가정하에접근하였고이가정을실험을통해검증하였다. 이와같은의미있는멜로디를인덱싱하여이들을먼저검색함으로써사용자가원하는음악을신속히알려주도록하는시스템을구축하였다. 본논문은인덱스에저장된의미있는멜로디의형태를기존의숫자형태의 2차원벡터가아닌문자열형태

20 302 정보과학회논문지 : 데이타베이스제 34 권제 4 호 (2007.8) 로변환하여검색속도를줄이고자하였다. 또한문자형태로변환하면서멜로디의정보손실을최소화하고검색결과의정확도를높이기위해 2차원벡터공간을하나의문자로치환하는방법을사용하였다. 이는허밍이가지고있는에러를허용하는방법으로서사용자가부정확한음악을입력하여도원하는음악이검색되어질수있도록하였다. 본논문은 3단계검색방법을사용하였다. 우선 1단계검색은빈번멜로디인덱스와쉼표단위인덱스를병행하여검색을수행하는방법으로서이때검색결과를얻지못했을경우 2단계검색으로들어간다. 2단계검색은모든음악을음표단위로저장한인덱스로서마찬가지로이때에도검색결과를얻지못했을경우에특징데이타베이스를순차적으로검색하는 3단계검색으로들어간다. 이와같은 3단계검색방법은 1차검색단계를통해원하는음악을찾는것이목표이다. 본논문은의미있는멜로디인덱싱방법과에러를허용하는문자변환방법그리고 3단계검색방법을사용함으로써기존의방법보다데이타베이스의접근을최소화하였을뿐만아니라검색시간이줄었고정확도가향상되어상당한성능향상을가져왔다. 본논문의공헌은다음과같다. 첫째, 사용자가자주질의하는멜로디를의미있는멜로디로취급하였고이들을추출하여인덱싱함으로써기존이검색방법보다검색이빠르게수행되도록하였다. 둘째, 사용자가허밍이많은부정확한멜로디라는특징을반영하여부정확한정도가커져도정확도가보장될수있는문자변환방법을적용하였다. 마지막으로데이타베이스의접근을최소화하는 3단계검색방법을사용하였다. 또한실험을통하여이들을검증하였다. 향후연구로는기존의사용한인덱스구조의문제점을분석하고이를보완하여검색성능향상을가져오는효과적인인덱스를생성하려한다. 또한 3개의인덱스를생성함으로써방대해진인덱스의크기를줄일수있는방안을강구하려한다. 참고문헌 [1] A. Uitdenbogard, J. Zobel, "Melodic Matching techniques for Large Music Databases," In Proc. ACM Multimedia, pp , [2] P. Rolland, G. Raskinis, and J. Ganascia, "Musical Content-Based Retrieval: An Overview of the Melodiscov Approach and System," In Proc. ACM Multimedia, pp , [3] A. Ghias, J. Logan, and D. Chamberlin, "Query By Humming," In Proc. ACM Multimedia, pp , [4] S. Pauws, "CubyHum: A Fully Operational Query by Humming System," In Proc. 3rd International Symposium on Music Information Retrieval (ISMIR), pp , [5] S. Doraisamy, S. Ruger, "Robust polyphonic music retrieval with n-grams," Journal of Intelligent Information Systems, 21:1, pp , [6] R. L. Kline, E. P. Glinert, "Approximate matching algorithms for music information retrieval using vocal input," In Proc. ACM Multimedia, pp , [7] R. B. Dannenberg, W. P. Birmingham, G. Tzanetakis, C. Meek, N. Hu, and B. Pardo, "The Musart Testbed or Query-By-Humming Evaluation," In Proc. 4th International Symposium on Music Information Retrieval (ISMIR), pp , [8] N. Kosugi, Y. Nishihara, T. Sakata, M. Yamamuro, and K. Kushima, "A Practical Query-By- Humming System for a Large Music Database," In Proc. ACM Multimedia, pp , [9] E. Scheirer, "Tempo and Beat Analysis of Acoustic Musical Signals," Acoustic Society of America, 103:1 January, pp , [10] A. Pienimaki, "Indexing Music Databases Using Automatic Extraction of Frequent Phrases," In Proc. 3rd International Symposium on Music Information Retrieval (ISMIR), pp , [11] J. Downie. "Evaluating a Simple Approach to Music Information Retrieval: Conceiving Melodic N-Grams as Text," Thesis, University of Western Ontario, [12] J. Reiss, J. Aucouturier and M. Sandler, "Efficient multidimensional searching routines for music information retrieval," In Proc. 2nd International Symposium on Music Information Retrieval (ISMIR), pp , [13] K. Ioannis, N. Alexandros, Apostolos N. Papadopoulos, M. Yannis, "Audio Indexing for Efficient Music Information Retrieval," International Multimedia Modelling Conference, pp , [14] K. Andreas, "Themefinder: A Web-based Melodic Search Tool, Melodic Similarity: Concepts, Procedures and Applications," Computing in Musicology, pp , [15] C. Liu, J. Hsu and A. L. P. Chen, "Efficient Theme and Non-trivial Repeating Pattern Discovering in Music Databases," In Proc. 15th International Conference on Data Engineering (ICDE '99), pp , [16] 노승민, 박동문, 황인준, 사용자질의패턴을이용한효율적인오디오색인기법, 한국정보과학회논문지, 제 31 권, 제 1 호, pp , [17] R. B. Dannenberg, N. Hu, "Understanding Search Performance in Query-by-humming Systems," In ISMIR, 2004.

21 허밍질의처리시스템의성능향상을위한효율적인빈번멜로디인덱싱방법 303 유진희 2004 년 8 월한성대학교정보시스템공학과졸업 ( 학사 ) 년 3 월 ~ 현재연세대학교컴퓨터과학과석사과정. 관심분야는멀티미디어데이타베이스, 데이타마이닝 박상현정보과학회논문지 : 데이타베이스제 34 권제 1 호참조