Ini adalah versi audio dari tantangan penyandian gambar Twitter .

Rancang format kompresi audio yang dapat mewakili setidaknya satu menit musik dalam 140 byte atau kurang dari teks berkode UTF-8 yang dapat dicetak.

Menerapkannya dengan menulis program baris perintah yang mengambil 3 argumen berikut (setelah nama program itu sendiri):

1. String encodeatau decode.
2. Nama file input.
3. Nama file keluaran.

(Jika bahasa pemrograman pilihan Anda tidak memiliki kemampuan untuk menggunakan argumen baris perintah, Anda dapat menggunakan pendekatan alternatif, tetapi harus menjelaskannya dalam jawaban Anda.)

The encodeoperasi akan mengkonversi dari format audio Anda memilih untuk dikompresi “Tweet” format Anda, dan decodeoperasi akan mengkonversi dari “Tweet” format ke format audio asli. (Tentu saja, Anda diharapkan untuk menerapkan kompresi lossy, sehingga file output tidak harus identik dengan input, hanya dalam format yang sama.)

Sertakan dalam jawaban Anda:

• Kode sumber program Anda, secara penuh. (Jika terlalu lama untuk halaman ini, Anda dapat meng-host-nya di tempat lain dan memposting tautan ke sana.)
• Penjelasan tentang cara kerjanya.
• Setidaknya satu contoh, dengan tautan ke file audio asli, teks "tweet" yang dimampatkan, dan file audio diperoleh dengan mendekode tweet. (Penjawab bertanggung jawab atas pernyataan “penggunaan wajar” hak cipta.)

Aturan

• Saya berhak untuk menutup celah dalam peraturan kontes kapan saja.
• [Diedit 24 April] Untuk input encodefungsi Anda (dan output decodefungsi Anda ), Anda dapat menggunakan format audio umum yang masuk akal, apakah itu:
  • Gelombang terkompresi, seperti WAV.
  • Gelombang terkompresi, seperti MP3.
  • Gaya "Lembaran musik", seperti MIDI.
• Format "tweet" terkompresi Anda harus benar-benar menyandikan suara dalam file input. Jadi, tipe-tipe output berikut ini tidak masuk hitungan:
  • URI atau jalur file yang memberikan lokasi penyimpanan output aktual.
  • Kunci ke tabel database di mana output aktual disimpan sebagai gumpalan.
  • Ada yang mirip.
• Program Anda harus dirancang untuk mengompres file musik umum , jadi jangan lakukan hal-hal yang terlalu jelas terkait dengan lagu contoh spesifik Anda. Misalnya, jika Anda mendemonstrasikan "Twinkle, Twinkle, Little Star", rutinitas kompresi Anda seharusnya tidak membuat hard-code simbol khusus untuk urutan do-do-so-la-la-so.
• Output program Anda seharusnya benar-benar dapat melalui Twitter dan keluar tanpa cedera. Saya tidak memiliki daftar karakter persis yang didukung, tetapi cobalah untuk tetap berpegang pada huruf, angka, simbol, dan tanda baca; dan menghindari karakter kontrol, menggabungkan karakter, penanda BIDI, atau hal-hal aneh lainnya seperti itu.
• Anda dapat mengirimkan lebih dari satu entri.

Kriteria penilaian

Ini adalah kontes popularitas (yaitu, sebagian besar upvote bersih menang), tetapi pemilih didorong untuk mempertimbangkan hal berikut:

Ketepatan

• Masih bisakah Anda mengenali lagu itu setelah dikompres?
• Apakah itu terdengar bagus?
• Masih bisakah Anda mengenali instrumen yang sedang dimainkan?
• Masih bisakah Anda mengenali liriknya? (Ini mungkin tidak mungkin, tetapi akan mengesankan jika ada yang menyelesaikannya.)

Kompleksitas

Pilihan contoh lagu penting di sini.

