Esta é a versão em áudio do desafio de codificação de imagens do Twitter .

Crie um formato de compactação de áudio que possa representar pelo menos um minuto de música em 140 bytes ou menos de texto codificado em UTF-8 imprimível.

Implemente-o escrevendo um programa de linha de comando que use os três argumentos a seguir (após o nome do próprio programa):

1. A sequência encodeou decode.
2. O nome do arquivo de entrada.
3. O nome do arquivo de saída.

(Se sua linguagem de programação preferida não possui a capacidade de usar argumentos de linha de comando, você pode usar uma abordagem alternativa, mas deve explicá-la em sua resposta.)

A encodeoperação será convertida do formato de áudio escolhido para o formato compactado de "tweet" e a decodeoperação será convertida do formato de "tweet" para o formato de áudio original. (Obviamente, você deve implementar a compactação com perdas, para que o arquivo de saída não precise ser idêntico à entrada, apenas no mesmo formato.)

Inclua na sua resposta:

• O código fonte do seu programa, na íntegra. (Se for muito longo para esta página, você pode hospedá-la em outro lugar e postar um link para ela.)
• Uma explicação de como isso funciona.
• Pelo menos um exemplo, com um link para o (s) arquivo (s) de áudio original (s), o texto do “tweet” que ele compacta e o arquivo de áudio obtido pela decodificação do tweet. (O respondente é responsável pelas afirmações de "uso justo" dos direitos autorais.)

Regras

• Reservo-me o direito de fechar as brechas nas regras do concurso a qualquer momento.
• [Editado em 24 de abril] Para a entrada de sua encodefunção (e a saída de sua decodefunção), você pode usar qualquer formato de áudio comum e razoável, seja ele:
  • Forma de onda não compactada, como WAV.
  • Forma de onda compactada, como MP3.
  • Estilo "Partituras", como MIDI.
• Seu formato "tweet" compactado deve realmente codificar os sons no arquivo de entrada. Portanto, os seguintes tipos de saída não contam:
  • Um caminho de arquivo ou URI que fornece o local onde a saída real está armazenada.
  • Uma chave para uma tabela de banco de dados onde a saída real é armazenada como um blob.
  • Qualquer coisa parecida.
• Seu programa deve ser projetado para compactar arquivos de música genéricos ; portanto, não faça coisas que obviamente estejam ligadas ao seu exemplo específico de música. Por exemplo, se você está demonstrando "Twinkle, Twinkle, Little Star", sua rotina de compactação não deve codificar um símbolo específico para a sequência faça-o-lo-la-la-lo.
• A saída do seu programa deve ser capaz de passar pelo Twitter e sair ilesa. Não tenho uma lista dos caracteres exatos suportados, mas tente seguir letras, dígitos, símbolos e pontuação; e evite caracteres de controle, combinando caracteres, marcadores BIDI ou outras coisas estranhas como essa.
• Você pode enviar mais de uma entrada.

Critérios de julgamento

Este é um concurso de popularidade (ou seja, a maioria das vitórias líquidas), mas os eleitores devem considerar o seguinte:

Precisão

• Você ainda consegue reconhecer a música depois de comprimida?
• Isso soa bem?
• Você ainda consegue reconhecer quais instrumentos estão sendo tocados?
• Você ainda consegue reconhecer a letra? (Isso provavelmente é impossível, mas seria impressionante se alguém conseguisse.)

Complexidade

A escolha da música de exemplo é importante aqui.

• [Adicionado em 24 de abril] Este desafio será mais fácil com formatos MIDI ou similares. No entanto, se você fizer um esforço extra para fazê-lo funcionar com formatos do tipo de forma de onda, isso merece crédito extra.
• Qual é a estrutura? Claro, você pode atender ao requisito de um minuto simplesmente repetindo as mesmas quatro medidas um número arbitrário de vezes. Mas estruturas musicais mais complexas merecem mais pontos.
• O formato pode lidar com muitas notas sendo tocadas ao mesmo tempo?

O código

• Mantenha-o o mais curto e simples possível. No entanto, como este não é um código de golfe, a legibilidade importa mais do que a contagem de caracteres.
• Algoritmos inteligentes e complicados também são bons, desde que justificados pela melhoria da qualidade dos resultados.

Scala

Claro, seria mais fácil codificar arquivos MIDI, mas quem tem um monte de arquivos MIDI por aí? Não é 1997!

Primeiras coisas: decidi interpretar um "byte Unicode" como um "caractere Unicode" e usar caracteres CJK, porque:

• Corresponde ao desafio da imagem
• Twitter é legal com isso
• Eu realmente preciso desses bits

Existem alguns truques que eu uso para extrair toda última gota de entropia das fontes:

