文字列照合

文字列照合のアルゴリズムとして，単純照合法およびKMP法を実装する．

プログラム：単純照合法

以下のソースコードは，次のURLからダウンロードできる． * ソースコード： https://www.coins.tsukuba.ac.jp/~amagasa/lecture/dsa-files/dsa-code-string.zip

readFile.c

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

/**
 * ファイルを読み込みむ．
 * @param path 読み込むファイルのパス
 * @param str 読み込んだ文字列を格納する配列へのポインタ
 * @return 読み込んだファイルのサイズ（バイト数）．
 */
int readFile(char* path, char* str) {
  FILE* fp = NULL;

  fp = fopen(path, "r");
  if ((fp = fopen(path, "r")) == NULL) {
    perror("Cannot not open file");
    exit(1);
  }

  int len = 0;
  while (!feof(fp))
    str[len++] = (char)fgetc(fp);
  fclose(fp);
  str[--len] = '\0';  // 末尾のEOFを削除
  return len;
}

cmp.c

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

extern bool isVerbose;
extern int Ncmp;

/**
 * 文字比較関数．比較回数をカウントする．
 * @param a 比較文字
 * @param b 比較文字
 * @return a と b が等しければ true, 等しくなければ false.
 */
bool cmp(char a, char b) {
  if (isVerbose)
    fprintf(stderr, "cmp(%c, %c)\n", a, b);
  Ncmp++;
  if (a == b)
    return true;
  else
    return false;
}

naive.c

#include <stdlib.h>
#include <stdbool.h>

extern bool isVerbose;
extern int Ncmp;

bool cmp(char, char);

/**
 * 単純照合法による文字列照合．
 * @param text テキスト
 * @param pat 検索パターン
 * @return 照合に成功した位置．失敗した場合は -1．
 */
int naive(char* text, unsigned int textlen, char* pat, unsigned int patlen) {
    /* 関数を完成させなさい */
}

mainNaive.c

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

#define PAT_MAX 256     // パターンの最大の長さ
#define TEXT_MAX 1024 * 1024 * 10 // テキストの最大の長さ（10 MB）

bool isVerbose = false;     // 比較回数表示スイッチ
unsigned int Ncmp = 0;      // 比較回数のカウンタ

int readFile(char*, char*);
int naive(char*, int, char*, int);

int main(int argc, char** argv) {
  char pat[PAT_MAX];    // 検索パターン
  char* text = (char *)malloc(TEXT_MAX * sizeof(char));
  int patlen = 0;
  int textlen = 0;

  // 引数処理・ファイル読み込み
  if (argc < 3 || 4 < argc) {
    fprintf(stderr, "Usage: ./main [-v] <text file> <pattern file>\n");
    return 1;
  }
  int i = 1;
  if (strcmp(argv[i], "-v") == 0) {
    isVerbose = true;
    i++;
  }
  textlen = readFile(argv[i++], text);
  patlen = readFile(argv[i], pat);

  // pat 末尾の改行コードを削除
  while (pat[patlen - 1] == '\r' || pat[patlen - 1] == '\n')
    pat[--patlen] = '\0';

  // 文字列照合・結果表示
  if (isVerbose) {
    printf("text size: %d\n", textlen);
    printf("pattern size: %d\n", patlen);
  }
  printf("Pattern found at %d.\n", naive(text, textlen, pat, patlen));
  if (isVerbose)
    printf("# of comparisons: %d.\n", Ncmp);

  free(text);

  return 0;
}

Makefile

mainNaive: cmp.o naive.o readFile.o

使い方

これはテキストおよび（検索）パターンを含む二つのファイルを引数として与えると，単純照合法による文字列照合を行い，パターンの含まれる位置を表示するプログラムでである．

$ echo This is a pen. > text
$ echo pen > pat
$ ./mainNaive text pat
Pattern found at 10.

パターンが存在しない場合は -1 を表示する．

$ echo ix > pat
$ ./mainNaive text pat
Pattern found at -1.

また，"-v" オプションとともに実行すると，比較の詳細と比較回数を表示する．

$ ./mainNaive -v text pat
text size: 15
pattern size: 2
cmp(i, T)
cmp(i, h)
（略）
Pattern found at -1.
# of comparisons: 17.

プログラムの説明

C言語では，文字列は char 型の配列として扱い，文字列の終端はナル文字 '\0' で識別される．
ファイルから文字列を読み出す場合，改行コードも文字として扱われることに注意すること．改行コードは OS によって異なるが，macOS や Linux では '\n' が用いられる．今回のサンプルコードでは，検索パターンの末尾の改行コードは削除するようになっている．
文字の比較回数を調査するために，cmp()関数を用意している．各文字の比較の際にこの関数を呼び出すと，比較回数を格納するカウンターが加算される．また，"-v" オプションを指定することで，比較回数の表示を簡単に行うことができる．

基本課題1

単純照合法に基づいて，上記のコードにおけるnaive()を作成してプログラムを完成させなさい．作成したプログラムを簡単な動作例を用いて説明し，それが正しく動作することを示しなさい．

基本課題2

上記ソースコードに基づいて，KMP法によって文字列照合を行うプログラムを作成する．まず，パターン pat を解析してまくらパターンのサイズを格納する配列 next を計算する関数

void compnext(char* pat, int* next)

を含むソースファイル compnext.c を作成しなさい．さらに，作成した関数が正しく動作することを，例を使って示しなさい．

基本課題3

KMP法によって文字列照合を行うプログラム kmp.c を完成させなさい．このために修正したメイン関数は mainKMP.c とする．さらに，作成したプログラムを簡単な動作例を用いて説明し，それが正しく動作することを示しなさい．

発展課題：文字列照合アルゴリズムの比較

発展課題1

長さnの文字列に対して，長さmのパターンを照合することを考える．異なる長さの文字列に対して，単純照合法とKMP法の比較回数を調査し，どちらが高速か検討しなさい．

ヒント

調査したデータは gnuplot や Python（Matplotlib）などを使って，分かりやすくまとめること．参考 *「二次元散布図」を参照 http://data-science.gr.jp/implementation/ida_gnuplot_basic_usage.html

発展課題2

単純照合法で最悪となる文字列およびパターンはどのようなものか．実例を挙げるとともに，計算量をオーダで示しなさい．さらに，単純照合法で最悪となる文字列およびパターンに対してKMP法における比較回数を調査し，どちらが高速かを検討しなさい．

提出締切

2023年1月30日（月）13:30