• [Ditambahkan 24 April] Tantangan ini akan paling mudah dengan MIDI atau format serupa. Namun, jika Anda melakukan upaya ekstra untuk membuatnya berfungsi dengan format tipe gelombang, itu layak mendapatkan kredit ekstra.
• Apa strukturnya? Tentu, Anda dapat memenuhi persyaratan satu menit dengan hanya mengulangi 4 langkah yang sama beberapa kali secara acak. Tetapi struktur lagu yang lebih kompleks layak mendapat poin lebih banyak.
• Bisakah format menangani banyak catatan yang dimainkan sekaligus?

Kode

• Buatlah sesingkat dan sesederhana mungkin. Namun, ini bukan kode golf, jadi keterbacaan lebih penting daripada jumlah karakter.
• Algoritma yang cerdas dan rumit juga OK, asalkan dibenarkan oleh peningkatan kualitas hasil.

Scala

Tentu, akan lebih mudah untuk menyandikan file MIDI, tetapi siapa yang punya banyak file MIDI? Ini bukan tahun 1997!

Hal pertama yang pertama: Saya telah memutuskan untuk menafsirkan "byte Unicode" sebagai "Unicode char" dan menggunakan karakter CJK, karena:

• Ini cocok dengan tantangan gambar
• Twitter keren dengan itu
• Saya benar - benar membutuhkan bit-bit itu

Ada beberapa trik yang saya gunakan untuk memeras setiap tetes terakhir entropi dari sumber:

Pertama, musik dibuat dengan catatan. Selain itu, kami umumnya menganggap nada yang sama dalam oktaf berbeda sebagai nada yang sama (itulah sebabnya gitar 12-string terdengar benar), jadi kami hanya memiliki 12 kemungkinan untuk menyandikan. (ketika saya output B, misalnya, saya benar-benar output chord, yang hanya terdiri dari B di semua oktaf, sedikit seperti gitar 12-string).

Selanjutnya, saya ingat dari kelas musik sekolah menengah bahwa kebanyakan transisi nada adalah kecil (naik atau turun satu nada). Lompatan kurang umum. Ini memberitahu kita bahwa mungkin ada lebih sedikit entropi dalam ukuran lompatan daripada di catatan itu sendiri.

Jadi, pendekatan kami adalah memecah sumber kami menjadi sejumlah blok - Saya menemukan 14 blok per detik bekerja dengan baik (catatan, saya selalu bertanya-tanya mengapa audio dikodekan pada 44100 Hz. Ternyata 44100 memiliki banyak faktor, jadi saya bisa memilih 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 25, 28 atau 30 blok per detik, dan itu akan dibagi dengan bersih ). Kami kemudian FFT blok ini (baik, secara teknis tidak cepat, karena perpustakaan yang saya gunakan tidak cepat untuk non-power-of-2 blok. Dan secara teknis saya menggunakan transformasi Hartley , bukan Fourier).

Kami kemudian menemukan catatan yang terdengar paling keras (saya menggunakan A-weighting , dengan cut-off tinggi dan rendah, sebagian besar karena paling mudah untuk diterapkan), dan menyandikan catatan ini, atau menyandikan diam (pendeteksian diam didasarkan pada SNR - SNR rendah diam).

Kami kemudian menerjemahkan catatan kami yang dikodekan ke dalam lompatan, dan memberi mereka ke kode aritmatika adaptif. Proses penerjemahan ke teks mirip dengan pertanyaan kompresi gambar (tetapi melibatkan beberapa penggunaan BigInteger yang kasar).

Sejauh ini, sangat bagus, tetapi bagaimana jika sampel memiliki terlalu banyak entropi? Kami menggunakan model psikoakustik kasar untuk menghapus beberapa. Lompatan entropi terendah adalah "tidak ada perubahan", jadi kami melihat data FFT kami untuk mencoba menemukan blok di mana pendengar mungkin tidak akan melihat jika kami terus memutar catatan sebelumnya, dengan mencari blok di mana catatan dari blok sebelumnya adalah hampir sekeras not paling keras (di mana "hampir" dikendalikan oleh parameter kualitas).

