Helsinki, November 21st,2000

String Matching Techniques for Music Retrieval

This thesis examines new methods with which to retrieve music from digital, symbolically coded databases, on the basis of its contents. For long now, communications companies and music producers have stored music in large digital databases for easier handling and to save storing space. In addition, there are thousands of music files on the Internet available to the general public. Until recently, retrieval from these databases has been based on key words that have been attached to the music documents, such as the name or text of the document. However, such methods as retrieval based on the contents of image databases have been available for years.

The possibility of music document retrieval based on their contents is essential, since attaching key words to documents takes an inordinately long time, and since it is impossible to create a complete and perfect list of key words for even the smallest database. In addition, it is natural to search multimedia documents based on their content; giving the search key for music, for example, by humming, playing an instrument, or with notation symbols. With the standards, methods and devices already developed and under development, it might be possible, in the near future, to select a song from the jukebox in a bar by humming a short excerpt of it into your own mobile phone.

The methods and their implementations presented in this thesis are based on general string algorithms, which were originally designed for comparing similarities in text strings, and for finding a text patterns in long text documents. This is why the music to be processed must be symbolically coded. This kind of encoding is used in traditional Western notation, for example, and in music files using MIDI encoding. This thesis will especially concentrate on the problems of searches where the pitches of the notes and the difference between them, i.e. the intervals, are taken into account in the search pattern and in the database documents. One important feature in this kind of searches is the so-called transposition invariance, which entails that the given search pattern must be found in the database, whatever its pitch.

The thesis presents new practical methods and theoretic search models, as well as evaluates the complexity of earlier distance specification results, on which the new models are based. The methods presented in the thesis use the so-called bit parallell algorithm technique. Bit-parallell algorithms are considerably faster than traditional methods. In addition, they need far less space than the methods based on indexing, which are faster, but demand at least ten times the space that the database to be indexed needs. One of the central results presented in the thesis is a new bit-parallell transposition invariant algorithm, with which to find monophonic search patterns in databases with polyphonic music documents.

The new methods presented in the thesis have been implemented as the prototype SEMEX (Search Engine for Melodic EXcerpts), which can retrieve occurences of the transposition invariants of monophonic search patterns quickly in large mono- and polyphonic music databses.

Helsinki, 21.11.2000

Merkkijonoalgoritmit musiikin haussa

Tämä väitöskirja käsittelee uusia menetelmiä, joiden avulla musiikkia voidaan hakea sen sisällön perusteella digitaalisista, symbolisesti koodatuista tietokannoista. Viestintäyhtiöt ja musiikintuottajat ovat jo pitkään arkistoineet musiikkia suuriin, digitaalisessa muodossa oleviin tietokantoihin käsittelyn helpottamiseksi ja arkistointitilan säästämiseksi. Lisäksi Internetissä on tuhansittain musiikkitiedostoja kaikkien ulottuvilla. Aina viime vuosiin saakka haut tällaisista tietokannoista ovat perustuneet musiikkidokumentteihin liitettyihin avainsanoihin, esimerkiksi haetun dokumentin nimeen tai sen sanoitukseen, vaikka esimerkiksi kuvatietokantojen sisältöön perustuvia hakumenetelmiä on ollut käytettävissä jo useita vuosia.

Mahdollisuus hakea multimediadokumentteja sisällön perusteella on tärkeää, koska avainsanojen liittäminen dokumentteihin vie kohtuuttomasti aikaa, ja koska täydellisen ja tyhjentävän avainsanaluettelon laatiminen on pienellekin tietokannalle mahdotonta. Lisäksi on luonnollista etsiä multimediadokumentteja niiden omassa muodossa, esimerksi musiikkia antamalla hakuavain hyräilemällä, soittamalla jotakin instrumenttia tai nuottisymboleina. Jo kehitettyjen ja parhaillaan kehitteillä olevien standardien, menetelmien ja laitteiden avulla saattaa lähitulevaisuudessa olla mahdollista esimerkiksi, että baarissa asiakas voi pyytää levyautomaattia soittamaan haluttu musiikkikappale hyräilemällä pätkän kappaleen melodiaa omaan matkapuhelimeensa.

Tässä väitöskirjassa esitettävät ja sovellettavat menetelmät perustuvat yleisiin merkkijonoalgoritmeihin, jotka on alunperin suunniteltu tekstimuotoisten merkkijonojen samankaltaisuuden vertailuun ja tekstihahmon etsimiseksi pitkästä tekstidokumentista. Siksi käsiteltävän musiikin pitää olla symbolisesti koodattua. Tällaista koodausta käytetään esimerkiksi perinteisessä länsimaisessa nuottikirjoituksessa ja MIDI-muotoisissa musiikkitiedostoissa. Väitöskirjassa keskitytään erityisesti sellaisten hakujen problematiikkaan, joissa annetusta hakuavaimesta ja tietokannassa olevista dokumenteista otetaan huomioon nuottien korkeudet ja niiden väliset korkeuserot eli intervallit. Eräs tärkeä ominaisuus tällaisissa hauissa on ns. transpositioinvarianssi, joka tarkoittaa sitä, että annetun hakuavaimen esiintymä on löydyttävä tietokannasta riippumatta sen sävelkorkeudesta.

