Sanan osajonojen lukumäärä

Sanan osajono on sanasta järjestyksessä poimituista merkeistä muodostettu uusi sana. Esimerkiksi sanalla ’ABBA’ on osajonot (11 kpl) [”, ’A’, ’AA’, ’AB’, ’ABA’, ’ABB’, ’ABBA’, ’B’, ’BA’, ’BB’, ’BBA’]. Huomaa, että esim. ’AB’ saadaan kahdella eri tavalla, mutta lasketaan vain kerran.

Kuinka laskea sanan w osajonojen lukumäärä f(w)? Oletetaan että w:ssä esiintyvien merkkien lukumäärä on jokin ennalta kiinnitetty pienehkö luku. Halutaan löytää lineaariaikainen algoritmi.

Ratkaisu

Olkoon w sana, jonka osajonot halutaan laskea. Olkoon w:n pituus n ja siinä esiintyvät merkit \{c_1, c_2, \dots, c_m\}. Kun samaistetaan jokainen w:n osajono v siihen indeksien osajonoon, josta v löytyy kaikkein aikaisimmin, vastaa jokainen sanan osajono solmusta -1 lähtevää kävelyä suunnatulla graafilla G, jonka solmut ovat V(G) = \{-1, 0,1,\dots, n-1 \} ja solmusta j lähtee kaaret (j, k_c) missä k_c on indeksi, jossa merkki c esiintyy w:ssä seuraavan kerran lukien indeksistä j+1 lähtien (ja jos c ei enää esiinny, niin kaarta ei ole) ja tämä vastaavuus on bijektiivinen.

Esimerkiksi sanalle w = ”ABBA” graafi näyttää seuraavalta

Sanan ”ABBA” graafi. theFolls on dicti, jonka ao Python-koodi antaa, koodissa indeksit ovat siirretty yhdellä ja itse asiassa theFolls antaa seuraavan etsimisen alkaa itse siitä indeksistä missä ollaan.

Olkoon A edellä kuvatun suunnatun graafin vierekkäisyysmatriisi. Osajonojen lukumäärä on tällöin ensimmäisen rivin summa seuraavasta matriisista

\begin{aligned}  \sum_{j=0}^\infty A^j  = \left(I - A \right)^{-1}   \end{aligned}

Huomaa, että edellä summa on itse asiassa vain äärellinen, sillä kaaret vievät aina eteen päin, joten graafin kävely voi olla korkeintaan n:n pituinen ja A^{n+1}=0, joten summan suppenemisen eikä I-A:n kääntyvyyden kanssa tule ongelmia.

Merkitään B=I-A. Mehän tarvitsemme vain sen ensimmäisen rivin summan, joten koko matriisia A ei tarvitse muodostaa, eikä summaa \sum_{j=0}^{n}A^j laskea, vaan riittää ratkaista

B^{T}x = e_1,

missä e_1 on sarakevektori, jonka ensimmäinen komponentti on 1 ja loput nollia. Kun tämä kirjoitetaan Gauss-Jordanin menetelmän vaatimaan muotoon (jossa ei ratkaista koko käänteismatriisia, vain sen ensimmäinen rivi), niin huomataan, että ratkaiseminen on erittäin helppoa, sillä B on alakolmiomatriisi, jossa on ykkösiä diagonaalilla ja jokaisessa sarakkeessa korkeintaan m:ssä paikassa -1 (ja muuten nollia). Näin ollen saadaan seuraava lineaariaikainen algoritmi (Python):

def theFolls(w):
    """map c -> list a where a[j] is the next index of c in w
    when start searching from the index j"""
    alph = list(set(c for c in w))
    n = len(w)
    ret = {c: [n]*n for c in alph}
    prevs = {c: -1 for c in alph}
    for i, c in enumerate(w):
        for j in range(prevs[c]+1, i+1):
            ret[c][j] = i
        prevs[c] = i
    return ret

def countSubsequences(w):
    """How many words can be obtained from w as subsequences"""
    n = len(w)
    folls = theFolls(w)
    edges = [
        [folls[c][i]+1 for c in folls if folls[c][i]<n]
        for i in range(n)
    ]
    ret = 0
    a = [0 for _ in range(n+1)]
    a[0] = 1
    for i in range(n):
        for j in edges[i]:
            a[j] += a[i]
    return sum(a)

Vastaa

Täytä tietosi alle tai klikkaa kuvaketta kirjautuaksesi sisään:

WordPress.com-logo

Olet kommentoimassa WordPress.com -tilin nimissä. Log Out /  Muuta )

Google photo

Olet kommentoimassa Google -tilin nimissä. Log Out /  Muuta )

Twitter-kuva

Olet kommentoimassa Twitter -tilin nimissä. Log Out /  Muuta )

Facebook-kuva

Olet kommentoimassa Facebook -tilin nimissä. Log Out /  Muuta )

Muodostetaan yhteyttä palveluun %s