過去ログ
No．１２７１ 一つの文字列の中から複数の文字列を検索する
[戻る] [ホームページ]No.16879 |
一つの文字列の中から複数の文字列を検索する 投稿者---Sciggepy(2004/09/22 22:56:29) |
||
いつも参考に（時に借用）させて頂いています。 質問は「一つの文字列の中から複数の文字列を検索する」という操作をどのようにすれば効率よく行えるかということです。 例えば、 Sciggepy a blinstra en xaeten noil scoek sembell listel. という文の中から、名詞だけを抜き出すといったものです。 strstrを分類に含まれる単語ごとに繰り返し使えば、題の目的は達成できるでしょう。しかし、検索語の中で使われていない単語の方がずっと多い場合は、明らかに無駄です。 この無駄を少なくするには、どのような方法をとればよいでしょうか？ |
|||
| No.16881 |
Re:一つの文字列の中から複数の文字列を検索する 投稿者---あかま(2004/09/22 23:43:46) |
||
まず単語ごとに切り分けて保存して（よくある単語帳のプログラム）、 ２分探索やハッシュなど線形探索より早いアルゴリズムで検索すればいいと思います。 たぶん切り分ける処理が重いですが。 検索する単語が決まっているならそちらを単語帳にするという手もありますね。 |
|||
| No.16887 |
Re:一つの文字列の中から複数の文字列を検索する 投稿者---Sciggepy(2004/09/23 12:09:03) |
||
ハッシュ法はよく解らなかったので、二分探索法を使うことにします。 検索語はほぼ固定なので、ソートなどの手間は気になりません。 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int cmp(const void *p1,const void *p2)
{
return strcmp(*(const char **)p1,*(const char **)p2);
}
#define MAX_ELM 10
int main(void)
{
char src[]="Sciggepy a blinstra en xaeten noil scoek sembell listel",
*words[MAX_ELM]={"adfen","dex","Ness","kliez","igrein","Sciggepy","blinstra","noil","listel","vinx"},
*buf,*p;
int i,m,mx;
qsort(words,MAX_ELM,sizeof(char *),cmp);
for(i=0,m=0;i<MAX_ELM;i++) {
mx=strlen(words[i]);
m=mx>m?mx:m;
}
buf=malloc(++m);
for(p=src;*p;p++) {
for(i=0;i<m&&*p&&!isspace(*p)&&*p!=','&&*p!='.';i++,p++) buf[i]=*p;
if(i==m) for(;*p&&!isspace(*p)&&*p!=','&&*p!='.';p++);
else {
buf[i]='\0';
if(bsearch(&buf,words,MAX_ELM,sizeof(char *),cmp)) printf("%s\n",buf);
}
if(!*p) break;
}
free(buf);
return 0;
}
|
|||
| No.16888 |
Re:一つの文字列の中から複数の文字列を検索する 投稿者---Sciggepy(2004/09/23 12:37:12) |
||
前回のものより、こちらの方が目的に近いです。 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int cmp(const void *p1,const void *p2)
{
return strcmp(*(const char **)p1,*(const char **)p2);
}
#define MAX_ELM 10
int main(void)
{
char src[]="Sciggepy a blinstra en xaeten noil scoek sembell listel",
*words[MAX_ELM]={"adfen","dex","Ness","kliez","igrein","Sciggepy","blinstra","noil","listel","vinx"},
*buf,*p,ary[64]="";
int i,m,mx,j;
qsort(words,MAX_ELM,sizeof(char *),cmp);
for(i=0,m=0;i<MAX_ELM;i++) {
mx=strlen(words[i]);
m=mx>m?mx:m;
}
buf=malloc(++m);
memset(ary,' ',strlen(src));
for(p=src,j=0;*p;p++,j++) {
for(i=0;i<m&&*p&&!isspace(*p)&&*p!=','&&*p!='.';i++,p++) buf[i]=*p;
if(i==m) for(;*p&&!isspace(*p)&&*p!=','&&*p!='.';p++) j++;
else {
buf[i]='\0';
if(bsearch(&buf,words,MAX_ELM,sizeof(char *),cmp)) while(i--) ary[j++]='~';
else j+=i;
}
if(!*p) break;
}
free(buf);
printf("%s\n%s\n",src,ary);
return 0;
}
|
|||
| No.16889 |
Re:一つの文字列の中から複数の文字列を検索する 投稿者---ＲＥＥ(2004/09/23 13:16:52) |
||
辞書よりも長い単語があった時に下線がずれそうですね。 ハッシュ法は要素が多い時には高速化に寄与しますので、 その時に考慮すればよいでしょう。 |
|||
| No.16890 |
Re:一つの文字列の中から複数の文字列を検索する 投稿者---Sciggepy(2004/09/23 13:50:10) |
||
>辞書よりも長い単語があった時に下線がずれそうですね。 修正： 第28行 if(i==m) for(j+=i;*p&&!isspace(*p)&&*p!=','&&*p!='.';p++) j++;>ハッシュ法は要素が多い時には高速化に寄与しますので、 >その時に考慮すればよいでしょう。 要素数は、特に決めてはいないのですが、65536個を限界としておきます。 二分探索で65536個の要素を検索する場合、最高でも16回程度の比較で済むので、そのままでも問題はないと思います。 |
|||
| No.16885 |
Re:一つの文字列の中から複数の文字列を検索する 投稿者---ＲＥＥ(2004/09/23 09:30:39) |
||
>例えば、 >Sciggepy a blinstra en xaeten noil scoek sembell listel. >という文の中から、名詞だけを抜き出すといったものです。 >strstrを分類に含まれる単語ごとに繰り返し使えば、題の目的は達成できるでしょう。しかし、検索語の中で使われていない単語の方がずっと多い場合は、明らかに無駄です。 >この無駄を少なくするには、どのような方法をとればよいでしょうか？ 単語単位で探すのであれば、文を単語で切り分けて、検索語の中から検索するのが良いと思います。 strstrの様に部分的に一致するもの(上の例ではtenでもヒット）を含めたいのであれば、文の検索開始位置を１文字ずつずらしながら、前方一致で検索語の中から検索することになりそうです。 |
|||