История создания алгоритма Быстрого Преобразования Фурье



8 коммент.
Сразу после публикации статьи Кули и Тьюки [1], в которой описывался алгоритм вычисления быстрого преобразования Фурье (БПФ, FFT, Fast Fourier Transform), к авторам начали приходить письма с различными отзывами. Одни писали, что их новый революционный алгоритм распахнул невиданные горизонты для обработки сигналов и изображений, и теперь любая задача по плечу. Другие говорили [2], что алгоритм давным-давно известен и используется, так что их статья - лишь повтор того, что есть.
И те, и другие были по-своему правы.

Следует заметить, что время публикации статьи Кули и Тьюки [1] совпало с бурным развитием вычислительной техники, когда всё больше и больше задач решались на ЭВМ. В 1965 году, тем не менее, все высокоскоростные компьютеры были забиты заданиями под завязку. Более того, в те годы начали активно разрабатываться АЦП, которые позволяли вводить информацию в ЭВМ со скоростью нескольких тысяч отсчётов в секунду. Это означало, что теперь можно обрабатывать сигнал цифровым способом вместо использования аналоговых устройств. В свою очередь, потребовались эффективные алгоритмы обработки сигналов и изображений, многие из которых используют преобразование Фурье. Поэтому появление нового алгоритма, сулившего ускорить вычисление дискретного преобразования Фурье в $N/\log_2(N)$ , было очень кстати.

Создание алгоритма

По рассказам одного из авторов алгоритма, Джеймса Кули [3], всё началось в конце 1963 года. Джеймс Кули был нанят в IBM Thomas J. Watson Research Center в Yorktown Heights, что в Нью-Йорке. Кули работал над своим собственным проектом, когда к нему обратился Ричард Гарвин (Richard Garwin) и показал некоторые заметки Джона Тьюки (John Tukey) об алгоритме, который теоретически способен вычислять быстрое преобразование Фурье со скоростью, пропорциональной $N\log_2(N)$, а не $N^2$. Гарвин, в отличие от Кули, хорошо понимал всю важность этого алгоритма и его огромную практическую значимость, и поэтому настаивал на разработке этого алгоритма.

``- Позже, - вспоминает Кули [2]. - я выяснил, что Гарвин был значительно более заинтересован в улучшении дистанционного сейсмического мониторинга ядерных взрывов; русские едва ли согласились бы на проведение инспекций на их территории. Гарвин так же видел необходимость в разработке методов раннего акустического обнаружения подводных лодок. Как и многие другие, я не считал это важным, поэтому поставил задаче разработки алгоритма БПФ приоритет ниже, чем собственным исследованиям. Тем не менее, под напором авторитета Гарвина и его постоянных телефонных звонков, я написал алгоритм для вычисления трёхмерного БПФ.''

История БПФ

Перед публикацией нужно было проверить, является ли идея алгоритма новой, и Кули решил посоветоваться с Джоном Тьюки. Тьюки посоветовал просмотерть несколько статей, в одной из которых [4] описывался очень похожий метод, скорость которого была несколько меньше. Было понятно, что идея их алгоритма в целом не нова, и это заставило Кули глубже изучить историю БПФ. Его непосредственный начальник, Гарвин, обратился к своему коллеге, профессору Томасу (Professor L.H. Thomas), который был в своё время научным руководителем Кули в институте. Томас дал свою опубликованную статью [5], в которой описывалось вычисление рядов Фурье, которые он проделал в 1948 году в IBM на табуляторе с перфокартами. По словам Томаса, он просто пошёл в библиотеку и взял справочник [6]. Методы, опубликованные в этом справочнике, позволяли вычислять ряды Фурье и уменьшать объёмы вычислений используя свойство симметрии тригонометрических функций.

Вскоре после публикации [1] Кули получил письмо от Филипа Рудника из Института Океанографии в Санн-Диего, Калифорния. Рудник сказал, что сам реализовал подобный алгоритм, используя метод из [7]. Статья Рудника с улучшенным вариантом такого метода вышла [8] чуть позднее статьи Кули и Тьюки - он не решился публиковать её сразу.
Оказалось, что приёмы, лежащие в основе БПФ, были опубликовы ещё раньше. В том же справочнике Стампффа [6] нашлась ссылка на более ранние работы Рунге и Кёнига [9]. В той работе так же использовался метод ``бабочки'' (Метод ``бабочки'', butterfly, заключается в использовании сделанных вычислений для получения соседних значений сложением или вычитанием уже полученных) для ускорения вычислений и контроля ошибок.

