与えられた複数の文字列からオートマトンを自動生成したい

[堀江伸一]

与えられた複数の文字列からオートマトンを自動生成したいのです。

たとえば
pjp,php,abcc,ccad、、、
という複数の単語を、長い文字列から見つけ出す。
このような処理を書くとき、与えられた文字列からオートマトンを自動生成したいのですが良い方法ありませんか？

最初木構造で行けるかなと考えたのですが、木構造だと探す単語の文字列に重複があった場合うまくいかないのではと考えました。
abcc ccda　ｂcaaのような単語の組み合わせも考えると単純にはいかないようです。

たぶんグラフ構造を作り出せばいいと思うのですが。
グラフの点は同じ文字でも別の点として扱う必要があるのかなと考えたりもして難しいなと感じています。
どうやったら有限オートマトンを与えられた単語列から自動生成できるのでしょうか？

おおざっぱな考え方からわかるとありがたいです。

[a5ua]

具体的にどのような処理をしたいのか、質問文からは良くわかりません。
＞pjp,php,abcc,ccad、、、
＞という複数の単語を、長い文字列から見つけ出す。
これだけだと、その長い文字列から、pjpを探す→phpを探す→...という処理をするように見えます。

[つうこうにん]

質問の意図はいまいちわかりませんが
グラフなら行列で表すことができると思います。
グラフ　行列　あたりでググってみてはいかがでしょう。

[ｓｈ]

>pjpを探す→phpを探す
まあそれでもいいんですけど、文字列に対する有限オートマトンは少し違うのです。
複数の単語を一度の読み込みで同時に探す機能があります。
この考えが進化すると正規表現になるらしいです。
有限オートマトンで文字列から単語を探す場合スウィッチ文とif文で書くのが高速で、自動生成すると低速になりやすいので実用性が低いだろうなとは考えています。
それでも技術的興味というか初歩の勉強といいますかその観点から勉強したいのです。

自動生成となると難しい場合が色々あるようです。
acccad,ccc
という文字列を有限オートマトンで探す場合。
acccaacccadという文字列があった場合、一度の読み込みで探すにはacccaまで読み込んだ次でaなためにｃｃｃが検索結果として上がってくる必要があり、こういう場合にも対処できるグラフ構造を探したいなあと思います。

グラフと行列の関係、調べて見ます。

[ｓｈ]

補足
見つけたい複数の単語をAとします。
Aを文字列の中から見つけたいのですが、このときAの検索を有限オートマトンで行いたいのです。

文字列の中からAを探す処理は有限オートマトンとして機能し、一度の読み込みで同時に複数の単語を検索できるようにしたいわけです。
これで伝わりますでしょうか？

[沖 滉均]

内容とは直接関係ありませんが、堀江伸一さん＝ｓｈさんですか？

以下、フォーラムルールから引用

なるべくオリジナルな名前を決め、以後同じ名前を使い続けてください。

と、ありますように途中で名前を変更しないようにしてください。

[a5ua]

「長い文字列を先頭から1文字ずつ読み、複数あるターゲット文字列のいずれかに一致したら、その文字列を表示する。」
という解釈で良いでしょうか。

次のようなアルゴリズムを考えてみましたが、いかがでしょうか？
0. 先頭の文字に注目する。
1. 注目位置が終端だったら終了。
2. 注目文字がターゲットの1文字目と一致したら、探索候補に追加する。
3. それぞれの探索候補に対して、不一致が起こったら、候補から除外する。最後まで一致していたら、その候補を表示した上で、候補から除外する。
4. 注目位置を1つ進めて、1.に戻る。

以下に具体例を示します。

見つけたい文字列を「acccad, ccc」とします。

acccaacccad // 長い文字列
() // 見つけたい文字列の探索経過

[a]cccaacccad // []は注目している位置を表す
([a]cccad) // acccadを候補として追加

a[c]ccaacccad
(a[c]ccad, [c]cc) // cccを候補として追加

ac[c]caacccad
(ac[c]cad, c[c]c, [c]cc) // cccを候補として追加

acc[c]aacccad
(acc[c]ad, cc[c], c[c]c, [c]cc) // cccを候補として追加。また、cccが一致（候補からは外す）

accc[a]acccad
(accc[a]d, [a]cccad) // acccadを候補として追加。また、途中で不一致が見つかったら候補から外す

accca[a]cccad
([a]cccad)

acccaa[c]ccad
(a[c]ccad, [c]cc)

acccaac[c]cad
(ac[c]cad, c[c]c, [c]cc)

acccaacc[c]ad
(acc[c]ad, cc[c], c[c]c, [c]cc) // cccが一致

