Esta es la versión de audio del desafío de codificación de imágenes de Twitter .

Diseñe un formato de compresión de audio que pueda representar al menos un minuto de música en 140 bytes o menos de texto imprimible codificado en UTF-8.

Impleméntelo escribiendo un programa de línea de comandos que tome los siguientes 3 argumentos (después del nombre del programa en sí):

1. La cuerda encodeo decode.
2. El nombre del archivo de entrada.
3. El nombre del archivo de salida.

(Si su lenguaje de programación preferido carece de la capacidad de usar argumentos de línea de comandos, puede usar un enfoque alternativo, pero debe explicarlo en su respuesta).

La encodeoperación se convertirá de su formato de audio elegido a su formato de "tweet" comprimido, y la decodeoperación se convertirá desde su formato de "tweet" al formato de audio original. (Por supuesto, se espera que implemente una compresión con pérdida, por lo que el archivo de salida no necesita ser idéntico a la entrada, solo en el mismo formato).

Incluye en tu respuesta:

• El código fuente de su programa, en su totalidad. (Si es demasiado larga para esta página, puede alojarla en otro lugar y publicar un enlace).
• Una explicación de cómo funciona.
• Al menos un ejemplo, con un enlace a los archivos de audio originales, el texto "tweet" al que se comprime y el archivo de audio obtenido al decodificar el tweet. (El respondedor es responsable de las afirmaciones de "uso justo" de los derechos de autor).

Reglas

• Me reservo el derecho de cerrar cualquier laguna en las reglas del concurso en cualquier momento.
• [Editado el 24 de abril] Para la entrada de su encodefunción (y la salida de su decodefunción), puede usar cualquier formato de audio común y razonable, ya sea:
  • Forma de onda sin comprimir, como WAV.
  • Forma de onda comprimida, como MP3.
  • Estilo de "partitura", como MIDI.
• Su formato comprimido de "tweet" debe codificar los sonidos en el archivo de entrada. Por lo tanto, los siguientes tipos de salida no cuentan:
  • Un URI o ruta de archivo que proporciona la ubicación donde se almacena la salida real.
  • Una clave para una tabla de base de datos donde la salida real se almacena como un blob.
  • Algo similar.
• Tu programa debe estar diseñado para comprimir archivos de música genéricos , así que no hagas cosas que obviamente estén demasiado vinculadas a tu canción de ejemplo específica. Por ejemplo, si está demostrando "Twinkle, Twinkle, Little Star", su rutina de compresión no debería codificar un símbolo específico para la secuencia do-do-so-so-la-la-so.
• La salida de su programa debería poder pasar por Twitter y salir ilesa. No tengo una lista de los caracteres exactos que son compatibles, pero trato de mantener letras, dígitos, símbolos y signos de puntuación; y evite los caracteres de control, combinando caracteres, marcadores BIDI u otras cosas extrañas como esa.
• Puede enviar más de una entrada.

Criterio de juzgar

Este es un concurso de popularidad (es decir, gana la mayoría de los votos positivos), pero se insta a los votantes a considerar lo siguiente:

Exactitud

• ¿Todavía puedes reconocer la canción después de que se ha comprimido?
• ¿Suena bien?
• ¿Todavía puedes reconocer qué instrumentos se están tocando?
• ¿Todavía puedes reconocer la letra? (Esto es probablemente imposible, pero sería impresionante si alguien lo lograra).

Complejidad

La elección de la canción de ejemplo es importante aquí.

• [Agregado el 24 de abril] Este desafío será más fácil con MIDI o formatos similares. Sin embargo, si hace un esfuerzo adicional para que funcione con formatos de forma de onda, eso merece un crédito adicional.
• Cual es la estructura Claro, puede cumplir el requisito de un minuto simplemente repitiendo las mismas 4 medidas un número arbitrario de veces. Pero las estructuras de canciones más complejas merecen más puntos.
• ¿Puede el formato manejar muchas notas que se reproducen al mismo tiempo?

El código

• Mantenlo lo más corto y simple posible. Sin embargo, este no es un código de golf, por lo que la legibilidad importa más que el recuento de caracteres.
• Los algoritmos inteligentes y complicados también están bien, siempre que estén justificados por una mejor calidad de resultados.

Scala

Claro, sería más fácil codificar archivos MIDI, pero ¿quién tiene un montón de archivos MIDI por ahí? ¡No es 1997!

Primero lo primero: he decidido interpretar un "byte Unicode" como un "char Unicode" y usar caracteres CJK, porque:

• Coincide con el desafío de la imagen
• Twitter es genial con eso
• Yo realmente necesito esos bits

Hay algunos trucos que uso para exprimir hasta la última gota de entropía de las fuentes:

En primer lugar, la música está hecha con notas. Además, generalmente consideramos la misma nota en una octava diferente como la misma nota (razón por la cual una guitarra de 12 cuerdas suena bien), por lo que solo tenemos 12 posibilidades de codificación. (cuando saco B, por ejemplo, realmente saco un acorde, que consiste únicamente en B en todas las octavas, un poco como una guitarra de 12 cuerdas).

A continuación, recuerdo de la clase de música de la escuela secundaria que la mayoría de las transiciones de notas son pequeñas (una nota hacia arriba o hacia abajo). Los saltos son menos comunes. Esto nos dice que probablemente haya menos entropía en los tamaños de salto que en las notas mismas.

