» »

Iskanje podvojenih zaporedij

Iskanje podvojenih zaporedij

Nejc Pintar ::

Zanima me kakšen bi izgledal algoritem ki bi v binarni datoteki poiskal podvojena zaporedja bitov. Najprej najdaljše podvojeno zaporedje, nato pa do vse krajših.
Lahko je biti prvi, če si edini!

Gundolf ::

Brute force, O(n2) ;)
za offsete n = -N do N (N je dolžina datoteke) v eni zanki pregleduješ, če je datoteka[i] == datoteka[i+n] in si pri tem lepo zapomniš vsa zaporedja, ki si jih našel. Sicer ne boš našel najprej najdaljših ampak kar vse naenkrat.

snow ::

from random import randint

n = 10
dat = []
for i in range(n):
    dat.append(randint(0,1))

print 'data:',dat

s = n - 1
while s > 1:
    zap = {}
    for offset in range(0,n-s+1):
        string = ""
        for i in dat[offset:offset+s]:
            string += str(i)
        if zap.has_key(string):
            zap[string] += 1
        else:
            zap[string] = 1
    s -= 1
    print zap


Opis:
Generiramo vse substringe dolžine N-1 do 2 in jih shranjujejemo v tabelo, kjer je indeks(key) kar string, njegova vrednost pa število ponovitev.

Izpis si lahko primerno urediš - npr. da ti izpiše tiste katerih vrednost je višja od 1.

Primer outputa:
data: [1, 1, 0, 1, 1, 0, 0, 0, 0, 1]
{'110110000': 1, '101100001': 1}
{'11011000': 1, '10110000': 1, '01100001': 1}
{'1100001': 1, '1011000': 1, '0110000': 1, '1101100': 1}
{'011000': 1, '100001': 1, '110000': 1, '110110': 1, '101100': 1}
{'11000': 1, '10000': 1, '01100': 1, '11011': 1, '00001': 1, '10110': 1}
{'0110': 1, '0000': 1, '0001': 1, '1100': 1, '1101': 1, '1011': 1, '1000': 1}
{'011': 1, '001': 1, '000': 2, '110': 2, '100': 1, '101': 1}
{'11': 2, '10': 2, '00': 3, '01': 2}
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

snow ::

Naprimer takole:
data: [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0]
1000011001 2
1100101011 2
000010111 2
110010101 2
100001100 2
100101011 2
000011001 2
00000101 2
11001010 2
11010000 2
10111100 2
01100101 2
10100001 2
10010101 2
11100001 2
01011110 2
00001100 2
10000110 2
00101011 2
00010111 2
00001011 2
00011001 2
0011001 2
0001011 2
0000101 3
0100000 2
0100001 2
1100001 2
1100101 3
0010101 3
1110000 2
0001100 2
1010100 2
1011110 3
0000110 2
0000010 2
1101000 2
1010000 3
1000011 2
1000010 2
0111100 2
0101111 2
0101011 2
0110010 2
1001010 2
0010111 2
110000 2
110100 2
010100 2
010101 3
001100 2
011110 3
000110 2
000011 2
000010 4
100101 3
111100 2
101111 3
111000 2
101011 2
101010 2
110010 3
010111 3
010110 2
011001 3
001010 3
001011 3
000001 2
000101 3
100001 4
100000 2
010000 4
111010 2
101000 3
10000 6
10101 4
10100 4
01101 2
01100 3
11110 3
11010 3
01000 4
00110 3
00010 4
00011 3
10010 4
10110 2
10111 4
01110 2
01111 3
11001 4
11000 2
11100 3
11101 2
01011 5
01010 5
00001 6
00000 3
00100 2
00101 6
0110 5
0111 5
0000 9
0001 7
0011 4
0010 8
0101 10
0100 6
1111 3
1110 5
1100 6
1101 4
1010 8
1011 6
1001 5
1000 6
010 16
011 10
001 12
000 16
111 8
110 10
100 12
101 14
11 18
10 26
00 29
01 26


Namesto:
    #print zap


Tole:
    for key in zap.keys():
        if zap[key] > 1:
            print key,zap[key]


Aja to je Python.
Tale primer z dolžino zaporedja 100 naredi praktično takoj, za 200 malo počaka (~1 sekundo), za 500 pa traja nekje 15 sekund na E6300.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Nejc Pintar ::

Hvala ti sneg.
Lahko je biti prvi, če si edini!

Gundolf ::

En zelo rahel problemček snow: Ker govorimo o datotekah (sicer ne vem kaj točno Nejc rabi) - 200 bitov (al pa bajtov, odvisno kako zapisuješ tale zaporedja, ampak razlike tu ni velike) dolga datoteka ni praktično nič. S takim algoritmom se že 1M bitov / bajtov datoteke zaradi prostorske zahtevnosti niti dotakniti ne moreš. Oz pri malo manjši 1k datoteki rabiš ~167.165.000 bitov / bajtov samo za shranjevanje vseh možnih zaporedij. To je verjetno tudi razlog, da je algoritem tako strašno počasen.

snow ::

Aja, ker nisem pastal pri popravku izpisa cele kode, sem pozabil tisto vrstico, kjer se za vsako iteracijo za določeno dolžino iskanega stringa vsi stringi pobrišejo.

Ja res je moja koda kar potratna z ramom :)
Pa dokler ni potrebe po daljših stringih (ali veliko izvajanji) tudi ni potrebe po drugih rešitvah.

Sicer pa.. a ni problem O(n^3)?

Različnih dolžin stringov: n
Primerjava stringov pa je tudi kvadratne odvisnosti, saj je potrebno primerjati vsakega z vsakim. (n-len)^2.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Gundolf ::

Aja valda, na to da bi sproti brisal se pa nisem spomnil, samo vseeno je požrešna zadeva, za 1M datoteko imaš potem v eni točki 0.5M 0.5M dolgih stringov naenkrat v RAMu.

Izgleda da je, če problem tako definiraš kot si ga, res O(n3), če ga pa drugače - preveriš le pokrivanja niza s samim sabo pri vseh možnih offsetih - je pa 100% O(n2).

snow ::

Hm 0.5M stringov po 0.5M znese 2.5*10^11 primerjav :=)
Ena primerjava pa pomeni primerjat do max. 0.5M bitov. No saj lahko prej greš ven iz primerjave takoj ko se dva bita ne ujemata, ampak vseeno tole trajaaaaa.
Sploh pa če upoštavamo, da je potrebno pregledat 1M različnih dolžin.

Po moje ti prej zmanjka časa kot rama.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Gundolf ::

Štos je v tem da ti ni treba pregledat različnih dolžin :) Ko pregledaš eno dolžino l, si hkrati pregledal že en kup dolžin < l. Samo pametno moraš pregledat. Tako se znebiš enega n-ja v časovni zahtevnosti.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Izdelava algoritma

Oddelek: Znanost in tehnologija
61174 (554) Klemen86
»

Verjetnost pri kroglicah

Oddelek: Šola
6916 (613) Math Freak
»

Vitezi in oprode, naloga

Oddelek: Šola
72267 (2003) noraguta
»

[JAVA] help

Oddelek: Programiranje
141120 (834) keworkian
»

problem s prekrivanjem likov

Oddelek: Programiranje
61136 (1059) McAjvar

Več podobnih tem