FI121583B

FI121583B - Symbolijonon etsintä

Info

Publication number: FI121583B
Application number: FI20021330A
Authority: FI
Inventors: Joerkki Hyvoenen
Original assignee: Syslore Oy
Priority date: 2002-07-05
Filing date: 2002-07-05
Publication date: 2011-01-14
Also published as: US20050278175A1; US8532988B2; AU2003242800A1; EP1552429A1; FI20021330A; WO2004006126A1; FI20021330A0

Description

Symbolijonon etsintä

Keksinnön ala Tämä keksintö koskee syötesymbolijonon etsintää symbolijonojen joukosta. Keksintö soveltuu erityisesti hyödynnettäväksi virheenkorjaavissa 5 tietokantahauissa, joissa syötteessä olevasta virheestä huolimatta tietokannasta löydetään oikea symbolijono tai lähimpänä oikeaa olevat symbolijonot.

Keksinnön tausta

Puheentunnistus, optinen luku, geeni- ja proteiinisekvenssien vastaavuushan bioinformatiikassa sekä tietokantahaut yleensä ovat esimerkkejä 10 tilanteista, joissa on tarvetta löytää määrätty syötesymbolijono symbolijonojen joukosta. Tällöin symbolijono voi muodostua esimerkiksi peräkkäisistä kirjaimista tai peräkkäisistä äänteitä kuvaavista symboleista. Usein on olemassa se vaara, että syötesymbolijono ei ole täysin virheetön. Päämäärä on kuitenkin se, että esimerkiksi tietokannassa olevien symbolijonojen joukosta tulee löytää 15 symbolijono, joka täysin vastaa syötesymbolijonoa, tai joka eniten muistuttaa syötesymbolijonoa, mikäli täysin vastaavaa syötesymbolijonoa ei löydy.

Ennestään tunnetaan ratkaisu symbolijonon hakemiseksi symboli-jonojen joukosta, jossa symbolijonoista on luotu trie-tietorakenne. Tällöin symbolijonot on ryhmitelty haaroihin siten, että samoilla symboleilla alkavat symbo-20 lijonot kuuluvat samaan haaraan. Samassa haarassa olevat symbolijonot jakaantuvat uusiin haaroihin niiden symbolien kohdalta, joista lähtien symbolijonot poikkeavat toisistaan.

£ "Puumaista" trie-tietorakennetta on hyödynnetty symbolijonojen ha- ^ kuun siten, että syvyyshaulla on edetty tietorakenteen haaroja pitkin sen lehtiin v 25 asti. Jokainen haaralla kohdattava uusi symboli osoittaa laskentapisteen, jossa lasketaan etäisyysmitta laskentapisteen ja sitä edeltävien laskentapisteiden e symbolien muodostaman näytesymbolijonon ja etsittävän syötesymbolijonon Q_ välille asettamalla nämä vastakkain vaihtoehtoisilla tavoilla. Etäisyysmitalla co tarkoitetaan mitä tahansa vertailuarvoa, jolla voidaan kuvata miten paljon muu- g 30 toksia tarvitaan, jotta verrattavana olevat symbolijonot saataisiin vastaamaan o cm toisiaan. Eräs tunnettu tapa laskea etäisyysmitta on Levenshtein-algoritmi.

Laskenta päättyy kun trie-tietorakenteessa on edetty loppuun asti laskemalla etäisyysmitat kaikkien haarojen kaikille laskentapisteille. Tällöin 2 suoritetaan vertailu pienimmän etäisyysmitan löytämiseksi. Vasteen tuottamiseen valitaan sen haaran symbolijono tai niiden haarojen symbolijonot, joiden viimeisten laskentapisteiden etäisyysmitat ovat pienimmät.

Edellä mainitun tunnetun ratkaisun merkittävin heikkous on se, että 5 se edellyttää suhteellisen paljon laskentaa. Paras mahdollinen, eli syötesym-bolijonoa lähinnä oleva, symbolijono voidaan löytää vasta sen jälkeen kuin laskenta on suoritettu loppuun asti kaikille trie-tietorakenteen laskentapisteille. Koska esimerkiksi tietokantahakujen yhteydessä tietokannassa olevien symbolijonojen lukumäärä on todella suuri, merkitsee tämä, että tarvittavien las-10 kuoperaatioiden lukumäärästä tulee hyvin suuri, ja näin ollen laskuoperaatioiden vaatima aika on pitkä. Vasteen saaminen syötteeseen vaatii näin ollen paljon aikaa.

