文字列の照合は、文字列の探索ともいう。「テキスト」と呼ばれる文字列の中に、「パターン」と呼ばれる文字列に一致する部分があるかどうかを調べる問題。そのような部分が見つかった場合には、さらにその場所を答える。

テキスト・エディタにおける探索コマンドやデータベースにおける検索などに使われ、使用頻度の多い操作だろう。いまの時代になって、WWWページの全文検索にも利用される。

ここで紹介する素朴法とは、テキストの先頭に、ます照合パターンを重ね、一致するかどうかを比較していく。一致しなければ重ねる位置を後一文字にずらしてまた比較、テキストの最後になるまで繰り返す、というもっとも基本的な方法。

なお、照合対象は漢字でも構わないが、漢字の場合、2文字(=全角1文字)分ずらすほうが意味的に正しいので、多少の修正を加えるといいかもしれない。

<関数名>
  naiveMatch  素朴法による文字列照合

<形式>
  char *naiveMatch(char *text, int len, char *pattern, int patlen);

<引数>
  text   (入力) テキスト
  len    (入力) テキストの長さ
  pattern (入力) 照合パターン
  patlen  (入力) 照合パターンの長さ

<関数値>
  照合パターンがテキストから見つかった場合はそのポインタ、
  見つからなかった場合は 0 (NULL)。

用例

<関数本体>
  naiveMatch.c

<説明>
  判りやすい照合方法ではあるが、計算時間は、最悪 O(mn) になる。 m、nはそれぞれテキスト、照合パターンの長さ。
  より速い照合アルゴリズムについてはこれから紹介する。

Comments are closed.

Post Navigation