内容


LDAP 搜索引擎,第 2 部分

添加评分系统

为 LDAP 数据开发自定义 Web 搜索样式引擎

Comments

系列内容:

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

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

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

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

许多组织都实现了某种形式的轻量级目录访问协议 (LDAP) 服务以存储企业目录信息。现有搜索选项允许根据特定数据在目录中的存储位置进行一系列查找。本系列中的文章允许您将正则表达式的功能与 grep 工具结合使用,创建自定义 LDAP 搜索功能。在成功的搜索引擎(例如 Google)的核心部分中,将把搜索格式从 LDAP 样式的查询字符串更改为简单且强大的关键字匹配和结果显示。

要获得数据架构策略和此处引用的搜索代码的完整说明,请一定要阅读本系列的 第 1 部分

要求

硬件

2000 年以后生产的所有 PC 都应当能提供足够的能力编译和运行本文中的代码。修订此代码将生成复杂搜索(在配有 500-MHz 处理器和 1 GB 以上 RAM 的系统中搜索 200 MB 或更多信息)的次秒响应时间。需快速运行的组件 —— grep 和 Perl —— 实际上都运行得很快,而算法和显示代码则尽量不产生干扰以保证运行速度。

软件

对于变音位匹配,需使用 Michael Schwern 编写的 Text-Metaphone 模块。在偏好的 CPAN 镜像中安装模块,并准备着手开发。

为搜索结果评分

第 1 部分 中,创建了匹配指定查询词的结果的简单打印输出。在未经分类的情况下,此输出提供了有用的返回信息所需的基本显示。给匹配结果评分是一个复杂的主题,很多优秀的开发人员对各种相关问题进行了不懈的研究,目的就是要提高搜索结果的质量。好消息是 LDAP 搜索绑定了相对少量、定义良好的约束,并且我们可以使用一些简单标准,调整搜索以便用最低的程序复杂度和最少的处理时间来交付具有较高相关性的结果。

评分标准文件

第一步是定义要评分的字段。这里采取的简单方法是只给认为比其他字段更重要的字段进行评分。考虑:

清单 1. 示例评分标准文件
name 600
workloc 400
mail 300
jobresponsibilities 50
coverage_state 50
additional 40

分数加权方案中给 name 字段评定了最高优先级。如果在 name 中找到查询词,则希望给它一个很高的分数;而在 jobresponsibilities 字段中找到查询词,则给一个较低的分数;如果在清单 1 中未定义的任何其他字段中找到查询词,则不给分。您需要调整数据环境的这些评分参数。例如,若主要匹配物理地址,则调整分数加权定义以强调物理地址字段。这样即使在 Person Name 字段中找到匹配,也可以使用适当的加权定义将匹配物理地址的记录先放入列表中。例如,如果搜索 “Orchard”,您可能会搜索到 IBM® 公司地址。使用经过适当调整的分数加权文件,它将在 “101 Orchard Drive” 放置 “IBM Mailing Address” 记录,放在诸如 “John Orchard” 或 “Orchard Industries” 之类的个人记录之前。

请注意分数是如何按 10 个数量级的顺序来划分的。在初始评分设置中使用宽间距以允许评分标准更改拥有最大的灵活性。

修改代码

评分标准文件就绪 (fieldWeights) 后,我们需要装入各种评分参数并构建匹配测试子例程。“参考资料” 部分包含完整代码的链接,或者遵循下面的修改说明将第 1 部分变为第 2 部分中完成的程序。第一步是向变量声明部分中添加必需的散列。确保在变量声明部分的开头插入行 my %fieldWeights = ();。然后使用以下子例程将字段权重装入内存。

清单 2. loadMainFieldWeight 子例程
sub loadMainFieldWeight{
  open( FLDWT, "fieldWeights") or die "can't open field weights file";
  while( my $line = <FLDWT> )
  {
    my($key, $val ) = split " ", $line;
    $fieldWeights{ $key } = $val;
  }#while field weights file
}#loadTwoWordFieldWeight

在 grep 阶段后,第 1 部分输出了按连续顺序返回的结果。第 2 部分把 scoreSortResults 子例程注入到主程序逻辑中来给每条匹配的记录评分、给结果列表排序并将其传递给显示步骤。

