Algorytm Berlekampa Masseya

Hej, muszę zaimplementować ten algorytm, by działał w sposób, że podajemy mu sekwencje, a on podaje nam wielomian charakterystyczny. Szukałem na internecie, ale nigdzie nie widzę dobrego wyjaśnienia jak to ma działać w środku i niestety nie potrafię tego zrozumieć. Jedyny działający kod znalazłem w Pythonie, ale niestety nie znam Pythona i kod muszę napisać w C++. Czy dałby radę ktoś wytłumaczyć co się dzieje w środku tego algorytmu, tak żeby dość łatwo go zaimplementować lub może ktoś ma ten kod i mógłby go podesłać, żebym mógł go lepiej zrozumieć?

#!/usr/bin/env python

def Berlekamp_Massey_algorithm(sequence):
    N = len(sequence)
    s = sequence[:]

    for k in range(N):
        if s[k] == 1:
            break
    f = set([k + 1, 0])  # use a set to denote polynomial
    l = k + 1

    g = set([0])
    a = k
    b = 0

    for n in range(k + 1, N):
        d = 0
        for ele in f:
            d ^= s[ele + n - l]

        if d == 0:
            b += 1
        else:
            if 2 * l > n:
                f ^= set([a - b + ele for ele in g])
                b += 1
            else:
                temp = f.copy()
                f = set([b - a + ele for ele in f]) ^ g
                l = n + 1 - l
                g = temp
                a = b
                b = n - l + 1

    # output the polynomial
    def print_poly(polynomial):
        result = ''
        lis = sorted(polynomial, reverse=True)
        for i in lis:
            if i == 0:
                result += '1'
            else:
                result += 'x^%s' % str(i)

            if i != lis[-1]:
                result += ' + '

        return result

    return (print_poly(f), l)


if name == 'main':
    seq = (0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0)
    (poly, span) = Berlekamp_Massey_algorithm(seq)

    print ('The input sequence is %s.' % str(seq))
    print ('Its characteristic polynomial is (%s),' % poly,)
    print ('and linear span is %d.' % span)

To jest kod który znalazłem

To teraz, których instrukcji Pythona, nie Rozumiesz, to Ci napiszę czym one są w C++.

lion137 napisał(a):

To teraz, których instrukcji Pythona, nie Rozumiesz, to Ci napiszę czym one są w C++.

Głównie

for k in range(N):
        if s[k] == 1:
            break

i jaki ten for ma zasięg, w sensie jakby w C++ dać for(..){ } to co jest w klamerkach, gdzie się for Pythonowy kończy. Druga rzecz f ^= set([a - b + ele for ele in g]) oraz f = set([b - a + ele for ele in f]) ^ g , b = n - l + 1 , result += 'x^%s' % str(i) , result += ' + '

W Pythonie scope wyznaczają wcięcia, więc ten for kończy się instrukcją: break. Następna instrukcja już jest na wysokości for, więc jest poza pętlą, tak samo w "ifie" wcięte jest break.
Kolejną trzeba rozbic mentalnie:

• f ^= sth - to samo co w C++: f = f XOR sth;
• [f(args) for arg in <iterable collection>] - to wyrażenie zwraca listę, którą Uworzyłbyś mapując jakąś funkcję na iterowalną kolekcję, np. :
  [x * x for x in [1, 2, 3]] = [1, 4, 9] , czyl iw powyższym, w C++, do każdego elementu kolekcji g, trzeba dodać a - b;
• set(iterable) - tworzy hashsetz iterowalnej kolekcji iterable, w C++, na przykład z listy: https://www.tutorialspoint.com/cpp_standard_library/cpp_set_init_constructor.htm

lion137 napisał(a):

W Pythonie scope wyznaczają wcięcia, więc ten for kończy się instrukcją: break. Następna instrukcja już jest na wysokości for, więc jest poza pętlą, tak samo w "ifie" wcięte jest break.
Kolejną trzeba rozbic mentalnie:

