Perl. Библиотека программиста

Поиск повторяющихся слов

Проблема

Требуется найти в документе повторяющиеся слова.

Решение

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

Комментарий

Механизм поиска запоминает часть строки, которая совпала с частью шаблона, заключенной в круглые скобки. Позднее в шаблоне обозначение \1 ссылается на первый совпавший фрагмент, \2 — на второй и т. д. Не используйте обозначение $1 — оно интерпретируется как переменная и интерполируется до начала поиска. Шаблон /([A-Z])\1/ совпадает с символом верхнего регистра, за которым следует не просто другой символ верхнего регистра, а именно тот, что был сохранен в первой паре скобок.

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

Модификатор /х разрешает внутренние пропуски и комментарии, упрощающие чтение регулярных выражений. Модификатор /i позволяет найти оба экземпляра "is" в предложении "Is is this ok?". Модификатор /g в цикле while продолжает поиск повторяющихся слов до конца текста. Внутри шаблона метасимволы \b (граница слова) и \s (пропуск) обеспечивают выборку целых слов.

$/=";
while (<>) {
  while ( m{
            \b
            (\S+)
            \b
            (
              \s+
              \1
              \b
            ) +
           }xig
        )
  {
  print "dup word  '$1'  at paragraph $.\n";
  }
}

Приведенный фрагмент найдет удвоенное test в следующем примере:

This is a test
test of the duplicate word funder.

Проверка \S+ между двумя границами слов обычно нежелательна, поскольку граница слова определяется как переход между \w (алфавитно-цифровым символом или подчеркиванием) и либо концом строки, либо не-\w. Между двумя \b обычный смысл \S+ (один и более символов, не являющихся пропусками) распространяется до последовательности символов, не являющихся пропускам первый и последний символ которой должны быть алфавитно-цифровыми символами или подчеркиваниями.

Рассмотрим другой интересный пример использования обратных ссылок. Представьте себе два слова, причем конец первого совпадает с началом второго например, "nobody" и "bodysnatcher". Требуется найти подобные «перекрытия». Сформировать строку вида "nobodysnatcher". Это вариация на тему нашей основной проблемы — повторяющихся слов.

Чтобы решить эту задачу, программисту на С, привыкшему к традиционной последовательной обработке байтов, придется написать длинную и запутанную программу. Но благодаря обратным ссылкам задача сводится к одному простому поиску:

$а = 'nobody'; 
$b = 'bodysnatcher';
if ("$a $b" =~ /^(\w+)(\w+) \2(\w+)$/) {
  print "$2 overlaps in $1-$2-$3\n";
}
body   overlaps   in   no-body-snatcher

Казалось бы, из-за наличия максимального квантификатора переменная $1 должна захватывать все содержимое "nobody". В действительности так и происходит — на некоторое время. Но после этого не остается ни одного символа, который можно было бы занести в $2. Механизм поиска дает задний ход, и $1 неохотно уступает один символ переменной $2. Пробел успешно совпадает, но далее в шаблоне следует переменная \2, которая в настоящий момент содержит просто "у". Следующий символ в строке — не "у", а "b". Механизм поиска делает следующий шаг назад; через некоторое время $1 уступит $2 достаточно символов, чтобы шаблон нашел фрагмент, пробел и затем тот же самый фрагмент.

Этот прием не работает, если само перекрытие содержит повторяющиеся фрагменты — как, например, для строк " rococo" и "cocoon". Приведенный выше алгоритм решит, что перекрываются символы "со", а не "coco". Однако мы хотим получить не "rocococoon", a "rococoon". Задача решается включением минимального квантификатора в $1:

/^(\w+?)(\w+) \2(\w+)$/

Поиск повторяющихся слов

Проблема

Решение

Комментарий

См. также