Em primeiro lugar, a música é feita com anotações. Além disso, geralmente consideramos a mesma nota em uma oitava diferente da mesma nota (e é por isso que um violão de 12 cordas soa bem), então só temos 12 possibilidades para codificar. (quando eu saio B, por exemplo, eu realmente saio um acorde, consistindo apenas de B em todas as oitavas, um pouco como um violão de 12 cordas).

Em seguida, lembro-me da aula de música do ensino médio que a maioria das transições de notas é pequena (uma nota para cima ou para baixo). Saltos são menos comuns. Isso nos diz que provavelmente há menos entropia nos tamanhos dos saltos do que nas próprias notas.

Portanto, nossa abordagem é dividir nossa fonte em vários blocos - descobri que 14 blocos por segundo funcionavam bem (nota lateral, eu sempre me perguntava por que o áudio era codificado em 44100 Hz. Acontece que o 44100 tem muitos fatores, então eu poderia ter escolhido 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 25, 28 ou 30 blocos por segundo, e teria dividido de maneira limpa ) Em seguida, transferimos esses blocos para FFT (bem, tecnicamente não é rápido, pois a biblioteca que eu usei não é rápida para blocos sem potência de 2.) E, tecnicamente, usei uma transformação de Hartley , não Fourier).

Em seguida, encontramos a nota que soa mais alta (usei a ponderação A , com cortes altos e baixos, principalmente porque é mais fácil de implementar) e codificamos essa nota ou codificamos o silêncio (a detecção de silêncio é baseada em SNR - SNR baixo é silêncio).

Em seguida, traduzimos nossas notas codificadas em saltos e as alimentamos com um codificador aritmético adaptativo. O processo de tradução para o texto é semelhante à questão da compactação de imagem (mas envolve algum uso abusivo do BigInteger).

Até agora, tudo bem, mas e se a amostra tiver muita entropia? Usamos um modelo psicoacústico bruto para remover alguns. O menor salto de entropia é "sem alteração"; portanto, examinamos nossos dados da FFT para tentar encontrar blocos nos quais o ouvinte provavelmente não notará se continuarmos tocando a nota anterior, procurando blocos onde a nota do bloco anterior é quase tão alto quanto a nota mais alta (onde "quase" é controlado pelo parâmetro de qualidade).