Väitöskirja esittelee uusia käytännöllisiä menetelmiä ja teoreettisia hakumalleja, sekä arvioi niiden jo aiemmin kehitettyjen etäisyysmääritelmien kompleksisuutta, joihin uudet mallit perustuvat. Esitettävät menetelmät käyttävät ns. bittirinnakkaista algoritmitekniikkaa. Bittirinnakkaiset algoritmit ovat huomattavasti vastaavia perinteisiä mentelmiä nopeampia. Lisäksi ne vaativat selvästi vähemmän ylimääräistä tilaa kuin niitä nopeammat indeksointiin perustuvat menetelmät, joiden vaatima tila saattaa olla jopa kymmenkertainen indeksoitavaan tietokantaan verrattuna. Eräs väitöskirjan keskeisimmistä tuloksista on uusi bittirinnakkainen transpositioinvariantti hakualgoritmi, jolla voidaan hakea yksiäänisten hakuavainten esiintymiä tietokannoista, joissa musiikkidokumentit voivat olla moniäänisiä.

Vaitoskirjassa esitellyt uudet menetelmät on toteutettu ja toteutuksen tuloksena syntynyt prototyyppi SEMEX (Search Engine for Melodic Excerpts) kykenee paikallistamaan nopeasti yksiäänisten hakuavainten transpositioinvariantteja esiintymiä suuristakin yksi- ja moniäänisistä musiikkitietokannoista.

Helsingfors, 21.11.2000

Musiksökning med strängalgoritmer

Denna avhandling utforskar nya metoder med vilka man, utgående från dess innehåll, kan söka musik i digitala, symboliskt kodade databaser. Kommunikationsföretag och musikproducenter har redan länge lagrat musik i stora databaser i digital form, för att underlätta hantering och för att spara lagerutrymme. Dessutom finns det tusentals musikfiler på Internet inom räckhåll för den stora allmänheten. Tills nyligen har sökningar i sådana databaser gjorts med hjälp av nyckelord som hänfört sig till musikdokumentets namn eller text, trots att det i flera år redan har funnits möjlighet att göra sökningar som baserar sig på t.ex. bilddatabaser.

Möjligheten att söka musikdokument på basen av innehållet är viktig, eftersom det tar onödigt mycket tid att foga nyckelord till dokumenten, och eftersom det är omöjligt att göra en fullständig lista av nyckelord till en databas, hur liten den än är. Dessutom är det mera naturligt att söka multimediedokument i deras egen form, t.ex. musikdokument genom att gnola, genom att spela något instrument eller med hjälp av notsymboler. Med hjälp av den standardisering, de metoder och de apparater som redan finns, och som håller på att utvecklas, kan det inom en snar framtid t.ex. bli möjligt, att en kund i en bar kan be en skivautomat spela det önskade stycket genom att gnola en del av stycket i sin mobiltelefon.

Metoderna och deras tillämpningar som presenteras i denna avhandling baserar sig på allmänna strängalgoritmer som ursprungligen har använts till att jämföra likheten mellan strängar och sökning av textformer i ett långt dokument. Därför måste musiken vara kodad symboliskt. Sådan kodifiering används i sådana sammanhang som traditionell västerländsk notskrivning och musikfiler i MIDI-format. Avhandlingen koncentrerar sig på problematiken hos sådana sökningar där man beaktar notläget och skillnaden mellan dem, alltså intervallerna, i söknyckeln och dokumenten i databasen. En viktig egenskap i sådana sökningar är den så kallade transpositionsinvariansen, vilket betyder att söknyckeln måste kunna hittas i tonläget oberoende av databasen.

Avhandlingen presenterar nya praktiska metoder och teoretiska sökmodeller, förutom att den utvärderar komplexiteten hos distansdefinitioner som utvecklats förut, och som de nya modellerna baserar sig på. Metoderna som presenteras här baserar sig på så kallad bitparallell algoritmteknik. De bitparallella algoritmerna är betydligt snabbare än motsvarande traditionella metoder. Dessutom krävs det mycket mindre utrymme med dem än med metoder som baserar sig på indexering, vilka är snabbare, men kan kräva upp till tio gånger mera utrymme än databasen som skall indexeras. Ett centralt resultat som presenteras i avhandlingen är den nya bitparallella transpositions-invarianta sökalgoritmen, med vilken man kan söka efter förekomsten av enstämmiga söknycklar i databaser, där musikdokumenten kan vara flerstämmiga.

De nya metoderna som presenteras i avhandlingen har implemeterats, och den implementerade prototypen SEMEX (Search Engine for Melodic Excerpts) kan snabbt hitta enstämmiga transpsitionsvarianter i stora en- och flerstämmiga musikdatabaser.