Entonces, nuestro enfoque es dividir nuestra fuente en varios bloques: encontré que 14 bloques por segundo funcionaron bien (nota al margen, siempre me pregunté por qué el audio estaba codificado a 44100 Hz. Resulta que 44100 tiene muchos factores, entonces podría haber elegido 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 25, 28 o 30 bloques por segundo, y se habría dividido limpiamente ) Luego FFT estos bloques (bueno, técnicamente no es rápido, ya que la biblioteca que utilicé no es rápida para bloques sin potencia de 2. Y técnicamente utilicé una transformación de Hartley , no Fourier).

Luego encontramos la nota que suena más fuerte (utilicé la ponderación A , con cortes altos y bajos, principalmente porque es más fácil de implementar) y codificamos esta nota o codificamos silencio (la detección de silencio se basa en SNR - baja SNR es silencio)

Luego traducimos nuestras notas codificadas en saltos y las enviamos a un codificador aritmético adaptativo. El proceso de traducción al texto es similar a la pregunta de compresión de imagen (pero implica un uso abusivo de BigInteger).

Hasta ahora, todo bien, pero ¿qué pasa si la muestra tiene demasiada entropía? Usamos un modelo psicoacústico crudo para eliminar algunos. El salto de entropía más bajo es "sin cambios", por lo que miramos nuestros datos FFT para tratar de encontrar bloques donde el oyente probablemente no se dará cuenta si seguimos tocando la nota anterior, buscando bloques donde está la nota del bloque anterior. casi tan alto como la nota más alta (donde "casi" está controlado por el parámetro de calidad).

Entonces, tenemos un objetivo de 140 caracteres. Comenzamos codificando con la calidad 1.0 (calidad máxima) y vemos cuántos caracteres hay. Si es demasiado, bajamos a 0.95 y repetimos, hasta llegar a 140 caracteres (o renunciamos después de la calidad 0.05). Esto hace que el codificador sea un codificador de paso n, para n <= 20 (aunque también es enormemente ineficiente en otras áreas, entonces m'eh).

El codificador / decodificador espera audio en formato s16be mono. Esto se puede lograr usando 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 ejecutar el 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 en https://github.com/jamespic/twelvestring .

Errores a tener en cuenta: necesitará la biblioteca de codificación aritmética de nayuki, que actualmente no tiene artefactos Maven disponibles. En su lugar, deberá construir e instalar localmente la bifurcación del desarrollador .

Y aquí hay algunas muestras. Suenan horribles, pero casi reconocibles:

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

Actualizar

Ajusté el umbral de silencio en el código y volví a codificarlo. Las codificaciones se han actualizado en consecuencia. Además, agregué otra canción (técnicamente no es de código abierto, pero dudo que el titular original de los derechos de autor sienta que su IP está bajo amenaza), solo por diversión:

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

Más actualizaciones

He ajustado un poco el codificador, y ha tenido un impacto sorprendente en la calidad (había olvidado que en DHT, las señales desfasadas son efectivamente negativas, por lo que estaba ignorando las señales desfasadas).

Una versión anterior del código simplemente tomó la mayor de estas señales desfasadas, pero ahora tomamos el RMS. Además, agregué una función de ventana bastante conservadora al codificador (Tukey, alpha 0.3), para tratar de combatir los artefactos.

Todo se actualiza en consecuencia.

Pitón

No hago ningún cambio especial con respecto a UTF-8, por lo que mi envío pasa el requisito de 140 bytes. No hago declaraciones sobre la utilidad, precisión o eficiencia de mi solución.

Usé una frecuencia de muestreo de 44100 Hz para la entrada y la salida. SAMPLES_PER_BYTE controla la calidad de la conversión. Cuanto menor sea el número, mejor será la calidad del sonido. Los valores que utilicé se dan en la sección de resultados.

Uso

Codificar

El archivo de entrada debe ser un wav. Solo codifica el primer canal.

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

Descodificar

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

Tocando la música decodificada

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

El 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))

Las entradas

Mi presentación oficial es Impromptu para Pianoforte y Beatbox por Kevin MacLeod . Para este archivo utilicé un SAMPLES_PER_BYTE de 25450.

También me tomé la libertad de codificar Twinkle, Twinkle, Little Star con un SAMPLES_PER_BYTE de 10200. Suena mucho mejor.

La salida

Impromptu para Pianoforte y Beatbox

aWnxQDg4mWqZWVl6W+LyOThfHOPyQThAe4x5XCqJK1EJ8Rh6jXt5XEMpk1Epe5JqTJJDSisrkkNCSqnSkkJDkiorCZHhCxsq8nlakfEp8vNb8iqLysp6MpJ7s4x7XlxdW4qKMinJKho

Enlazar

Brilla brilla pequeña estrella

HBobGlJSUlJSY2FlYVNRUVFCQkJCQjs5PDksKisqGxoZGVFTUVNRREFDQjs6OjoqKykpKVRRVFJDQkJCOjs6OzksKikpGxobG1JSUlNRZWFlYVNSUVFCQkJDQTw5PDorKisqGhsZGRk

Enlazar