Wyszukiwanie powtarzalnych wzorców w plikach

[picorisu]

Cześć
Mam trochę nietypowy problem do rozwiązania. Otóż posiadam sporą ilość (>500) plików zawierających dane, które składają się z powtarzających się sekwencji (tych oczywiście nie znam). Szukam programu który mógłby te sekwencje zidentyfikować i wyodrębnić. Jeśli to coś ułatwi to dodam, że owe dane to 16-bitowy dźwięk. Jednak z uwagi na jego charakter jak i ilość plików nie da się tego zrobić ręcznie w edytorze.
Pewnie dla programisty napisanie programiku który by się z tym w minutę uporał byłoby banalne, niestety ja programistą nie jestem , więc może poleci ktoś jakiegoś gotowca?

[1709]

Napisz coś więcej / dokładniej jak ten program ma działać.
- te wszystkie  (>500) pliki znajdują się w 1 folderze ?
- pliki mają identyczne rozszerzenie w nazwie ?
- powtarzalność ma dotyczyć wszystkich plików ? Czy tylko tam gdzie powturzenie występuje ? (czyli minimum w 2 plikach)
- jaki ma być minimalny zakres powtarzalności ? Jedna minuta  ? 400 znaków ?

[picorisu]

Zakładając że zawartość pliku wygląda tak:

Kod: [Zaznacz]

123456789012345678901234567890

chodzi mi o uzyskanie wynikowego pliku o zawartości:

Kod: [Zaznacz]

1234567890

Przy czym sekwencja powyżej przykładowo podana jako "1234567890" nie jest mi znana, a w zależności od pliku jej długość będzie wynosić od kilkuset bajtów do kilku MB

Pliki są w jednym folderze i mają rozszerzenie wav, ale domyślam się że trzeba będzie je przekonwertować do raw przed rozpoczęciem wyszukiwania. Każda sekwencja jest unikalna dla danego pliku dlatego trzeba ją wykryć.

[1709]

Możesz pobawić się w napisanie skryptu w bash
1. Konwertujesz kazdy plik .wav do hex
2. I porównujesz jakimś bardziej inteligentnym diffem lub algorytmem.

Przykłady masz tutaj jak porównać dwa pliki binarne na różne sposoby
http://superuser.com/questions/125376/how-do-i-compare-binary-files-in-linux

Kurs basha
http://dief.republika.pl/main.html

Kod: [Zaznacz]

 
# a = Lista plików wav
a=$(ls twoja_sciezka_do_katalogu | grep ".wav" )

b=$(ls  twoja_sciezka_do_katalogu | grep ".wav" | wc -l)
# Policzy pliki wav
echo "Plików jest $b"

# petla for wykona sie tyle ile jest 
# razem plików
        for i in `seq 1 $b`
        do

            # linia
            echo "$i"

            # nazwa pliku
            d=$(awk 'NR=='$i <<< "$a")

        for i in `seq 1 $b`
        do

            # nazwa pliku
            c=$(awk 'NR=='$i <<< "$a")
            echo "Porównaj: $d - $c"

	done
        done

Otrzymasz coś takiego

Kod: [Zaznacz]

 ./test