Jadi, kami punya target 140 karakter. Kami mulai dengan penyandian pada kualitas 1.0 (kualitas maks), dan melihat berapa banyak karakter yang ada. Jika terlalu banyak, kita turun menjadi 0,95 dan mengulang, sampai kita mencapai 140 karakter (atau kita menyerah setelah kualitas 0,05). Ini membuat encoder menjadi n-pass encoder, untuk n <= 20 (meskipun secara besar-besaran juga tidak efisien, jadi m'eh).

Encoder / decoder mengharapkan audio dalam format mono s16be. Ini dapat dicapai dengan menggunakan avconv sebagai:

#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

Untuk menjalankan encoder:

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"

Kode lengkap di https://github.com/jamespic/twelvestring .

Pitfall yang perlu diperhatikan: Anda perlu pustaka Aritmatika Pengkodean nayuki, yang saat ini tidak memiliki artefak Maven. Alih-alih, Anda harus membuat dan menginstal fork forster secara lokal .

Dan ini beberapa contoh. Kedengarannya mengerikan, tetapi hanya bisa dikenali:

• Beethoven ke-5: asli , disandikan - 刲 檁 囉 罓 佖 镱 賑 蝩 蝩 蔲 峕 逊 呯 兲 兲 搆 蝺 蝺 筶 筶 一 一 一 趤 笲 僭 僭 獄 儏 儏 儏 儏 儏 儏 儏 儏 儏 儏 eth姑 椻 趕 挍 呪 鸞 鸞 盙 宠 埘 謭 擆 闯 脲 誜 忘 忘 笸 囃 俖 俖 咛 咛 咛 湙 弻 弻 弻 鍖 訁 訁 訁 鹻 趇 趇 趇 杅 櫬 峦 峦 峦 峦 峦 峦 峦 峦 峦 峦 峦 峦 峦 峦 峦 窈茏 蛏 姆 臸 胝 婁 遼 憀 憀 麁 黦 掏 毈 眝 綄 綄 鴀 耢 椚 筤 筤 斗 斗 斗 俼 俼 湛 营 营 筬 筬 筬 嬧 嬧 窻 丄 丄
• Fur Elise: asli , disandikan - 訖 忢 擫 鏝 拪 纒 铇 鯪 鉰 孝 孝 埛 痏 痏 莻 莻 暆 暆 屖 鳮 鳮 鳮 蠣 騶 腀 腀 饚 饚 脅 脅 敗 萖 萖 萖 萖 鄔 萖 冏 萖 萖 冏 鄔苯 劺 誺 軩 忇 锳 锳 婁 伉 巠 桭 晘 晘 筟 緵 俅 俅 尵 鎽 飿 飿 嘔 嘔 鈐 鈐 謽 謽 謽 誥 鶮 鶮 鶮 龔 繬 繬 繬 肜 摲 楾 咁 咁 咁 咁 楾 咁 楾 楾 咁 凧 楾 凧 楾 楾 楾 楾 凧媡 夥 俰 欓 焵 韀 冊 嗥 嗥 燠 鱧 駟 髉
• Twinkle Twinkle Little Star: asli , disandikan - 欠 悺 矜 莳 錥 鷗 谴 裴 裴 皽 鳺 憝 憝 漿 皇 殤 殤 殤 鸧 鸧 蜻 猻 丱
• Chiptune yang menyenangkan: asli , disandikan - 简 詐 諥 尘 牿 扫 鲑 箫 颫 颫 蠏 蠏 阒 阒 阒 萎 萎 鮇 雝 雝 雝 芉 鬦 嶏 嶏 觲 觲 漥 漥 咔 僵 擕 鲠 桬 擕 桬 鲠 桬 鲠 桬 桬 擕灼 攲 陇 亄 鹘 業 業 纟 鵼 牤 棌 匩 碆 踬 葫 鶙 鶙 欃 铳 鋡 鋡 疡 疡 疡 澯 伅 伅 伅 囻 夹 夹 夹 咽 袒 袒 袒 貊 骬 鍡 鍡 鍡 鍡 鍡 鍡 鍡 鍡 鍡 鍡 鍡 鍡 鍡 鍡 鍡 夜乔 蚖 醶 矕 咻 喸 碋 利 褼 裊 裊 匎 嶮 幘 六 六 沧 鼝 瞮 坡 锆 锆 邵 邵 旻 符 符 琨 琨 琨 烇 仾 椃 椃 騋 荄 嘵 篏 罽 罽 罽

Memperbarui

Saya mengubah ambang keheningan dalam kode, dan menyandikan ulang. Pengkodean telah diperbarui sesuai. Juga, saya menambahkan lagu lain (secara teknis bukan open source, tapi saya ragu pemegang hak cipta asli akan merasa IP mereka di bawah ancaman), hanya untuk bersenang-senang:

• Imperial March: asli , disandikan - 岼 讶 湠 衢 嫵 焅 喋 藭 霔 嗗 嗗 橳 蕖 蕖 嗅 鈪 鈪 鈪 芔 顕 顕 樭 樭 常 萉 萉 萉 乹 俚 拷 邢 霈 璥 璥 璥 盒 盒 璥 盒 璥 璥 盒 璥唂 焰 銯 艉 鶱 巻 巻 痭 虊 窻 熲 紆 耺 哅 淙 苉 苉 庸 锺 蘄 蘄 籷 籷 籷 刨 繱 繱 繱 摺 牰 牰 牰 杊 浕 浕 浕 眮 菸 税 税 税 税採 偋 隆 兎 豅 蚦 紛 襈 洋 折 折 跅 跅 树 爺 爺 奘 庄 玫 亳 匑 匑 仡 仡 仡 昐 炡 炡 炡 煟 煟 价 价 价 价 恐 恐 璌 嬨 勀 茌 愋 愋 愋

Lebih Banyak Pembaruan

Saya telah sedikit mengubah encoder, dan ini berdampak mengejutkan pada kualitas (saya lupa bahwa di DHT, sinyal out-of-phase efektif negatif, jadi saya mengabaikan sinyal out-of-phase).

Versi sebelumnya dari kode hanya mengambil yang lebih besar dari sinyal-sinyal di luar fase ini, tetapi kami sekarang mengambil RMS. Juga, saya menambahkan fungsi jendela yang cukup konservatif ke encoder (Tukey, alpha 0,3), untuk mencoba memerangi artefak.

Semuanya diperbarui sesuai.

Python

Saya tidak melakukan mangling khusus sehubungan dengan UTF-8, jadi kiriman saya melewati persyaratan 140 byte. Saya tidak membuat klaim tentang kegunaan, keakuratan, atau efisiensi solusi saya.

Saya menggunakan sample rate 44100 Hz untuk input dan output. SAMPLES_PER_BYTE mengontrol kualitas konversi. Semakin rendah angkanya, semakin baik kualitas suaranya. Nilai yang saya gunakan diberikan di bagian hasil.

Pemakaian

Menyandi

File input harus berupa wav. Ini hanya mengkodekan saluran pertama.

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

Membaca sandi

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

Memutar Musik yang Didekodekan

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

Kode

#!/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))

Input

Kiriman resmi saya adalah Impromptu untuk Pianoforte dan Beatbox oleh Kevin MacLeod . Untuk file ini saya menggunakan SAMPLES_PER_BYTE dari 25450.

Saya juga mengambil kebebasan menyandikan Twinkle, Twinkle, Little Star dengan SAMPLES_PER_BYTE dari 10200. Kedengarannya jauh lebih baik.

Hasil

Dadakan untuk Pianoforte dan Beatbox

aWnxQDg4mWqZWVl6W+LyOThfHOPyQThAe4x5XCqJK1EJ8Rh6jXt5XEMpk1Epe5JqTJJDSisrkkNCSqnSkkJDkiorCZHhCxsq8nlakfEp8vNb8iqLysp6MpJ7s4x7XlxdW4qKMinJKho

Link

Twinkle, Twinkle Little Star

HBobGlJSUlJSY2FlYVNRUVFCQkJCQjs5PDksKisqGxoZGVFTUVNRREFDQjs6OjoqKykpKVRRVFJDQkJCOjs6OzksKikpGxobG1JSUlNRZWFlYVNSUVFCQkJDQTw5PDorKisqGhsZGRk

Link