内容


LDAP 搜索引擎,第 1 部分

借助 Perl 和正则表达式生成器搜索并显示 LDAP 数据库记录

Comments

系列内容:

此内容是该系列 # 部分中的第 # 部分: LDAP 搜索引擎,第 1 部分

敬请期待该系列的后续内容。

此内容是该系列的一部分:LDAP 搜索引擎,第 1 部分

敬请期待该系列的后续内容。

许多组织都实现了某种形式的 LDAP 服务以存储企业目录信息。现有搜索选项允许基于特定数据存储所在的目录进行一系列查找。本文允许将正则表达式的强大功能与 grep 工具结合使用来创建定制的 LDAP 搜索功能。以成功的搜索引擎(例如 Google)的核心思想为引导,将搜索形式从 LDAP 样式的查询字符串更改为简单且强大的关键字匹配和结果显示。

在本文中,我们将介绍如何构建平面文件数据库,如何创建正则表达式,以及如何进行基本的搜索和显示。第 2 部分将介绍如何进行计分和语音匹配以帮助完成搜索功能。

系统需求

硬件

2000 年以后生产的所有新式 PC 都应当能够编译和运行本文中的代码。若系统配有 500 MHz 处理器和 1 GB 以上的 RAM,那么修改这些代码将会为针对 200 MB 或更多信息的复杂搜索产生次秒级的响应时间。那些快速组件( grep 和 Perl)的速度也的确能非常快,事实上,算法和显示代码完全不会妨碍速度。

软件

不需要为此项目安装特定的软件包。如果在 Linux® 已经安装了 Perl 和 grep,那么您就可以开始下面的操作了。

平面文件数据库选择

用于 LDAP 查询的现有搜索工具要求搜索程序必须知道 —— 或者至少要指定 —— 正确的字段才能搜索其中的数据。正则表达式支持有可能并且通常会无法识别或不能处理复杂查询,而正则 grep 却可以轻松处理。注:本文中的代码不直接搜索 LDAP 数据,但需要导出到平面文件数据库中,然后再进行处理。LDAP 所提供的现有数据存储搜索选项不具有 grep 用户已经习惯了的速度和灵活性。我们将使用 LDAP 数据的摘录并创建自己的自由格式的搜索引擎以查找我们所需的确切信息。

与自由文本或结构化文档搜索比较而言,处理、搜索和显示数据是一个简单的过程。通常,只搜索目录信息:个人的姓名、地址、电话号码等。使用在本文中开发的工具,您将能够构建自己的搜索引擎,它比现有 LDAP 查找要快,能迅速获得搜索结果。获得此速度的关键组件是使用 grep 内包含的高度精确的高效算法。利用 grep 的速度和正则表达式功能的高效且可移植的方法是从 LDAP 目录的内容创建一个按新行分隔的平面文件。

构建平面文件数据库

在我们的组织中,将 LDAP 数据提取为如下格式相对来讲很容易:

清单 1. LDAP —— 一条记录,多行显示
dn: uid=123456897,c=us,ou=bluepages,o=ibm.com
objectclass: person
objectclass: organizationalPerson
objectclass: ibmPerson
objectclass: ePerson
objectclass: top
internalmaildrop: MARKET ST
personaltitle: Ms.
mail: developerWorks@us.ibm.com
uid: 123456897
...

LDAP 数据库中的每条个人记录都将由空行分隔。但我们需要的是按新行分隔的平面文件,其中每行都包含一条完整的记录。如果 LDAP 数据的格式与上面所示的格式类似,就可以使用 compileLineByLine.pl 脚本来创建每行一条记录的平面文件。

下面列出了 compileLineByLine.pl 脚本,也可以 下载 该脚本。可能需要修改代码才能处理 LDAP 具体数据。

清单 2. compileLineByLine.pl 脚本
#!/usr/bin/perl -w
# compileLineByLine.pl - build a line by line record of LDAP data
use strict;

my $lastFlip = 0; # flipper for end of record output, start of record