• f ^= sth - to samo co w C++: f = f XOR sth;
• [f(args) for arg in <iterable collection>] - to wyrażenie zwraca listę, którą Uworzyłbyś mapując jakąś funkcję na iterowalną kolekcję, np. :
  [x * x for x in [1, 2, 3]] = [1, 4, 9] , czyl iw powyższym, w C++, do każdego elementu kolekcji g, trzeba dodać a - b;
• set(iterable) - tworzy hashsetz iterowalnej kolekcji iterable, w C++, na przykład z listy: https://www.tutorialspoint.com/cpp_standard_library/cpp_set_init_constructor.htm

Dzięki, prawie już rozumiem tylko jeszcze jedna rzecz, po co jest w takim razie ta część

for k in range(N):
        if s[k] == 1:
            break

skoro kończy się na break, co ona w ogóle wykonuje? Rozumiem, że to jest for(int k=0; k<N; k++){if (s[k]==1) k=N;}, czemu to ma służyć?

He, he, rzeczywiście, nie ma to sensu (ta pętla robi nic: iteruje po kolekcji i jak napotka w niej element o wartości 1 to się zatrzymuje). Algorytm na pewno dobrze działa? Może reszta linijek zaczynając od: f = set([k + 1, 0]), a kończąc na b = 0, ma też być w tej pętli (ma być wcięta), wtedy wyglądałoby to tak:

for k in range(N):
        if s[k] == 1:
            break
		f = set([k + 1, 0])  # use a set to denote polynomial
		l = k + 1

		g = set([0])
		a = k
		b = 0

Najlepiej Wrzuć źródło tego kodu, proszę.

lion137 napisał(a):

He, he, rzeczywiście, nie ma to sensu (ta pętla robi nic: iteruje po kolekcji i jak napotka w niej element o wartości 1 to się zatrzymuje). Algorytm na pewno dobrze działa? Może reszta linijek zaczynając od: f = set([k + 1, 0]), a kończąc na b = 0, ma też być w tej pętli (ma być wcięta), wtedy wyglądałoby to tak:

Kopiuj

for k in range(N):
        if s[k] == 1:
            break
		f = set([k + 1, 0])  # use a set to denote polynomial
		l = k + 1

		g = set([0])
		a = k
		b = 0

Najlepiej Wrzuć źródło tego kodu, proszę.

Kod jest z https://github.com/bozhu/BMA/blob/master/bma.py , wytłumaczyłbyś proszę jeszcze jak działają te 2 linijki ze sobą? f = set([k + 1, 0]) tworzy tablicę np. {4, 0} , a potem

for ele in f:
            d ^= s[ele + n - l]

, to ten for ele inn f: to pętla która sprawdza nam te dwa elementy w tablicy f ?

f = set([k + 1, 0]) tworzy zbiór (hashset); do konstruktora zbioru dajemy listę ([] - lista w Pythonie) i zwraca nam zbiór złożony z elementów listy.

To zaś:

for ele in f:
    d ^= s[ele + n - l]

Pętla, jak for (auto & ele : f) {d ^= s[ele + n - 1]} w C++, a w pętli: s[i] to operator zwracający element kolekcji s o indeksie i, a dalej, jak wyżej pisałem,
d = d XOR s[ele + n - 1].

DarQxxx napisał(a):

Dzięki, prawie już rozumiem tylko jeszcze jedna rzecz, po co jest w takim razie ta część

Kopiuj

for k in range(N):
        if s[k] == 1:
            break

skoro kończy się na break, co ona w ogóle wykonuje? Rozumiem, że to jest for(int k=0; k<N; k++){if (s[k]==1) k=N;}, czemu to ma służyć?

Ta część ustawia wartość k.
Odpowiada raczej takiej konstrukcji:

  int k;
  for(k=0; k<N; k++)
  {
    if(s[k] == 1)
      break;
  }
  //tu coś robię z k

Po usunięciu klamer nawet wizualnie będzie podobne.

Pisalismy o tym, wyglada, ze to robi nic. Moze jakies pozostalosci po debuggowaniu:-)?