Рецензии на книгу
"Методы и алгоритмы вычислений на строках"

14.03.2007

Андрей Ставровский, канд. ф.-м. н., доцент КНУ имени Тараса Шевченка.

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

В монографической литературе алгоритмы обработки строк появились в 1970-х годах. В классической книге по алгоритмам А.Ахо, Дж.Хопкофта, Дж.Ульмана "Построение и анализ вычислительных алгоритмов", перевод которой вышел в уже далеком 1979г., работе со строками была посвящена глава. Из последных изданий отмечу фундаментальную книгу Т.Кормена, Ч.Лейзерсон, Р.Ривест, К.Штайн, "Алгоритмы. Построение и анализ" и монографию В.И.Романовского по дискретному анализу. Однако подобных изданий очень мала, и в них представлены лишь отдельные задачи и алгоритмы обработки строк.

Есть несколько англо- и франкоязычных книг, посвященных теоретическим основам и практическим алгоритмам обработки строк, но они недоступны русскоязычному читателю. Таким образом, перевод книги Б.Смитта "Методы и алгоритмы вычислений на строках" (в оригинале - "Computing Patterns in String") заполняет довольно серьезный пробел в русскоязычной литературе.

Данная книга содержит как базовые теоретические сведения, связанные со строками и "паттернами" ("образцами", "шаблонами"), так и постановки основных задач обработки строк и конкретные методы и алгоритмы их решения.

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

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

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

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

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

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

31.10.2006
Регулярные выражения
Андрей Шитов
http://regexp.ru/books/smyth/

Алгоритмы на строках — это алгоритмы поиска и работы с подстроками-образцами, называемыми паттернами. Книга организована в соответствии с классификацией строковых паттернов, о которой автор говорит в предисловии. Каждому из трех типов паттернов соответствует своя часть книги: II Вычисление внутренних паттернов, III Вычисление частных паттернов и IV Вычисление характеристических паттернов.

Обработка строковых данных крайне необходима практически во всех областях современного программирования, как в традиционных офлайновых средах, так и в интернете. Например, многие распространенные протоколы передачи данных основаны на текстовом представлении. При этом нетекстовые данные подвергаются сериализации и становятся текстом. На стремительное развитие текстовых форматов обмена повлияли, в частности, стандарты HTTP и XML и огромное число производных от последнего форматов.

Книга будет полезна, например, разработчикам поисковых систем в интернете, создателям электронных словарей, программистам, создающим инструментальные средства для работы других программистов или разработчикам браузеров. Не секрет, что многие текстовые редакторы начинают работать неадекватно медленно при попытке заменить один фрагмент текста другим в документе большого объема, а браузеры иногда крайне долго анализируют принятый HTML-код.

Особый интерес должны проявить разработчики систем автоматической классификации и кластеризации текстов (например, сайтов-агрегатов новостей или блогов). Описанные в книге алгоритмы вычисления расстояния между строками и приближенного сравнения с образцом (главы 9 и 10) окажутся полезными, в частности, в задачах автоматического выявления плагиата.

Автор подходит к описанию проблем по возможности абстрактно, обильно используя математическую нотацию и при этом не ориентируется на какой-либо конкретный язык программирования. С одной стороны, это требует более или менее основательной математической подготовки читателя, с другой — такую книгу не почитаешь в метро, поскольку чтение требует внимания и сосредоточенности. Несмотря на большое число математики, автор (про это он делает оговорку, например, в начале 11-й главы) старается соблюсти необходимый минимум абстракции, вводя новые понятия только по необходимости.

Регулярным выражениям посвящена отдельная глава (как раз только что упомянутая 11-я). Поклонникам регеспов будет интересно сравнить строгое описание Смита с описанием тех же алгоритмов в книге Фридла.

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

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

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

С текстом перевода хуже. Например, читая предисловие, я несколько раз спотыкался на неудобном тексте. Сравнив эти места с английским оригиналом, выяснилось, что недостаточно качественно выполнены не только редактура и корректура текста, но и сам перевод. Например: С. 11. «Данная книга ставит целью заполнить этот пробел...». Сразу бросается в глаза неверное слово «заполнить» вместо более уместного здесь «восполнить». Очевидно, что это дословный перевод англ. fill the gap. Если сравнить с оригиналом, то окажется еще хуже: авторская мысль искажена. В оригинале сказано, что автор собирается только начать заполнять пустоту: The purpose of this book then is to begin to fill a gap. Слово begin при переводе потерялось.

С. 14. «Я поддерживаю Web-узел». По русски правильно говорить просто «сайт» или, если угодно переводчику, «веб-узел». Но не «веб-сайт» и тем более не «web-узел».

С. 19. «...метки не обязаны принимать значения только целых положительных чисел». Фраза «принять значение числа» совершенно неестественна и почти лишена смысла. Оригинальная фраза была намного легковеснее для чтения — «метки не обязательно должны быть целыми числами»: they do not need to be integers. Кстати, ни слова о том, что числа положительны.

С. 22. «...где элементами будут определенные (...) вместе со „словами“, со „словами“, заключенными между...». Вместо пропущенного слова после «определенные» дважды повторяется «со „словами“». Оригинал: ...whose elements are certain “separators” (...) together with the “words” between separators.

С. 23. «...будь-то действительные числа...». Правильно: «будь то».

Резюме: книгу должны обязательно прочитать те, кто собирается серьезно заниматься обработкой текстов.