清单 3. scoreSortResults 子例程
sub scoreSortResults
{
  my @scored = ();

  for my $oneRec ( @_ )
  {
    chomp($oneRec);
    my @delRecs = split "##", $oneRec;
    shift(@delRecs); # first field is empty
    my $localScore = 0;

    for my $fld ( @delRecs  )
    { 
      $localScore += match( "contains", $fld );
      $localScore += match( "isExact",  $fld );
    }#for each field in the linex

    push @scored, "$localScore" . "$oneRec";
  }#for each line 

  my @idx = (); #temporary index for sorting
  for( @scored ){
    # create an index of scores
    my $item =  substr($_,0,index($_,'##'));
    push @idx, $item;
  }

  # sort the index of scores
  my @sorted = @scored[ sort { $idx[$b] <=> $idx[$a] } 0 .. $#idx ];

  return( @sorted );
}#scoreResults

for 循环将迭代每条匹配平面文件的记录。对于每条用新行分隔的记录,系统将提取和检查字段是否匹配任何一个查询词。分开检查 contains 匹配和 isExact 匹配将有效地使找到查询词精确匹配的机会加倍。这是第一种简单却较为健壮的方法,用于提供可靠的、能区分 “John” 与 “Johnny” 的结果。记录的分数插入到记录行的开头后,循环将重复执行。

每条从平面文件匹配的记录都评完分后,接着建立排序过程。第一步是通过选择用 ## 分隔的列表中的第一条记录来隔离实际分数。创建分数索引数组后,我们将按照 perlfaq 的第 4 部分中的说明使用标准排序命令来创建排序后搜索结果的 @sorted 数组。

让我们回去充实 match 子例程:

清单 4. match 子例程
sub match
{
  my $matchType = $_[0];
  my $input = $_[1];
  my( $field, $value ) = split ':', $input;
  my $retScore = 0;

  for my $qPiece ( @queryWords )
  {
    if( $matchType eq "contains" )
    { 
      if( $value =~ /($qPiece)/i )
      { 
        next unless exists($fieldWeights{$field});
        $retScore .= $fieldWeights{$field};
      }#if word match found
    }#if contains

    else
    { 
      if( $value =~ /(\($qPiece\))/i   ||   $value =~ /(\b$qPiece\b)/i  )
      { 
        next unless exists($fieldWeights{$field});
        $retScore .= $fieldWeights{$field};
      }#if exact word match found
    }#if isexact

  }#for each query word
  return($retScore);
}#match

对于查询中指定的每个查询词,检查包含查询词的结果和完全匹配查询词的结果。针对 LDAP 数据的一项特殊修改是考虑将 '('')' 作为查询词边界指示符。这将有助于匹配诸如 “smith,dave” 和 “smith, david (dave)” 之类的条目。

为了便于根据特定数据集进行调整,需要考虑修改 scoreSortResults 子例程使其只接受精确匹配。

利用就绪的简单评分过程和已排序的结果文本数组,我们可以打印结果。需要修改 buildHashPrintResults 子例程以便在变量中存储 print 输出。稍后将使用此输出进行一些简单结果检查。将行 my $outStr = ""; 添加到主程序变量声明部分中。将清单 5 中 buildHashPrintResults 子例程的打印行更改为清单 6 中的打印行。

清单 5. 第 1 部分 buildHashPrintResults 打印语句
my @delRecs = split "##", $oneRec;
...
print getSelectedFields();
%fieldHash = ();
清单 6. 第 2 部分 buildHashPrintResults 打印语句
my @delRecs = split "##", $oneRec;
$outStr .= "Score: $delRecs[0]\n";
...
$outStr .= getSelectedFields();
%fieldHash = ();

完成评分代码升级剩下的全部操作就是将主程序逻辑流程从清单 7 修改为清单 8。

清单 7. 第 1 部分主程序逻辑
@queryWords = split " ", $searchQuery;
  
buildHashPrintResults( alg_N_Word( @queryWords ) );
清单 8. 第 2 部分主程序逻辑
@queryWords = split " ", $searchQuery;

loadMainFieldWeight();

buildHashPrintResults
( 
  scoreSortResults
  ( 
    alg_N_Word( @queryWords )
  )
);

print "$outStr";

继续并尝试使用以前的数据集。对于示例数据集,如果执行诸如 perl cmdSearch.pl devel chri 之类的查询,则将获得如清单 9 所示的结果。注意第一条记录是如何获得较高分数的,因为 “chris” 匹配 mail 字段,也匹配 name 字段。

清单 9. 评分后的查询结果
Score: 950
mail:  nchristo@us.ibm.com
telephonenumber:  1-522-223-2214
physicaldeliveryofficename:  1P-027
co:  USA
cn:  Christopher Q Public 
buildingname:  007
jobresponsibilities:  Senior Software Engineer, \
IBM Developer Skills Program, developerWorks
givenname:  Christopher,  Chris,  Kris,  Christian,  Christine,  Cristiane
primaryuserid:  NCHRIS
name:  Public, Christopher

Score: 650
mail:  crothemooi@us.ibm.com
telephonenumber:  1-822-223-2215
physicaldeliveryofficename:  HOME
co:  USA
cn:  Christine D. Public
buildingname:  311
jobresponsibilities:  developerWorks WebSphere Editor: Wireless, Web Services, Voice
givenname:  Christine D.,  Christine,  Chris,  Kris,  Christian,  Christopher,  Cristiane
name:  Public, Christine D. (Chris)
preferredfirstname:  Christine

您现在已经有一个功能全面的、加权计分、形式自由的查询搜索引擎。虽然是为 LDAP 类型的数据量身定做的,但是可以使用以上代码执行任意数量的文本相关查询。调整搜索引擎时请牢记:只需修改几段代码,就能获得对算法的性能和结果的主要修改。例如,如果删除多次匹配查询词或多次匹配同一字段的功能,则记录中的分数分布将发生很大变化。

使用 Text-Metaphone 的巧妙建议

变音位匹配是根据查询词的语音发音生成关键字的算法方法。例如,“developerWorks” 的变音位是 “TFLPRWRKS”。为 devoloperworks、devaloperworks、devaloperwerks 等生成的变音位是相同的。用于各种拼写检查程序和建议制定程序,我们将使用一个简单版本的变音位匹配方法来根据特定数据提供一些有用的建议。

构建变音位数据库

本文中使用的方法是从整个平面文件数据库中指定的字段中提取所有单个关键词。然后将为每个关键词创建频率计数及其相关的变音位关键字。使用清单 10 中的程序 buildMetaphones.pl 来创建您自己的变音位数据库。

清单 10. buildMetaphones.pl 脚本
#!/usr/bin/perl -w
use strict;
use Text::Metaphone;

if( @ARGV != 1 ){ die "specify a fieldname" };

my $selectField = $ARGV[0];
my %metaPhones;

# build the metaphone frequency counts
while( my $line = <STDIN>){
  my @allRecs = split '##', $line;
  shift( @allRecs ); #first on is empty

  for my $entry ( @allRecs )
  {
    next unless $entry =~ /\:/;
    my( $field, $value ) = split ':', $entry;
    next unless $field =~ $selectField;

    # remove characters that inhibit space delimiting
    $value =~ s/\W/ /g;

    for my $word ( split ' ', lc($value) )
    { 
      $metaPhones{ Metaphone($word) }{ $word }++;
    }
  }#for each field entry
}#while input

# now print them out
for my $metaKey( keys %metaPhones )
{
  print "$metaKey##";

  # build a sorted list of actual word counts associated with a metaphone
  my @countKeys = sort
  {
    $metaPhones{$metaKey}{$b} <=> $metaPhones{$metaKey}{$a}
  } keys %{ $metaPhones{$metaKey} };

  for my $sortKey ( @countKeys )
  {
    print "$sortKey $metaPhones{$metaKey}{$sortKey}##";
  }

  print "\n";
}#for metakey

cat <data_file> | perl buildMetaphones.pl name > metaphones.name 命令运行脚本,然后它将生成与清单 11 相似的输出。data_file 条目应当是按照第 1 部分所述提取的 LDAP 数据生成的用新行分隔的平面文件。

清单 11. 示例 metaphones.name 文件
XKR##shekerow 1##
JLBR0##gilbreath 1##
JM##jim 103##
MKKMN##mccommon 12##
MRKN##morgan 33##
TNS##denise 3##
JKFLF##jakovlev 1##
JN##john 18##jeanne 12##jenni 10##jon 1##

还需要用命令 cat <data_file> | perl buildMetaphones.pl jobresponsibilities > metaphones.jobresponsibilities 创建一个 metaphones.jobresponsibilities 文件。

要使用这些文件,需要用装入的子例程更新 cmdSearch.pl 代码。

清单 12. loadMetaphones 子例程
sub loadMetaPhones{

  open( FH, "metaphones.name" ) or \
  die "can't load name metaphones";
    while(<FH>){
      my( $key, $val ) =split '##';
      $nameMP{$key} = $val;
    }#while FH
  close(FH);

  open( FH, "metaphones.jobresponsibilities" ) or \
  die "can't load jobresponsibilities metaphones";
    while(<FH>){
      my( $key, $val ) = split '##';
      $jobMP{$key} = $val;
    }#while FH
  close(FH);

}#loadMetaPhones

loadMetaPhones 子例程是创建变音位关键字和值的两个散列的简单代码。在本文的示例中,认为 name 字段中的 1 次变音位匹配比 jobresponsibilities 字段中的 50 次匹配好。为顾及这一思想,代码不是创建了另一个评分系统,而只是先搜索 name 变音位匹配,如果没有可用匹配,则继续搜索 jobresponsibilities 变音位。执行变音位匹配的实际代码位于 getMetaphoneMatch 子例程中:

清单 13. getMetaphonematch 子例程
sub getMetaphoneMatch{
  my $retStr = "";
  my @notFound = ();
  #HRNKTN ##harrington 41##herrington 4 - metaphone file format

  for my $qPiece ( @_ )
  {
    my $word = $qPiece;
    my $phone = Metaphone($word);
    my @mParts = ();

    if( exists($nameMP{$phone}) )
    { 
      @mParts = split '##', $nameMP{$phone};
    }
    elsif( exists($jobMP{$phone}) )
    { 
      @mParts = split '##', $jobMP{$phone};
    }

    next unless @mParts ne "";

    # print the most common match only
    for my $metaWord ( @mParts )
    { 
      if( $metaWord !~ /$qPiece/i )
      { 
        $retStr .= "$metaWord, ";
        last;
      }
    }#for metaword check
  }#for each query word

  return($retStr);
}#getMetaphoneMatch

声明局部变量后,子例程将遍历每个指定查询词,搜索 name 或 jobresponsibilities 散列中的变音位匹配。如果找到变音位匹配,只选择第一个具有适当变音位的匹配词进行打印。例如,“Horington” 查询有 “HRNKTN” 变音位,并将打印 “Harrington” 作为建议,即使 “Herrington” “Herringdon” 和其他词都可以是变音位匹配结果。如果未找到任何名 称变音位匹配,则搜索工作职责变音位。选择打印最常见匹配(buildMetaphones.pl 脚本中确定)是基于为用户提供简单建议这一考谅。可以打印所有匹配变音位,甚至还可以根据变音位匹配中的头几个字符自动搜索数据库。选择最适于应用程序的策略。

要完成修改,请将 my %jobMP = (); my %nameMP = (); 添加到变量声明部分中并将主程序逻辑从清单 14 修改为清单 15。

清单 14. 以前的主程序逻辑
@queryWords = split " ", $searchQuery;
loadMainFieldWeight();

buildHashPrintResults
(
  scoreSortResults
  (
    alg_N_Word( @queryWords )
  )
);

print "$outStr";
清单 15. 最终的第 2 部分主程序逻辑
@queryWords = split " ", $searchQuery;
loadMainFieldWeight();
loadMetaPhones();

buildHashPrintResults
(
  scoreSortResults
  (
    alg_N_Word( @queryWords )
  )
);

print "$outStr";
if( $outStr eq "" ){ print "Try: ", getMetaphoneMatch( @queryWords ), "\n" }

用一个数据集外的查询运行 cmdSearch.pl 应用程序。例如,如果搜索 “jaff devaloperWerks”,则 cmdSearch.pl 程序将输出 Try: jeff 114, developerworks 50,

结束语

使用上面描述的 LDAP 搜索引擎(连同有效的评分和简单搜索建议),您可在企业内拥有很多集成选择。一种典型的方法是将接口移植到 HTML 生成环境并允许用户搜索 LDAP 数据库,就像他们可搜索 Internet 的其余部分一样。您可以创建面向服务架构(Service-Oriented Architecture,SOA)的应用程序编程接口 (API) 来集成其他应用程序,包括建议支持以便为各种应用程序提供更智能的查找。

通用算法和文本搜索方法还可以在企业内部移植和轻松整合。使用变音位匹配和正则表达式生成器创建基于 404 采样数的 Web 站点建议链接。插入搜索查询建议的另一种方法的 Aspell 或 Ispell API 的调用,或将变音位匹配替换为应用程序的最佳现代探测法。


下载资源


相关主题


评论

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Open source
ArticleID=226132
ArticleTitle=LDAP 搜索引擎,第 2 部分: 添加评分系统
publish-date=06072007