Кули написал статью [10], в которой приводилась, как он полагал, полную историю предшествующих похожих алгоритмов вычисления БПФ вплоть до работ Рунге [9]. Однако пыль веков скрывала в себе много интересного, и вскоре Кули получил ссылку от коллеги [11] на ещё более ранюю работу по вычислению БПФ. Это была глава книги великого Карла Фридриха Гаусса [12]. В этой главе, написанной на неоклассической латыни, приводились основные соображения алгоритма БПФ. Гаусс применял разновидность интерполяции по Лагранжу, и это могло привести его к возможности сокращения количества операций при быстром преобразовании. Позже были опубликованы работы [13,11], в которых приведён краткий перевод работы Карла Гаусса, предвосхтившей БПФ, а так же упомянуты другие работы, посвящённые БПФ.

Выводы

Из всей этой истории читатель может извлечь ценные выводы:

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

Литература

1
Cooley J.W. and Tukey J.W. An algorithm for the machine calculation of the complex fourier series. Mathematics Computation, 19:297-301, 1965.
2
James W. Cooley. The re-discovery of the fast fourier transform algorithm. Mikrochimica Acta, III:33-45, 1987.
3
J.W. Cooley. How the FFT gained acceptance. Proceedings of the Association for Computing Machinery Conference on the History of Scientific and Numeric Computation, Princeton, NJ, pages 10-13, 1987.
4
J. Good I. J. Royal Statist. Soc.,, 20:361, 1958.
5
L. H. Thomas. Applications of Digital Computers, chapter Using a Computer to Solve Problems in Physics. Boston: Ginn and Company, 1963.
6
K. Stumpff. Grundlagen und Methoden der Periodenforschung, Tafeln und Aufgaben zur Harmonischen Analyse und Periodogrammrechnung. Springer, Berlin, 1939.
7
G. C. Danielson and C. Lanczos. Some improvements in practical fourier analysis and their application to x-ray scattering from liquids. J. Franklin Inst. 233, Pergamon Journals, Ltd., pages 365-80, 1942.
8
Philip Rudnick. Note on the calculation of fourier series. Math. Comp., Vol. 20, No.3:429-430, July 1966.
9
C. Runge and H. Konig. Vorlesungen uber Numerisches Rechnen (Die Grundlehren der Mathematischen Wissenschaften, Band XI). Springer, Berlin, 1924.
10
J.W. Cooley, P.A. Lewis, and P.D. Welch. An algorithm for the machine calculation of complex fourier series. IEEE Trans. Audio Electroacoustics, AU-15:76, 1967.
11
H.H. Goldstine. A History of Numerical Analysis from the 16th Through the 19th Century. Springer-Verlag, New York, Heidelberg, and Berlin, 1977.
12
C.F. Gauss. Nachla: Theoria interpolationis methodo nova tractata. (Carl Friedrich Gauss, Werke, Band 3), Konigliche Gesellschaft der Wissenschaften, Gottingen, pages 265-303, 1866.
13
M.T. Heideman, D.H. Johnson, and C.S. Burrus. Gauss and the history of the fast fourier transform. The ASSP Magazine, Vol. 1, No. 4:14-21, Oct. 1984.
Читать далее

Свистульки, бубенчики и рюшечки в документах LaTeX



12 коммент.
Как все уже хорошо знают, в ЛаТеХ добиться хорошего качества документов по умолчанию очень просто: используя десяток стандартных команд, вы получите неизменно превосходный результат (ТМ) без лишних усилий. То есть документ будет хорош, но ведь иногда хочется украшательств, мигалок, свистулек и бубенчиков. На эту тему автор уже собрал небольшую коллекцию, которой и рад поделиться. Кроме того, автор открыл для себя удивительные книги Edward Tufte, который знает толк в визуальной подаче информации.


Читать далее

Как написать статью в LaTeX



17 коммент.
Результатом любого приличного исследования являются публикации. Вы делаете что-то новое, и это по идее должно немного (или значительно) двинуть научное знание вперёд. А так как научные тексты удобнее писать в LaTeX, специально для этого созданным не абы кем, а Дональдом Кнутом, то возникает непраздный вопрос: как же написать статью в LaTeX?!

Вернее, вопросов два: как написать научную статью и как это сделать в ЛаТеХе?


Как написать научную статью
В Сети есть много хороших и правильных постов о том, как следовало бы писать статьи. Там вам скажут, что сначала придумывается заглавие, потом аннотация (abstract), потом красивое введение, потом, собственно, результаты исследований и, как апофеоз экзистенциального катарсиса, заключение.