acccaaccc[a]d
(accc[a]d, [a]cccad)

acccaaccca[d]
(accca[d]) // acccadが一致

終端なので終了

オートマトンを意識せずに書いてしまったけど、
結局は、「acccad|ccc」を受理するオートマトンを1文字読み込むごとに起動する感じなのかな？と思いました。

[kimuchi]

蛇足ですが、面白そうだったのでC++でプログラムを組んでみました。
また、アルゴリズムはa5uaさんのものをお借りしました。
ただ、オートマトンについて私個人の解釈は間違っているかもしれません。ご了承ください。

※オートマトンについて参考にしたサイト
ウィキペディア
http://www.adachi.ne.jp/users/katz/prim ... a.html#dfa

コード:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define STRING_MAX 256
#define WORD_MAX 30

//正規言語とする文字列
char moji[] = "addccfikkbeghcjrouiedrjhbjdkdieraddaaqalwjuil";
int  mojinum;

void object_list(char *ROB[], int wordn)
{
	printf("検索している文字\n");
	for(int i=0; i<wordn; i++){
		printf("文字：%s\n",ROB[i]);
	}
	printf("\n");
}

int T(int r, int x, int pos)
{
	int judge=1;
	if(x!=(int)moji[pos])
		judge = 0;
	return (judge+r);
}

void automaton(char *ROB[], int strnum[], int wordn)
{
	//  S = {0~strnum}     //状態の有限集合 (S)
	//  全ASCII文字-(,)    //文字の有限集合 (Σ)
	//  s = 0              //開始状態 (s ∈ S)
	//  A = {strnum}       //受容状態の集合 (A ⊆ S)

	int i,j,k;
	int r[WORD_MAX],x;     //各検索文字の状態、取り出す文字
	memset(r,0,sizeof(r)); //開始状態にする

	printf("発見された文字\n");
	for(i=0; i<mojinum; i++)
	{
		for(j=0; j<wordn; j++)
		{
			for(k=0; k<strnum[j]; k++)
			{
				if(strnum[j]>mojinum-i) break;
				x = (int)*(ROB[j]+sizeof(char)*k);
				r[j] = T(r[j],x,i+k); //遷移関数 (T : S × Σ → S)
			}
			//状態r[j] ={strnum}  検索文字は発見された。
			//状態r[j] ={etc...}  検索文字は発見されなかった。
			if(r[j]==strnum[j])
				printf("文字：%s 位置：%d文字目\n",ROB[j],(i+1));
			r[j] = 0;
		}
	}
	printf("\n");
}

int main()
{
	mojinum = strlen(moji);//検索元の文字数

	char buf[STRING_MAX];
	char *split[WORD_MAX];
	int strnum[WORD_MAX];
	int c,i,n=0, wordn=0, pos=0;
	memset(split, 0, sizeof(split));

	printf( "検索したい文字を(,)で区切って入力して下さい。\n" ); 

	//入力処理
	while(1)
	{
		c = getchar();
		if(n>=STRING_MAX) break;
		if(c==',' || c=='\n' || c==EOF)
		{
			if(wordn>=WORD_MAX) break;
			split[wordn] = (char*)malloc(sizeof(char)*(n-pos+1));
			for(i=0; i<(n-pos); i++)
				*(split[wordn]+i) = buf[i+pos];
			*(split[wordn]+(n-pos)) = '\0';
			strnum[wordn] = strlen(split[wordn]);
			pos = n;
			wordn++;
		}
		else buf[n++] = c;

		if(c=='\n' || c==EOF) break;
	}

	//検索
	object_list(split,wordn);
	automaton(split,strnum,wordn);
	printf( "検索終了。\n" );

	//メモリ解放
	for(i=0; i<wordn; i++)
		free(split[i]);

	while((c=getchar())!=EOF && c!='\n')
	return 0;
}

少しでも役に立てれば幸いです。

[堀江伸一]

ありがとうございます。

後日、木構造で検索が出来る方法を考え付いたのですが、木を何度も再加工する複雑な方法になりました。

シンプルな方法もよさそうですね。
提示のサンプルコードについては印刷して読んでみます。

[maru]

複数の文字列を一度で検索するっていうのをどこかでみたような気がすると思ったら、「C言語で書くアルゴリズム」
（ISBN4-7973-0004-3）という本で実装例が出てました。P102　「4-4 複数文字列の検索」です。
Alfred AhoとM.J.Corasick が1975年に発表したテクニックだそうで、有限ステートマシンを利用してキーワードを
見つける方法だそうです。プログラムはC言語で９ページ半（５４行／ページ、従って５００行位）あり結構な量です。