Max Home Industry• О практической точности алгоритмов аппроксимации расстояния редактирования
• Иногда нужны иррациональные охранники
• 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