Главная » Java, Структуры данных и алгоритмы » Обработка текста

0

Обработка документов становится одной из наиболее важных функций компьютера. Компьютеры используются для редактирования, поиска, пересылки документов через Интернет, отображения на экране монитора и распечатки на принтере. Поиск и добавление информации в Сети становятся одной из важнейших сфер применения компьютеров, а значительная часть работы с документами состоит из обработки символьных строк и использования^ строковых шаблонов. Например, документы в формате HTML и XML изначально являются текстовыми, дополненными специальными метками, называемыми тэгами (tag), мультимедийного контекста. Чтобы найти требуемое в огромном объеме информации, имеющейся в Сети, необходимы значительные затраты на обработку текста.

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

Порядок рассматриваемых в этой главе тем является дальнейшим развитием исследования абстрактного типа данных. Терминология и понятия, используемые в этой главе для обсуждения строкового АТД, определяются в разделе 11.1. Оказывается, представление строки в виде массива символов является простым и удобным, поэтому не будем много говорить об этом. Тем не менее строковый АТД содержит любопытный метод для определения соответствий строковым шаблонам, алгоритм которого рассматривается в разделе 11.2. В разделе 11.3 описывается древовидная структура данных, которая позволяет осуществлять быстрый поиск в массиве строк. В разделе 11.4 приведена одна из существенных проблем обработки текста, а именно — сжатие текстового документа для более удобного хранения или пересылки по сети. Еще одну задачу, рассматриваемую в разделе 11.5, представляет собой сравнение двух документов. Все эти темы являются результатом общения авторов с Сетью при помощи различного рода поисковых машин, хранилищ документов, информационных справочников и т.п.

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии