Pattern matching and text compression algorithms
В настоящем докладе описываются несколько стандартных алгоритмов, используемых для обработки текстов. Они применяются , например, к манипулированию текстов ( слово редакторы ) , в хранилище текстовых данных (текст сжатии) , а также данные поисковые системы . Алгоритмы доклада интересны в различных аспектах. Во-первых, они являются основными компоненты, используемые в практической реализации программного обеспечения. Во-вторых, они вводят программирования методов, которые служат парадигм в других областях компьютерных наук ( системы или программного обеспечения ) . В-третьих, они играют важную роль в теоретической информатике , предоставляя сложных проблем . Хотя данные запоминаются по-разному, текст остается основной формой для обмена информацией. Это особенно очевидно в литературных данных или лингвистики , где данные состоят из огромного тела и словарей. Это также применимы в информатике , где большое количество данных, которые хранятся в линейном файлов. И это тожеимеет место, например , в области молекулярной биологии , потому что биологические молекулы могут часто можно аппроксимировать в виде последовательностей нуклеотидов или аминокислот. Кроме того, количество доступных Данные в этих областях , как правило, удваивается каждые восемнадцать месяцев. Это является причиной, почему алгоритмы должны быть эффективным, даже если скорость компьютеров регулярно увеличивается . Сопоставление с шаблоном задачи размещения конкретного шаблона внутри исходных данных . Образец обычно набор строк, описанных в некотором формальном языке . Два вида текстовой модели представлены : одной строки и приближенных строк. Приведем два алгоритма сопоставления с шаблоном в образах, которые являются расширениями строки алгоритмам. В нескольких приложениях , тексты должны быть структурированы , прежде чем искать. Даже если нет никакой дополнительной информации
Известно на их синтаксической структуры , можно и в самом деле очень эффективны построить структуру данных , который поддерживает поиск. Среди нескольких существующих структур данных эквивалентна индексы, мы представляем Дерево суффиксов с его строительством . Сравнение строк подразумевается в приближенной задачи поиска шаблона. Так как это иногда требуется только для сравнения двух строк (файлы, или молекулярных последовательностей ) вводятся основные Метод, основанный на длинной общей подпоследовательности . Наконец, в докладе содержится две классические алгоритмы сжатия текста. Варианты этих algorihms реализованы в практических программного обеспечения сжатия , в которых они часто в сочетании друг с другом или с помощью другими элементарными методами. Эффективность алгоритмов оценивают их время работы, а иногда и количество места в памяти они требуют во время выполнения.