В жизни всё несколько иначе. Обычно стоит большая задача, которую нужно решить. Мы сидим, чещем затылок и листаем журналы в поисках намёков на решение. Пробуем то и это, и чаще всего либо оно не работает вообще, либо работает, но не так, как надо. Потом иногда приходит какая-нибудь хорошая и свежая мысль, и внутренний голос говорит "О! Это интересно", а внешний - "Ахххаааа!".

После прихода этого самого "Аха!" вместе с хорошей идеей автор начинает что-то быстро писать на бумаге, прикидывать, покрякивать и энергично потирать ручонки. Далее, в состоянии полного угара творчества что-то ваяется, вычисляется, математически выводится, разливается по колбам, экспериментируется, программируется и численно симулируется. Это самое счастливое время, когда забываешь обо всём на свете и делаешь что-то занятное - за это, собственно, научным сотрудникам и платят деньги.

Через некоторое время угар творчества проходит и автор видит наброски, куски кода, булькающие колбы, вереницы данных, таблицы и графики. Работа принимает более организованный характер: нужно сравнить с имеющимися методами, провести дополнительные эксперименты или расчёты. Если это что-то, чего ещё никто не делал - самое время приступать к написанию статьи.

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

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


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


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

Обычно заключение отвечает на три вопроса:
  1. Что за проблема решалась в статье?
  2. Какие результаты были получены в статье?
  3. Ну и что!?
Для ответа на эти вопросы, в особенности на последний, хорошо поиграть в игру "Ну и что?!". То есть представьте, что вы беседуете с редактором журнала, и он вас спрашивает: "ну и что в статье интересного-то?" или "почему я должен обратить на это внимание?".


Введение это вторая по трудности часть после заключения. Введение обычно даёт формулировку целей исследования и достаточный обзор существующей литературы. Но это легко сказать, а что писать-то? Ну, например, автор этих строк пользуется следующей болванкой:
  1. Почему это исследование вообще проводилось?
  2. Какая литература уже существует по этому вопросу? Здесь можно провести обзор и показать ту брешь, которую вы хотите заткнуть своей статьёй.
  3. Какова конкретная цель исследований? Это теоретическое обоснование чего-то, или экспериментальная работа, или численные симуляции.
  4. В чём новизна работы?
После написания введения и заключения можно писать аннотацию (abstract).


Аннотация (abstract) это короткое описание цели работы, результатов и что в работе сообщается. В целом, аннотация пишется обычно из надёрганных предложений из Введения и Заключения. Обычно аннотации короткие и должны быть не длиннее, скажем, 250 слов (у журналов и конференций по этому поводу свои правила).






Как написать научную статью в LaTeX
Эпиграф:
LaTeX is capable of most things 
but not always in the most obvious manner.

Собственно, как уже говорилось выше, почти всё, что нужно для этого, есть в постах о написании диплома в LaTeX:
Есть одно НО: у каждого журнала или конференции есть свой собственный, не имеющий аналогов в мире, стилевой файл  LaTeX разной степени корявости и тухлости. Как правило, там содержится рабочий пример статьи, так что лучше попробовать сначала собрать пример.

Но если вы думаете, что отправленную вами в журнал статью примут "с колёс" и без редакции, то вы либо крутой нобелевский лауреат, либо большой оптимист. И поэтому скорее всего вам предстоит общение с рецензентами и редактором журнала. Вот тут-то LaTeX нам и сослужит добрую службу....


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


Нумерация строк в LaTeX
Нумерация строк включается пакетом lineno, который можно скачать здесь. В преамбуле документа добавляем
\usepackage[mathlines]{lineno}% Enable numbering 
Отлично, теперь вставляем команду:
\linenumbers\par %%% <---- turn on the numeration of lines
там, где мы хотим начать нумерацию линий. Если нужно оборвать нумерацию в конце статьи перед, скажем, списком литературы, команда выглядит так:
\nolinenumbers %%% do not use line numbers any more.
Важно то, что пакет lineno позволяет не только автоматически проставлять номера строк, но ещё и ссылаться на них. Автор настоятельно рекомендует использовать эту возможность, чтобы не сойти с ума самому при правках и не злить рецензентов.

Для этого в том месте, которое вы обещаете рецензенту поправить (и делаете это), ставим ссылку:
\linelabel{review:1R1}
Как и везде в ЛаТеХе, ссылки стоит ставить разумные: например, здесь написано, что это ответ на замечание 1 от рецензента 1 (они обычно анонимные).

Далее в тексте ответа на замечания рецензентов пишем что-то типа:
We clarified this on page~\pageref{review:1R1} line~\ref{review:1R1}.

Наступает счастье: здесь мы приводим не только ссылку на строку (\ref{review:1R1}) но и сразу на страницу (\pageref{review:1R1}).

Вместо конструкции $$ ..... $$  следует использовать \[ ... \] или \begin{displaymath} ....\end{displaymath}, тогда пакет lineno правильно проставит номера строк в тексте с математическими формулами.

Больше о нумерации строк вам расскажет весьма толковая документация к пакету lineno.


Ссылка на сноски в LaTeX
Допустим, вы сказали, что угоняете часть тектса в сноску. Об этом лучше написать рецензенту прямо, чтобы он не искал кусок пропавшего текста по всему документу.

Для этого пишем в преамбуле документа:
\newcommand{\footnoteremember}[2]{\footnote{#2} \newcounter{#1} \setcounter{#1}{\value{footnote}}} \newcommand{\footnoterecall}[1]{\footnotemark[\value{#1}]}
Теперь в тексте можно написать:

The Finite Element Analysis was perfomed on a crappy computer\footnoteremember{footnotelatitude}{Simulations were run on the Dell Latitude E5400 notebook with Intel Celeron 2.2 GHz processor, 2GB DDR2 SDRAM, 120 GB SATA HDD 5400 rpm under Debian GNU/Linux v 5.0 with MATLAB v2007b for UNIX.}.

Так что у нас есть ссылка footnotelatitude которая ведёт на сноску. Теперь сослаться на неё можно так:
(see footnote\footnoterecall{footnotelatitude})
И вы теперь сможете видеть номер сноски, на которую вы ссылаетесь. Трюк позаимствован отсюда.


Перевод PDF в простой текст
Сгенерированные ЛаТеХом документы часто переводятся в PDF, но иногда требуется перевести всё в простой текст. Часто это следует делать с сохранением структуры, и тут нам поможет pdftotext:
pdftotext -layout  -nopgbrk   reviewnotes_12-0238_MS.pdf
где ключи означают:
 -layout           : maintain original physical layout
 -nopgbrk          : don't insert page breaks between pages
Если нужно перевести в текст только со страницы 5 по страницу 10, даём команду:
pdftotext  -f 5 -l 10 reviewnotes_12-0238_MS.pdf
После этого текст можно вставлять в веб-форму для ответа рецензентам.




Ссылка название раздела или главы в LaTeX
Тоже часто используется, особенно если вы при правках радикально меняете структуру статьи (скажем, рецензенты вам это настоятельно советуют). Делается ссылка на название раздела с помощью пакета nameref и который входит в пакет hyperref - он входит в стандартный набор TexLive и потому уже должен быть установлен.

Включаем пакет в преамбуле:
\usepackage{nameref}

Ставим метку для раздела (section):

\section{Introduction}\label{intro}
И ссылемся в тексте:
See more details in the \nameref{intro} section that has number \ref{intro}.
Вместо этого мы при компиляции увидим:
See more details in the Introduction section that has number 1.
Этот удобный и простой трюк подсмотрен тут.


Вместо заключения
Собственно, этот пост - небольшая зарубка на память и собрание нескольких рецептов из моего уже порядком разросшегося черновика. Полностью приведённый пример можно посмотреть на моей странице в Google Code.

Читать далее

Вырываем список книг для чтения из zotero с мясом, Tcl-ем и SQlite-ом



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

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

Читать далее

Как сделать календарь в LaTeX на год и месяц автоматически?



6 коммент.
Это краткая заметка в стиле "как отстрелить себе ногу с помощью LaTeX". Автору этих строк потребовалось сделать себе календарик, в котором отображались бы оповещения о событиях, и чтобы это дело регенерировалось автоматически при смене месяца.

Предисловие

Автор этих строк - человек очень ленивый, но любопытный и обожающий ковырять свой Дебиан на предмет того, как бы сбросить побольше рутины на компьютер. Так появилась LaTeX-реализация организационной системы Getting Things Done, которая выполнена полностью на латехе, вместе с адресной книгой и календарём.

Календарь на LaTeX реализован с помощью пакета расширений calendar [скачать ZIP-файл]. Проблема в том, что месяцы в календаре нужно обновлять самому, а вот это как раз и забывается чаще всего. Поэтому хочется, чтобы дни, месяцы и годы в календарике LaTeX обновлялись автомагически латехом и без вмешательства ленивого и забывчивого автора этих строк.
Нужно сказать, что LaTeX является Turing complete language, то есть на нем можно писать любые программы. Например, можно написать интерпретатор Бейсика, симулятор машины Тьюринга, Mandelbrot with LaTeX и другие программы. То есть на латехе можно писать что угодно. Не всегда это просто (особенно в случае с календарём), но можно.
Пост поделён на две части: сначала немного о возможностях пакета Calendar, а потом про то, как обновление названий месяцев сделать автоматически из LaTeX.

Возможности пакета Calendar в LaTeX

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

После распаковки всех файлов в преамбуле документа подключаем пакеты:
%%% Turning on the Monthly calendar and Event list
\usepackage{monthly,evntlist,lscape} \parindent=0pt
для календаря на месяц и списка событий, и:
%%% Turning on the Yearly calendar
\usepackage{yearly}
для календаря на год соответсвенно.

Создание событий для календаря

Пакет calendar не просто создаёт календарь, но и позволяет отображать в нём события. Все события хранятся в одном текстовом файле myEvents.cld из которого они дёргаются календарём. Файл событий выглядит так:
%%%%%%% My Personal Calendar
range Essentials/Calendar/year2010 %% What year do we want?
%% ONE-TIME EVENTS
january 28 2010 {Описать GTD} [Описать GTD для блога]
%%%%% RECURRING EVENTS
every Sunday {Еженед. обзор} [Еженед. обзор]
Сначала указываем год в отдельном файле Essentials/Calenda/year2010.cld в котором пишем:
%% Span the whole year here
January 1 2010 to December 31 2010 {The year 2010}
Повторяющиеся события будут определены только в интервале из этого файла.

Список событий из календаря

Часто нужно просто видеть события, приуроченные к календарным датам (особенно если их не так много). Для этого мы пользуемся окружением eventlist, которое предоставляет пакет calendar. Настройки того, как выглядит список событий, хранятся в файле evntlist.sty который можно приукрасить разными значками и иконками.

Чтобы распечатать события между нужными датами, вы просто ставите две даты, между которыми хотите показывать события (хранятся в файле events.cld):
\begin{eventlist} {} {Essentials/Calendar/myEvents}
january 24 2010 to january 30 2010
\end{eventlist}
и собираете LaTeXом документ, получая список календарных событий на это время:



Иконки сделаны пакетами шрифтов marvosym и wasysym.

Календарь на месяц с отображением событий

Пакет calendar может больше - можно создать календарь на месяц и показывать там события. Код такой:
\begin{monthly}
{firstday=1} %% begins with Monday
{Essentials/Calendar/myEvents}
jan 2010
\end{monthly}
Все события в календаре на указанный месяц (январь 2010 в данном случае) берутся из того же файла events.cld, который мы использовали для генерации списка календарных дней на неделю.
Компилируем документ и вот он, календарь на месяц, обновлённый и со вставленными событиями:


Календарь работает с кириллицей, во всяком случае кодировка KOI8-R у него возражений не вызывает.

Календарь на год

Места для отображения событий в календаре на год особенно не много, но возможность сгенерировать годовой календарь, не отходя от кассы выходя из латеха весьма кстати. Код для этого:
\begin{yearly}
 {title= \begin{center} \textbf{\Large The Year 2013}\end{center} \normalsize,firstday=1}
{}
2013
\end{yearly}
После сборки документа годовой календарик будет выглядеть так:



Можно посылать в печать.

Вызов скриптов из LaTeX

С календарём всё сравнительно понятно, и теперь настало время его автоматизировать: хочется, чтобы названия месяцев и дней подставлялись автоматически. Это не такая простая задача, как может показаться. Дело в том, что стандартные команды типа \the\year с пакетом calendar работать не будут, как не получится и подставлять значения из файлов через команду \input.

Поэтому мы пойдём другим путём, как завещал нам Ильич, и напишем скрипт на питоне, генерирующий полный текст латеховского файла с использованием безграничных возможностей команды date. Собственно, идея в том, чтобы написать простенький скрипт на Питоне и вызывать его каждый раз латехом для обновления файлов календаря.

Скрипт на Питоне для генерации файлов календаря

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

Весь латеховский файл представляет собой склеенные строки в переменной out. Вставка символа r в строках out +=r'\begin{landscape}'+'\n' указывает Питону не интерпретировать \b а печатать как есть. Вызов команды date делается через os.popen(cmd), хотя теперь так уже не модно (но тем не менее работает), а модно через subprocess.check_output (но у меня так не получилось).

От полученной строки из команды date отдельно откусывается символ новой строки через .rstrip('\n') и далее сшивается с другими стоками. Результат записывается в файл tmpCalendarMonth.tex, который в свою очередь вставляется в ЛаТеХ через \input{Calendar/tmpCalendarMonth} и обрабатывается при сборке. Скрипт на питоне ниже:
#! /usr/bin/python
import string, os
import commands

kmvStartDir = '.'
kmvDestDir = kmvStartDir+'/Calendar/' #destination directory for graphs

###### Getting dates and months as text using DATE command in Linux ####
cmd='date --date="today" +%Y'
stdout_handle = os.popen(cmd)
kmv_year = stdout_handle.read()
kmv_year = kmv_year.rstrip('\n')
stdout_handle.close()

cmd='date --date="today" +%B'
stdout_handle = os.popen(cmd)
kmv_month = stdout_handle.read()
kmv_month = kmv_month.rstrip('\n')
stdout_handle.close()

cmd='date --date="today" +%e'
stdout_handle = os.popen(cmd)
kmv_day = stdout_handle.read()
kmv_day = kmv_day.rstrip('\n')
stdout_handle.close()

####################################
#### Month Calendar regeneration ###
####################################
kmvCalName = kmvDestDir+'tmpCalendarMonth'

out = '' 
out +=r'\begin{landscape}'+'\n'
out +=r'\begin{monthly}'
out +='\n {firstday=1} \n'
out +='{Calendar/myEvents} \n'
out +=kmv_month+' '+kmv_year+'\n'
out +='\end{monthly}\n'
out +='\end{landscape}\n'

### Output to the Calendar's file ######
kmvCalName+='.tex'
fout=open(kmvCalName,'w')
fout.write(out)
fout.close()
####################################

Скрипт calendar_regenerate.py и все остальные файлы можно взять отсюда. Скрипт написан для того, чтобы быть максимально понятным, а не красивым или эффективным.

Вызов скрипта на Питоне из LaTeX

Вызывать скрипты из латеха можно несколькими способами:
Здесь я приведу второй вариант, как наиболее простой. Для этого мы помещаем питоний скрипт calendar_regenerate.py в тот же каталог, где лежит файл 4myGTD.tex, из которого скрипт будет вызываться. В преамбуле документа пишем:

%%% Python script for calendar regeneration
\immediate\write18{./calendar_regenerate.py}

Чтобы всё это заработало, нужно вызывать LaTeX с параметром -shell-escape который позволяет выполнение внешних скриптов.

Кто такой \write18 и почему так называется?!

Команда \write это низкоуровневая инструкция TeX, которая используется для того, чтобы производить запись в файловые "потоки". ТеХ ссылается на каждый открытый файл не по имени, а по номеру. Поток 18 является особым и зарезервирован для того, чтобы попросить операционную систему что-то выполнить - например, внешний скрипт.
Внимание! Как совершенно справедливо отмечается многими, подобный трюк в сочетании с параметром –shell-escape небезопасен и представляет собой потенциальную дыру в безопасности. Так можно написать вредоносный документ с командой типа \write18{rm -rf ~} в Unix. По этому поводу есть статья (PDF) об этой и других опасных командах в LaTeX.
Команда \immediate приказывает ЛаТеХ выполнить скрипт немедленно, не дожидаясь окончания генерации всего документа. В данном случае это оправдано, так как мы хотим, чтобы в документ вставился уже обновлённый календарь.

Заключение

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

Как объединить и разбить PDF в Linux подручными средствами



16 коммент.
В этой безблагодатной и беспросветной жизни, когда тебе в линукс присылают документы в DocX и формы в последнем Adobe Acrobat, приходится несладко. Часто заполненные с воем и рыданиями PDF-файлы приходится склеивать или, наоборот, разрезать на несколько. К счастью,деятели опенсорса иногда отвлекаются от Wayland, Mir и прочих systemd и делают годные костыли для простых страждущих.

Объединение файлов pdf в один с помощью PDFSaM

Для тех, кто не хочет перечитывать томик квантовой физики от авторов pdftk, есть вариант с рюшечками и бубенчиками под названием PDF Split and Merge (pdfsam).
Как это всегда бывает, когда что-то кажется слишком прекрасным, чтобы быть правдой, обязательно найдётся заподлянка. И pdfsam не исключение - написан он на Java, а это значит кучи exceptions по поводу и без, лютые тормоза и интерфейс из фильма ужасов.

Установка и использование PDFsam в Linux

Скачать самую свежую версию можно здесь. Запуск этого поделия командой
$ java -jar pdfsam
даёт что-то вроде:


Собственно, дальше всё довольно просто: pdfsam умеет объединять (merge), разрезать (split), поворачивать (rotate) документы PDF. Кроме того, имеет место быть режим burst, при котором из одного PDF-файла будет сделана куча одностраничных.


Например, для объединения PDF-файлов в один, просто добавляем файлы в порядке следования, выбираем новое имя файла и жмём RUN.

Из преимуществ можно отметить разве что графический, скажем так, интерфейс. Всё остальное - это типичное джава приложение: глючное, медленное и корявое (например, при split нужно указывать номер страницы, на единицу меньший той, с которой разрезание начнётся, и т.д.).

Сжатие и компрессия PDF файлов

Побочным продуктом работы pdfsam может быть раздувание PDF-файла до непричиных размеров. Этому горю можно помочь с помощью утилиты gs вот так:
gs -sDEVICE=pdfwrite -dCompatibilityLevel=1.4 -dPDFSETTINGS=/screen -dNOPAUSE -dQUIET -dBATCH -sOutputFile=output.pdf input.pdf
Это может сжать PDF, по крайней мере в большинстве случаев.

Мастерам консоли: резка и склейка PDF файлов в pdftk

PDFtk расшифровывается как pdf tool kit, и, как и подобает настоящему набору инструментов, требует некоторого изучения. Зато работает быстро, умеет много и клацать мышью не надо.
Установка pdftk проста - он уже есть в Debian:
$ sudo apt-get install pdftk
Синтаксис pdftk можно описать примерно так:
pdftk исходный_файл.pdf ДЕЙСТВИЕ страницы output получаемый_файл.pdf
Итак, поехали....

Как разбить PDF файл на несколько

Для того, чтобы разрезать PDF-файл на несколько, нужно воспользоваться ДЕЙСТВИЕМ cat, например вот так:
$ pdftk document.pdf cat 140-142 output zz1.pdf
Эта команда выдаст файл zz1.pdf, в котором будут три страницы, а именно 140, 141 и 142. Если же нужно разбить файл с какой-то страницы до конца, делаем так:
$ pdftk foo.pdf cat 30-end output biography.pdf

Объединение нескольких файлов PDF в один с помощью PDFtk

Та же самая команда cat может склеивать PDF-файлы в один:
$ pdftk zz* cat output Issue26.pdf
служит для объединения всех файлов, содержащих zz в имени, в один Issue26.pdf
Если файлы называются по-разному, можно использовать следующую команду для объединения файлов в один:
$ pdftk 1.pdf 2.pdf ... cat output merged.pdf
будет объединён в один файл merged.pdf.

Изменение полей PDF-документа

Речь идёт о полях в PDF файле вроде автора, заголовка или времени создания:

Не раз и не два товарищи, работающие с документами повышенной важности, оставляли в этих полях значения, подставленные услужливым MS Word - и имели на этом немало проблем. Это можно поправить с помощью pdftk сравнительно легко.
Сначала достаём исходные данные (metadata):
pdftk book.pdf dump_data output report.txt
В этом файле мы увидим нечто вроде:
InfoKey: Title
InfoValue: Coders At Work
InfoKey: Author
InfoValue: Peter Seivel
InfoKey: Subject
InfoValue: Programming
Эти значения можно отредактировать в полученном текстовом файле (report.txt в этом примере) и загрузить обратно:
pdftk book.pdf update_info report.txt output bookcopy.pdf
У pdf-документов могут быть и другие поля, которые тоже можно поправить при желании.

И это ещё не всё!

Возможности pdftk весьма велики, и желающие могут припасть к официальной документации.


Склейка страниц PDF файла в буклет с помощью LaTeX pdfpage

Отличная иллюстрация мощи пакета pdfpages была найдена на tex.stackexchange.com. Идея сводится к тому, что сначала мы создаём исходный документ, а потом ещё один, в который вставляются PDF-страницы в нужном порядке.

Например, у нас есть документ под формат А6, созданный в ЛаТеХе (назовём его mya6doc.pdf:

\documentclass{book}
\usepackage[english]{babel}%
\usepackage[a6paper]{geometry}% http://ctan.org/pkg/geometry
\usepackage{lipsum}% http://ctan.org/pkg/lipsum
\begin{document}
\chapter{First chapter} \lipsum[1-10]
\chapter{Second chapter} \lipsum[11-20]
\chapter{Third chapter} \lipsum[21-30]
\chapter{Final chapter} \lipsum[31-40]
\end{document}

Теперь создаём ещё один документ (назовём его mya4doc):

\documentclass{article}
\usepackage[english]{babel}%
\usepackage[a4paper]{geometry}% http://ctan.org/pkg/geometry
\usepackage{pdfpages}% http://ctan.org/pkg/pdfpages
\begin{document}
\includepdf[pages=-,nup=2x2,frame,noautoscale]{mya6doc}%
\end{document}

Скомпилировать его нужно с помощью pdflatex. Это позволит получить все страницы (pages=-) в 2x2 страницы на одной (nup=2x2) с прорисованной границей вокруг каждой страницы (frame).

Это означает, что pdfpages воспринимает вставляемые страницы как изображения, так что можно дополнительно задать поля для обрезки:

\includepdf[pages=1,landscape,clip,trim=1cm 2cm 3cm 4cm,frame,noautoscale,fitpaper=false]{AllTheMyGTDinOneScheme}

то есть страница будет обрезана на 1, 2, 3, 4 сантиметра слева, снизу, справа и сверху. Опция clip=true обрежет страницу.

Путь джедая: склеивание PDF документов с помощью gs

Как многие джедаи уже в курсе, gs это GhostScript, свободный как Столлман интерпретатор postscript и, соответственно, PDF. Командой gs можно не только орехи колоть, но и соединять документы. Соединять документы с помощью Ghostscript можно вот так:
$ gs -dBATCH -dNOPAUSE -q -sDEVICE=pdfwrite -sOutputFile=finished.pdf file1.pdf file2.pdf
Теперь что это всё значит:

-dBATCH -- после окончания пакетной обработки, GS прекращает работу (без этой опции он будет продолжать имитировать бурную деятельность)
-dNOPAUSE -- обрабатывать каждую страницу без пауз между ними
-q -- тихий режим, без выдачи сообщений
-sDEVICE=pdfwrite -- использовать встроенный обработчик PDF
-sOutputFile=finished.pdf -- записать выхлоп в файл finished.pdf
 
Преимущество такого джедайства в том, что Ghostscript входит во все дистрибутивы Linux и часто уже установлен в системе. И не нужно тащить килотонны джавы.

Сохранение размеров EPS файлов при конвертировании в PDF

Не совсем в тему, но тем не менее про PDF. Дело в том, что при конвертировании файлов EPS в PDF разными поделками вроде ps2pdf вы получаете PDF в виде пустой страницы A4 с картинкой EPS где-то в углу. То есть поделка ps2pdf просто игнорирует выставленный BoundingBox при использовании по умолчанию:
 
$ ps2pdf letterhead.eps
Я не буду говорить о вменяемости авторов ps2pdf, но всякий разработчик с IQ выше комнатной температуры должен понимать, что подобные WTF-моменты в пользовательском опыте в конечном итоге приводят к тому, год линупсов на десктопе уезжает в голубую даль. И это происходит именно из-за таких вот казусов, коих в ёпенсорце год от года становится только больше из-за набегающих леннартов поттерингов и прочих ковбоев, склонных к тяжёлому велосипедостроению там, где этого абсолютно не требуется.
Так как ps2pdf принимает те же аргументы, что и Ghostscript, имеющий 900 газиллионов опций, среди которых должна быть возможность сохранять BoundingBox. И таки да, чудо случилось:

$ ps2pdf -dEPSCrop letterhead.eps

который даёт тот самый PDF, который от него, собственно, и ждёшь.

Заключение

Перечисленные возможности - не предел мечтаний, и всегда можно найти свежесобранный опенсорцовый велосипед со спойлером, антикрыльями и колёсами в форме листа Мёбиуса. Обнаружившим нечто интересное в деле работы с PDF документами просьба не стесняться в комментариях.
Читать далее

Как экстрагировать подсвеченный (highlight) текст из PDF файлов в Linux: Zotero и ZotFile



29 коммент.
Когда читаешь текст статей и книг в PDF-файлах, есть желание подсветить (highlight) интересные участки и вернуться к ним ещё разок - прямо как на бумаге. Более того, хочется текст из этих самых подсвеченных участков выдрать из PDF и экспортировать куда-нибудь ещё. И желательно это сделать в Linux и без необходимости загружать виртуальную машину с десктопным софтом для Windows. Казалось бы, в опенсорце так любят изобетать велосипеды, и должен же какой-нибудь велосипедостроитель до этого дотумкать.

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

Читать далее