Ennen tunnetaan julkaisusta US - 5377281 A ratkaisu, jossa syö-tesymbolijonon jäljellä olevien merkkien määrä voidaan ottaa huomioon opti-15 mistisen arvion laskennassa. Voidaan siis laskea, kuinka monta merkkiä syötteestä täytyy vielä käsitellä ja että kuinka se vaikuttaa lopulliseen todennäköisyyteen. Trien-haaran sisältämien merkkijonojen pituuksia ei oteta huomioon, jolloin haaran sisältö syvemmällä ei vaikuta laskentaan. Ennestään tunnetaan myös EP-julkaisusta 1052576 ratkaisu, jossa hyödynnetään trie-rakennetta. 20 Kuitenkaan tässäkään ratkaisussa ei laskentapisteissä ole käytettävissä tietoa siitä mitä ja miten pitkiä merkkijonoja trien-haara sisältää. Nämä ratkaisut eivät siksi mahdollista optimaalista ratkaisua tarvittavien laskuoperaatioiden lukumäärän minimoimiseen.

? Keksinnön yhteenveto

(M

^ 25 Tämän keksinnön tarkoitus on ratkaista edellä selostettu ongelma ja T tarjota käyttöön ratkaisu, joka mahdollistaa sen, että vasteen tuottamiseen tar- ^ vittavien laskuoperaatioiden lukumäärää voidaan alentaa, jolloin vasteen tuot- £ tamisesta tulee entistä nopeampaa. Tämä päämäärä saavutetaan itsenäisen o patenttivaatimuksen 1 mukaisella menetelmällä, itsenäisen patenttivaatimuk- 00 £2 30 sen 5 mukaisella tietokoneohjelmalla, itsenäisen patenttivaatimuksen 6 mukai- o sella tietovälineellä, ja itsenäisen patenttivaatimuksen 7 mukaisella laitteistolla.

^ Keksinnön mukainen ratkaisu perustuu siihen ajatukseen, että sym bolijonon etsimiseen ja näin ollen vasteen tuottamiseen tarvittavien laskuoperaatioiden määrää voidaan merkittävästi alentaa, kun jokaisen etäisyysmitan 3 osalta lasketaan myös sitä vastaava lyhin mahdollinen pituusero, ja etäisyys-mitan ja pituuseron perusteella vertailuarvo. Kyseinen vertailuarvo osoittaa tällöin parasta mahdollista etäisyysmittaa, joka on teoreettisesti saavutettavissa, mikäli edetään kyseisen haaran päähän asti, edellyttäen, että kaikki haa-5 rassa jäljellä olevat symbolit vastaavat syötteen huomiotta jätettyjä symboleja. Tällaisessa tilanteessa nimittäin ratkaisevaksi tulee syötteen ja symbolijonojen väliset pituuserot. Kun syöte ja symbolijono ovat eripituiset, kasvattaa nimittäin jokainen "ylimääräinen" symboli näiden välistä etäisyysmittaa.

Koska jokaisesta lasketusta pisteestä saadaan tietoon paras mah-10 dollinen vertailuarvo, voidaan vertailuarvoja vertaamalla päätellä mistä haarasta tai haaroista voidaan saada alin mahdollinen etäisyysmitta. Tällöin edetään ainoastaan näissä haaroissa, ja jätetään laskenta suorittamatta sellaisissa haaroissa, joiden vertailuarvo osittaa, että niistä ei voida saavuttaa muita haaroja parempaa etäisyysmittaa.

15 Keksinnön mukaisen ratkaisun ansiosta laskenta voidaan jättää suorittamatta suurelle osalle trie-tietorakenteessa olevien haarojen laskenta-pisteille, ilman että tämän vuoksi olisi vaaraa siitä, että parasta symbolijonoa ei löydettäisi. Tämä vuorostaan alentaa merkittävästi laskentaan kuluvaa aikaa, jolloin parhaan tai parhaiden symbolijonojen löytäminen on entistä nopeam-20 paa.

Eräässä keksinnön edullisessa suoritusmuodossa verrataan vasteen tuottamiseen käytetyn symbolijonon (tai symbolijonojen) ja syötesymboli-jonon etäisyysmittaa ennalta määrättyyn maksimietäisyyteen, eli raja-arvoon. 0 Mikäli etäisyysmitta ylittää maksimietäisyyden, merkitsee tämä, että löytynyt o 25 symbolijono poikkeaa niin paljon syötesymbolijonosta, että sen edelleen lähet- -Λ täminen vasteessa ei ole tarkoituksenmukaista (syötesymbolijonoa riittävästi muistuttavaa symbolijonoa ei ole löydetty). Tällöin muunnetaan tuotettua vas-^ tetta ennen sen lähettämistä edelleen osoittamaan, että syötesymbolijonoa ei £ löytynyt.

g 30 Eräässä toisessa keksinnön edullisessa suoritusmuodossa haaran ^ valinnan yhteydessä verrataan mainittua alinta vertailuarvoa ennalta määrät- § tyyn maksimietäisyyteen, ja päätetään laskenta mikäli alin vertailuarvo ylittää

(M

maksimietäisyyden. Vertailuarvo kuvaa parasta mahdollista saavutettavissa olevaa etäisyysmittaa, mikäli loput haarassa olevat symbolit vastaavat syöt-35 teen jäljellä olevia symboleja ja symbolien lukumäärät täsmäävät. Mikäli näin 4 ollen alin vertailuarvo ylittää maksimietäisyyden, merkitsee tämä, että syö-tesymbolijonoa tai sitä muistuttavaa symbolijonoa ei löydy symbolijonojen joukosta, jolloin laskenta ja samalla koko syötesymbolijonon etsintä voidaan lopettaa turhana.

5 Eräässä kolmannessa keksinnön edullisessa suoritusmuodossa haaran valinnan yhteydessä tarkistetaan onko jossakin haarassa jo suoritettu laskenta viimeisen laskentapisteen osalta, ja päätetään laskenta mikäli osoittautuu, että jonkin haaran viimeisen laskentapisteen osalta on saatu vertailuarvo, joka on pienempi kuin kaikkien muiden laskentapisteiden osalta saadut 10 vertailuarvot. Näin ollen laskenta ja symbolijonon etsintä voidaan päättää jo ennen kuin laskenta on toteutettu kaikkien haarojen laskentapisteiden osalta, koska vertailuarvojen käytön ansiosta voidaan olla varmoja, että loppuun asti lasketun haaran symbolijono parhaiten vastaa syötesymbolijonoa.

Keksinnön mukaisen menetelmän edulliset suoritusmuodot ilmene-15 vät oheisista epäitsenäisistä patenttivaatimuksista 2-4.

Kuvioiden lyhyt kuvaus

Keksintöä selostetaan seuraavassa esimerkinomaisesti lähemmin viittaamalla oheisiin kuvioihin, joista: kuvio 1 esittää, vuokaaviota keksinnön mukaisen menetelmän en-20 simmäisestä edullisesta suoritusmuodosta, kuviot 2a - 2f havainnollistavat syötesymbolijonon etsinnän etenemistä kuvion 1 vuokaaviota noudatettaessa, ja kuvio 3 esittää lohkokaaviota keksinnön mukaisen laitteiston en- S simmäisestä edullisesta suoritusmuodosta.

CVJ

V 25 Edullisten suoritusmuotojen kuvaus

CO

w Seuraavassa keksintöä selostetaan esimerkinomaisesti lähemmin i viitaten kuvion 1 vuokaavioon sekä kuvioiden 2a - 2f laskentaesimerkkiin.

CL

o Kuvion 1 lohkossa A luodaan sinänsä tunnetusti trie-tietorakenne, ja

CO

£2 symbolijonot ryhmitellään trie-tietorakenteen haaroihin. Kuviossa 2a on esitetty o 30 tällainen tietorakenne, johon on ryhmitelty symbolijonot: ABACUS, ABOARD, ^ BOARD ja BORDER. Trie-tietorakenteen luominen on vaihe, jota ei välttämättä tarvitse toistaa joka kerta kun haetaan uutta symbolijonoa tietokannasta. Aikaisemmin luotua tietorakennetta voidaan hyödyntää esimerkiksi niin kauan, kun 5 tietokantaan ei ole lisätty uusia symbolijonoja. Eli vasta kun uusi symbolijonon lisätään tietokantaan tulee uuden trie-tietorakenteen luonti ajankohtaiseksi.

Kuvion 1 lohkossa B vastaanotetaan syötesymbolijono, eli se symbolijono, jota on tarkoitus etsiä symbolijonojen joukosta. Seuraavassa kuvauk-5 sessa oletetaan esimerkinomaisesti että, etsittävä syötesymbolijono on ABORD.

Lohkossa C aloitetaan etenemällä ensimmäiseen laskentapisteeseen P, jossa lohkon D mukaisesti lasketaan sinänsä tunnetusti Levenshtein-algoritmilla etäisyys syötteen ja kyseisen haaran laskentapisteen ja sitä edeltä-10 vien laskentapisteiden symbolien muodostaman näytesymbolijonon välillä. Lisäksi keksinnön mukaisesti lasketaan vielä pituuserot D ja vertailuarvot C seuraavasti. Laskentapisteen P osalta näytesymbolijono on "" (tyhjä merkki alussa) ja syötesymbolijono on (kun alkuun on lisätty tyhjä merkki)" ABORD". Laskenta etenee seuraavasti: 15 - etäisyys tyhjien merkkien " " välillä on 0, koska merkit vastaavat toisiaan. Tällöin syötesymbolijonosta on vielä huomioimatta 5 merkkiä, ja pisteen P kautta kulkevien symbolijonojen pituudesta on vielä jäljellä 5-6 merkkiä, mikä on merkitty pisteen P kohdalle merkinnällä max 6, min 5. Pienin mahdollinen pituusero on siten 5-5=0. Vertailuarvo on etäisyys + pituusero, eli 20 0+0=0.

- etäisyys symbolijonojen "" ja " A" välillä on 1, koska yhdellä merkin lisäyksellä/muutoksella verrattavana olevat symbolijonot vastaavat toisiaan. Syötesymbolijonosta on vielä huomioimatta 4 merkkiä, ja pisteen P kautta kul-o kevien symbolijonojen pituudesta on vielä jäljellä 5 - 6 merkkiä. Pienin mahdol- o 25 linen pituusero on siten 5 - 4=1. Vertailuarvo on 1+1=2.

A - etäisyys symbolijonojen " " ja " AB" välillä on 2, koska kahdella ^ merkin lisäyksellä/muutoksella verrattavana olevat symbolijonot vastaavat toi-

C\J

siaan. Syötesymbolijonosta on vielä huomioimatta 3 merkkiä, ja pisteen P £ kautta kulkevien symbolijonojen pituudesta on vielä jäljellä 5 - 6 merkkiä. Pie- g 30 nin mahdollinen pituusero on siten 5 - 3=2. Vertailuarvo on 2+2=4.

^ - etäisyys symbolijonojen " " ja " ABO" välillä on 3, koska kolmella o merkin lisäyksellä/muutoksella verrattavana olevat symbolijonot vastaavat toi siaan. Syötesymbolijonosta on vielä huomioimatta 2 merkkiä, ja pisteen P kautta kulkevien symbolijonojen pituudesta on vielä jäljellä 5 - 6 merkkiä. Pie-35 nin mahdollinen pituusero on siten 5 - 2=3. Vertailuarvo on 3+3=6.

6

Kun verrattavat symbolijonot on asetettu vastakkain kaikilla vaihtoehtoisilla tavoilla päädytään kuvion 2a alalaidassa olevan taulukon osoittamiin tuloksiin.

Lohkossa E etsitään laskentapiste, josta on saatu alin vertailuarvo.

5 Alin vertailuarvo on saatu pisteen P osalta, joka toistaiseksi on ainoa laskenta-piste, jonka osalta laskut on toteutettu. Näin ollen seuraavaksi edetään tästä laskentapisteestä haaraa 1 pitkin.

Lohkossa F tarkistetaan toteutuuko laskennan päätösehto. Päätös-ehtoja voi olla monta. Seuraavassa mainitaan esimerkinomaisesti kaksi pää-10 tösehtoa: Päätösehto 1: Lopetetaan laskenta mikäli alin vertailuarvo ylittää ennalta määrätyn maksimietäisyyden. Tällöin todetaan, että etsitty syötesym-bolijono poikkeaa niin paljon symbolijonojen joukosta, että etsintä voidaan keskeyttää, koska syötesymbolijonoa muistuttavaa symbolijonoa ei kuitenkaan 15 löydetä. Sopivan maksimietäisyyden määrittely riippuu sovellutuksesta. Tässä esimerkissä oletetaan kuitenkin että maksimietäisyydeksi on määritelty 5.

Päätösehto 2: Lopetetaan laskenta mikäli jossakin haarassa on jo suoritettu laskenta viimeisen laskentapisteen osalta, ja viimeisen laskentapisteen osalta on saatu vertailuarvo, joka on pienempi kuin kaikkien muiden las-20 kentapisteiden osalta saadut vertailuarvot. Näin ollen laskenta ja symbolijonon etsintä voidaan päättää jo ennen kuin laskenta on viety loppuun kaikkien haarojen laskentapisteissä, koska vertailuarvojen käytön ansiosta voidaan olla varmoja, että loppuun asti lasketun haaran symbolijono parhaiten vastaa syötesymbolijonoa.

° 25 Kuvion 2a taulukosta ilmenee, että alin vertailuarvo C on 0, joka on <m pienempi kuin maksimietäisyys 5. Näin ollen ensimmäinen päätösehto ei to- i ^ teudu. Päätösehto 2 ei myöskään toteudu, koska missään haarassa ei vielä i ole päädytty viimeiseen laskentapisteeseen asti. Näin ollen kuvion 1 lohkokaa-x viossa päädytään lohkoon C ja kuviossa 2a edetään haaraa 1 pitkin pistee- 30 seenPI.

co Pisteessä P1 toistetaan lohkon D mukainen laskenta. Näytesymboli- c\j jono on " A" ja syötesymbolijono on edelleen " ABORD". Pisteen P1 etäisyyk- ^ sien laskennan helpottamiseksi laskennan lähtökohtana on pisteessä P tehdyt 7 etäisyyslaskut, jotka siirtyvät mukaan kuvion 2b alaosan taulukkoon. Laskenta etenee seuraavasti: - etäisyys symbolijonojen " A" ja "" välillä on 1, koska yhdellä merkin lisäyksellä/muutoksella verrattavana olevat symbolijonot vastaavat toisiaan.

5 Tällöin syötesymbolijonosta on vielä huomioimatta 5 merkkiä, ja pisteen P1 kautta kulkevien symbolijonojen pituudesta on vielä jäljellä 5 merkkiä, mikä on merkitty pisteen P1 kohdalle merkinnällä max 5 min 5. Pienin mahdollinen pituusero D on siten 5-5=0. Vertailuarvo C on etäisyys + pituusero, eli 1+0=1.

- etäisyys symbolijonojen " A" ja " A" välillä on 0, symbolijonot vas-10 taavat toisiaan. Syötesymbolijonosta on vielä huomioimatta 4 merkkiä, ja pisteen P1 kautta kulkevien symbolijonojen pituudesta on vielä jäljellä 5 merkkiä. Pienin mahdollinen pituusero on siten 5 - 4=1. Vertailuarvo on 0+1=1.

- etäisyys symbolijonojen " A" ja " AB" välillä on 1, koska yhdellä merkin lisäyksellä/muutoksella verrattavana olevat symbolijonot vastaavat toils siaan. Syötesymbolijonosta on vielä huomioimatta 2 merkkiä, ja pisteen P1 kautta kulkevien symbolijonojen pituudesta on vielä jäljellä 3 merkkiä. Pienin mahdollinen pituusero on siten 5 - 3=2. Vertailuarvo on 1+2=3.

- etäisyys symbolijonojen " A" ja " ABO" välillä on 2, koska kahdella merkin lisäyksellä/muutoksella verrattavana olevat symbolijonot vastaavat toi- 20 siaan. Syötesymbolijonosta on vielä huomioimatta 2 merkkiä, ja pisteen P kautta kulkevien symbolijonojen pituudesta on vielä jäljellä 5 merkkiä. Pienin mahdollinen pituusero on siten 5 - 2=3. Vertailuarvo on 2+3=5.

Kun verrattava symbolijonot on asetettu vastakkain kaikilla vaihto-0 ehtoisilla tavoilla päädytään kuvion 2b alalaidassa olevan taulukon osoittamiin o 25 tuloksiin. On kuitenkin huomattava, että edellä selostettu tapa laskea etäisyy- A det verrattavien symbolijonojen välillä on vain yksi esimerkki, jonka lisäksi on ^ olemassa muitakin tunnettuja ja kenties jopa yksinkertaisempia tapoja. Keksin- ^ nön kannalta ei ole olennaista se, miten etäisyydet lasketaan. Eräs vaihtoehto £ laskea etäisyydet on hyödyntää kuvion 2b alaosassa näkyvän kaltaista tauluk- o 30 koa, ja erityisesti edellistä laskettua etäisyyssaraketta.

” Kun pisteen P1 laskenta on suoritettu haetaan jälleen lohkossa E

CM

§ laskentapiste, jolla on alin vertailuarvo C. Tulokseksi saadaan piste P, josta

(M

löytyy vertailuarvo 0, joka on pienempi kuin pisteen P1 pienin vertailuarvo 1. Näin ollen seuraavaksi edetään haaraa 2 pitkin edelleen pisteeseen P2. Loh 8 kossa F todetaan, että päätösehdot eivät toteudu, jonka jälkeen päädytään lohkoon C toistamaan laskut pisteen P2 osalta.

Seuraavassa ei käydä läpi kaikkien laskentapisteiden laskuja, vaan siirrytään suoraan kuvion 2c osoittamaan tilanteeseen, jossa laskut on saatu 5 valmiiksi pisteille P3 ja P4. Tällöin kuvion 1 lohkokaavion lohkossa E todetaan, että alin vertailuarvo C on saatu laskentapisteestä P3, jonka alin vertailuarvo C on 1 kuvion 2c mukaan, kun taas alin vertailuarvo C pisteessä P4 on 2. Näin ollen seuraavaksi edetään laskentapisteen P3 haarasta.

Kuvio 2d osoittaa tilannetta, kun laskut on suoritettu valmiiksi las-10 kentapisteille P5 ja P6. Tällöin kuvion 1 lohkokaavion lohkossa E todetaan, että alin vertailuarvo C on saatu kahdessa laskentapisteessä, eli sekä laskentapisteen P5 että P6 alin vertailuarvo C on 1. Seuraavaksi edetään laskenta-pisteen P5 haarasta.

Kuvio 2e osoittaa tilannetta, kun laskut on suoritettu valmiiksi las-15 kentapisteelle P7. Tällöin kuvion 1 lohkokaavion lohkossa E todetaan, että alin vertailuarvo C on saatu laskentapisteessä P6, jossa alin vertailuarvo C = 1 (laskentapisteen P7 alin vertailuarvo C = 2). Seuraavaksi edetään laskentapisteen P6 haarasta.

Kuvioissa ei ole esitetty kaikkia välivaiheita, mutta laskuja toistetta-20 essa laskentapisteille P9 ja P10 on vertailuarvo C=1 näille pisteille. Kun laskut vielä toistetaan laskentapisteelle P10 on tilanne kuvion 2f osoittama, kun kuvion 1 lohkokaaviossa jälleen päädytään lohkoon E. Laskentapisteen P10 osalta alin vertailuarvo C on 1. Koska kaikkien muiden haarojen viimeisen lasketun 0 laskentapisteen vertailuarvot (haarassa johon piste P7 kuuluu on C=2 ja haa- δ 25 rassa johon piste P4 kuuluu on C=2) ovat suuremmat kuin laskentapisteen A P10 vertailuarvo C=1 on laskentapiste P10 se piste, josta seuraavaksi tulisi ^ edetä. Laskentapiste P10 on kuitenkin viimeinen laskentapiste kyseisessä haa- ^ rassa. Näin ollen lohkossa F todetaan, että edellä selostettu päätösehto 2 ιοί teutuu, ja laskenta voidaan lopettaa.

o 30 Lohkossa G valitaan laskentapisteeseen P10 johtaneen haaran ” symbolijono vasteen tuottamista varten. Kyseinen symbolijono on ABOARD.

§ Tämä symbolijono tuotetaan vasteeksi syötteeseen.

C\J

Kuvion 1 lohkokaaviosta poiketen voidaan lohkon G jälkeen vielä suorittaa ylimääräinen tarkistus. Tällöin verrataan vasteen tuottamiseen käyte-35 tyn symbolijonon (tai symbolijonojen) ja syötesymbolijonon etäisyysmittaa en- 9 naita määrättyyn maksimietäisyyteen, eli raja-arvoon. Kuvion 2f tilanteessa vasteen tuottamiseen käytetyn symbolijonon ABOARD ja syötesymbolijonon ABORD välinen etäisyysmitta on 1 (ympyröity kuviossa 2f). Mikäli etäisyysmitta ylittää maksimietäisyyden, merkitsee tämä, että löytynyt symbolijono poikkeaa 5 niin paljon syötesymbolijonosta, että sen edelleen lähettäminen vasteessa ei ole tarkoituksenmukaista (riittävän läheistä symbolijonoa ei ole löydetty). Tällöin muunnetaan tuotettua vastetta ennen sen lähettämistä edelleen osoittamaan, että syötesymbolijonoa ei löytynyt. Näin vältytään tilanteelta, jossa vasteeksi muodostuisi symbolijono joka erittäin paljon poikkeaa syötesymboli-10 jonosta.

Kuvio 3 esittää lohkokaaviota keksinnön mukaisen laitteiston ensimmäisestä edullisesta suoritusmuodosta. Kuviossa 3 laitteistoa 10 havainnollistetaan toiminnallisilla lohkoilla 11 - 18. On kuitenkin tärkeää huomata, että laitteiston tosiasiallinen rakenne saattaa poiketa kuviossa 3 esitetystä. Lohko-15 jen toiminnot kuviossa 3 voidaan käytännössä toteuttaa yhdellä tai usealla piirillä tai tietokoneohjelmalla tai vaihtoehtoisesti piirien ja ohjelmien yhdistelmällä. Tällöin on myös mahdollista, että laitteiston toimintoja ei toteuteta tarkasti havainnollistetuilla lohkoilla, vaan sen sijaan kahden tai useamman lohkon toiminnot on saatettu yhdistää yhteen piiriin tai ohjelmaan.

20 Laitteisto 10, jonka avulla kuvioiden 1 ja 2a - 2f yhteydessä selostet tua menetelmää voidaan soveltaa, voi muodostua esimerkiksi tietoliikenneverkkoon kytketystä tietokoneesta, jonka muistiin 13 on muodostettu symboli-jonoista muodostuva tietokanta. Laitteistoon kuuluu välineitä 12 trie-0 tietorakenteen luomiseksi ryhmittelemällä muistiin 13 tallennetut symbolijonot o 25 trie-tietorakenteen haaroihin.

-A Kun trie-tietorakenne on luotu ja laitteen tulon 11 kautta vastaanote- taan syötesymbolijono aloittaa laitteisto 10 syötesymbolijonoa parhaiten vas-™ taavan symbolijonon hakemisen muistista 13. Tämän suorittamiseksi laitteissa toon kuuluu laskentavälineitä 14 etäisyysmittojen, pituuserojen ja vertailuarvo- g 30 jen laskemiseksi kyseessä olevan haaran laskentapisteen ja sitä edeltävien ^ laskentapisteiden muodostaman näytesymbolijonon ja syötesymbolijonon välil- § lä asettamalla nämä vastakkain vaihtoehtoisilla tavoilla.

(M

Laitteistossa on lisäksi valintavälineitä 15, jotka toistuvasti valitsevat seuraavan haaran jota pitkin edetä, ja jotka osoittavat laskentavälineille 14 35 seuraavan laskentapisteen, jonka osalta laskut tulee suorittaa, kuten aikai- 10 semmin on selostettu kuvion 1 vuokaavion yhteydessä. Kun valintavälineet 15 havaitsevat, että päättymisehto toteutuu, eli lasketa tulee lopettaa, välittyy tästä tieto välineille 16.

Välineet 16 valitsevat muistissa 13 olevien tietojen perusteella yh-5 den tai useamman symbolijonon, joiden etäisyysmitta syötesymbolijonoon on suoritettujen laskujen perustella pienin. Tämän jälkeen vasteen tuottamisvälineet 17 tuottavat ja lähettävät edelleen laitteiston 10 lähdön 18 kautta vasteen, joka siis muodostuu siitä symbolijonosta tai niistä symbolijonoista, joka eniten muistuttavat syötesymbolijonoa.

10 On ymmärrettävä, että edellä oleva selitys ja siihen liittyvät kuviot on ainoastaan tarkoitettu havainnollistamaan esillä olevaa keksintöä. Alan ammattimiehelle tulevat olemaan ilmeisiä erilaiset keksinnön variaatiot ja muunnelmat ilman että poiketaan oheisissa patenttivaatimuksissa esitetyn keksinnön suoja-piiristä.

o o

(M

CO

(M

X

cc Q.

O

co co oj o o

(M

Claims

1. Menetelmä syötesymbolijonon etsimiseksi symbolijonojen joukosta, jossa: 5 luodaan (A) trie-tietorakenne symbolijonoista, jolloin symbolijonot ryhmitellään haaroihin siten, että samoilla symboleilla alkavat symbolijonot kuuluvat samaan haaraan, ja samassa haarassa olevat symbolijonot jakaantuvat uusiin haaroihin niiden symbolien kohdalta, joista lähtien symbolijonot poikkeavat toisistaan, 10 vastaanotetaan (B) syötesymbolijonosta muodostuva syöte, edetään (C) trie-tietorakenteen alkupisteestä haaraa pitkin seuraa-van symbolin osoittamaan laskentapisteeseen, lasketaan (D) etäisyysmitat laskentapisteessä kyseessä olevan haaran laskentapisteen sekä sitä edeltävien laskentapisteiden symbolien muodos- 15 tämän näytesymbolijonon ja syötesymbolijonon välillä asettamalla nämä vastakkain vaihtoehtoisilla tavoilla, valitaan (E) toistuvasti seuraava haara jota pitkin edetään (C) seu-raavan symbolin osoittamaan laskentapisteeseen, jossa mainittu laskenta (D) toistetaan uuden laskentapisteen osalta, 20 laskennan (G) päätyttyä valitaan yksi tai useampi symbolijono, joi den etäisyysmitta syötesymbolijonoon on suoritettujen laskujen perusteella pienin, ja käytetään valittua tai valittuja symbolijonoja vasteen tuottamiseen, o 5 tunnettu siitä, cv ^ 25 että lasketaan (D) laskentapisteissä etäisyysmittojen lisäksi myös ^ jokaista etäisyysmittaa vastaava pienin mahdollinen pituusero, joka osoittaa CO ^ miten paljon kyseisen etäisyysmitan laskennassa huomiotta jääneen syö- g tesymbolijonon loppuosan pituus eroaa kyseessä olevan laskentapisteen kaut- o ta kulkevien symbolijonojen laskentapisteen jälkeisistä pituuksista, ja lasketaan CO £2 30 jokaisen etäisyysmitan ja sitä vastaavan pituuseron perusteella vertailuarvo, ja o että mainittu haaran valinta (E) suoritetaan siten, että seuraavaksi ^ edetään siitä laskentapisteestä, josta on saatu tulokseksi alin vertailuarvo.

2. Patenttivaatimuksen 1 mukainen menetelmä, tunnettu siitä, että verrataan vasteen tuottamiseen käytetyn symbolijonon tai symboli-jonojen ja syötesymbolijonon etäisyysmittaa ennalta määrättyyn maksimietäi-syyteen, ja muunnetaan tuotettua vastetta osoittamaan, että syötesymbolijonoa 5 ei löytynyt, mikäli etäisyysmitta ylittää maksimietäisyyden.

3. Patenttivaatimuksen 1 tai 2 mukainen menetelmä, tunnettu siitä, että haaran valinnan yhteydessä verrataan mainittua alinta vertailuarvoa ennalta määrättyyn maksimietäisyyteen, ja 10 päätetään laskenta mikäli alin vertailuarvo ylittää maksimietäisyy den.

4. Jonkin patenttivaatimuksen 1 - 3 mukainen menetelmä, tunnettu siitä, että haaran valinnan yhteydessä tarkistetaan onko jossakin haarassa jo 15 suoritettu laskenta viimeisen laskentapisteen osalta, ja päätetään laskenta mikäli osoittautuu, että jonkin haaran viimeisen laskentapisteen osalta on saatu vertailuarvo, joka on pienempi kuin kaikkien muiden laskentapisteiden osalta saadut vertailuarvot.

5. Tietokoneohjelma, tunnettu siitä, että se käsittää tietoko-20 neohjelmavälineet, jotka on järjestetty suorittamaan jonkin patenttivaatimuksen 1 - 4 mukaisen menetelmän kaikki vaiheet suoritettaessa mainittu ohjelma tietokoneessa.

6. Tietokoneella luettava tietoväline, tunnettu siitä, että tietoväli- 0 neeltä on luettavissa tietokoneohjelma, joka käsittää tietokoneohjelmavälineet o 25 jotka on järjestetty suorittamaan jonkin patenttivaatimuksen 1-4 mukaisen t"·— menetelmän kaikki vaiheet suoritettaessa mainittu ohjelma tietokoneessa.

7. Laitteisto (10) symbolijonon etsimiseksi symbolijonojen joukosta, ^ joka laitteisto käsittää: £ välineitä (12) trie-tietorakenteen luomiseksi symbolijonoista ryhmit- g 30 telemällä symbolijonot haaroihin siten, että samoilla symboleilla alkavat sym- bolijonot kuuluvat samaan haaraan, ja samassa haarassa olevat symbolijonot o jakaantuvat uusiin haaroihin niiden symbolien kohdalta, joista lähtien symboli en jonot poikkeavat toisistaan, tulon (11) syötesymbolijonosta muodostuvan syötesymbolijonon 35 vastaanottamiseksi, laskentavälineitä (14) etäisyysmittojen laskemiseksi laskentapisteessä kyseessä olevan haaran laskentapisteen sekä sitä edeltävien laskenta-pisteiden symbolien muodostaman näytesymbolijonon ja syötesymbolijonon välillä asettamalla nämä vastakkain vaihtoehtoisilla tavoilla, 5 valintavälineitä (15), jotka toistuvasti valitsevat seuraavan haara jota pitkin edetä seuraavan symbolin osoittamaan laskentapisteeseen, jossa mainittu laskenta toistuu uuden laskentapisteen osalta, valintavälineitä (16), jotka laskennan päätyttyä valitsevat yhden tai useamman symbolijonon, joiden etäisyysmitta syötteeseen on suoritettujen 10 laskujen perusteella pienin, vasteen tuottamisvälineitä (17), jotka tuottava vasteen käyttäen valittua tai valittuja symbolijonoja ja lähdön (18) vasteen syöttämiseksi edelleen, tunnettu siitä, laitteisto on järjestetty: 15 laskemaan laskentapisteissä etäisyysmittojen lisäksi myös jokaista etäisyysmittaa vastaava pienin mahdollinen pituusero, joka osoittaa miten paljon kyseisen etäisyysmitan laskennassa huomiotta jääneen syötesymbolijonon loppuosan pituus eroaa kyseessä olevan laskentapisteen kautta kulkevien symbolijonojen laskentapisteen jälkeisistä pituuksista, ja laskemaan jokaisen 20 etäisyysmitan ja sitä vastaavan pituuseron perusteella vertailuarvon, ja suorittamaan mainitun haaran valinnan siten, että seuraava eteneminen tapahtuu siitä laskentapisteestä, josta on saatu tulokseksi alin vertailuarvo. o δ CM CO CM X cc CL O CO CO CM O O CM