To jest wersja audio wyzwania kodowania obrazu na Twitterze .

Zaprojektuj format kompresji dźwięku, który może reprezentować co najmniej jedną minutę muzyki w 140 bajtach lub mniej drukowanego tekstu zakodowanego w UTF-8.

Zaimplementuj go, pisząc program wiersza polecenia, który przyjmuje następujące 3 argumenty (po nazwie samego programu):

1. Ciąg encodelub decode.
2. Nazwa pliku wejściowego.
3. Wyjściowa nazwa pliku.

(Jeśli preferowanemu językowi programowania brakuje możliwości korzystania z argumentów wiersza polecenia, możesz zastosować alternatywne podejście, ale musisz to wyjaśnić w odpowiedzi).

encodeOperacja konwersji od wybranego formatu audio do formatu skompresowanego „tweet”, a decodeoperacja konwersji z formatu „tweet” z oryginalnym formacie audio. (Oczywiście, oczekuje się implementacji kompresji stratnej, więc plik wyjściowy nie musi być identyczny z danymi wejściowymi, tylko w tym samym formacie).

Uwzględnij w swojej odpowiedzi:

• Kod źródłowy twojego programu w całości. (Jeśli ta strona jest za długa, możesz ją hostować w innym miejscu i opublikować link do niej).
• Wyjaśnienie, jak to działa.
• Co najmniej jeden przykład, z linkiem do oryginalnego pliku (plików) audio, tekstem „tweet”, do którego kompresuje, i plikiem audio uzyskanym przez dekodowanie tweeta. (Odpowiadający jest odpowiedzialny za stwierdzenia dotyczące „dozwolonego użytku” praw autorskich).

Zasady

• Zastrzegam sobie prawo do usunięcia luk w regulaminie konkursu w dowolnym momencie.
• [Edytowano 24 kwietnia] Do wprowadzenia encodefunkcji (i wyjścia decodefunkcji) możesz użyć dowolnego rozsądnego, wspólnego formatu audio, niezależnie od tego, czy będzie to:
  • Nieskompresowany przebieg, taki jak WAV.
  • Skompresowany przebieg, taki jak MP3.
  • Styl „nuty”, jak MIDI.
• Twój skompresowany format „tweet” musi faktycznie kodować dźwięki w pliku wejściowym. Tak więc następujące typy wyników nie liczą się:
  • Identyfikator URI lub ścieżka do pliku podająca lokalizację, w której przechowywane są rzeczywiste dane wyjściowe.
  • Klucz do tabeli bazy danych, w której rzeczywiste dane wyjściowe są przechowywane jako obiekt blob.
  • Coś podobnego.
• Twój program musi być zaprojektowany do kompresji ogólnych plików muzycznych, więc nie rób rzeczy, które w oczywisty sposób są powiązane z konkretną przykładową piosenką. Na przykład, jeśli demonstrujesz „Twinkle, Twinkle, Little Star”, twoja procedura kompresji nie powinna zakodować na stałe określonego symbolu dla sekwencji zrób-to-tak-tak-la-la-so.
• Dane wyjściowe Twojego programu powinny być w stanie przejść przez Twittera i wyjść bez szwanku. Nie mam listy obsługiwanych znaków, ale staram się trzymać liter, cyfr, symboli i znaków interpunkcyjnych; i unikaj znaków kontrolnych, łączenia znaków, znaczników BIDI i innych podobnych dziwnych rzeczy.
• Możesz przesłać więcej niż jeden wpis.

Kryteria oceniania

Jest to konkurs popularności (tzn. Wygrywa większość zwycięstw netto), ale wyborcy powinni rozważyć następujące kwestie:

Precyzja

• Czy potrafisz rozpoznać utwór po skompresowaniu?
• Czy to brzmi dobrze?
• Czy nadal potrafisz rozpoznać, na którym instrumencie grasz?
• Czy nadal rozpoznajesz teksty piosenek? (Jest to prawdopodobnie niemożliwe, ale byłoby imponujące, gdyby ktoś to osiągnął).

Złożoność

Wybór przykładowej piosenki ma tutaj znaczenie.

