[voikko] tokenize isoille dokumenteille

[Harri Pitkänen]

On Wednesday 06 January 2016 12:13:32 Harri Pitkänen wrote:
> > 1.5k noin 0.01s
> > 25k noin 1s
> > 30k noin 2s
> > 40k noin 3s
> > 60k noin 5s
> > 65k noin 7s
> > 115k noin 20s
> > 270k noin 2min 8s eli 128s
> > 415k noin 5min 20s eli 320s
> 
> Tämä näyttää viittaavan melko selvästi siihen, että aikaa kuluu
> neliöllisesti syötteen pituuteen nähden (pituuden kaksinkertaistaminen
> nelinkertaistaa ajankäytön). Teoriassa tämän algoritmin aikavaativuuden
> pitäisi olla lineaarinen, joten bugihan siellä jossain on.
> 
> Yritän korjailla loppuviikon aikana.

Taisin löytää ongelman syyn: libvoikon funktiossa voikkoNextTokenCstr tehdään 
UTF-8-stringin dekoodausta vähän liikaa eli jokaisen tokenin alusta koko 
annetun tekstin loppuun. Tämä on teoriassa tarpeellistakin, koska rajapinta on 
sellainen, ettei tuota dekoodattua stringiä voida säilyttää missään kutsujen 
välillä, ja toisaalta ei voida olla varmoja etteikö se koko tuhansien merkkien 
kokonaisuus voisikin olla yhtä sanaa.

Ihan triviaalia korjausta tuohon ei siis ole tehtävissä, mutta pienellä 
väännöllä tuon pitäisi taipua pahimmassakin tapauksessa vaativuuteen n log(n) 
ja tyypillisessä tapauksessa lineaariseksi. Palaan asiaan...

Harri