От переводчика: предлагаю вашему вниманию перевод очень старой статьи, опубликованной 15 января 1983 года. Несмотря на столь внушительный возраст, статья показалась мне интересной, и возможно, что она будет полезной для кого-то и сегодня. На эту статью, кстати, ссылается раздел справки man locate(1) на opennet.ru: https://www.opennet.ru/man.shtml?topic=locate.

Краткое содержание

Статья описывает механизм быстрого поиска файлов в UNIX. Он объединяет два метода компрессии данных с новой техникой поиска строк, и предназначен для быстрого поиска произвольных файлов. Код, интегрированный в стандартную утилиту find, производит поиск в предварительно созданной базе данных, обновляемой ежедневно. Это отличает его от обычного механизма поиска совпадений ключа с кандидатами, которые генерируются «на лету» из разбросанной (по диску) структуры директорий.

База данных путей к файлам является инкрементально-кодированным, отсортированным в лексикографическом порядке списком (иногда называемом «сжатым спереди» файлом), который также подвергнут обычному биграмному кодированию с целью получения эффективного сжатия. Коэффициент сжатия составляет от 5 до 6 по сравнению с обычным ASCII-представлением. Список сканируется с использованием модифицированного линейного поиска, специально приспособленного для инкрементального кодирования, при этом типичное время, затрачиваемое алгоритмом, на 40-50% меньше, чем обычный поиск.

Введение

Поиск файлов в компьютерной системе, или компьютерной сети, является сложным процессом. Пользователи UNIX могут осуществлять его различными способами, начиная с манипуляциями командами cd, ls и grep, до специализированных команд, таких как, разработанных в Беркли whereis и fleese, и до более распространённой юниксовой команды find.

К несчастью, fleece (из Беркли) ограничен домашней директорией, а whereis может искать только системный код и документацию, расположенную в стандартных местах.

Поиск:

find / -name "*<filename>*" -print

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

Предварительные вычисления

Почему бы не построить просто статический список всех файлов в системе и искать по нему grep-ом? Типичная система, содержащая 20000 файлов, будет содержать 1000 блоков имён файлов, даже если сократить /usr до /u. Grep на нашей ненагруженной системе PDP-11/70 обрабатывает 30-40 блоков в секунду, и потребует полминуты на сканирование. Это неприемлемо для часто используемой команды.

Но если мы принесём небольшую жертву — невозможность поиска файлов возрастом меньше суток, то это не создаст больших проблем, так как тот, кто создал такой файл, и так, скорее всего, находится в пределах досягаемости, или, возможно, файл ещё не готов к использованию. Старые файлы, созданные другими группами пользователей, с другими соглашениями именования файлов — это наиболее вероятные кандидаты на поиск.

Сжатие

Для ускорения доступа для приложений, можно предложить использовать бинарный поиск или хэш-таблицу, но такие схемы не работают хорошо для частичного сравнения, если нам интересна только часть имени. Легко реализуется техника сжатия упорядоченных данных, известная как инкрементальное кодирование, которая была применена для сходной задачи сжатия словаря [Morris/Thompson, 1974]. В этом случае вычисляется наиболее длинный префикс предшествующего имени. Например:

/usr/src
/usr/src/cmd/aardvark.c
/usr/src/cmd/armadillo.c
/usr/tmp/zoo

преобразуется в

0/usr/src
8/cmd/aardvark.c
14armadillo.c
5tmp/zoo

Декодирование будет простым (объявления переменных опущены)

fp = fopen(COMPRESSED_FILELIST, "r");
while((count = (getc(fp) & 0177)) != EOF) {
    for(p = path + count; (*p++ = getc(fp)) < 0200; )
        ; /*overlay old path with new*/
    ungetc(*--p, fp);
    *p-- = NULL;
    if(math(path, name) == YES)
        puts(path);
}

где math — функция, определяющая, содержится ли подстрока name в строке path.

Фактически, так как кодированный список примерно в пять раз короче некодированного, и декодирование производится очень просто, программа работает от трёх до четырёх раз быстрее, чем grep на текcтовом файле.

Ещё быстрее

Такой подход уже является полезным, но оставляет место для дальнейших усовершенствований. (Примечание: этот код используется в утилите find. Нет необходимости обременять UNIX ещё одной командой [и man-страницей], когда мы можем улучшить существующую аналогичную программу. К счастью, не существует вызова find с двумя аргументами, и мы можем заполнить пустоту без приукрашиваний:

find name

Отметим, что код, приведённый выше, по-прежнему производит поиск по распакованному списку, хотя и в памяти, а не на диске. Этого можно избежать путём сравнения строки с подстрокой в обратном направлении. Пусть namend указывает на последний символ строки name, и заменим math на:

for(s = p, cutoff = path + count; s > cutoff; s--) {
    if(*s == namend) { /*quick first char check*/
        for(p = namend - 1, q = s - 1; *p != NULL; p--, q--)
            if(*q != *p)
                break;
        if(*p == NULL) {
            puts(path);
            break;
        }
    }
}

Это проще понять, рассмотрев три случая. Если подстрока находится полностью справа от cutoff, сравнение будет заканчиваться успешно. Если они перекрываются, cutoff становится «мягким» и сравнение продолжается. Если подстрока лежит полностью слева от cutoff, то совпадение было бы выявлено для предыдущих строк, а значит, мы можем не выполнять этот поиск! Технически, cutoff может быть перенесён на path немедленно после выполнения сравнения. Это условие опущено выше.

Двухъярусная техника

Можно избежать замедления поиска, вызванного обработкой символов шаблонов поиска. При этом мы обрабатываем часть имени, не содержащую метасимволы, и используем более медленную рекурсивную функцию amatсh внутри find. То есть,

puts(path)

становится

if(globchars == NO | amatch(path, name))
    puts(path);

где globchars устанавливается, если name содержат метасимволы. Пример использования шаблона поиска для простой команды man:

vtroff -man 'find '*man*'"$1"'.[1-9]

Дальнейшие улучшения

Продакшн-код утилиты find увеличивает степень сжатия ещё на 20-25% путём замены самых распространённых двухсимвольных сочетаний на непечатаемые ASCII-коды. ".c" и ".P" встречаются особенно часто.

Другие алгоритмы, реализующие другие компромиссы между временем и размером данных, например, алгоритм Хаффмана [Reghbati, 1981] не выглядят многообещающими: они всего лишь заменяют ограничение по производительности ввода-вывода ограничением по быстродействию.

Могут быть использованы методы сублинейного поиска Бойера-Мура (Boyer-Moore) [Boyer, 1977] или метод макромоделей [Storer/Szymanski, 1982].

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

Ссылки

Boyer, R.S. A Fast String Searching Algorithm, Commun. ACM, Vol. 20, No 10, October 1977.
Morris, R. and Thompson, K. Webster's Second on the Head of a Pin, Unpublished Technical Memo, Bell Laboratories, Murray Hill, N.Y., 1974.
Reghbati, H.K. An Overview of Data Compression Techinques, Computer, Vol. 14, No. 4, April 1981.
Storer, J.A. and Szymanski, T.G. Data Compression via Textual Substitution, J. ACM, Vol. 29, No. 4, October 1982.