• [Dodano 24 kwietnia] To wyzwanie będzie najłatwiejsze z MIDI lub podobnymi formatami. Jeśli jednak dołożysz wszelkich starań, aby działał z formatami typu falowego, zasługuje to na dodatkowe uznanie.
• Jaka jest struktura Jasne, że możesz spełnić wymóg jednej minuty, po prostu powtarzając te same 4 miary dowolną liczbę razy. Ale bardziej złożone struktury piosenek zasługują na więcej punktów.
• Czy format może obsłużyć wiele nut granych jednocześnie?

Kod

• Utrzymuj to tak krótko i prosto, jak to możliwe. Nie jest to jednak golf golfowy, więc czytelność ma większe znaczenie niż liczba znaków.
• Sprytne, skomplikowane algorytmy też są OK, o ile są uzasadnione lepszą jakością wyników.

Scala

Jasne, łatwiej byłoby zakodować pliki MIDI, ale kto ma w okolicy mnóstwo plików MIDI? To nie jest 1997 rok!

Po pierwsze: postanowiłem zinterpretować „bajt Unicode” jako „znak Unicode” i użyć znaków CJK, ponieważ:

• Pasuje do wyzwania obrazu
• Twitter jest z tym fajny
• I naprawdę potrzebujemy tych bitów

Jest kilka sztuczek, których używam do wyciskania każdej ostatniej kropli entropii ze źródeł:

Po pierwsze, muzyka jest tworzona z nut. Co więcej, ogólnie uważamy tę samą nutę w innej oktawie za tę samą nutę (dlatego 12-strunowa gitara brzmi dobrze), więc mamy tylko 12 możliwości kodowania. (kiedy na przykład wyprowadzam B, tak naprawdę generuję akord składający się wyłącznie z B we wszystkich oktawach, trochę jak gitara 12-strunowa).

Następnie pamiętam z licealnej klasy muzycznej, że większość przejść nutowych jest niewielka (jedna nuta w górę lub w dół). Skoki są mniej powszechne. To mówi nam, że prawdopodobnie rozmiary entropii są mniejsze niż w samych nutach.

Nasze podejście polega na rozbiciu źródła na kilka bloków - stwierdziłem, że 14 bloków na sekundę działało dobrze (uwaga, zawsze zastanawiałem się, dlaczego dźwięk był kodowany przy częstotliwości 44100 Hz. Okazuje się, że 44100 ma wiele czynników, więc mógłbym wybrać 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 25, 28 lub 30 bloków na sekundę, i podzieliłby się czysto ). Następnie FFT bloków (cóż, technicznie nie jest szybki, ponieważ biblioteka, której użyłem, nie jest szybka dla bloków bez potęgi 2. I technicznie użyłem transformacji Hartleya , a nie Fouriera).

Następnie znajdujemy nutę, która brzmi najgłośniej (zastosowałem A-ważenie , z wysokimi i niskimi odcięciami, głównie dlatego, że jest najłatwiejsza do wdrożenia), i albo kodujemy tę nutę, albo kodujemy ciszę (wykrywanie ciszy opiera się na SNR - niski SNR to cisza).

Następnie tłumaczymy nasze zakodowane nuty na skoki i podajemy je do adaptacyjnego kodera arytmetycznego. Proces tłumaczenia na tekst jest podobny do pytania o kompresję obrazu (ale wiąże się z pewnym niewłaściwym użyciem BigInteger).

Jak dotąd tak dobrze, ale co jeśli próbka ma zbyt dużo entropii? Używamy prymitywnego modelu psychoakustycznego, aby go usunąć. Najniższym skokiem entropii jest „bez zmian”, więc patrzymy na nasze dane FFT, aby spróbować znaleźć bloki, w których słuchacz prawdopodobnie nie zauważy, jeśli będziemy kontynuować odtwarzanie poprzedniej nuty, szukając bloków, w których nuta z poprzedniego bloku jest prawie tak głośno, jak najgłośniejsza nuta (gdzie „prawie” jest kontrolowane przez parametr jakości).

