Это аудио версия задачи кодирования изображений в Twitter .
Разработайте формат сжатия звука, который может представлять по меньшей мере одну минуту музыки в 140 байтах или менее для печатаемого текста в кодировке UTF-8.
Реализуйте это, написав программу командной строки, которая принимает следующие 3 аргумента (после имени самой программы):
- Строка
encode
илиdecode
. - Имя входного файла.
- Выходное имя файла.
(Если в вашем предпочтительном языке программирования отсутствует возможность использовать аргументы командной строки, вы можете использовать альтернативный подход, но должны объяснить это в своем ответе.)
encode
Операция преобразования из выбранного аудио формата в вашем сжатом формате «твит», а decode
операция преобразования из вашего формата «чирикать» в оригинальном формате аудио. (Конечно, вы должны реализовать сжатие с потерями, поэтому выходной файл не обязательно должен быть идентичным входному, только в том же формате.)
Включите в свой ответ:
- Исходный код вашей программы, в полном объеме. (Если она слишком длинная для этой страницы, вы можете разместить ее в другом месте и опубликовать ссылку на нее.)
- Объяснение того, как это работает.
- По меньшей мере, один пример со ссылкой на исходный аудиофайл (ы), текст «твита», в который он сжимается, и аудиофайл, полученный путем декодирования твита. (Ответчик несет ответственность за утверждения о добросовестном использовании авторских прав.)
правила
- Я оставляю за собой право закрыть любые лазейки в правилах конкурса в любое время.
- [Отредактировано 24 апреля] Для ввода вашей
encode
функции (и вывода вашейdecode
функции) вы можете использовать любой приемлемый, распространенный аудиоформат, будь то:- Несжатый сигнал, как WAV.
- Сжатый сигнал, как MP3.
- Стиль «Ноты», например, MIDI.
- Ваш сжатый «твит» формат должен фактически кодировать звуки во входном файле. Итак, следующие типы вывода не учитываются:
- URI или путь к файлу, указывающий место, где хранится фактический вывод.
- Ключ к таблице базы данных, где фактический вывод хранится в виде большого двоичного объекта.
- Ничего подобного.
- Ваша программа должна быть разработана для сжатия общих музыкальных файлов, поэтому не делайте вещи, которые слишком явно связаны с вашей конкретной песней-примером. Например, если вы демонстрируете «Twinkle, Twinkle, Little Star», ваша процедура сжатия не должна жестко кодировать конкретный символ для последовательности «сделай сам».
- Вывод вашей программы должен быть в состоянии проходить через Twitter и выходить невредимым. У меня нет списка точных поддерживаемых символов, но я стараюсь придерживаться букв, цифр, символов и знаков препинания; и избегайте управляющих символов, сочетания символов, маркеров BIDI или других странных вещей, подобных этому.
- Вы можете подать более одной заявки.
Критерии оценки
Это конкурс популярности (т. Е. Выигрывает большинство чистых голосов), но избирателям настоятельно рекомендуется учитывать следующее:
точность
- Можете ли вы распознать песню после того, как она была сжата?
- Звучит хорошо?
- Можете ли вы узнать, на каких инструментах играют?
- Вы все еще можете узнать текст? (Это, вероятно, невозможно, но было бы впечатляющим, если бы кто-то достиг этого.)
сложность
Выбор песни примера имеет значение здесь.
- [Добавлено 24 апреля] Эта задача будет проще всего с MIDI или аналогичными форматами. Однако, если вы приложите дополнительные усилия, чтобы заставить его работать с форматами типа волны, это заслуживает дополнительной оценки.
- Какова структура? Конечно, вы можете выполнить требование в одну минуту, просто повторяя те же 4 измерения произвольное количество раз. Но более сложные песенные структуры заслуживают большего количества очков.
- Может ли формат обрабатывать много нот, играемых одновременно?
Код
- Держите это как можно более коротким и простым. Однако это не кодовый гольф, поэтому читаемость важнее, чем количество символов.
- Умные, сложные алгоритмы тоже подойдут, если они оправданы улучшенным качеством результатов.
Ответы:
Scala
Конечно, было бы проще кодировать MIDI-файлы, но у кого есть куча MIDI-файлов? Это не 1997!
Перво-наперво: я решил интерпретировать «байт Юникода» как «символ Юникода» и использовать символы CJK, потому что:
Есть несколько приемов, которые я использую, чтобы выжать каждую последнюю каплю энтропии из источников:
Во-первых, музыка сделана с нотами. Более того, мы обычно рассматриваем одну и ту же ноту в другой октаве как одну и ту же ноту (именно поэтому 12-струнная гитара звучит правильно), поэтому у нас есть только 12 возможностей для кодирования. (например, когда я вывожу B, я фактически вырабатываю аккорд, состоящий исключительно из B во всех октавах, что-то вроде 12-струнной гитары).
Далее, я помню из школьного музыкального класса, что большинство переходов нот маленькие (вверх или вниз на одну ноту). Прыжки встречаются реже. Это говорит нам о том, что, вероятно, энтропия меньше в размерах прыжков, чем в самих нотах.
Итак, наш подход состоит в том, чтобы разбить наш источник на несколько блоков - я обнаружил, что 14 блоков в секунду работают хорошо (примечание: мне всегда было интересно, почему аудио кодировалось с частотой 44100 Гц. Оказывается, что 44100 имеет много факторов, так что я мог бы выбрать 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 25, 28 или 30 блоков в секунду, и он бы четко разделился ). Затем мы БПФ эти блоки (ну, технически не быстро, так как библиотека, которую я использовал, не быстро для блоков не степени 2. И технически я использовал преобразование Хартли , а не Фурье).
Затем мы находим заметку, которая звучит громче (я использовал A-взвешивание с высокими и низкими отсечками, в основном потому, что ее легче всего реализовать), и либо кодируем эту заметку, либо кодируем тишину (обнаружение молчания основано на SNR - низком SNR это тишина).
Затем мы переводим наши закодированные заметки в скачки и передаем их адаптивному арифметическому кодеру. Процесс перевода в текст похож на вопрос о сжатии изображений (но включает в себя некоторое злоупотребление BigInteger).
Пока все хорошо, но что, если в образце слишком много энтропии? Мы используем грубую психоакустическую модель, чтобы удалить некоторые из них. Самый низкий энтропийный скачок - «без изменений», поэтому мы смотрим на наши данные FFT, чтобы попытаться найти блоки, где слушатель, вероятно, не заметит, если мы продолжим воспроизведение предыдущей ноты, ища блоки, где нота из предыдущего блока почти так же громко, как самая громкая нота (где «почти» контролируется параметром качества).
Итак, у нас есть цель 140 символов. Мы начнем с кодирования с качеством 1.0 (максимальное качество) и посмотрим, сколько символов это. Если это слишком много, мы снижаемся до 0,95 и повторяем, пока не получим 140 символов (или не сдадимся после качества 0,05). Это делает кодировщик n-проходным кодером для n <= 20 (хотя в других областях он также крайне неэффективен, так что м'е).
Кодер / декодер ожидает аудио в монофоническом формате s16be. Это может быть достигнуто с помощью avconv как:
Чтобы запустить кодировщик:
Полный код на https://github.com/jamespic/twelvestring .
Заметьте: вам понадобится библиотека арифметического кодирования nayuki, в которой в настоящее время нет доступных артефактов Maven. Вместо этого вам нужно будет локально собрать и установить ветвь разработчика .
А вот несколько примеров. Они звучат ужасно, но почти узнаваемо
Обновить
Я подправил порог молчания в коде и перекодировал. Кодировки были обновлены соответствующим образом. Кроме того, я добавил еще одну песню (технически не с открытым исходным кодом, но я сомневаюсь, что первоначальный правообладатель будет чувствовать, что его IP-адрес находится под угрозой), просто для удовольствия:
Больше обновлений
Я немного подправил кодировщик, и это оказало удивительное влияние на качество (я забыл, что в DHT синфазные сигналы фактически отрицательны, поэтому я игнорировал синфазные сигналы).
Более ранняя версия кода просто принимала больший из этих синфазных сигналов, но теперь мы берем RMS. Кроме того, я добавил довольно консервативную оконную функцию в кодировщик (Tukey, alpha 0.3), чтобы попытаться бороться с артефактами.
Все обновляется соответственно.
источник
BitOutputStream::close
метод, который я забыл вызвать. Я исправлю код и обновлю выводы.питон
Я не делаю каких-либо особых искажений в отношении UTF-8, поэтому мое представление проходит требование 140 байт. Я не претендую на полезность, точность или эффективность моего решения.
Я использовал частоту дискретизации 44100 Гц для входа и выхода. SAMPLES_PER_BYTE контролирует качество конверсии. Чем меньше число, тем лучше качество звука. Используемые мной значения приведены в разделе результатов.
использование
шифровать
Входной файл должен быть WAV. Кодирует только первый канал.
раскодировать
Воспроизведение декодированной музыки
Код
Входы
Мое официальное представление - « Экспромт» для Pianoforte и Beatbox от Кевина МакЛауда . Для этого файла я использовал SAMPLES_PER_BYTE из 25450.
Я также взял на себя смелость кодировать Twinkle, Twinkle, Little Star с SAMPLES_PER_BYTE 10200. Звучит намного лучше.
Выход
Экспромт для фортепиано и битбокса
Ссылка
Twinkle, Twinkle Маленькая Звезда
Ссылка
источник