Рекурсивные объекты и фрактальные узоры. Программирование

Программирование >> Рекурсивные объекты и фрактальные узоры

1 ... 31 32 33 [ 34 ] 35 36 37 ... 43

ГЛАВА 8.

операции с текстовыми данными

Обработка текстовых данных - тематика почти столь же старая, что и ре-nienne математических задач. В последнее время анализ строк связывается ещё и с актуальными проблемами генетики (в частности, последовательности генов ДНК описываются текстовыми строками). Алгоритмам на строках посвящают целые книги

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

8,1, В КАЧЕСТВЕ РАЗМИНКИ - ПОИСК АНАГРАММ

Ничего, кроме смекалки

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

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

Пример ввода:

кот брак бра ток крот бар краб Программа должна вывести:

брак барк краб бра бар крот ток кот

1 См., например, Д. Гасфилд. Строки, деревья и последовательности в алгоритмах: информати-

ка и вычислительная биология. СПб.: БХВ, 2003.

Решение

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

(кот, (брак (бра, (ток, (барк (крот (бар, (краб

кот) абкр)

абр)

кот) , абкр) , корт)

абр) , абкр)

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

(брак,

(барк,

(краб,

(бра,

(бар,

(крот,

(ток,

(кот.

абкр) абкр) абкр)

абр)

абр) корт)

кот)

Осталось лишь пройтись по списку и распечатать найденные анаграммы.

8.2. ПРОВЕРКА ПРАВОПИСАНИЯ. ИСПОЛЬЗОВАНИЕ РАССТОЯНИЯ ЛЕВЕНШТЕЙНА

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

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

Например, если входной документ содержит фразу:

тарелка стояла на стле.

то программа должна напечатать:

Не найдено: стле. Варианты: стиле, столе, стуле.

Похожесть слов определяется с помощью расстояния Левенштейна. Процедура определения расстояния между входными строками s и t приведена на псевдокоде:

int LevenshteinDistance(char s[l..n], char t[l..in]) int d[0..n, 0..m]; int i, j, cost;

for i := 0 to n

d[i.O] := i; for j := 0 to m

d[0,j] := j;

for i := 1 to n

for j := 1 to m

if s[i] = t[j] then cost := 0;

else cost := 1; d[i,j] := ininimum(d[i-l, j ] + 1, вставка

d[i, j-l]+l, удаление

d[i-l,j-l] + cost); замена

return d[n,m];

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

Можно также использовать эвристические методы. Например, если некоторая картинка или flash-анимация находится в подкаталоге banners или adverts, загружать её, вероятно, не стоит.

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

Задача заключается в программировании ядра баннсрорезалки. Па вход программе поступает список фильтров (о нём ниже) и обрабатываемая HTML-страпица. На выходе создаётся страница с вырезанными багптсрами. Хорошие системы фильтрации обычно замещают бапнсры пустыми прямоугольниками, поэтому внешний вид страницы не очс!п> страдает. В нашем случае для простоты можно вместо ссылки на баннср поставить ссылку на локалыплй компьютер http: 127.0.0.1.

Например, фрагмент:

будет заменён на:

width=240 height=400 marginwidth=0 Tnarginheight=0 scrolling=no frameborder=0>

В браузере при этом отобразится рамка, сигнализирующая об отсутствии ресурса (рис. 8.1).

8.3, БАННЕРОРЕЗАЛКА, ИЛИ ПОИСК СТРОК ПО

ШАБЛОНУ

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

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

[х] CAPhosl banner

Рис. 8.1. Вырезанный баннер

Элементами списка фильтров являются шаблоны строк, описывающие адреса баннеров. Например:

*/adframe.*

*/ads??.*

♦/banner/*

♦counter*.bravenet.*

Символы подстановки * и ? несут стандартную смысловую нагрузку: знак * означает произвольное количестволюбых символов (в том числе пустую строку), знак ? замещает ровно один произвольный символ.

1 ... 31 32 33 [ 34 ] 35 36 37 ... 43