while( my $ldapLine = <STDIN>)
{
  # ignore meta-data "object" lines
  next if( $ldapLine =~ / objects\n/ );
  next if( $ldapLine =~ / Ok\n/      );
  next if( $ldapLine =~ / object\n/  );

  if( $ldapLine eq "\n" )
  { 
    # if a blank line and "in-record", print out the end of record
    print "##\n" if $lastFlip == 1;
    $lastFlip = 0;
  }else
  { 
    # if not a blank line, print out the field, set "in-record" 
    chomp($ldapLine);
    print qq{##$ldapLine};
    $lastFlip = 1;
  }#if newline

}#while stdin

cat <data_file> | perl compileLineByLine.pl 命令运行脚本,将生成以下输出:

清单 3. 逐行的 LDAP 记录
##alternatenode: RHQVM19##internalmaildrop: MD 1329##pdif: 1##tieline: 82...
##pdif: 1##tieline: 930-5888##preferredfirstname: Christine##mail: crothe...
##additional: Mobex:274571##alternatenode: UKVM##internalmaildrop: 135##p...
##alternatenode: RALVM14##internalmaildrop: 1034##pdif: 1##tieline: 793-0...
##additional: MAIL-ADDR:(PO Box 12195, 3039 Cornwallis Road RTP, NC 27709...
##alternatenode: RALVM17##internalmaildrop: 007-1S023##pdif: 1##tieline: ...
##alternatenode: RALVM14##tieline: 273-3598##pdif: 1##preferredfirstname:...
##additional: MAIL-ADDR:(PO Box 12195, 3039 Cornwallis Road RTP, NC 27709...
##additional: MAIL-ADDR:(PO Box 12195, 3039 Cornwallis Road RTP, NC 27709...
...

数据库专家无疑会惊骇于这种向大型机历史的明显倒退。不过,请不要担心,因为本文中的算法和正则表达式构建代码可以很容易适应关系数据库环境。对我们而言,这种用 ## 字段和 \n 记录分隔的平面文件是一种最佳的可移植方法。此外,由于杰出的计算机黑客们为了提效和提速对 grep 进行了优化,所以通过使用 grep,我们就可以充分利用这种便利。此外,许多版本的 Linux 都在 grep 运行期间把整个平面文件装入到内存中,可极大地增强后续运行的性能。

以上示例数据显示了分隔符 (##)、字段名:数据值、分隔符、字段名等等。将字段名包含到数据本身中可能看似多余,但却是在某些记录中搜索字段是否存在的一种很好的方法。例如,有些记录中有 IPTelephoneNumber 字段名,有些记录则没有。允许对 IPTelephoneNumber 进行自由文本搜索将列出公司内拥有 IP 电话使用权限的所有人。将字段名包含到带有数据的记录中是跟踪更改的好方法。只需将插入日期追加到字段名后,就可以拥有基于每条记录更改的时间表。要查看记录中有哪些类字段名分布,可以尝试使用以下代码:

cat <data_file> | perl -lane '@a=split " ";$h{$a[0]}++;END{for(keys %h)\
{print "$h{$_} $_"}}' | sort -nr

其中 data_file 是每行一个字段的 LDAP 目录输出和用空行分隔的记录。上面的代码行将为您提供字段名的排序后的频率分布,类似以下清单所示。

清单 4. LDAP 字段名频率分布
505 objectclass:
491 cn:
357 givenname:
113 mail:
101 serialnumber:
99 div:
98 buildingname:
97 worklocation:
97 workloc:
97 physicaldeliver

用 cmdSearch.pl 搜索数据库

平面文件就绪后,可以开始创建搜索代码。下载 中包含的 cmdSearch.pl 程序在指定了一组文字作为搜索字符串的情况下在命令行中运行。让我们先来看一看程序的概述,接下来再分节说明每个组件。

第一步是创建与每个查询词一致的正则表达式,只有在查询词包含通配符 * 时才需要修改。与正则表达式一致的查询词就绪后,将在平面文件自身上执行第一个 grep,然后再用 Perl 的 grep 改进结果。检查过所有查询词后,最终的记录将被处理并以适于进行联系人查找的简化格式显示给用户。

我们先来看一看声明部分中的代码。

清单 5. cmdSearch.pl 声明部分
#!/usr/bin/perl -w
#cmdSearch.pl - return LDAP data from command line query
use strict;

die "usage cmdSearch.pl 'query w*rds here'" if ( @ARGV == 0 );

my $initQuery = "@ARGV";
my $searchQuery = $initQuery;
my $grepFile = "data/10head";
my @queryWords = ();
my %fieldHash = ();

向前跳到主程序部分:

清单 6. cmdSearch.pl 主程序
# remove extraneous spaces, + signs
$searchQuery =~ s/\s+$//g;
$searchQuery =~ s/^\s+//g;
$searchQuery =~ s/\+//g;

@queryWords = split " ", $searchQuery;

buildHashPrintResults( alg_N_Word( @queryWords ) );

我们可以看到所有前导空格或后置空格已被删除,然后 + 号被转义以删除用正则表达式搜索的潜在干扰。在将查询词数组传递给 N 词算法后,将打印出结果。

让我们先来看一看 alg_N_Word 子程序。

清单 6. alg_N_Word 子程序
sub alg_N_Word
{
  my @regexpWords = ();

  for my $qPiece ( @_ )
  { 
    push @regexpWords, createRegexp( $qPiece );
  }
  
  my @step1Recs = `grep -i -E "$regexpWords[0]" $grepFile`;
  for my $rWord ( @regexpWords )
  { 
    next if $rWord eq $regexpWords[0];
    my @step2Recs = ();
    @step2Recs = grep( /($rWord)/i, @step1Recs );
    @step1Recs = ();
    @step1Recs = @step2Recs;
  }#for each regexp word
  
  return( @step1Recs );
}#alg_N_Word

虽然保留最初的查询词数组不动,但是为每个词构建了正则表达式。从第一个正则表达式开始,创建一个来自数据文件的记录数组,然后循环执行其余的正则表达式以改进结果。完成时将返回匹配平面文件中的记录的最终数组。alg_N_Word 函数中的第一个子程序调用是指向 createRegexp 的。让我们来看一下。

清单 8. createRegexp 子程序,第 1 部分
sub createRegexp
{
  my $inQuery = $_[0];
  my $localQuery = "";
  my $returnStr = "";
  my $astCount = ($inQuery =~ tr/\*// );
  my $longPart = "";
  my @wordParts = split '\*', $inQuery;
  my $breakString = '\b';
  
  $inQuery =~ s/\./\\\./g;  # replace . with \.

  # if no wildcards, return the plain words
  return( $inQuery ) if ( $astCount == 0 );

我们创建了一些变量并计算了输入“词”中的星号数。用于处理查询的 Web 搜索引擎样式的界面专门用于处理查询中的多个星号。在转义了 '.' 字符后,如果未找到星号,子程序则会返回一个未修改的字符串。如果有一个或多个星号,子程序将继续执行处理来创建正则表达式。

清单 9. createRegexp 子程序,第 2 部分
  # determine the longest part of the string to search for
  for( @wordParts )
  {
    next if ( length($_) < length($longPart) );
    $longPart = $_;
  }

  # if an asterisk is present in the query, build the regular expression
  if( $astCount == 1 )
  {
    # examples: *sam, sam*, sam*l
    if(     substr( $inQuery, 0, 1 ) eq '*' )
    {

# this is a (any word char) one or more times, (query), word boundary - *sam
      $localQuery = "(" . '\w' . ")+($longPart)" . '\b';

    }elsif( substr($inQuery, length($inQuery)-1,1) eq '*' ){

# this is word boundary, query, (any word char) one or more times - sam*
      $localQuery = '\b' . "($longPart)(" . '\w' . ")+";

    }else{

# word boundary, query, (any word char) one or more times,  query, word boundary sam*l
      $localQuery = '\b' . "($wordParts[0])(" . '\w' . ")+($wordParts[1])" . '\b';

    }#if a single asterisk is at beginning, end or middle

这段代码主要创建了正则表达式,其中只有一个星号。带有一个星号的查询示例包括 *sam, sam*sam*l。代码的第一部分将查找查询词的最长部分,这一部分用于插入到正则表达式中。如果星号出现在查询词的开头,我们就要知道这意味着指定的查询必须以该词后面的部分为结束。例如,如果查询是 *sam,则需要确保它匹配 iamsam,但不匹配 iamsamson

构建的正则表达式要求在构建的表达式末尾有一个词界以确保此行为。同样地,如果星号出现在查询词末尾,程序将把该星号视为要求指定的查询必须以该词前面的部分为开始。照这样来说,sam* 将匹配 samson,但不匹配 iamsamson

最后,如果查询词的中间有星号,则要求严格匹配查询词的开头和结尾。因此,sam*l 将匹配 samuel,但不匹配 iamsamuelsamueliam。清单 10 详细说明了在每个查询词中有多个星号的情况下需要遵循的步骤。

清单 10. createRegexp 子程序,第 3 部分
  }elsif( $astCount > 1 ){
    # examples: s*m*l, *am*l, sa*m*

    for my $partChunk( @wordParts ) {
      next if( $partChunk eq "" );
      $breakString .= "($partChunk)(". '\w' . ")+";
    }#for each part of the query

    if( substr($inQuery, length($inQuery)-1,1) ne '*' ){

      # if the last characters is not a *, remove the (any word char) section 
      # from the end, and replace with a word boundary
      $breakString = substr($breakString,0,length($breakString)-5);
      $breakString .= '\b';

    }#if not an asterisk at the end

    if( substr($inQuery, 0, 1)  eq '*' ){

      # if beginning is a asterisk, remove the word starting boundary
      $breakString = substr($breakString,2);

    }#if asterisk at the beginning

    $localQuery = $breakString;

  }#count asterisks in the query 

  return($localQuery);
}#createRegexp

无论每个当前词查询的内容为何,都需要一次或多次为字符后接的字符块创建用于搜索的正则表达式。所有多星号查询都会遇到这个过程,然后进行后期处理以确保修改正则表达式的开头和结尾匹配所需的条件。例如,使用查询 s*m*l,在第一轮 for 循环后,breakString 变量将包含值 (s)(\w)+(m)(\w)+(l)(\w)+。接下来的 if 语句将删除后置的 “任何字符部分” 以生成 (s)(\w)+(m)(\w)+(l)。在本例中,最有一条 if 语句为 false(因为查询词不以星号为开头),因此构建好的正则表达式将被返回给 alg_N_Word 子程序。alg_N_Word 子程序完成并返回搜索记录和改进记录后,将调用 buildHashPrintResults 子程序。

让我们来看一看这个子程序并了解一下其工作原理。

清单 11. buildHashPrintResults
sub buildHashPrintResults
{
  for my $oneRec ( @_ )
  {
    chomp($oneRec);
    my @delRecs = split "##", $oneRec;
    shift(@delRecs); # first field is empty
    
    for my $fld ( @delRecs  )
    { 
      #example data: additional: MAIL-ADDR:(PO...
      my $key = substr($fld, 0, index($fld,':') );
      my $val = substr($fld, index($fld,':')+1 );
     
      $fieldHash{$key} .= ", " if( exists($fieldHash{$key}) );
      $fieldHash{$key} .= "$val";
    }
    
    print getSelectedFields();
    %fieldHash = ();
  }#for each line 

}#buildHashPrintResults

@_ 变量是已匹配了搜索条件的所有记录的列表。对于这其中的每条记录,都将按名称提取字段并将每个字段值存储到与字段名关联的散列中。字段都是用 ## 分隔的,并且上面的子程序将把一条记录的所有字段放入 delRecs 数组中。对于这其中的所有字段,收集字段名作为第一个冒号前的内容,并将字段值作为冒号后的内容。如果值存在,则将其追加到与字段名关联的散列值后,因为这样做将启用每个字段组合的简单输出,而不管哪些字段匹配。例如,如果名称为 jane,则在 cn 字段中可以匹配 ju*y,但 cn 字段中同时存储的昵称是 judyjuly。将多个字段名组合成一个变量进行打印将允许您通过一次搜索查看实际名称和昵称。

既然已经为当前记录构建了散列,现在就可以打印选定的字段。下面的子程序 getSelectedFields 将显示在我们的示例中这些选定字段是什么。

清单 12. getSelectedFields
sub getSelectedFields
{
  my @desiredFields = split " ",
    "mail telephonenumber physicaldeliveryofficename co cn buildingname";
  my $returnStr = "";

  # print the desired fields
  for my $key ( @desiredFields ){ $returnStr .= "$key: $fieldHash{$key}\n"; }

  # find other fields where search terms exist
  for my $searchWord( @queryWords )
  {
    for my $searchKey ( keys %fieldHash )
    {

      if( $fieldHash{$searchKey} =~ /$searchWord/i )
      {
        # word found in value, make sure it's not already printed as part 
        # of the desiredFields
        next if( "@desiredFields" =~ /$searchKey/i );
        $returnStr .= "$searchKey: $fieldHash{$searchKey}\n";
      }#if match found

    }#for each key in the field hash
  }#for each search word

  $returnStr .= "\n";
  return($returnStr);
}#getSelectedFields

对于 desiredFields 数组中指定的每个字段名,搜索构建的 fieldhash 以查找在搜索条件中指定的所有词。如果找到匹配,请检查以确保在其他字段中找到的同一个搜索词的匹配尚未被打印。如果它是找到的第一个匹配,则将其添加到要打印的字符串中。例如,使用清单 3 中所示的相同数据,搜索 930-5* 将生成以下搜索结果:

清单 13. 930-5* 搜索输出
mail:  chrisQDevel1@us.ibm.com
telephonenumber:  1-877-848-8888
physicaldeliveryofficename:  HOME
co:  USA
cn:  Christine Q. Micham,  Chris D. Micham
buildingname:  131
tieline:  930-5888

注意 getSelectedFields 子程序如何打印指定的字段以及匹配搜索条件的任何字段(如果尚且没有匹配)。您还可以从上面的示例中看到所有 cn:(命令名)值的输出。

结束语

现在,您已经了解了 LDAP 搜索引擎的基础知识。今后,您可以在除了 LDAP 搜索以外的多种地方使用在这里介绍的简单正则表达式构建工具,并根据具体环境调整正则表达式的生成或通配符语法。本文中介绍的算法和自由形式的文本搜索也可应用到客户数据库和其他小范围数据库。

在 “LDAP 搜索引擎” 系列的第 2 部分中,将介绍搜索结果的权重和排序,以及如何进行语音匹配以更正数据集的常见拼写错误。


下载资源


相关主题

  • 您可以参阅本文在 developerWorks 全球站点上的 英文原文
  • 查阅 Perl 和 LDAP 资源
  • Paul Dwerryhouse 为 Linux Journal 撰写了一篇关于 Perl 和 LDAP 的题为 “An Introduction to perl-ldap” 的文章。
  • 可在 OpenLDAP 获得大量背景和实现知识。
  • 浏览 developerWorks 上的所有开源 文章教程
  • 要收听针对软件开发人员的有趣访谈和讨论,一定要访问 developerWorks 的 podcast
  • 访问 developerWorks 开源软件技术专区 以获得丰富的 how-to 信息、工具和项目更新,帮助您用开放源码技术进行开发,并与 IBM 产品结合使用。
  • 访问 Safari 网上书店 浏览开源技术的各种参考资料。

评论

添加或订阅评论,请先登录注册

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Open source
ArticleID=226131
ArticleTitle=LDAP 搜索引擎,第 1 部分: 借助 Perl 和正则表达式生成器搜索并显示 LDAP 数据库记录
publish-date=06072007