Plików jest 5
1
Porównaj: plik1 (1. kopia).wav - plik1 (1. kopia).wav
Porównaj: plik1 (1. kopia).wav - plik1 (2. kopia).wav
Porównaj: plik1 (1. kopia).wav - plik1 (3. kopia).wav
Porównaj: plik1 (1. kopia).wav - plik1 (4. kopia).wav
Porównaj: plik1 (1. kopia).wav - plik1.wav
2
Porównaj: plik1 (2. kopia).wav - plik1 (1. kopia).wav
Porównaj: plik1 (2. kopia).wav - plik1 (2. kopia).wav
Porównaj: plik1 (2. kopia).wav - plik1 (3. kopia).wav
Porównaj: plik1 (2. kopia).wav - plik1 (4. kopia).wav
Porównaj: plik1 (2. kopia).wav - plik1.wav
3
Porównaj: plik1 (3. kopia).wav - plik1 (1. kopia).wav
Porównaj: plik1 (3. kopia).wav - plik1 (2. kopia).wav
Porównaj: plik1 (3. kopia).wav - plik1 (3. kopia).wav
Porównaj: plik1 (3. kopia).wav - plik1 (4. kopia).wav
Porównaj: plik1 (3. kopia).wav - plik1.wav
4
Porównaj: plik1 (4. kopia).wav - plik1 (1. kopia).wav
Porównaj: plik1 (4. kopia).wav - plik1 (2. kopia).wav
Porównaj: plik1 (4. kopia).wav - plik1 (3. kopia).wav
Porównaj: plik1 (4. kopia).wav - plik1 (4. kopia).wav
Porównaj: plik1 (4. kopia).wav - plik1.wav
5
Porównaj: plik1.wav - plik1 (1. kopia).wav
Porównaj: plik1.wav - plik1 (2. kopia).wav
Porównaj: plik1.wav - plik1 (3. kopia).wav
Porównaj: plik1.wav - plik1 (4. kopia).wav
Porównaj: plik1.wav - plik1.wav

Oczywiście musisz zamiast echo "Porównaj: $d - $c" musisz podać własną komendę  (komendy) lub algorytm do porównania który Ci najbardziej będzie odpowiadał,
lub nawet jeśli chcesz zmienić pętle z for na while.

Kombinuj, a napewno coś wymyślisz.

[picorisu]

Chyba nie do końca się zrozumieliśmy . Zapomnij że jest 500 plików, one nie mają ze sobą żadnego związku i każdy musi być obrobiony indywidualnie. Basha znam na tyle żeby sobie potrafić zautomatyzować cały proces, natomiast pytam o algorytm/program, bo jak już wspomniałem z informatyką nie mam nic wspólnego i stworzenie takowego moje możliwości przerasta. Porównywać nie ma co, bo wzór trzeba najpierw zidentyfikować, a dopiero później wydobyć, jedyne co wiadomo to że się on stale powtarza w pliku.
Może tak będzie latwiej wyjaśnić o co mi chodzi:

Jeśli zdołam ustalić długość wzorca w bajtach/samplach/ms to z resztą już sobie poradzę

[1709]

Mozesz  plik .wav do hex , potem podzielić plik na pakiety ( to zakres ( pakietów ) o którym wspomnialem , od tego zakresu będzie zalezała skuteczność metody )
( przesuwając po bicie dany pakiet ) i porównywać,  jeśli się powtórzy to próbkować w lewo i w prawo po bicie i masz powtórzenie.

PS: Moze spytaj jeszcze na http://forum.audacityteam.org/  to może Ci plugin stworzą.


Edytowane

[ultr]

Czy długość bloku jest znana?
Założę, że nie, choć oczywiście musi być określona (sensowna) długość minimalna.

Jak rozumiem powtórzeń szukamy tylko w ramach danego pliku? A nie we wszystkich?

Program na szybko, ale wygląda, że działa:

Kod: [Zaznacz]

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MIN_BLOCK_LENGTH 5

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("Usage:\n    %s filename\n", argv[0]);
        return 1;
    }

    FILE *f = fopen(argv[1], "rb");

    fseek(f, 0, SEEK_END);
    long size = ftell(f);
    fseek(f, 0, SEEK_SET);

    char *content = malloc(size + 1);
    fread(content, size, 1, f); // assume we can fit the file in the memory
    fclose(f);

    int i = 0; // origin index
    while (i < size - 2 * MIN_BLOCK_LENGTH) {
        int s = i + MIN_BLOCK_LENGTH; // search index
        while (s < size - MIN_BLOCK_LENGTH) {
            if (memcmp(content + i, content + s, MIN_BLOCK_LENGTH) == 0) {
                // we have at least minimum length match
                int length = MIN_BLOCK_LENGTH + 1;
                // check if the match is longer than the minimum
                while (i + length <= s && s + length <= size) {
                    if(memcmp(content + i, content + s, length) != 0) {
                        break;
                    }
                    length++;
                }
                length--; // the loop above ended with a valid value plus one
                // print data for the found repetition and the string itself
                printf("Found %d bytes long repetition"
                       " starting byte %d at byte %d:\n",
                       length, i + 1, s + 1);
                printf("%.*s\n", length, content + i);
                // skip origin index after the found repetition
                i = i + length - 1; // will ++ soon in the outer loop
                break;
            }
            s++; // next search index
        }
        i++; // next origin index
    }

    free(content);

    return 0;
}

