Get best of the week

快速文件搜索

译者的话：我提请您注意1983年1月15日发表的一篇非常古老的文章的译文。尽管年龄如此令人印象深刻，但这篇文章对我来说似乎很有趣，并且它可能对今天的某人有用。顺便说一句，本文由opennet.ru上的manlocate（1）帮助主题引用：https ://www.opennet.ru/man.shtml ? topic = locate 。



摘要


本文介绍了UNIX上的一种快速文件搜索机制。它结合了两种数据压缩方法和新的行搜索技术，旨在快速搜索任意文件。集成到标准查找实用程序中的代码将搜索以前创建的数据库，并每天进行更新。这使其与通常的搜索候选关键字匹配的机制有所区别，后者是从分散的（在磁盘上）目录结构中动态生成的。

文件路径数据库是一个按字典顺序排序的增量编码列表（有时称为“前压缩”文件），该列表也经过常规二元编码，以获得有效压缩。与通常的ASCII表示相比，压缩率是5到6。使用经过修改的线性搜索（特别适合于增量编码）扫描列表，而算法所花费的典型时间比常规搜索少40-50％。

介绍


在计算机系统或计算机网络中查找文件是一个复杂的过程。 UNIX用户可以通过多种方式来实现它，从操作cd，ls和grep命令到专用命令（例如在Berkeley whereis和fleese中开发的命令），再到更常见的find Unix命令。

不幸的是，羊毛（来自伯克利）仅限于主目录，而whereis只能搜索位于标准位置的系统代码和文档。

搜索：

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

当然，它可以搜索任意文件，但速度很慢，因为它在整个文件系统中使用递归下降，而在整个磁盘上无情地散布。不耐烦的心情促使我们开发了一种替代方法（与“搜索和查找”方法有关）来搜索文件路径。

初步计算


为什么不只是建立系统中所有文件的静态列表并在其上寻找grep？即使将/ usr缩短为/ u，包含20,000个文件的典型系统也会包含1,000个文件名。卸载的PDP-11 / 70系统上的Grep每秒处理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是确定路径字符串中是否包含名称子字符串的函数。 实际上，由于编码列表比未编码列表短约五倍，并且解码非常简单，因此该程序在文本文件上的运行速度比grep快三到四倍。



甚至更快


这种方法已经很有用，但仍有进一步改进的余地。（注意：该代码在find实用程序中使用。当我们可以改进现有的类似程序时，不需要给UNIX加上另一个命令[和手册页]。幸运的是，没有带有两个参数的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的左侧，则将显示前几行的匹配项，这意味着我们无法执行此搜索！从技术上讲，可以在比较完成后立即将截止值移植到路径。上面省略了此条件。

两层设备


您可以避免因处理搜索模式字符而导致搜索速度变慢。在此过程中，我们处理不包含元字符和使用较慢的递归函数名称的一部分amath内找到。即

puts(path)

变成

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

如果名称包含元字符，则 在其中设置globchars。将搜索模式用于简单的man命令的示例：

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

进一步改进


通过使用不可打印的ASCII代码替换最常见的两个字符的组合，find实用程序的生产代码将压缩率又提高了20-25％。“ .c”和“ .P”特别常见。

在时间和数据大小之间实现其他折衷的其他算法，例如霍夫曼算法[Reghbati，1981]，看起来并不乐观：它们只是用性能极限代替了I / O性能极限。

可以使用Boyer-Moore次线性搜索方法[Boyer，1977]或宏模型方法[Storer / Szymanski，1982]。

总之，应该指出的是，我们使用180个块和一个适合两页的C代码，在几秒钟内扫描了19,000个文件名。

参考文献


Boyer，RS一种快速字符串搜索算法，Commun。ACM，卷 1977年10月，第20期，第10期
。Morris，R.和Thompson，K. Webster的第二张
图钉，未发表的技术备忘录，贝尔实验室，纽约，默里山，1974年。Reghbati，香港，数据压缩技术概述，计算机，卷 14号 1981年4月4日
。Storer，JA和Szymanski，通过文本替换的TG数据压缩，J.ACM，第1卷。29号 1982年10月4日。

More articles:


All Articles