Blogini hakutoiminnossa on nyt käytössä hakusanojen automaattitäydennys. Sitä voi kokeilla näpyttelemällä sanoja oikeasta yläkulmasta löytyvään hakulaatikkoon.

Suositeltavat hakusanat perustuvat kaikista artikkeleista löytyvien sanojen esiintymistiheyteen. Suosittelu ei siis perustu siihen, mitä on haettu eniten. (Ei täällä tehdä niin paljon hakuja, että siitä olisi iloa.)

Toteutus perustuu kolmeen osaan:

  • jQuery Autocomplete -laajennukseen, jolla on helppo lisätä tarvittava käyttöliittymä tavalliseen input-kenttään.
  • Redis 2.0 -tietokantaan, joka tukee suoraan tarvittavia sorted set -tietorakenteita. Redis tulee Ubuntun mukana.
  • Muutamaan riviin omaa Python/Django-koodia, jolla luodaan Redis-tietokannan sisältö ja etsitään sieltä hakusanoja.

Tietokannan rakenne

Tietokannan rakenne pohjautuu tähän artikkeliin ja tarkemmin sanottuna sen loppupuoleen, jossa on kuvailtu painotetun autocomplete-järjestelmän idea. Rakenne on kaksitasoinen. Ensimmäisellä tasolla Redisiin on tallennettu avaimina kaikkien sanojen kaikki mahdolliset alkuosat:

r
re
red
redis
ru
rul
rule
rulez

Kunkin avaimen alta löytyy erillinen sorted set, joka sisältää kaikki kyseisen alkuosan sisältävät sanat ja niiden painoarvot. Esimerkiksi avaimen "r" alta löytyy tässä esimerkissä sorted set, joka sisältää seuraavat arvot:

r:
  redis -20
  rulez -10

Tietokannan muodostaminen

Tietorakenne muodostetaan lisäämällä jokainen sanan alkuosa yksitellen ZADD-komennolla Redis-tietokantaan:

ZADD "r" -20 "redis"
ZADD "re" -20 "redis"
ZADD "red" -20 "redis"
ZADD "redi" -20 "redis"
ZADD "redis" -20 "redis"
ZADD "r" -10 "rulez"
ZADD "ru" -10 "rulez"
ZADD "rul" -10 "rulez"
ZADD "rule" -10 "rulez"
ZADD "rulez" -10 "rulez"

Hakujen tekeminen

Hakusanojen etsiminen tietylle alkuosalle on hyvin yksinkertainen Redis-operaatio:

ZRANGEBYSCORE "r" -inf +inf LIMIT 10
=>
  redis
  rulez

Operaatio palauttaa kymmenen parhaiten täsmäävää hakusanaa paremmuusjärjestyksessä. Painoarvot on tallennettu negatiivisina, jotta järjestys menee oikein päin (suurin painoarvo tulee ensimmäiseksi). Redis 2.1 tukisi myös ZREVRANGEBYSCORE-kommentoa, mutta koska Ubuntun mukana tulee Redis 2.0, on helpompi käyttää negatiivisia painoarvoja.

Redisin dokumentaation mukaan rajoitetun ZRANGEBYSCORE-operaation kompleksisuus on O(log(N)), jossa N on sorted setin sisältämien hakusanojen määrä. Hakujen raskaus kasvaa siis logaritmisessa suhteessa hakusanojen määrään nähden, mikä on hyvä asia. Ylemmän tason avaimen etsiminen on aina O(1) -operaatio riippumatta siitä, montako hakusanaa tietokantaan on tallennettu. Rajoituksena on lähinnä se, että koko tietokannan täytyy mahtua muistiin. Oman blogini kaikki hakusanat vievät noin 5MB tällä tietorakenteella.