目次


LDAP 検索エンジン、第 1 回: Perl と正規表現ジェネレーターを使って LDAP データベース・レコードを検索し、表示する

Comments

多くの組織では、エンタープライズ・ディレクトリー情報を保存するために、何らかの形の LDAP サービスを実装しています。既存の検索オプションを使うと、ディレクトリーのどこにデータが保存されているかに基づいて、広範な種類の検索を行うことができます。この記事では、正規表現の威力を grep ツールと組み合わせ、独自のカスタム LDAP 検索機能を作成します。Google などの成功した検索エンジンと同じ精神で、検索フォーマットを、LDAP スタイルのクエリー・ストリングから、単純で強力なキーワード・マッチングと結果表示に変更します。

この記事では、フラット・ファイル・データベースの構築、正規表現の作成、そして基本的な検索と表示について説明します。第 2 回では、検索機能を完成させるために、スコアリングと metaphone マッチングについて説明します。

要件

ハードウェア

2000年以降に製造された最近の PC であれば、ここで紹介するコードをコンパイルし、実行するために十分すぎるほどのパワーを持っているはずです。このコードでは、500-MHz のプロセッサーと 1 GB を越える RAM を持つシステム上で 200 MB 以上の情報を持つ複雑な検索を行った場合に、1 秒以下のレスポンス時間を実現することができます。高速であるべきコンポーネント (grep と Perl) は、実際に非常に高速であり、また高速なものをアルゴリズムと表示コードが邪魔することはありません。

ソフトウェア

このプロジェクトには、特別なパッケージは何も必要ありません。Linux® に Perl と grep がインストールしてあれば、準備は完了です。

フラット・ファイル・データベースを選択する

LDAP クエリー用の既存の検索ツールでは、検索する人が、そのデータの検索対象となる適切なフィールドを知っている (あるいは少なくとも指定する) 必要があります。このツールでは、正規表現がサポートされている場合でも最低限のサポートしかなく、通常の grep であれば容易に処理できる複雑なクエリーに対して、正規表現を認識できなかったり、あるいは処理できなかったりすることが多いものです。この記事のコードが LDAP データを直接検索するわけではなく、処理が発生する前にフラット・ファイル・データベースにエクスポートする必要があることに注意してください。LDAP で提供されている既存のデータ・ストア検索オプションは、grep ユーザーが慣れ親しんだスピードや柔軟性を持ち合わせていません。ここでは LDAP データから抽出したものを使って、本当に必要な情報を発見するための、自由形式の独自検索エンジンを作成します。

データの処理や検索、表示は、自由形式のテキスト検索や構造化文書の検索に比較すれば単純なプロセスです。私達は通常、ディレクトリー情報、つまり個人の名前や住所、電話番号などしか検索しません。ここで開発するツールを使うと、既存の LDAP 検索よりもずっと高速に結果を得られる、独自の検索エンジンを作成することができます。このスピードを得るための重要な要素として、grep に含まれている、非常に洗練された効率的なアルゴリズムを使います。grep のスピードと正規表現機能を利用するために最も効率的で移植性の高い方法は、改行で区切られたフラット・ファイルを LDAP ディレクトリーの内容から作る方法です。

フラット・ファイル・データベースを構築する

私達の組織では、LDAP データを次のようなフォーマットに抽出することは比較的容易です。

リスト 1. LDAP -- 1 つのレコードに複数の行
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 データベースの個々のレコードは、空白行で区切られています。私達が必要としているファイルは、改行で区切られ、完全なレコードがそれぞれ 1 つの行に含まれたフラット・ファイルです。もし LDAP データが上記のようなフォーマットである場合は、compileLineByLine.pl スクリプトを使って、1 行が 1 レコードのフラット・ファイルを作ります。

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 は、1 行1 フィールドの 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 サブルーチンを始めることにしましょう。

リスト 7. 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 検索エンジン・スタイルのインターフェースは、クエリー中の複数のアスタリスクを処理するように設計されています。このサブルーチンは「.」文字をエスケープした後、もしアスタリスクが見つからなかった場合には未修正のストリングを返します。もし1 つ以上のアスタリスクがあると、このサブルーチンは正規表現を作成するための処理を継続します。

リスト 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

