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

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

Например:

/aaa/bbb /aaa/bbb/ccc /ddd/eee /fff/ggg /fff/ggg/hhh/iii /jjj/kkk/lll/mmm /jjj/kkk/lll/mmm/nnn 

Необходимо уменьшить до:

 /aaa/bbb /ddd/eee /fff/ggg /jjj/kkk/lll/mmm 

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

5 Solutions collect form web for “Отфильтруйте пути из текстового файла, который глубже, чем их непосредственный предшественник”

Я думаю, это должно сделать это. Измененный входной файл для добавления еще нескольких случаев

 $ cat ip.txt /aaa/bbb /aaa/bbbd /aaa/bbb/ccc /ddd/eee /fff/ggg /fff/ggg/hhh/iii /jjj/kkk/lll/mmm /jjj/kkk/lll/mmm/nnn /jjj/kkk/xyz 

Использование awk

 $ awk '{for (i in paths){if (index($0,i"/")==1) next} print; paths[$0]}' ip.txt /aaa/bbb /aaa/bbbd /ddd/eee /fff/ggg /jjj/kkk/lll/mmm /jjj/kkk/xyz 
  • paths[$0] – это ссылка на строку ввода как клавишу
  • for (i in paths) каждая строка сравнивается со всеми сохраненными ключами
  • if (index($0,i"/")==1) next если строка ввода совпадает с сохраненным ключом, добавленным с / в начале строки, затем пропустите эту строку
    • / используется для избежания соответствия /aaa/bbbd против /aaa/bbb

И обязательное решение sed :

 sed '1s/^/#/;x;G;\_#\([^#]*\)#.*\n\1/_s/\n.*//;s/\n\(.*\)/\1#/;h;$! d;x;s/^#//;s/#$//;y/#/\n/' 

Сценарий собирает пути в пространстве удержания. Для каждой новой строки пространство удержания добавляется в пространство шаблонов, чтобы проверить, произошло ли это.

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

Объяснение подробно:

 1s/^/#/ 

Для переносимости символ # используется для разделения путей в пространстве удержания. Для первой строки нам нужно начать с начального #

 x;G By exchanging the spaces and appending the hold space, we have the list of already occured buffers first, then the new path. \_#\([^#]*\)#.*\n\1/_s/\n.*// 

Если адрес \_..._ совпадает, новый путь является подпутью более раннего пути, поэтому удалите его.

 s/\n\(.*\)/\1#/ 

В нашем пространстве все еще есть новая строка, поэтому путь новый, и мы добавляем его в список.

 h;$! d 

Сохраните новый список в пространстве удержания и начните сначала, если это не последняя строка.

 x;s/^#//;s/#$//;y/#/\n/ 

Для последней строки удалите # в начале и конце и замените другой # символами новой строки.

Альтернатива для GNU sed

Это можно сделать более компактным с расширениями GNU на sed , если вы не возражаете, если заказ вернется:

 sed 'G;\_^\([^\n]*\)/.*\n\1\n_s/[^\n]*\n//;h;$! d;x;s/^\n//;s/\n$//' 

Объяснение, как указано выше, но используя новые строки как разделители вместо добавления # .

Что-то вроде этого:

 $ awk '{sub(/\/$/, "")} NR != 1 && substr($0, 0, length(prev)) == prev {next}; {print; prev = $0"/" } ' paths 

На всех, кроме первой строки ( NR != 1 ), сравните префикс этой строки с строкой, хранящейся в prev (столько же символов, сколько и длина prev ). Если они совпадают, перейдите к next строке. В противном случае print и сохраните эту строку в prev .

Предполагая, что файл отсортирован в локали C, т. Е. / Идет до любого из букв, или если он генерируется прогулкой по дереву каталогов, этого должно быть достаточно, чтобы протестировать предыдущую сохраненную строку. Если файл отсортирован в какой-либо другой локали, параметр / может не влиять на сортировку, что приводит к упорядочиванию как /aaa/bbb , /aaaccc , /aaa/ddd . Если файл не отсортирован вообще, поддиректории могут появиться перед их родителями, и проблема будет затруднена.

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

Решение, вдохновленное тем, что отправлено @Sundeep:

 awk -F / -v OFS=/ ' { p = $0 while(--NF > 1) { if ($0 in paths) next } print p paths[p] }' file 

Решение, отправленное @Sundeep, равно O(N^2) в числе N входных путей. Подход выше – O(M) на максимальной глубине D входных путей. Это должно быть значительно быстрее для большого количества входных путей.

Если вы знаете, что все пути имеют глубину не менее 9 уровней, вы можете, конечно, улучшить вышеизложенное, изменив --N > 1 на --N > 9 .

На стороне примечания: и мое решение, и сообщение, отправленное @Sundeep, предполагают, что все пути нормализованы (т. /foo/../../bar вас нет таких вещей, как /foo/../../bar , nor /foo//bar/baz ).

 perl -lne '$l=$_; grep $l =~ m|^\Q$_/|, @A or print, push @A, $_' 
  • Мы накапливаем все различные пути в array @A предоставляемом для данной строки, которые не соответствуют тому, что уже хранится в нем.
  • grep m|^\Q$_/| будут цитировать элементы массива и найти совпадение.

 sed -ne ' H # append current line into hold space g # pattern space = hold space \n current line y/\n_/_\n/ # change coordinate system \|_\([^_]*\)_\(.*_\)\{0,1\}\1/|s/\(.*\)_.*/\1/ # match yes, strip current line y/\n_/_\n/ # revert coordinate system h # update hold space $s/.//p # answer ' 

Вывод

 /aaa/bbb /ddd/eee /fff/ggg /jjj/kkk/lll/mmm 
  • Как добавить новые строки из другого файла с помощью sed
  • Изменить имена файлов в Makefile
  • Скопируйте первые 2 строки из файла, а затем удалите строки
  • команда sed для добавления другого текста при множественном вводе строки
  • Извлечь третью группу текста из разделителей диапазонов
  • bash расширяется до того же значения вместо значения строки за строкой в ​​команде sed
  • grep -A с обратной совпадением распечатывает только несоответствие в поле после
  • замените '_' на ',' в файле, который содержит список имен файлов
  • Как удалить строки, содержащие IP-адрес?
  • Сравните 2 файла, если он находится между диапазоном чисел
  • Как создать список, сгенерированный md5deep в алфавитном порядке относительных путей?
  • Linux и Unix - лучшая ОС в мире.