Как найти общие пути из списка путей / файлов

Question

Прелюдия:

Учитывая отсортированный ввод списка путей / файлов, как найти их общие пути?

В переводе на технический термин, если подать отсортированный ввод из stdin, как выбрать самый короткий правильный префикс из stdin?

Здесь "префикс" имеет нормальное значение, например, строка "abcde" имеет префикс "abc". Вот мой пример ввода

$ echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2'
/home/dave
/home/dave/file1
/home/dave/sub2/file2

Это пример удаления последующего правильного префикса из стандартного ввода с помощью команды sed:

$ echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2' | sed "N; /^\(.*\)\n\1\//D; P; D" 
/home/dave/file1
/home/dave/sub2/file2

Вопрос:

Мой вопрос заключается в том, как вместо этого сохранить правильный префикс и удалить все строки, которые имеют этот префикс. Так как оба /home/dave/file1 и /home/dave/sub2/file2 имеют префикс /home/dave , /home/dave будет сохранен, а два других - нет. То есть, это будет полностью противоположно тому, что делает вышеуказанная команда sed .

Больше информации:

• Вход будет уже отсортирован
• Если у меня есть /home/dave /home/dave/file1 /home/phil /home/phil/file2 (echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2\n/home/phil\n/home/phil/file2'), я ожидаю, что ответом будут /home/dave и /home/phil .

Заявка:

У меня есть два тома диска с похожим содержанием. Я хочу скопировать то, что есть в v1, но отсутствует в v2, на другой том диска, v3. Используя find , sort и comm , я могу получить список того, что копировать, но мне нужно еще кое-что почистить. Т.е., пока у меня есть /home/dave в списке, мне не нужны другие два.

Спасибо!

Answer 1

Этот ответ использует Python. Поскольку ОП хотел удалить каталоги, на которые ссылались их родители, как я видел возможность, я начал писать другую программу для удаления покрытий:

Пример:

$ echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2\n/home/phil\n/home/phil/file1' | removecoverings 
/home/phil
/home/dave

Код команды removecoverings :

#!/usr/bin/env python2

import sys

def list_startswith(a, b):
    if not len(a) >= len(b):
        return False
    return all(x == y for x,y in zip(a[:len(b)],b))

def removecoverings(it):
    g = list(it)
    g.sort(key=lambda v: len(v.split('/')), reverse=True)
    o = []
    while g:
        c = g.pop()
        d = []
        for v in g:
            if list_startswith(v.split('/'), c.split('/')):
                d.append(v)
        for v in d:
            g.remove(v)
        o.append(c)
    return o

for o in removecoverings(l.strip() for l in sys.stdin.readlines()):
    print o

---

Этот ответ использует Python. Он также выполняет компонентный, а не строковый общий префикс. Лучше для путей, поскольку общий префикс /ex/ample и /exa/mple должен быть / not /ex . Это предполагает, что требуется самый распространенный префикс, а не список префиксов с удаленными покрытиями. Если у вас есть /home/dave /home/dave/file1 /home/phil /home/phil/file2 и ожидаете /home/dave /home/phil а не /home . Это не тот ответ, который вы бы искали.

Пример:

$ echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2' | commonprefix 
/home/dave

Код команды commonprefix :

#!/usr/bin/env python2

import sys

def commonprefix(l):
    # this unlike the os.path.commonprefix version
    # always returns path prefixes as it compares
    # path component wise
    cp = []
    ls = [p.split('/') for p in l]
    ml = min( len(p) for p in ls )

    for i in range(ml):

        s = set( p[i] for p in ls )         
        if len(s) != 1:
            break

        cp.append(s.pop())

    return '/'.join(cp)

print commonprefix(l.strip() for l in sys.stdin.readlines())

Answer 2

Учитывая, что входные данные отсортированы, псевдокод будет:

$seen = last_line;
if current_line begins exactly as $seen then next
else { output current_line; $seen = current_line }

Перевод на Perl-код (да, Perl, самый красивый язык сценариев из всех):

perl -e '
my $l = "\n";
while (<>) {
    if ($_ !~ /^\Q$l/) {
        print;
        chomp;
        $l = $_;
    }
}
'

Предоставлено : Ben Bacarisse @ bsb.me.uk, comp.lang.perl.misc. Спасибо Бен, это прекрасно работает!

Answer 3

И, версия с одним вкладышем ответа XPT. Опять же, предполагая отсортированный ввод:

perl -lne 'BEGIN { $l="\n"; }; if ($_ !~ /^\Q$l/) { print $_; $l = $_; }'

Запустить на входе примера

/home/dave
/home/dave/file1
/home/dave/sub2/file2
/home/phil
/home/phil/file2 

с помощью

echo -e '/home/dave\n/home/dave/file1\n/home/dave/sub2/file2\n/home/phil\n/home/phil/file2' | perl -lne 'BEGIN { $l="\n"; }; if ($_ !~ /^\Q$l/) { print $_; $l = $_; }'

дает

/home/dave
/home/phil

Волшебство заключается в аргументах командной строки для perl: -e позволяет нам задавать скрипт в командной строке, -n выполняет итерации по строкам файла (помещая каждую строку в $_), а -l работает с символами новой строки для нас.

Сценарий работает с использованием l для отслеживания последнего увиденного префикса. Блок BEGIN выполняется до того, как будет прочитана первая строка, и инициализирует переменную строкой, которая не будет видна (без новых строк). Условие выполняется в каждой строке файла (удерживается $_). Условие выполняется во всех строках файла и говорит, что «если строка не имеет текущего значения l в качестве префикса, выведите строку и сохраните ее как значение l ». Из-за аргументов командной строки это по существу идентично другому сценарию.

Уловка в том, что оба сценария предполагают, что общий префикс существует как отдельная строка, поэтому не нужно искать общий префикс для ввода, например

/home/dave/file1
/home/dave/file2