// Без комментариев — приблизительное расстояние редактирования, иррациональная гвардия и DCT в 14 дополнениях


• О практической точности алгоритмов аппроксимации расстояния редактирования

• Иногда нужны иррациональные охранники

• DCT-подобное преобразование для сжатия изображений требует только 14 добавлений

Иногда новости достаточно хорошо сообщаются в других местах, и нам нечего добавить, кроме как обратить на это ваше внимание.

Без комментариев — это формат, в котором мы представляем исходную информацию об источнике, слегка отредактированную, чтобы вы могли решить, хотите ли вы следить за ней.

О практической точности алгоритмов аппроксимации расстояния редактирования

Расстояние редактирования между двумя строками — это просто количество операций редактирования примитивов, необходимых для преобразования одной строки в другую. Легко сформулировать, но очень сложно вычислить, и это важный алгоритм, который используется во всем, от проверки орфографии до генетического анализа. Во многих случаях мы можем обойтись приближением, которое легче вычислить, но насколько они хороши?

Расстояние редактирования — это базовая мера сходства строк, используемая во многих приложениях, таких как интеллектуальный анализ текста, обработка сигналов, биоинформатика и т. Д. Однако вычислительные затраты могут стать проблемой, когда мы повторяем много вычислений расстояния, как это видно в реальных ситуациях поиска.

Перспективным решением проблемы является аппроксимация расстояния редактирования другим расстоянием с меньшими вычислительными затратами. Действительно, было предложено много расстояний для приближения расстояния редактирования. Однако точность их аппроксимации оценивается только теоретически: многие из них оцениваются только с большими (асимптотическими) обозначениями и без экспериментального анализа. Поэтому полезно знать их фактическую производительность в реальных приложениях.

В этом исследовании мы сравнили существующие шесть приближенных расстояний в двух подходах:

(i) мы повысили точность их теоретической аппроксимации, рассчитав с точностью до постоянных коэффициентов,

а также

(ii) мы провели несколько экспериментов на одном искусственном и двух реальных наборах данных, чтобы выявить, в каких ситуациях они работают лучше всего.

В результате мы получили следующие результаты: [Batu 2006] — лучший теоретически, а [Andoni 2010] — экспериментально. Теоретические соображения показывают, что [Batu 2006] является лучшим, если длина строки n достаточно велика (n> = 300). [Andoni 2010] экспериментально лучший для большинства наборов данных и теоретически второй лучший. [Bar-Yossef 2004], [Charikar 2006] и [Sokolov 2007], несмотря на их средние теоретические характеристики, экспериментально так же хороши, как [Andoni 2010] для пар строк с большим размером алфавита.

Иногда нужны иррациональные стражи

Проблема с художественной галереей — это весело, и в этом случае иррациональность охранников не совсем означает то, что вы думаете — это кликбейт? Наверное, но это очень элитная приманка.

В этой статье мы изучаем проблему художественной галереи, которая является одной из фундаментальных проблем вычислительной геометрии.

Цель состоит в том, чтобы разместить минимальное количество охранников внутри простого многоугольника, чтобы охранники вместе могли видеть весь многоугольник. Мы говорим, что охранник в позиции x видит точку y, если отрезок xy полностью содержится в многоугольнике.

Несмотря на обширное исследование проблемы художественной галереи, оставался открытым вопрос, существуют ли многоугольники, заданные целочисленными координатами, которые требуют охранных позиций с иррациональными координатами в любом оптимальном решении.

Мы даем положительный ответ на этот вопрос, построив монотонный многоугольник с целыми координатами, который могут охранять три охранника только тогда, когда мы разрешаем размещать охранников в точках с иррациональными координатами. В противном случае потребуется четыре охранника.

Расширяя этот пример, мы показываем, что для каждого n существует многоугольник, который может охраняться 3n охранниками с иррациональными координатами, но требуются 4 охранника, если координаты должны быть рациональными. Впоследствии мы покажем, что существуют прямолинейные многоугольники, заданные целочисленными координатами, которые требуют защиты с иррациональными координатами в любом оптимальном решении.

DCT-подобное преобразование для сжатия изображений требует только 14 добавлений

Дискретное косинусное преобразование DCT — это приближение к преобразованию Фурье, используемому в большей части цифровой обработки сигналов, и возможность его быстрого вычисления важна. Например, 8-точечный DCT используется при сжатии JPEG. Теперь у нас есть приближение к матричному преобразованию, которое можно выполнить всего за 14 добавлений:

Представлен 8-точечный ортогональный приближенный DCT с низкой сложностью. Предлагаемое преобразование не требует операций умножения или битового сдвига. Полученный быстрый алгоритм требует всего 14 добавлений, меньше, чем любое существующее приближение DCT. Более того, в нескольких сценариях сжатия изображения предлагаемое преобразование может превзойти хорошо известный подписанный DCT, а также современные алгоритмы.

Чтобы быть в курсе новых статей на I Programmer, подпишитесь на нашу еженедельную рассылку новостей, подпишитесь на RSS-канал и подпишитесь на нас в Twitter, Facebook, Google+ или Linkedin.

Комментарии

Оставьте комментарий или просмотрите существующие комментарии с помощью Disqus


Добавить комментарий