Mamy więc cel 140 znaków. Zaczynamy od kodowania w jakości 1.0 (maksymalna jakość) i sprawdzamy, ile to znaków. Jeśli jest ich zbyt wiele, spadamy do 0,95 i powtarzamy, aż dojdziemy do 140 znaków (lub poddamy się po jakości 0,05). To sprawia, że ​​enkoder jest enkoderem n-pass, dla n <= 20 (chociaż jest on bardzo nieefektywny również w innych obszarach, więc m'eh).

Koder / dekoder oczekuje dźwięku w formacie mono s16be. Można to osiągnąć za pomocą avconv jako:

#decoding ogg to s16be, and keeping only the first 60s
avconv -i input.ogg -ac 1 -ar 44100 -f s16be -t 60s input.raw
#encoding s16be to mp3
avconv -f s16be -ac 1 -ar 44100 -i output.raw output.mp3

Aby uruchomić koder:

sbt "run-main com.stackexchange.codegolf.twelvestring.TwelveString encode input.raw encoded.txt"
sbt "run-main com.stackexchange.codegolf.twelvestring.TwelveString decode encoded.txt output.raw"

Pełny kod na https://github.com/jamespic/twelvestring .

Pułapka, na którą należy zwrócić uwagę: będziesz potrzebować biblioteki arytmetycznej kodowania nayuki, która obecnie nie ma dostępnych artefaktów Maven. Zamiast tego musisz lokalnie zbudować i zainstalować rozwidlenie dewelopera .

A oto kilka próbek. Brzmią okropnie, ale prawie rozpoznawalne:

• Beethoven's 5th: original , encoded - 刲 檁 囉 罓 罓 佖 镱 賑 皌 蝩 蔲 恁 峕 逊 躹 呯 呯 笲 銗 娵 纜 庬 庬 一 掛 獴 趤 趤 笲 銗 娵 喫 喫 覤 粠 僭 嫭 裵 裵 獄 鱨 蠰 儏 咍 箪姑 椻 趕 挍 呪 白 鸞 盙 宠 埘 謭 擆 擆 脲 誜 笸 囃 囃 庣 稨 稨 俖 咛 脔 湙 弻 籚 砌 鍖 裏 橈 橈 镙 镙 鹻 塿 塿 骱 踠 筟 七 七 趇 杅 峇 敖 敖 窈 裞 瘫 櫬 咰 咰茏 蛏 姆 臸 胝 婁 遼 憀 麁 黦 掏 毈 喙 眝 綄 鴀 耢 椚 筤 菮 蟞 斗 斗 湛 营 筬 禴 籙 嬧 窻 丄
• Fur Elise: original , encoded - 訖 忢 擫 鏝 拪 纒 纒 铇 鯪 薯 鉰 孝 暱 埛 痏 絘 僌 莻 莻 饚 緂 緂 婘 婘 譮 蠣 託 騶 騶 腀 饚 緂 柤 碠 瞢 瞢 碩 脅 歙 棆 敗 敗 冏 冏 鄔 酾 萖苯 劺 誺 軩 忇 穤 锳 婁 伉 巠 桭 桭 晘 酉 怚 尵 鎽 蜓 蜓 崁 飿 飿 但 鈐 謽 酝 屮 呤 呤 誥 俊 覊 覊 覊 龔 癸 埙 煂 臙 臙 牎 繬 肜 摲 摲 炚 雗 頨 菩 凧 燈 燈 楾媡 夥 俰 欓 焵 韀 冊 嗥 燠 鱧 駟 髉
• Twinkle Twinkle Little Star: oryginalne , zakodowane - 欠 悺 矜 矜 莳 錥 鷗 谴 裴 皽 鳺 憝 漿 箔 皇 殤 鸧 蜻 猻 丱
• Zabawny chiptuna: oryginalny , zakodowany - 简 詐 諥 尘 牿 牿 扫 鲑 龮 箫 颫 齰 蠏 騁 煟 靸 阒 阒 觲 沠 丆 贀 芉 馄 鈿 鈿 鬦 嶏 觲 沠 丆 贀 蛑 蛀 蛀 漥 荤 侲 咔 咔 桬 桬 鲠 僵 擕灼 攲 陇 亄 鹘 琾 業 纟 鵼 牤 棌 匩 匩 踬 葫 欃 铳 铳 樯 柇 柇 鋡 疡 衻 澯 伅 墇 搢 囻 荸 香 香 貱 貱 咽 蟽 蟽 籐 屈 锂 蛉 蛉 袒 貊 屨 鈦 鈦 夜 镤 沄 骬 唦 唦乔 蚖 醶 矕 咻 喸 碋 利 褼 裊 匎 嶮 嶮 幘 六 沧 鼝 瞮 坡 葍 帷 帷 锆 邵 旻 符 琨 鱴 郤 栱 烇 仾 椃 椃 荄 荄 嘵 統 篏 珆 罽

Aktualizacja

Poprawiłem próg ciszy w kodzie i ponownie zakodowałem. Kodowania zostały odpowiednio zaktualizowane. Dodałem też inny utwór (technicznie nie jest to oprogramowanie typu open source, ale wątpię, by pierwotny właściciel praw autorskich poczuł, że jego adres IP jest zagrożony), dla zabawy:

• Imperial March: oryginalny , zakodowany - 岼 讶 湠 衢 嫵 焅 喋 喋 霔 憣 嗗 嗗 橳 蕖 匵 腾 嗅 嗅 鈪 俚 俚 戂 冂 冂 常 僠 寝 寝 萉 乹 俚 戂 闤 灈 蟑 蟑 拷 盒 音 褈 褈 霈 媬 盒 萳 璥唂 焰 銯 艉 鶱 縩 巻 痭 虊 窻 熲 紆 紆 耺 淙 庸 锺 禒 禒 旇 旇 蘄 遪 遪 刨 繱 蕖 嬯 摺 祑 仰 仰 軈 軈 杊 瘷 棏 郖 弘 弘 卄 浕 眮 眮 騜 阖 阖 鶺 鶺 艂 税 寛 寛採 偋 隆 兎 豅 蚦 紛 襈 洋 折 踜 跅 跅 树 爺 奘 庄 玫 亳 攩 獼 獼 匑 仡 葾 昐 炡 瞱 咏 斎 煟 价 藭 藭 恐 鷖 璌 榍 脅 樐 樐 嬨 勀 茌 愋

Więcej aktualizacji

Ulepszyłem trochę koder i miał on zaskakujący wpływ na jakość (zapomniałem, że w DHT sygnały poza fazą są faktycznie ujemne, więc ignorowałem sygnały poza fazą).

Wcześniejsza wersja kodu po prostu pobierała większy z tych sygnałów niefazowych, ale teraz bierzemy RMS. Dodałem także dość konserwatywną funkcję okna do kodera (Tukey, alfa 0.3), aby spróbować zwalczyć artefakty.

Wszystko jest odpowiednio aktualizowane.

Pyton

Nie robię żadnego specjalnego manipulowania w odniesieniu do UTF-8, więc moje zgłoszenie przekracza wymóg 140 bajtów. Nie twierdzę, że moje rozwiązanie jest użyteczne, dokładne lub skuteczne.

Użyłem częstotliwości próbkowania 44100 Hz dla wejścia i wyjścia. SAMPLES_PER_BYTE kontroluje jakość konwersji. Im niższa liczba, tym lepsza jakość dźwięku. Wartości, których użyłem, podano w sekcji wyników.

Stosowanie

Kodować

Plik wejściowy powinien być wav. Koduje tylko pierwszy kanał.

twusic.py -e [input file] > output.b64

Rozszyfrować

twusic.py -d [input file] > output.raw

Odtwarzanie dekodowanej muzyki

aplay -f U8 --rate=[rate of input file] output.raw

Kod

#!/usr/bin/env python
SAMPLES_PER_BYTE = 25450

from math import sin, pi, log
from decimal import Decimal

PI_2 = Decimal(2) * Decimal(pi)

FIXED_NOTE = Decimal('220') # A
A = Decimal('2') ** (Decimal('1') / Decimal('12'))
A_LN = A.ln()

def freq(note):
    return FIXED_NOTE * (A ** Decimal(note))

def note(freq):
    return (Decimal(freq) / FIXED_NOTE).ln() / A_LN

VOLUME_MAX = Decimal('8')
def volume(level):
    return Decimal('127') * (Decimal(level+1).ln() / VOLUME_MAX.ln())

def antivolume(level):
    x = Decimal(level) / Decimal('127')
    y = VOLUME_MAX ** x
    return y - 1

NOTES = [freq(step) for step in xrange(-16, 16)]
VOLUMES = [volume(level) for level in xrange(0, VOLUME_MAX)]


def play(stream, data):
    t = 0
    for x in data:
        x = ord(x)
        w = PI_2 * NOTES[(x&0xf8) >> 3] / Decimal(16000)
        a = float(VOLUMES[x&0x07])
        for _ in xrange(0, SAMPLES_PER_BYTE):
            stream.write(chr(int(128+(a*sin(w*t)))))
            t += 1

NOTE_MAP = {'A': 0b00000000,
    'g': 0b00001000,
    'G': 0b00010000,
    'f': 0b00011000,
    'F': 0b00100000,
    'E': 0b00101000,
    'd': 0b00110000,
    'D': 0b00111000,
    'c': 0b01000000,
    'C': 0b01001000,
    'B': 0b01010000,
    'a': 0b01011000}

def convert(notes, volume):
    result = []
    for n in notes:
        if n == ' ':
            result += '\00'
        else:
            result += chr(NOTE_MAP[n] | (volume & 0x07)) * 2
    return ''.join(result)

TWINKLE = convert('C C G G A A GG' +
                    'F F E E D D CC' +
                    'G G F F E E DD' +
                    'G G F F E E DD' +
                    'C C G G A A GG' +
                    'F F E E D D CC', 0x7)

if __name__ == '__main__':
    from base64 import b64encode, b64decode
    import numpy as np
    from numpy.fft import fft, fftfreq
    import wave
    import sys

    if len(sys.argv) != 3:
        print 'must specify -e or -d plus a filename'
        sys.exit(1)

    if sys.argv[1] == '-e':
        w = wave.open(sys.argv[2], 'rb')

        try:
            output = []
            (n_channels, sampwidth, framerate, n_frames, comptype, compname) = w.getparams()
            dtype = '<i' + str(sampwidth)

            # Find max amplitude
            frames = np.abs(np.frombuffer(w.readframes(n_frames), dtype=dtype)[::n_channels])
            max_amp = np.percentile(frames, 85)

            w.rewind()

            read = 0
            while read < n_frames:
                to_read = min(n_frames-read, SAMPLES_PER_BYTE)
                raw_frames = w.readframes(to_read)
                read += to_read

                frames = np.frombuffer(raw_frames, dtype=dtype)[::n_channels]
                absolute = np.abs(frames)
                amp = np.mean(absolute)

                amp = int(round(antivolume(min((amp / max_amp) * 127, 127))))

                result = fft(frames)
                freqs = fftfreq(len(frames))

                while True:
                    idx = np.argmax(np.abs(result)**2)
                    freq = freqs[idx]
                    hz = abs(freq * framerate)
                    if hz > 0:
                        break
                    result = np.delete(result, idx)
                    if len(result) <= 0:
                        hz = 220
                        amp = 0
                        break

                n = int(round(note(hz)))
                n &= 0x1F
                n <<= 3
                n |= amp & 0x07
                output.append(chr(n))
        finally:
            w.close()
        print b64encode(''.join(output)).rstrip('=')
    else:
        with open(sys.argv[2], 'rb') as f:
            data = f.read()
        data = data + '=' * (4-len(data)%4)
        play(sys.stdout, b64decode(data))

Wejścia

Moje oficjalne zgłoszenie to Impromptu dla Pianoforte i Beatbox autorstwa Kevina MacLeoda . Do tego pliku użyłem SAMPLES_PER_BYTE z 25450.

Pozwoliłem sobie również na kodowanie Twinkle, Twinkle, Little Star za pomocą SAMPLES_PER_BYTE 10200. Brzmi znacznie lepiej.

Wyjście

Impromptu dla Pianoforte i Beatbox

aWnxQDg4mWqZWVl6W+LyOThfHOPyQThAe4x5XCqJK1EJ8Rh6jXt5XEMpk1Epe5JqTJJDSisrkkNCSqnSkkJDkiorCZHhCxsq8nlakfEp8vNb8iqLysp6MpJ7s4x7XlxdW4qKMinJKho

Połączyć

Twinkle, Twinkle Little Star

HBobGlJSUlJSY2FlYVNRUVFCQkJCQjs5PDksKisqGxoZGVFTUVNRREFDQjs6OjoqKykpKVRRVFJDQkJCOjs6OzksKikpGxobG1JSUlNRZWFlYVNSUVFCQkJDQTw5PDorKisqGhsZGRk

Połączyć