曖昧検索ライブラリ

増井俊之 @ pitecan.com
ヘッダ/API定義 プログラムソース 使用例

曖昧検索ライブラリ

曖昧検索ライブラリは 高速に曖昧検索(approximate pattern matching)を行なうためのライブラリです。 曖昧検索とは、 指定した検索文字列パタンに 被検索テキストが完全に一致しない場合でもマッチングが成功する検索手法です。

本曖昧検索ライブラリでは以下のような曖昧マッチングが有効です。

これらは 曖昧度を1として検索を行なった場合ですが、 曖昧度は0からMAXMISMATCHまでの値を使うことができます。 曖昧度に0を指定すると普通の検索が行なわれます。

  • POBoxの検索には本曖昧検索ライブラリが使用されています。
  • wtangleを利用することにより、 このHTMLファイルから曖昧検索プログラムを生成することができます。

    曖昧検索ライブラリのヘッダとAPI

    //
//	2001/02/12 18:10:50
//	$Date: 2006-12-18 13:49:34 -0800 (Mon, 18 Dec 2006) $
//	$Revision: 1752 $
//
#ifndef _ASEARCH_H_
#define _ASEARCH_H_

#define MAXMISMATCH 3
    検索パタンと曖昧度の指定
    void asearch_makepat(unsigned char *pattern, int ambig);
    引数 pattern 検索パタン
    ambig 検索の曖昧度
    返り値 なし
    備考
  • 検索処理の最初に呼んで曖昧検索のための状態遷移機械を生成する。 実際の検索はasearch_match()を使用する。
  • 検索パタンには文字クラスを使用可能。(e.g. "k[aiueo]")
  • 検索パタン中の空白文字(0x20)はワイルドカードとなる。 (0文字以上のあらゆる文字の並びにマッチする。正規表現の".*"と同様。)
  • 曖昧度ambigの値が0のときは完全マッチングが行なわれ、 値が1のときは曖昧度1の曖昧マッチングが行なわれる。
    • 曖昧検索の実行
    int asearch_match(unsigned char *text);
    引数 text 検索されるテキスト
    返り値 マッチするとき1を返し、マッチしないとき0を返す。
    備考 曖昧検索が可能になっていると検索時間が増える。 検索時間はasearch_makepat()で指定するambigの値には依存せず、 最大曖昧度MAXMISMATCHに依存するので、 速度が問題になる場合はMAXMISMATCHの値を小さくすること。 

    #endif

    曖昧検索ライブラリソース

    //
//	2001/02/12 18:10:50
//	$Date: 2006-12-18 13:49:34 -0800 (Mon, 18 Dec 2006) $
//	$Revision: 1752 $
//
#include "asearch.h"

#define INITPAT 0x4000
#define MAXCHAR 0x100

static int mismatch;
static unsigned int epsilon;
static unsigned int acceptpat;
static unsigned int shiftpat[MAXCHAR];

#define isupper(c) ((c) >= 'A' && (c) <= 'Z')
#define islower(c) ((c) >= 'a' && (c) <= 'z')
#define toupper(c) ((c) - 'a' + 'A')
#define tolower(c) ((c) - 'A' + 'a')

void asearch_makepat(unsigned char *pat, int m)
{
	int i;
	unsigned int mask = INITPAT;

	mismatch = m;
	epsilon = 0;

	for(i=0;i<MAXCHAR;i++) shiftpat[i] = 0;
	for(;*pat;pat++){
		if(*pat == ' '){ // ワイルドカード文字
			epsilon |= mask;
		}
		else if (*pat == '\003'){
			for(pat++;*pat != '\004';pat++){
				shiftpat[*pat] |= mask;
				if(isupper(*pat)) shiftpat[tolower(*pat)] |= mask;
				if(islower(*pat)) shiftpat[toupper(*pat)] |= mask;
			}
			mask >>= 1;
		}
		else {
			shiftpat[*pat] |= mask;
			if(isupper(*pat)) shiftpat[tolower(*pat)] |= mask;
			if(islower(*pat)) shiftpat[toupper(*pat)] |= mask;
			mask >>= 1;
		}
	}
	acceptpat = mask;
}

int asearch_match(register unsigned char *text)
{
	register unsigned int i0 = INITPAT;
#if MAXMISMATCH > 0
	register unsigned int i1=0;
#endif
#if MAXMISMATCH > 1
	register unsigned int i2=0;
#endif
#if MAXMISMATCH > 2
	register unsigned int i3=0;
#endif
	register unsigned int mask;
	register unsigned int e = epsilon;

	for(;*text;text++){
		mask = shiftpat[*text];
#if MAXMISMATCH > 2
		i3 = (i3 & e) | ((i3 & mask) >> 1) | (i2 >> 1) | i2;
#endif
#if MAXMISMATCH > 1
		i2 = (i2 & e) | ((i2 & mask) >> 1) | (i1 >> 1) | i1;
#endif
#if MAXMISMATCH > 0
		i1 = (i1 & e) | ((i1 & mask) >> 1) | (i0 >> 1) | i0;
#endif
		i0 = (i0 & e) | ((i0 & mask) >> 1);
#if MAXMISMATCH > 0
		i1 |= (i0 >> 1);
#endif
#if MAXMISMATCH > 1
		i2 |= (i1 >> 1);
#endif
#if MAXMISMATCH > 2
		i3 |= (i2 >> 1);
#endif
	}
	switch(mismatch){
		case 0: return (i0 & acceptpat);
		case 1: return (i1 & acceptpat);
		case 2: return (i2 & acceptpat);
		case 3: return (i3 & acceptpat);
		default: return 0;
	}
}

    曖昧検索ライブラリ使用例

    曖昧検索ライブラリのテストプログラムです。 引数で与えられたパタンに近い英単語をリストします。 パタンの最後尾に" "を付加してから asearch_makepat()を呼ぶことにより 単語の先頭マッチングを行なっています。 
    % asearchtest masui
massif
massive
mastic
mastiff
% 

    //
//	$Date: 2006-12-18 13:49:34 -0800 (Mon, 18 Dec 2006) $
//	$Revision: 1752 $
//
#include <stdio.h>
#include <string.h>
#include "asearch.h"

#define DIC "/usr/dict/words"  // 英単語辞書
#define MAXWORDS 50000
char *words[MAXWORDS];
int nwords = 0;

main(int argc, char **argv)
{
	FILE *f;
	char buf[1000];
	int i;
	f = fopen(DIC,"r");
	if(f == NULL) exit(0);
	while(fgets(buf,1000,f)){
		words[nwords++] = strdup(buf);
	}

	if(argc > 1){
		sprintf(buf,"%s ",argv[1]);
		asearch_makepat(buf,1);
		for(i=0;i< nwords;i++){
			if(asearch_match(words[i])){
				printf("%s",words[i]);
			}
		}
	}
}

    更新履歴

  • 2001ごろ作成
  • 最終更新: $Date: 2006-12-18 13:49:34 -0800 (Mon, 18 Dec 2006) $