Então, temos um alvo de 140 caracteres. Começamos codificando na qualidade 1.0 (qualidade máxima) e ver quantos caracteres são. Se for demais, caímos para 0,95 e repetimos, até chegarmos a 140 caracteres (ou desistimos após a qualidade 0,05). Isso torna o codificador um codificador n-pass, para n <= 20 (embora seja massivamente ineficiente em outras áreas também, então m'eh).

O codificador / decodificador espera áudio no formato s16be mono. Isso pode ser alcançado usando o avconv como:

#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

Para executar o codificador:

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"

Código completo em https://github.com/jamespic/twelvestring .

Armadilha a ser observada: você precisará da biblioteca Aritmetic Coding de nayuki, que atualmente não possui artefatos do Maven disponíveis. Em vez disso, você precisará construir e instalar localmente o fork do developerster .

E aqui estão algumas amostras. Eles soam horríveis, mas quase reconhecíveis:

• 5º de Beethoven: original , codificado - 刲 檁 囉 罓 佖 镱 皌 蝩 蔲 恁 峕 逊 躹 呯 兲 搆 摼 蝺 筶 槛 庬 一 一 獴 獴 庬 一 掛 獴 庬 一 一 獴 銗 庬 一 掛 獴 娵 一姑 椻 趕 挍 呪 謭 擆 闯 脲 忘 椐 笸 囃 庣 稨 俖 咛 脔 湙 弻 砌 砌 鍖 裏 橈 镙 鹻 鹻 鹻 骱 咰 鹻 裞 瘫 咰 裞 裞 裞 咰 裞 裞 裞 裞 裞茏 蛏 姆 臸 胝 遼 憀 麁 掏 毈 喙 綄 鴀 耢 椚 筤 菮 蟞 斗 俼 湛 营 筬 俼 湛 营 筬 俼 湛 湛 丄 俼 丄
• Fur Elise: original , codificado - 訖 訖 擫 鏝 纒 鉰 鯪 埛 痏 孝 暱 埛 痏 絘 僌 莻 暆 鴈 屖 鳮 婘 婘 譮 蠣 託 鴈 婘 譮 蠣 託 鴈 婘 譮 託 託 婘 譮 譮 託 饚 婘 譮苯 劺 誺 軩 忇 桭 晘 酉 筟 俅 怚 尵 鎽 蜓 崁 飿 嘔 但 鈐 謽 屮 屮 呤 誥 俊 覊 龔 龔 癸 牎 燈 頨 頨 頨 燈 頨 頨 頨 頨 頨 頨 楾.媡 夥 俰 欓 焵 冊 嗥 燠 鱧 駟.
• Twinkle Twinkle Little Star: original , codificado - tradução - 欠 悺 矜 莳 錥 谴 裴
• Um chiptune divertido: original , codificado - 简 詐 諥 尘 牿 扫 蠏 箫 颫 齰 蠏 騁 煟 靸 阒 萎 囦 鮇 雝 愯 訖 芉 馄 鈿 囦 訖 芉 馄 鈿 觲 訖 芉 馄 鈿 沠 訖 芉 鈿 觲 沠 芉灼 攲 陇 亄 鹘 棌 匩 碆 踬 鶙 懲 欃 铳 樯 柇 鋡 疡 衻 澯 伅 搢 搢 囻 荸 香 貱 咽 咽 咽 籐 唦 咽 镤 沄 唦 镤 镤 镤 唦 镤 镤 镤 镤 镤乔 蚖 醶 矕 咻 碋 利 窢 幘 沧 鼝 瞮 坡 葍 帷 锆 邵 旻 符 琨 鱴 郤 栱 栱 仾 罽 罽 栱 邵 罽 罽 罽 锆 邵 邵

Atualizar

Apertei o limiar do silêncio no código e recodifiquei. As codificações foram atualizadas de acordo. Além disso, adicionei outra música (tecnicamente não é de código aberto, mas duvido que o detentor dos direitos autorais originais sinta que seu IP está ameaçado), apenas por diversão:

• Marcha Imperial: original , codificado - 岼 讶 湠 衢 嫵 喋 藭 霔 憣 嗗 颟 蕖 匵 匵 腾 鈪 芔 芔 顕 樭 眀 冂 常 僠 寝 眀 冂 常 僠 寝 区 冂 常 僠 芔 冂 冂 常 鈪 俚 冂 冂 僠 寝 俚 冂 冂 僠 俚唂 焰 銯 艉 鶱 熲 紆 耺 哅 苉 嘏 庸 锺 禒 旇 蘄 籷 遪 刨 繱 嬯 嬯 摺 祑 仰 軈 杊 杊 杊 杊 杊 杊 鶺 艂 寛 眮 鶺 鶺 寛 鶺 鶺 鶺 寛 寛採 偋 隆 兎 豅 踜 襈 軩 树 奘 庄 玫 亳 攩 獼 匑 仡 葾 昐 炡 瞱 咏 斎 煟 价 璌 咏 斎 价 鷖 璌 斎 煟 价 璌 咏 斎 匑 仡

Mais atualizações

Ajustei um pouco o codificador e isso teve um impacto surpreendente na qualidade (eu havia esquecido que, no DHT, os sinais fora de fase são efetivamente negativos, então eu estava ignorando os sinais fora de fase).

Uma versão anterior do código apenas absorveu o maior desses sinais fora de fase, mas agora usamos o RMS. Além disso, adicionei uma função de janela bastante conservadora ao codificador (Tukey, alpha 0.3), para tentar combater artefatos.

Tudo é atualizado de acordo.

Python

Eu não faço nenhuma manipulação especial em relação ao UTF-8; portanto, meu envio passa o requisito de 140 bytes. Não reivindico a utilidade, precisão ou eficiência da minha solução.

Eu usei uma taxa de amostragem de 44100 Hz para a entrada e saída. SAMPLES_PER_BYTE controla a qualidade da conversão. Quanto menor o número, melhor a qualidade do som. Os valores que eu usei são dados na seção de resultados.

Uso

Codificar

O arquivo de entrada deve ser um wav. Ele codifica apenas o primeiro canal.

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

Decodificar

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

Tocando a música decodificada

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

O código

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

As entradas

Minha submissão oficial é Impromptu para Pianoforte e Beatbox por Kevin MacLeod . Para este arquivo, usei um SAMPLES_PER_BYTE de 25450.

Também tomei a liberdade de codificar Twinkle, Twinkle, Little Star com um SAMPLES_PER_BYTE de 10200. Parece muito melhor.

A saída

Impromptu para Pianoforte e Beatbox

aWnxQDg4mWqZWVl6W+LyOThfHOPyQThAe4x5XCqJK1EJ8Rh6jXt5XEMpk1Epe5JqTJJDSisrkkNCSqnSkkJDkiorCZHhCxsq8nlakfEp8vNb8iqLysp6MpJ7s4x7XlxdW4qKMinJKho

Ligação

Brilha Brilha Estrelinha

HBobGlJSUlJSY2FlYVNRUVFCQkJCQjs5PDksKisqGxoZGVFTUVNRREFDQjs6OjoqKykpKVRRVFJDQkJCOjs6OzksKikpGxobG1JSUlNRZWFlYVNSUVFCQkJDQTw5PDorKisqGhsZGRk

Ligação