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):
- Ciąg
encode
lubdecode
. - Nazwa pliku wejściowego.
- 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).
encode
Operacja konwersji od wybranego formatu audio do formatu skompresowanego „tweet”, a decode
operacja 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
encode
funkcji (i wyjściadecode
funkcji) 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.
Odpowiedzi:
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ż:
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:
Aby uruchomić koder:
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:
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:
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.
źródło
BitOutputStream::close
sposób, o którym zapomniałem zadzwonić. Naprawię kod i zaktualizuję dane wyjściowe.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ł.
Rozszyfrować
Odtwarzanie dekodowanej muzyki
Kod
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
Połączyć
Twinkle, Twinkle Little Star
Połączyć
źródło