このコードで集中的に行っていることは、アスタリスクが 1 つしかない正規表現を作成することです。アスタリスクが 1 つのクエリーの例としては、*sam や sam*、sam*l があります。このコードの最初の部分では、クエリー・ワードのうちの最も長い部分を見つけ、その部分は正規表現の中に挿入するために使われます。もしアスタリスクがクエリー・ワードの最初に現れた場合、そのワードは、指定されたクエリー・ワードで終わるとみなします。例えば、もしクエリー・ワードが *sam だとすると、そのクエリー・ワードが iamsam と一致し、iamsamson とは一致しないようにします。

作成された正規表現には、その表現の最後に、この動作を保証するためのワード境界が必要です。同様に、もしクエリー・ワードの最後にアスタリスクが現れる場合には、プログラムはそれを、指定されたクエリー・ワードで単語が始まる必要があるとして扱います。こうすることで、sam* は samson に一致しますが、iamsamson とは一致しないことになります。

最後に、もしクエリー・ワードの真ん中にアスタリスクがある場合には、そのクエリー・ワードの最初と最後で一致する必要があります。従って、sam*l は samuel に一致しますが、iamsamuel や samueliam とは一致しません。リスト 10 は、1 つのクエリー・ワードに複数のアスタリスクがある場合に従うべきステップの詳細を示しています。

リスト 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

現在のワード・クエリーの各部の内容にかかわらず、その内容のチャンクと、その後に単語の文字が 1 回以上続くものを検索する正規表現を作成します。このプロセスはアスタリスクが複数あるすべてのクエリーで起こり、期待される規準に正規表現の最初と最後が一致するように変更する後処理を行います。例えば s*m*l というクエリーの場合、最初の for ループの後では、breakString 変数は値 (s)(\w)+(m)(\w)+(l)(\w)+ を含みます。次の if 文は、後に続く「any word character section」を削除して (s)(\w)+(m)(\w)+(l) を作成します。最後の if 文は、この場合は偽なので (このクエリー・ワードはアスタリスクで始まっていませんでした)、作成された正規表現は 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

@_ 変数は、検索規準に一致した全レコードのリストです。こうした各レコードに対して名前で各フィールドを抽出し、それぞれの値を、各フィールド名をキーとするハッシュの中に保存します。ここで、フィールドが ## で区切られており、上記のサブルーチンが 1 つのレコードの全フィールドを delRecs 配列に置くことを思い出してください。こうした各フィールドに対して、最初のコロンの前にあるものすべてをフィールド名として集め、後にあるものすべてを値として集めます。この値を、フィールド名をキーとするハッシュ値に付加します (もしハッシュ値が既に存在している場合)。こうすることで、どのフィールドが一致したかによらず、すべてのフィールドの組み合わせを単純に出力できるのです。例えば、もし名前が jane であれば、cn フィールドの ju*y と突き合わせることができますが、同じ cn フィールドにはニックネーム judy あるいは july も保存されています。複数のフィールド名を組み合わせ、出力用の 1 つの変数にすることで、本当の名前とニックネームとを 1 回の検索で見ることができます。

現在のレコードに対するハッシュが作成できたので、選択されたフィールドを出力します。下記のサブルーチン 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 回では、検索結果に対する重み付きのスコアリングとソート、データセットの一般的なスペリング・ミスを修正する metaphone マッチングについて紹介します。


ダウンロード可能なリソース


関連トピック

  • Perl と LDAP のソースを調べてください。
  • Paul Dwerryhouse が Linux Journal に、Perl と LDAP について「An Introduction to perl-ldap」という標題の記事を書いています。
  • OpenLDAP には、背景情報や実装に関する情報が豊富に用意されています。
  • developerWorks のオープンソースに関する記事を読んでください。
  • developerWorks の Open source ゾーンをご覧ください。オープンソース技術を使った開発や、IBM 製品でオープンソース技術を使用するためのハウ・ツー情報やツール、プロジェクトの更新情報など、豊富な情報が用意されています。
  • Safari Books Online には、オープンソース技術に関するリソースが豊富に取り揃えられています。
  • 皆さんの次期オープンソース開発プロジェクトを IBM trial software を使って革新してください。ダウンロード、あるいは DVD で入手することができます。

コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Open source
ArticleID=246247
ArticleTitle=LDAP 検索エンジン、第 1 回: Perl と正規表現ジェネレーターを使って LDAP データベース・レコードを検索し、表示する
publish-date=02202007