Kompilacja:

Kod: [Zaznacz]

gcc findrep.c -o findrep

Odpalanie:

Kod: [Zaznacz]

./findrep plik.wav

Przykładowy plik na wejściu:

Kod: [Zaznacz]

abc1234567890123xyz1234567890123AAAAA111qwerty1234567890123qwerty000abc000AAAAABBBBBBBBBBB

Wyjście:

Kod: [Zaznacz]

Found 13 bytes long repetition starting byte 4 at byte 20:
1234567890123
Found 13 bytes long repetition starting byte 20 at byte 47:
1234567890123
Found 5 bytes long repetition starting byte 33 at byte 75:
AAAAA
Found 6 bytes long repetition starting byte 41 at byte 60:
qwerty
Found 5 bytes long repetition starting byte 80 at byte 85:
BBBBB

[Paweł Kraszewski]

Czy wzór jest generowany, przesyłany, zbierany i przetwarzany cyfrowo? Bo - jak obrazek sugeruje - jeżeli jest to wynik jakiegoś samplowania, to jest problem.

Ze względu na jitter, nierównomierność zegarów generatora i samplera, itp dyrdymały - nawet w przypadku sygnału idealnie okresowego, zrzuty kolejnych okresów nie będą miały takiego samego obrazu binarnego.

Jeżeli sygnał jest czysty, idealny i generowany lokalnie (np zrzut do WAV bezpośrednio z programu muzycznego), to szukanie okresu jest proste - dla sygnału y(0..XX) szukasz takiego n, że y(i)=y(i+n) dla wszystkich i=0..XX-n. Pierw ustawiasz i na 0. Szukasz n takiego, że punkty 0,n,2n,...XX mają tą samą wartość. Jak mają, to sprawdzasz punkt dalej (1,n+1,2n+1, itd). Jak nie wychodzi, to wracasz na początek i sprawdzasz następne n. Jak jest zgodność dla dla wszystkich punktów 0..n-1, to n jest okresem. Algorytm jest szybki, niewiele gorzej od O(n) - ale wymaga idealnych danych.

Jeżeli sygnał nie jest idealny, to możesz pokusić się o analizę autokorelacyjną: bierzesz sygnał i ten sam sygnał przesunięty o n.  Liczysz średni błąd kwadratowy E oryginału i przesuniętego. Dla n równego wielokrotności okresu błąd powinien być minimalny (niekoniecznie równy 0 - to dla przypadku idealnego). Wykres E(n) powinien wyglądać mniej więcej tak: ⋂⋂⋂⋂⋂ , ze szpilkami w dół odpowiadającymi wielokrotnościom okresu. Algorytm jest wolniejszy, O(N²), ale nie wymaga danych idealnych

Możesz zrobić też taką samą analizę dla sygnału stransformowanego przez FFT (autokorelacja transformaty). k*O(N²)+O_transformaty, gdzie k to rozmiar okna transformaty.

Możesz też zrobić transformatę FFT całego pliku naraz (nie szereg transformat z przesuwającym się okienkiem) - w sprzyjających warunkach okres może wyjść jako "pik" na transformacie.

EDIT:

Jak możesz, to wrzuć jeden przykładowy plik.

[picorisu]

Program na szybko, ale wygląda, że działa:

Dzięki, sprawdzę w weekend czy to zadziała

Jak możesz, to wrzuć jeden przykładowy plik.

Dzięki za wskazówki, niestety niewiele z nich rozumiem i sam sobie takiego programu na pewno nie napiszę, ale jeśli komuś temat wydaje się ciekawy to zapraszam do zmierzenia się z nim . A może i inni skorzystają z wyniku tego wyzwania?
Pliki są generowane, a ze specyfikacji teoretycznie wynika że sekwencja powinna być idealnie powtarzalna.
Przykładowy plik: 2A03_N_Long_vF_D.wav]
Ewentualnie inna opcja - może ktoś na bazie tych tajemniczych cyferek potrafi wyliczyć długość sekwencji? ΦωΦ）
http://wiki.nesdev.com/w/index.php/APU_Noise

[Paweł Kraszewski]

Jak możesz, to wrzuć jeden przykładowy plik.

Dzięki za wskazówki, niestety niewiele z nich rozumiem i sam sobie takiego programu na pewno nie napiszę, ale jeśli komuś temat wydaje się ciekawy to zapraszam do zmierzenia się z nim . A może i inni skorzystają z wyniku tego wyzwania?

O_O` Takie coś jest do działu "Bazar/Kupię"

Pliki są generowane, a ze specyfikacji teoretycznie wynika że sekwencja powinna być idealnie powtarzalna.
Przykładowy plik: 2A03_N_Long_vF_D.wav]
Ewentualnie inna opcja - może ktoś na bazie tych tajemniczych cyferek potrafi wyliczyć długość sekwencji? ΦωΦ）
http://wiki.nesdev.com/w/index.php/APU_Noise

Dałeś opis generatora dźwięku w procesorze konsoli NES. W jaki sposób znalazł się on w pliku WAV? No, ale dobrze:

Po analizie autokorelacyjnej pliku wyszło, że powtarzalność nie jest dokładna:

Kod: [Zaznacz]

import scipy.io.wavfile as wf
import matplotlib.pyplot as plt
import numpy as np

# Wczytanie pliku
frq, sound = wf.read("dane.wav")

# Normalizacja na zakres -1.0 .. 1.0
sound = sound / 32768.0

# Ile sampli wycinamy (całość się wolno liczy)
fragment = 400000

# Odkomentuj, jeżeli jendak chcesz liczyć dla całości
# fragment = len(sound)

# Liczymy autokorelację fragmentu
ac = np.correlate(sound[:fragment], sound[:fragment], mode="same")

# Autokorelacja sam ze sobą bez przesunięcia jest w połowie,
# Na lewo i prawo masz przesunięcia w lewo i prawo względem oryginału
# Obraz jest symetryczny, bo to jest autokorealcja, dlatego wycinamy tylko
# "górną" połówkę

acr = ac[fragment // 2:]

# Maksimum jest gdzieś koło 28k
base = 28000

# Szukamy w zakresie base-rang .. base+rang
rang = 2000

# Analiza dla kolejnych harmonicznych:
for harm in range(1, 1 + (len(acr) - rang) // base):

    maxy = -1000.0
    maxx = 0

    for x in range(harm * base - rang, harm * base + rang):
        if acr[x] > maxy:
            maxy = acr[x]
            maxx = x

    print(
        "Harmoniczna %d: Największa korelacja jest dla okresu %d sampli 2-bajtowych (%f)" % (
        harm, maxx / harm, maxy))

# Oś X to przesunięcie kopii i oryginału
x = np.arange(len(acr))

# Rysujemy wykres autokorelacji. Kolejne "piki" opowiadają okresom.
# Piki mają malejącą wysokość, więc dane NIE SĄ IDEALNIE POWTARZALNE
# i szukanie po bajtach nie ma sensu.
plt.plot(x, acr)
plt.show()

Dla Twojego pliku wychodzi "pseudookres" 28119 sampli (56238 bajtów)

[picorisu]

@ultr:
Twój program wykrył mi całą masę małych powtórzeń po kilka-kilkadziesiąt bajtów, jednak nie tego szukamy, poza tym ponieważ powórzenia najwyraźniej nie są idealne to Twoja metoda się nie sprawdzi . Niemniej dzięki za poświęcony czas

@Paweł Kraszewski:
Dane znalazły się w plikach wav poprzez wygenerowanie w famitrackerze, który posiada (podobno) bardzo wierny model tego układu dźwiękowego. Faktycznie dla przykładowego pliku znaleziony okres wydaje się być prawidłowy, jednak dla innych praktycznie nie zmienia się i stale oscyluje w okolicach 28000, a w rzeczywistości różnice powinny być bardzo duże. Sprawdzałem zarówno dla fragmentu jak i całości pliku
Czy da się na podstawie tamtej specyfikacji wyliczyć długość sekwencji dla poszczególnych tonów?

[Paweł Kraszewski]

Tu jest program sam wyszukujący pików (poprzedni mógł pokazywać bzdury jak się żle dobrało base i rang)

Kod: [Zaznacz]

import scipy.io.wavfile as wf
import matplotlib.pyplot as plt
import numpy as np

# Wczytanie pliku
frq, sound = wf.read("dane.wav")

# Normalizacja na zakres -1.0 .. 1.0
sound = sound / 32768.0

# Ile sampli wycinamy (całość się wolno liczy)
fragment = 400000

# Odkomentuj, jeżeli jendak chcesz liczyć dla całości
# fragment = len(sound)

# Liczymy autokorelację fragmentu
ac = np.correlate(sound[:fragment], sound[:fragment], mode="same")

# Autokorelacja sam ze sobą bez przesunięcia jest w połowie,
# Na lewo i prawo masz przesunięcia w lewo i prawo względem oryginału
# Obraz jest symetryczny, bo to jest autokorealcja, dlatego wycinamy tylko
# "górną" połówkę

acr = ac[fragment // 2:]

harm = 0

level = acr[0] / 10

# Szukamy końca 1. piku

# End of peak 1
eop1 = 0

for x in range(0, len(acr)):
    if acr[x] < level:
        # Pierwszy pik kończy się po spadnięciu poziomu do 10%
        eop1 = x
        break

maxy = 0.0
maxx = 0

# Numer peaku
peak = 1

# 0 - jesteśmy w piku
# 1 - jesteśmy między pikami
state = 1
maxy = 0.0
maxx = 0

for x in range(eop1, len(acr)):
    if state == 1:
        # Między pikami - szukamy początku piku
        if acr[x] > 2 * level:
            state = 0
            maxy = 0.0
            maxx = 0
            harm += 1
    else:
        # W piku - szukamy makymalnej wartości
        if acr[x] > maxy:
            maxy = acr[x]
            maxx = x

        # Szukamy końca piku
        if acr[x] < level:
            state = 1
            print(
                "Harmoniczna %d: Największa korelacja jest dla okresu %d sampli 2-bajtowych" % (
                    harm, maxx // harm))
            # Dostrajamy poziom
            level = maxy / 10

# Oś X to przesunięcie kopii i oryginału
x = np.arange(len(acr))

# Rysujemy wykres autokorelacji. Kolejne "piki" opowiadają okresom.
# Piki mają malejącą wysokość, więc dane NIE SĄ IDEALNIE POWTARZALNE
# i szukanie po bajtach nie ma sensu.
plt.plot(x, acr)
plt.show()

[picorisu]

Tu jest program sam wyszukujący pików (poprzedni mógł pokazywać bzdury jak się żle dobrało base i rang)

Niestety nie działa, teraz program zwraca dla różnych plików wartość około 236 sampli, o wiele za małą

[Paweł Kraszewski]

1. "You get what you pay for".
2. Więcej nie zrobię, bo nie mam danych.

[picorisu]

Rozwiązałem problem inną metodą. W każdym razie dzięki za pomoc